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 org.checkerframework.checker.nullness.qual.Nullable; 035 036/** 037 * Implementation of {@code Table} whose row keys and column keys are ordered by their natural 038 * ordering or by supplied comparators. When constructing a {@code TreeBasedTable}, you may provide 039 * comparators for the row keys and the column keys, or you may use natural ordering for both. 040 * 041 * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link #rowMap} method 042 * returns a {@link SortedMap}, instead of the {@link Set} and {@link Map} specified by the {@link 043 * Table} interface. 044 * 045 * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link #columnMap()} have 046 * iterators that don't support {@code remove()}. Otherwise, all optional operations are supported. 047 * Null row keys, columns keys, and values are not supported. 048 * 049 * <p>Lookups by row key are often faster than lookups by column key, because the data is stored in 050 * a {@code Map<R, Map<C, V>>}. A method call like {@code column(columnKey).get(rowKey)} still runs 051 * quickly, since the row key is provided. However, {@code column(columnKey).size()} takes longer, 052 * since an iteration across all row keys occurs. 053 * 054 * <p>Because a {@code TreeBasedTable} has unique sorted values for a given row, both {@code 055 * row(rowKey)} and {@code rowMap().get(rowKey)} are {@link SortedMap} instances, instead of the 056 * {@link Map} specified in the {@link Table} interface. 057 * 058 * <p>Note that this implementation is not synchronized. If multiple threads access this table 059 * concurrently and one of the threads modifies the table, it must be synchronized externally. 060 * 061 * <p>See the Guava User Guide article on <a href= 062 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#table"> {@code Table}</a>. 063 * 064 * @author Jared Levy 065 * @author Louis Wasserman 066 * @since 7.0 067 */ 068@GwtCompatible(serializable = true) 069public class TreeBasedTable<R, C, V> extends StandardRowSortedTable<R, C, V> { 070 private final Comparator<? super C> columnComparator; 071 072 private static class Factory<C, V> implements Supplier<TreeMap<C, V>>, Serializable { 073 final Comparator<? super C> comparator; 074 075 Factory(Comparator<? super C> comparator) { 076 this.comparator = comparator; 077 } 078 079 @Override 080 public TreeMap<C, V> get() { 081 return new TreeMap<>(comparator); 082 } 083 084 private static final long serialVersionUID = 0; 085 } 086 087 /** 088 * Creates an empty {@code TreeBasedTable} that uses the natural orderings of both row and column 089 * keys. 090 * 091 * <p>The method signature specifies {@code R extends Comparable} with a raw {@link Comparable}, 092 * instead of {@code R extends Comparable<? super R>}, and the same for {@code C}. That's 093 * necessary to support classes defined without generics. 094 */ 095 public static <R extends Comparable, C extends Comparable, V> TreeBasedTable<R, C, V> create() { 096 return new TreeBasedTable<>(Ordering.natural(), Ordering.natural()); 097 } 098 099 /** 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({"rawtypes", "unchecked"}) 200 Comparator<Object> cmp = (Comparator) 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}