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