1 /*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21
22 import com.google.common.annotations.GwtCompatible;
23 import com.google.common.base.Function;
24 import com.google.common.base.Supplier;
25 import java.io.Serializable;
26 import java.util.Comparator;
27 import java.util.Iterator;
28 import java.util.Map;
29 import java.util.NoSuchElementException;
30 import java.util.Set;
31 import java.util.SortedMap;
32 import java.util.SortedSet;
33 import java.util.TreeMap;
34 import org.checkerframework.checker.nullness.qual.Nullable;
35
36 /**
37 * Implementation of {@code Table} whose row keys and column keys are ordered by their natural
38 * ordering or by supplied comparators. When constructing a {@code TreeBasedTable}, you may provide
39 * comparators for the row keys and the column keys, or you may use natural ordering for both.
40 *
41 * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link #rowMap} method
42 * returns a {@link SortedMap}, instead of the {@link Set} and {@link Map} specified by the {@link
43 * Table} interface.
44 *
45 * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link #columnMap()} have
46 * iterators that don't support {@code remove()}. Otherwise, all optional operations are supported.
47 * Null row keys, columns keys, and values are not supported.
48 *
49 * <p>Lookups by row key are often faster than lookups by column key, because the data is stored in
50 * a {@code Map<R, Map<C, V>>}. A method call like {@code column(columnKey).get(rowKey)} still runs
51 * quickly, since the row key is provided. However, {@code column(columnKey).size()} takes longer,
52 * since an iteration across all row keys occurs.
53 *
54 * <p>Because a {@code TreeBasedTable} has unique sorted values for a given row, both {@code
55 * row(rowKey)} and {@code rowMap().get(rowKey)} are {@link SortedMap} instances, instead of the
56 * {@link Map} specified in the {@link Table} interface.
57 *
58 * <p>Note that this implementation is not synchronized. If multiple threads access this table
59 * concurrently and one of the threads modifies the table, it must be synchronized externally.
60 *
61 * <p>See the Guava User Guide article on <a href=
62 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#table"> {@code Table}</a>.
63 *
64 * @author Jared Levy
65 * @author Louis Wasserman
66 * @since 7.0
67 */
68 @GwtCompatible(serializable = true)
69 public class TreeBasedTable<R, C, V> extends StandardRowSortedTable<R, C, V> {
70 private final Comparator<? super C> columnComparator;
71
72 private static class Factory<C, V> implements Supplier<TreeMap<C, V>>, Serializable {
73 final Comparator<? super C> comparator;
74
75 Factory(Comparator<? super C> comparator) {
76 this.comparator = comparator;
77 }
78
79 @Override
80 public TreeMap<C, V> get() {
81 return new TreeMap<>(comparator);
82 }
83
84 private static final long serialVersionUID = 0;
85 }
86
87 /**
88 * Creates an empty {@code TreeBasedTable} that uses the natural orderings of both row and column
89 * keys.
90 *
91 * <p>The method signature specifies {@code R extends Comparable} with a raw {@link Comparable},
92 * instead of {@code R extends Comparable<? super R>}, and the same for {@code C}. That's
93 * necessary to support classes defined without generics.
94 */
95 public static <R extends Comparable, C extends Comparable, V> TreeBasedTable<R, C, V> create() {
96 return new TreeBasedTable<>(Ordering.natural(), Ordering.natural());
97 }
98
99 /**
100 * Creates an empty {@code TreeBasedTable} that is ordered by the specified comparators.
101 *
102 * @param rowComparator the comparator that orders the row keys
103 * @param columnComparator the comparator that orders the column keys
104 */
105 public static <R, C, V> TreeBasedTable<R, C, V> create(
106 Comparator<? super R> rowComparator, Comparator<? super C> columnComparator) {
107 checkNotNull(rowComparator);
108 checkNotNull(columnComparator);
109 return new TreeBasedTable<>(rowComparator, columnComparator);
110 }
111
112 /**
113 * Creates a {@code TreeBasedTable} with the same mappings and sort order as the specified {@code
114 * TreeBasedTable}.
115 */
116 public static <R, C, V> TreeBasedTable<R, C, V> create(TreeBasedTable<R, C, ? extends V> table) {
117 TreeBasedTable<R, C, V> result =
118 new TreeBasedTable<>(table.rowComparator(), table.columnComparator());
119 result.putAll(table);
120 return result;
121 }
122
123 TreeBasedTable(Comparator<? super R> rowComparator, Comparator<? super C> columnComparator) {
124 super(new TreeMap<R, Map<C, V>>(rowComparator), new Factory<C, V>(columnComparator));
125 this.columnComparator = columnComparator;
126 }
127
128 // TODO(jlevy): Move to StandardRowSortedTable?
129
130 /**
131 * Returns the comparator that orders the rows. With natural ordering, {@link Ordering#natural()}
132 * is returned.
133 *
134 * @deprecated Use {@code table.rowKeySet().comparator()} instead.
135 */
136 @Deprecated
137 public Comparator<? super R> rowComparator() {
138 return rowKeySet().comparator();
139 }
140
141 /**
142 * Returns the comparator that orders the columns. With natural ordering, {@link
143 * Ordering#natural()} is returned.
144 *
145 * @deprecated Store the {@link Comparator} alongside the {@link Table}. Or, if you know that the
146 * {@link Table} contains at least one value, you can retrieve the {@link Comparator} with:
147 * {@code ((SortedMap<C, V>) table.rowMap().values().iterator().next()).comparator();}.
148 */
149 @Deprecated
150 public Comparator<? super C> columnComparator() {
151 return columnComparator;
152 }
153
154 // TODO(lowasser): make column return a SortedMap
155
156 /**
157 * {@inheritDoc}
158 *
159 * <p>Because a {@code TreeBasedTable} has unique sorted values for a given row, this method
160 * returns a {@link SortedMap}, instead of the {@link Map} specified in the {@link Table}
161 * interface.
162 *
163 * @since 10.0 (<a href="https://github.com/google/guava/wiki/Compatibility" >mostly
164 * source-compatible</a> since 7.0)
165 */
166 @Override
167 public SortedMap<C, V> row(R rowKey) {
168 return new TreeRow(rowKey);
169 }
170
171 private class TreeRow extends Row implements SortedMap<C, V> {
172 final @Nullable C lowerBound;
173 final @Nullable C upperBound;
174
175 TreeRow(R rowKey) {
176 this(rowKey, null, null);
177 }
178
179 TreeRow(R rowKey, @Nullable C lowerBound, @Nullable C upperBound) {
180 super(rowKey);
181 this.lowerBound = lowerBound;
182 this.upperBound = upperBound;
183 checkArgument(
184 lowerBound == null || upperBound == null || compare(lowerBound, upperBound) <= 0);
185 }
186
187 @Override
188 public SortedSet<C> keySet() {
189 return new Maps.SortedKeySet<>(this);
190 }
191
192 @Override
193 public Comparator<? super C> comparator() {
194 return columnComparator();
195 }
196
197 int compare(Object a, Object b) {
198 // pretend we can compare anything
199 @SuppressWarnings("unchecked")
200 Comparator<Object> cmp = (Comparator<Object>) comparator();
201 return cmp.compare(a, b);
202 }
203
204 boolean rangeContains(@Nullable Object o) {
205 return o != null
206 && (lowerBound == null || compare(lowerBound, o) <= 0)
207 && (upperBound == null || compare(upperBound, o) > 0);
208 }
209
210 @Override
211 public SortedMap<C, V> subMap(C fromKey, C toKey) {
212 checkArgument(rangeContains(checkNotNull(fromKey)) && rangeContains(checkNotNull(toKey)));
213 return new TreeRow(rowKey, fromKey, toKey);
214 }
215
216 @Override
217 public SortedMap<C, V> headMap(C toKey) {
218 checkArgument(rangeContains(checkNotNull(toKey)));
219 return new TreeRow(rowKey, lowerBound, toKey);
220 }
221
222 @Override
223 public SortedMap<C, V> tailMap(C fromKey) {
224 checkArgument(rangeContains(checkNotNull(fromKey)));
225 return new TreeRow(rowKey, fromKey, upperBound);
226 }
227
228 @Override
229 public C firstKey() {
230 SortedMap<C, V> backing = backingRowMap();
231 if (backing == null) {
232 throw new NoSuchElementException();
233 }
234 return backingRowMap().firstKey();
235 }
236
237 @Override
238 public C lastKey() {
239 SortedMap<C, V> backing = backingRowMap();
240 if (backing == null) {
241 throw new NoSuchElementException();
242 }
243 return backingRowMap().lastKey();
244 }
245
246 transient @Nullable SortedMap<C, V> wholeRow;
247
248 /*
249 * If the row was previously empty, we check if there's a new row here every
250 * time we're queried.
251 */
252 SortedMap<C, V> wholeRow() {
253 if (wholeRow == null || (wholeRow.isEmpty() && backingMap.containsKey(rowKey))) {
254 wholeRow = (SortedMap<C, V>) backingMap.get(rowKey);
255 }
256 return wholeRow;
257 }
258
259 @Override
260 SortedMap<C, V> backingRowMap() {
261 return (SortedMap<C, V>) super.backingRowMap();
262 }
263
264 @Override
265 SortedMap<C, V> computeBackingRowMap() {
266 SortedMap<C, V> map = wholeRow();
267 if (map != null) {
268 if (lowerBound != null) {
269 map = map.tailMap(lowerBound);
270 }
271 if (upperBound != null) {
272 map = map.headMap(upperBound);
273 }
274 return map;
275 }
276 return null;
277 }
278
279 @Override
280 void maintainEmptyInvariant() {
281 if (wholeRow() != null && wholeRow.isEmpty()) {
282 backingMap.remove(rowKey);
283 wholeRow = null;
284 backingRowMap = null;
285 }
286 }
287
288 @Override
289 public boolean containsKey(Object key) {
290 return rangeContains(key) && super.containsKey(key);
291 }
292
293 @Override
294 public V put(C key, V value) {
295 checkArgument(rangeContains(checkNotNull(key)));
296 return super.put(key, value);
297 }
298 }
299
300 // rowKeySet() and rowMap() are defined here so they appear in the Javadoc.
301
302 @Override
303 public SortedSet<R> rowKeySet() {
304 return super.rowKeySet();
305 }
306
307 @Override
308 public SortedMap<R, Map<C, V>> rowMap() {
309 return super.rowMap();
310 }
311
312 /** Overridden column iterator to return columns values in globally sorted order. */
313 @Override
314 Iterator<C> createColumnKeyIterator() {
315 final Comparator<? super C> comparator = columnComparator();
316
317 final Iterator<C> merged =
318 Iterators.mergeSorted(
319 Iterables.transform(
320 backingMap.values(),
321 new Function<Map<C, V>, Iterator<C>>() {
322 @Override
323 public Iterator<C> apply(Map<C, V> input) {
324 return input.keySet().iterator();
325 }
326 }),
327 comparator);
328
329 return new AbstractIterator<C>() {
330 @Nullable C lastValue;
331
332 @Override
333 protected C computeNext() {
334 while (merged.hasNext()) {
335 C next = merged.next();
336 boolean duplicate = lastValue != null && comparator.compare(next, lastValue) == 0;
337
338 // Keep looping till we find a non-duplicate value.
339 if (!duplicate) {
340 lastValue = next;
341 return lastValue;
342 }
343 }
344
345 lastValue = null; // clear reference to unused data
346 return endOfData();
347 }
348 };
349 }
350
351 private static final long serialVersionUID = 0;
352 }