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 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021 022import com.google.common.annotations.GwtCompatible; 023import com.google.common.base.Function; 024import com.google.common.base.Supplier; 025import java.io.Serializable; 026import java.util.Comparator; 027import java.util.Iterator; 028import java.util.Map; 029import java.util.NoSuchElementException; 030import java.util.Set; 031import java.util.SortedMap; 032import java.util.SortedSet; 033import java.util.TreeMap; 034import javax.annotation.Nullable; 035 036/** 037 * Implementation of {@code Table} whose row keys and column keys are ordered 038 * by their natural ordering or by supplied comparators. When constructing a 039 * {@code TreeBasedTable}, you may provide comparators for the row keys and 040 * the column keys, or you may use natural ordering for both. 041 * 042 * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link 043 * #rowMap} method returns a {@link SortedMap}, instead of the {@link Set} and 044 * {@link Map} specified by the {@link Table} interface. 045 * 046 * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link 047 * #columnMap()} have iterators that don't support {@code remove()}. Otherwise, 048 * all optional operations are supported. Null row keys, columns keys, and 049 * values are not supported. 050 * 051 * <p>Lookups by row key are often faster than lookups by column key, because 052 * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code 053 * column(columnKey).get(rowKey)} still runs quickly, since the row key is 054 * provided. However, {@code column(columnKey).size()} takes longer, since an 055 * iteration across all row keys occurs. 056 * 057 * <p>Because a {@code TreeBasedTable} has unique sorted values for a given 058 * row, both {@code row(rowKey)} and {@code rowMap().get(rowKey)} are {@link 059 * SortedMap} instances, instead of the {@link Map} specified in the {@link 060 * Table} interface. 061 * 062 * <p>Note that this implementation is not synchronized. If multiple threads 063 * access this table concurrently and one of the threads modifies the table, it 064 * must be synchronized externally. 065 * 066 * <p>See the Guava User Guide article on <a href= 067 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#table"> 068 * {@code Table}</a>. 069 * 070 * @author Jared Levy 071 * @author Louis Wasserman 072 * @since 7.0 073 */ 074@GwtCompatible(serializable = true) 075public class TreeBasedTable<R, C, V> extends StandardRowSortedTable<R, C, V> { 076 private final Comparator<? super C> columnComparator; 077 078 private static class Factory<C, V> implements Supplier<TreeMap<C, V>>, Serializable { 079 final Comparator<? super C> comparator; 080 081 Factory(Comparator<? super C> comparator) { 082 this.comparator = comparator; 083 } 084 085 @Override 086 public TreeMap<C, V> get() { 087 return new TreeMap<C, V>(comparator); 088 } 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> TreeBasedTable<R, C, V> create() { 103 return new TreeBasedTable<R, C, V>(Ordering.natural(), 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, Comparator<? super C> columnComparator) { 115 checkNotNull(rowComparator); 116 checkNotNull(columnComparator); 117 return new TreeBasedTable<R, C, V>(rowComparator, columnComparator); 118 } 119 120 /** 121 * Creates a {@code TreeBasedTable} with the same mappings and sort order 122 * as the specified {@code TreeBasedTable}. 123 */ 124 public static <R, C, V> TreeBasedTable<R, C, V> create(TreeBasedTable<R, C, ? extends V> table) { 125 TreeBasedTable<R, C, V> result = 126 new TreeBasedTable<R, C, V>(table.rowComparator(), table.columnComparator()); 127 result.putAll(table); 128 return result; 129 } 130 131 TreeBasedTable(Comparator<? super R> rowComparator, Comparator<? super C> columnComparator) { 132 super(new TreeMap<R, Map<C, V>>(rowComparator), new Factory<C, V>(columnComparator)); 133 this.columnComparator = columnComparator; 134 } 135 136 // TODO(jlevy): Move to StandardRowSortedTable? 137 138 /** 139 * Returns the comparator that orders the rows. With natural ordering, {@link Ordering#natural()} 140 * is returned. 141 * 142 * @deprecated Use {@code table.rowKeySet().comparator()} instead. This method is scheduled for 143 * removal in April 2019. 144 */ 145 @Deprecated 146 public Comparator<? super R> rowComparator() { 147 return rowKeySet().comparator(); 148 } 149 150 /** 151 * Returns the comparator that orders the columns. With natural ordering, {@link 152 * Ordering#natural()} is returned. 153 * 154 * @deprecated Store the {@link Comparator} alongside the {@link Table}. Or, if you know that the 155 * {@link Table} contains at least one value, you can retrieve the {@link Comparator} with: 156 * {@code ((SortedMap<C, V>) table.rowMap().values().iterator().next()).comparator();}. This 157 * method is scheduled for removal in April 2019. 158 */ 159 @Deprecated 160 public Comparator<? super C> columnComparator() { 161 return columnComparator; 162 } 163 164 // TODO(lowasser): make column return a SortedMap 165 166 /** 167 * {@inheritDoc} 168 * 169 * <p>Because a {@code TreeBasedTable} has unique sorted values for a given 170 * row, this method returns a {@link SortedMap}, instead of the {@link Map} 171 * specified in the {@link Table} interface. 172 * @since 10.0 173 * (<a href="https://github.com/google/guava/wiki/Compatibility" 174 * >mostly source-compatible</a> since 7.0) 175 */ 176 @Override 177 public SortedMap<C, V> row(R rowKey) { 178 return new TreeRow(rowKey); 179 } 180 181 private class TreeRow extends Row implements SortedMap<C, V> { 182 @Nullable final C lowerBound; 183 @Nullable final C upperBound; 184 185 TreeRow(R rowKey) { 186 this(rowKey, null, null); 187 } 188 189 TreeRow(R rowKey, @Nullable C lowerBound, @Nullable C upperBound) { 190 super(rowKey); 191 this.lowerBound = lowerBound; 192 this.upperBound = upperBound; 193 checkArgument( 194 lowerBound == null || upperBound == null || compare(lowerBound, upperBound) <= 0); 195 } 196 197 @Override 198 public SortedSet<C> keySet() { 199 return new Maps.SortedKeySet<C, V>(this); 200 } 201 202 @Override 203 public Comparator<? super C> comparator() { 204 return columnComparator(); 205 } 206 207 int compare(Object a, Object b) { 208 // pretend we can compare anything 209 @SuppressWarnings({"rawtypes", "unchecked"}) 210 Comparator<Object> cmp = (Comparator) comparator(); 211 return cmp.compare(a, b); 212 } 213 214 boolean rangeContains(@Nullable Object o) { 215 return o != null 216 && (lowerBound == null || compare(lowerBound, o) <= 0) 217 && (upperBound == null || compare(upperBound, o) > 0); 218 } 219 220 @Override 221 public SortedMap<C, V> subMap(C fromKey, C toKey) { 222 checkArgument(rangeContains(checkNotNull(fromKey)) && rangeContains(checkNotNull(toKey))); 223 return new TreeRow(rowKey, fromKey, toKey); 224 } 225 226 @Override 227 public SortedMap<C, V> headMap(C toKey) { 228 checkArgument(rangeContains(checkNotNull(toKey))); 229 return new TreeRow(rowKey, lowerBound, toKey); 230 } 231 232 @Override 233 public SortedMap<C, V> tailMap(C fromKey) { 234 checkArgument(rangeContains(checkNotNull(fromKey))); 235 return new TreeRow(rowKey, fromKey, upperBound); 236 } 237 238 @Override 239 public C firstKey() { 240 SortedMap<C, V> backing = backingRowMap(); 241 if (backing == null) { 242 throw new NoSuchElementException(); 243 } 244 return backingRowMap().firstKey(); 245 } 246 247 @Override 248 public C lastKey() { 249 SortedMap<C, V> backing = backingRowMap(); 250 if (backing == null) { 251 throw new NoSuchElementException(); 252 } 253 return backingRowMap().lastKey(); 254 } 255 256 transient SortedMap<C, V> wholeRow; 257 258 /* 259 * If the row was previously empty, we check if there's a new row here every 260 * time we're queried. 261 */ 262 SortedMap<C, V> wholeRow() { 263 if (wholeRow == null || (wholeRow.isEmpty() && backingMap.containsKey(rowKey))) { 264 wholeRow = (SortedMap<C, V>) backingMap.get(rowKey); 265 } 266 return wholeRow; 267 } 268 269 @Override 270 SortedMap<C, V> backingRowMap() { 271 return (SortedMap<C, V>) super.backingRowMap(); 272 } 273 274 @Override 275 SortedMap<C, V> computeBackingRowMap() { 276 SortedMap<C, V> map = wholeRow(); 277 if (map != null) { 278 if (lowerBound != null) { 279 map = map.tailMap(lowerBound); 280 } 281 if (upperBound != null) { 282 map = map.headMap(upperBound); 283 } 284 return map; 285 } 286 return null; 287 } 288 289 @Override 290 void maintainEmptyInvariant() { 291 if (wholeRow() != null && wholeRow.isEmpty()) { 292 backingMap.remove(rowKey); 293 wholeRow = null; 294 backingRowMap = null; 295 } 296 } 297 298 @Override 299 public boolean containsKey(Object key) { 300 return rangeContains(key) && super.containsKey(key); 301 } 302 303 @Override 304 public V put(C key, V value) { 305 checkArgument(rangeContains(checkNotNull(key))); 306 return super.put(key, value); 307 } 308 } 309 310 // rowKeySet() and rowMap() are defined here so they appear in the Javadoc. 311 312 @Override 313 public SortedSet<R> rowKeySet() { 314 return super.rowKeySet(); 315 } 316 317 @Override 318 public SortedMap<R, Map<C, V>> rowMap() { 319 return super.rowMap(); 320 } 321 322 /** 323 * Overridden column iterator to return columns values in globally sorted 324 * order. 325 */ 326 @Override 327 Iterator<C> createColumnKeyIterator() { 328 final Comparator<? super C> comparator = columnComparator(); 329 330 final Iterator<C> merged = 331 Iterators.mergeSorted( 332 Iterables.transform( 333 backingMap.values(), 334 new Function<Map<C, V>, Iterator<C>>() { 335 @Override 336 public Iterator<C> apply(Map<C, V> input) { 337 return input.keySet().iterator(); 338 } 339 }), 340 comparator); 341 342 return new AbstractIterator<C>() { 343 C lastValue; 344 345 @Override 346 protected C computeNext() { 347 while (merged.hasNext()) { 348 C next = merged.next(); 349 boolean duplicate = lastValue != null && comparator.compare(next, lastValue) == 0; 350 351 // Keep looping till we find a non-duplicate value. 352 if (!duplicate) { 353 lastValue = next; 354 return lastValue; 355 } 356 } 357 358 lastValue = null; // clear reference to unused data 359 return endOfData(); 360 } 361 }; 362 } 363 364 private static final long serialVersionUID = 0; 365}