001 /*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.Beta;
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.base.Function;
025 import com.google.common.base.Supplier;
026
027 import java.io.Serializable;
028 import java.util.Comparator;
029 import java.util.Iterator;
030 import java.util.Map;
031 import java.util.NoSuchElementException;
032 import java.util.PriorityQueue;
033 import java.util.Queue;
034 import java.util.Set;
035 import java.util.SortedMap;
036 import java.util.SortedSet;
037 import java.util.TreeMap;
038
039 import javax.annotation.Nullable;
040
041 /**
042 * Implementation of {@code Table} whose row keys and column keys are ordered
043 * by their natural ordering or by supplied comparators. When constructing a
044 * {@code TreeBasedTable}, you may provide comparators for the row keys and
045 * the column keys, or you may use natural ordering for both.
046 *
047 * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link
048 * #rowMap} method returns a {@link SortedMap}, instead of the {@link Set} and
049 * {@link Map} specified by the {@link Table} interface.
050 *
051 * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link
052 * #columnMap()} have iterators that don't support {@code remove()}. Otherwise,
053 * all optional operations are supported. Null row keys, columns keys, and
054 * values are not supported.
055 *
056 * <p>Lookups by row key are often faster than lookups by column key, because
057 * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code
058 * column(columnKey).get(rowKey)} still runs quickly, since the row key is
059 * provided. However, {@code column(columnKey).size()} takes longer, since an
060 * iteration across all row keys occurs.
061 *
062 * <p>Because a {@code TreeBasedTable} has unique sorted values for a given
063 * row, both {@code row(rowKey)} and {@code rowMap().get(rowKey)} are {@link
064 * SortedMap} instances, instead of the {@link Map} specified in the {@link
065 * Table} interface.
066 *
067 * <p>Note that this implementation is not synchronized. If multiple threads
068 * access this table concurrently and one of the threads modifies the table, it
069 * must be synchronized externally.
070 *
071 * @author Jared Levy
072 * @author Louis Wasserman
073 * @since 7.0
074 */
075 @GwtCompatible(serializable = true)
076 @Beta
077 public class TreeBasedTable<R, C, V> extends StandardRowSortedTable<R, C, V> {
078 private final Comparator<? super C> columnComparator;
079
080 private static class Factory<C, V>
081 implements Supplier<TreeMap<C, V>>, Serializable {
082 final Comparator<? super C> comparator;
083 Factory(Comparator<? super C> comparator) {
084 this.comparator = comparator;
085 }
086 @Override
087 public TreeMap<C, V> get() {
088 return new TreeMap<C, V>(comparator);
089 }
090 private static final long serialVersionUID = 0;
091 }
092
093 /**
094 * Creates an empty {@code TreeBasedTable} that uses the natural orderings
095 * of both row and column keys.
096 *
097 * <p>The method signature specifies {@code R extends Comparable} with a raw
098 * {@link Comparable}, instead of {@code R extends Comparable<? super R>},
099 * and the same for {@code C}. That's necessary to support classes defined
100 * without generics.
101 */
102 public static <R extends Comparable, C extends Comparable, V>
103 TreeBasedTable<R, C, V> create() {
104 return new TreeBasedTable<R, C, V>(Ordering.natural(),
105 Ordering.natural());
106 }
107
108 /**
109 * Creates an empty {@code TreeBasedTable} that is ordered by the specified
110 * comparators.
111 *
112 * @param rowComparator the comparator that orders the row keys
113 * @param columnComparator the comparator that orders the column keys
114 */
115 public static <R, C, V> TreeBasedTable<R, C, V> create(
116 Comparator<? super R> rowComparator,
117 Comparator<? super C> columnComparator) {
118 checkNotNull(rowComparator);
119 checkNotNull(columnComparator);
120 return new TreeBasedTable<R, C, V>(rowComparator, columnComparator);
121 }
122
123 /**
124 * Creates a {@code TreeBasedTable} with the same mappings and sort order
125 * as the specified {@code TreeBasedTable}.
126 */
127 public static <R, C, V> TreeBasedTable<R, C, V> create(
128 TreeBasedTable<R, C, ? extends V> table) {
129 TreeBasedTable<R, C, V> result
130 = new TreeBasedTable<R, C, V>(
131 table.rowComparator(), table.columnComparator());
132 result.putAll(table);
133 return result;
134 }
135
136 TreeBasedTable(Comparator<? super R> rowComparator,
137 Comparator<? super C> columnComparator) {
138 super(new TreeMap<R, Map<C, V>>(rowComparator),
139 new Factory<C, V>(columnComparator));
140 this.columnComparator = columnComparator;
141 }
142
143 // TODO(jlevy): Move to StandardRowSortedTable?
144
145 /**
146 * Returns the comparator that orders the rows. With natural ordering,
147 * {@link Ordering#natural()} is returned.
148 */
149 public Comparator<? super R> rowComparator() {
150 return rowKeySet().comparator();
151 }
152
153 /**
154 * Returns the comparator that orders the columns. With natural ordering,
155 * {@link Ordering#natural()} is returned.
156 */
157 public Comparator<? super C> columnComparator() {
158 return columnComparator;
159 }
160
161 // TODO(user): make column return a SortedMap
162
163 /**
164 * {@inheritDoc}
165 *
166 * <p>Because a {@code TreeBasedTable} has unique sorted values for a given
167 * row, this method returns a {@link SortedMap}, instead of the {@link Map}
168 * specified in the {@link Table} interface.
169 * @since 10.0
170 * (<a href="http://code.google.com/p/guava-libraries/wiki/Compatibility"
171 * >mostly source-compatible</a> since 7.0)
172 */
173 @Override
174 public SortedMap<C, V> row(R rowKey) {
175 return new TreeRow(rowKey);
176 }
177
178 private class TreeRow extends Row implements SortedMap<C, V> {
179 @Nullable final C lowerBound;
180 @Nullable final C upperBound;
181
182 TreeRow(R rowKey) {
183 this(rowKey, null, null);
184 }
185
186 TreeRow(R rowKey, @Nullable C lowerBound, @Nullable C upperBound) {
187 super(rowKey);
188 this.lowerBound = lowerBound;
189 this.upperBound = upperBound;
190 checkArgument(lowerBound == null || upperBound == null
191 || compare(lowerBound, upperBound) <= 0);
192 }
193
194 @Override public Comparator<? super C> comparator() {
195 return columnComparator();
196 }
197
198 int compare(Object a, Object b) {
199 // pretend we can compare anything
200 @SuppressWarnings({"rawtypes", "unchecked"})
201 Comparator<Object> cmp = (Comparator) comparator();
202 return cmp.compare(a, b);
203 }
204
205 boolean rangeContains(@Nullable Object o) {
206 return o != null && (lowerBound == null || compare(lowerBound, o) <= 0)
207 && (upperBound == null || compare(upperBound, o) > 0);
208 }
209
210 @Override public SortedMap<C, V> subMap(C fromKey, C toKey) {
211 checkArgument(rangeContains(checkNotNull(fromKey))
212 && rangeContains(checkNotNull(toKey)));
213 return new TreeRow(rowKey, fromKey, toKey);
214 }
215
216 @Override public SortedMap<C, V> headMap(C toKey) {
217 checkArgument(rangeContains(checkNotNull(toKey)));
218 return new TreeRow(rowKey, lowerBound, toKey);
219 }
220
221 @Override public SortedMap<C, V> tailMap(C fromKey) {
222 checkArgument(rangeContains(checkNotNull(fromKey)));
223 return new TreeRow(rowKey, fromKey, upperBound);
224 }
225
226 @Override public C firstKey() {
227 SortedMap<C, V> backing = backingRowMap();
228 if (backing == null) {
229 throw new NoSuchElementException();
230 }
231 return backingRowMap().firstKey();
232 }
233
234 @Override public C lastKey() {
235 SortedMap<C, V> backing = backingRowMap();
236 if (backing == null) {
237 throw new NoSuchElementException();
238 }
239 return backingRowMap().lastKey();
240 }
241
242 transient SortedMap<C, V> wholeRow;
243
244 /*
245 * If the row was previously empty, we check if there's a new row here every
246 * time we're queried.
247 */
248 SortedMap<C, V> wholeRow() {
249 if (wholeRow == null
250 || (wholeRow.isEmpty() && backingMap.containsKey(rowKey))) {
251 wholeRow = (SortedMap<C, V>) backingMap.get(rowKey);
252 }
253 return wholeRow;
254 }
255
256 @Override
257 SortedMap<C, V> backingRowMap() {
258 return (SortedMap<C, V>) super.backingRowMap();
259 }
260
261 @Override
262 SortedMap<C, V> computeBackingRowMap() {
263 SortedMap<C, V> map = wholeRow();
264 if (map != null) {
265 if (lowerBound != null) {
266 map = map.tailMap(lowerBound);
267 }
268 if (upperBound != null) {
269 map = map.headMap(upperBound);
270 }
271 return map;
272 }
273 return null;
274 }
275
276 @Override
277 void maintainEmptyInvariant() {
278 if (wholeRow() != null && wholeRow.isEmpty()) {
279 backingMap.remove(rowKey);
280 wholeRow = null;
281 backingRowMap = null;
282 }
283 }
284
285 @Override public boolean containsKey(Object key) {
286 return rangeContains(key) && super.containsKey(key);
287 }
288
289 @Override public V put(C key, V value) {
290 checkArgument(rangeContains(checkNotNull(key)));
291 return super.put(key, value);
292 }
293 }
294
295 // rowKeySet() and rowMap() are defined here so they appear in the Javadoc.
296
297 @Override public SortedSet<R> rowKeySet() {
298 return super.rowKeySet();
299 }
300
301 @Override public SortedMap<R, Map<C, V>> rowMap() {
302 return super.rowMap();
303 }
304
305 // Overriding so NullPointerTester test passes.
306
307 @Override public boolean contains(
308 @Nullable Object rowKey, @Nullable Object columnKey) {
309 return super.contains(rowKey, columnKey);
310 }
311
312 @Override public boolean containsColumn(@Nullable Object columnKey) {
313 return super.containsColumn(columnKey);
314 }
315
316 @Override public boolean containsRow(@Nullable Object rowKey) {
317 return super.containsRow(rowKey);
318 }
319
320 @Override public boolean containsValue(@Nullable Object value) {
321 return super.containsValue(value);
322 }
323
324 @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
325 return super.get(rowKey, columnKey);
326 }
327
328 @Override public boolean equals(@Nullable Object obj) {
329 return super.equals(obj);
330 }
331
332 @Override public V remove(
333 @Nullable Object rowKey, @Nullable Object columnKey) {
334 return super.remove(rowKey, columnKey);
335 }
336
337 /**
338 * Overridden column iterator to return columns values in globally sorted
339 * order.
340 */
341 @Override Iterator<C> createColumnKeyIterator() {
342 return new MergingIterator<C>(
343 Iterables.transform(backingMap.values(),
344 new Function<Map<C, V>, Iterator<C>>() {
345 @Override
346 public Iterator<C> apply(Map<C, V> input) {
347 return input.keySet().iterator();
348 }
349 }), columnComparator());
350 }
351
352 /**
353 * An iterator that performs a lazy N-way merge, calculating the next value
354 * each time the iterator is polled. This amortizes the sorting cost over the
355 * iteration and requires less memory than sorting all elements at once.
356 * Duplicate values are omitted.
357 *
358 * <p>Retrieving a single element takes approximately O(log(M)) time, where M
359 * is the number of iterators. (Retrieving all elements takes approximately
360 * O(N*log(M)) time, where N is the total number of elements.)
361 */
362 // TODO(user): Push this into OrderedIterators or somewhere more generic.
363 private static class MergingIterator<T> extends AbstractIterator<T> {
364 private final Queue<PeekingIterator<T>> queue;
365 private final Comparator<? super T> comparator;
366
367 // The last value we returned, used for removing duplicate values.
368 private T lastValue = null;
369
370 public MergingIterator(
371 Iterable<? extends Iterator<T>> iterators,
372 Comparator<? super T> itemComparator) {
373 // checkNotNull(iterators, "iterators");
374 // checkNotNull(comparator, "comparator");
375 this.comparator = itemComparator;
376
377 // A comparator that's used by the heap, allowing the heap
378 // to be sorted based on the top of each iterator.
379 Comparator<PeekingIterator<T>> heapComparator =
380 new Comparator<PeekingIterator<T>>() {
381 @Override
382 public int compare(PeekingIterator<T> o1, PeekingIterator<T> o2) {
383 return comparator.compare(o1.peek(), o2.peek());
384 }
385 };
386
387 // Construct the heap with a minimum size of 1, because
388 // Because PriorityQueue will fail if it's 0.
389 queue = new PriorityQueue<PeekingIterator<T>>(
390 Math.max(1, Iterables.size(iterators)), heapComparator);
391 for (Iterator<T> iterator : iterators) {
392 if (iterator.hasNext()) {
393 queue.add(Iterators.peekingIterator(iterator));
394 }
395 }
396 }
397
398 @Override protected T computeNext() {
399 while (!queue.isEmpty()) {
400 PeekingIterator<T> nextIter = queue.poll();
401
402 T next = nextIter.next();
403 boolean duplicate =
404 lastValue != null
405 && comparator.compare(next, lastValue) == 0;
406
407 if (nextIter.hasNext()) {
408 queue.add(nextIter);
409 }
410 // Keep looping till we find a non-duplicate value.
411 if (!duplicate) {
412 lastValue = next;
413 return lastValue;
414 }
415 }
416
417 lastValue = null; // clear reference to unused data
418 return endOfData();
419 }
420 }
421
422 private static final long serialVersionUID = 0;
423 }