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<>(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<>(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<>(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<>(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.
143   */
144  @Deprecated
145  public Comparator<? super R> rowComparator() {
146    return rowKeySet().comparator();
147  }
148
149  /**
150   * Returns the comparator that orders the columns. With natural ordering, {@link
151   * Ordering#natural()} is returned.
152   *
153   * @deprecated Store the {@link Comparator} alongside the {@link Table}. Or, if you know that the
154   *     {@link Table} contains at least one value, you can retrieve the {@link Comparator} with:
155   *     {@code ((SortedMap<C, V>) table.rowMap().values().iterator().next()).comparator();}.
156   */
157  @Deprecated
158  public Comparator<? super C> columnComparator() {
159    return columnComparator;
160  }
161
162  // TODO(lowasser): make column return a SortedMap
163
164  /**
165   * {@inheritDoc}
166   *
167   * <p>Because a {@code TreeBasedTable} has unique sorted values for a given
168   * row, this method returns a {@link SortedMap}, instead of the {@link Map}
169   * specified in the {@link Table} interface.
170   * @since 10.0
171   *     (<a href="https://github.com/google/guava/wiki/Compatibility"
172   *     >mostly source-compatible</a> since 7.0)
173   */
174  @Override
175  public SortedMap<C, V> row(R rowKey) {
176    return new TreeRow(rowKey);
177  }
178
179  private class TreeRow extends Row implements SortedMap<C, V> {
180    @Nullable final C lowerBound;
181    @Nullable final C upperBound;
182
183    TreeRow(R rowKey) {
184      this(rowKey, null, null);
185    }
186
187    TreeRow(R rowKey, @Nullable C lowerBound, @Nullable C upperBound) {
188      super(rowKey);
189      this.lowerBound = lowerBound;
190      this.upperBound = upperBound;
191      checkArgument(
192          lowerBound == null || upperBound == null || compare(lowerBound, upperBound) <= 0);
193    }
194
195    @Override
196    public SortedSet<C> keySet() {
197      return new Maps.SortedKeySet<>(this);
198    }
199
200    @Override
201    public Comparator<? super C> comparator() {
202      return columnComparator();
203    }
204
205    int compare(Object a, Object b) {
206      // pretend we can compare anything
207      @SuppressWarnings({"rawtypes", "unchecked"})
208      Comparator<Object> cmp = (Comparator) comparator();
209      return cmp.compare(a, b);
210    }
211
212    boolean rangeContains(@Nullable Object o) {
213      return o != null
214          && (lowerBound == null || compare(lowerBound, o) <= 0)
215          && (upperBound == null || compare(upperBound, o) > 0);
216    }
217
218    @Override
219    public SortedMap<C, V> subMap(C fromKey, C toKey) {
220      checkArgument(rangeContains(checkNotNull(fromKey)) && rangeContains(checkNotNull(toKey)));
221      return new TreeRow(rowKey, fromKey, toKey);
222    }
223
224    @Override
225    public SortedMap<C, V> headMap(C toKey) {
226      checkArgument(rangeContains(checkNotNull(toKey)));
227      return new TreeRow(rowKey, lowerBound, toKey);
228    }
229
230    @Override
231    public SortedMap<C, V> tailMap(C fromKey) {
232      checkArgument(rangeContains(checkNotNull(fromKey)));
233      return new TreeRow(rowKey, fromKey, upperBound);
234    }
235
236    @Override
237    public C firstKey() {
238      SortedMap<C, V> backing = backingRowMap();
239      if (backing == null) {
240        throw new NoSuchElementException();
241      }
242      return backingRowMap().firstKey();
243    }
244
245    @Override
246    public C lastKey() {
247      SortedMap<C, V> backing = backingRowMap();
248      if (backing == null) {
249        throw new NoSuchElementException();
250      }
251      return backingRowMap().lastKey();
252    }
253
254    transient SortedMap<C, V> wholeRow;
255
256    /*
257     * If the row was previously empty, we check if there's a new row here every
258     * time we're queried.
259     */
260    SortedMap<C, V> wholeRow() {
261      if (wholeRow == null || (wholeRow.isEmpty() && backingMap.containsKey(rowKey))) {
262        wholeRow = (SortedMap<C, V>) backingMap.get(rowKey);
263      }
264      return wholeRow;
265    }
266
267    @Override
268    SortedMap<C, V> backingRowMap() {
269      return (SortedMap<C, V>) super.backingRowMap();
270    }
271
272    @Override
273    SortedMap<C, V> computeBackingRowMap() {
274      SortedMap<C, V> map = wholeRow();
275      if (map != null) {
276        if (lowerBound != null) {
277          map = map.tailMap(lowerBound);
278        }
279        if (upperBound != null) {
280          map = map.headMap(upperBound);
281        }
282        return map;
283      }
284      return null;
285    }
286
287    @Override
288    void maintainEmptyInvariant() {
289      if (wholeRow() != null && wholeRow.isEmpty()) {
290        backingMap.remove(rowKey);
291        wholeRow = null;
292        backingRowMap = null;
293      }
294    }
295
296    @Override
297    public boolean containsKey(Object key) {
298      return rangeContains(key) && super.containsKey(key);
299    }
300
301    @Override
302    public V put(C key, V value) {
303      checkArgument(rangeContains(checkNotNull(key)));
304      return super.put(key, value);
305    }
306  }
307
308  // rowKeySet() and rowMap() are defined here so they appear in the Javadoc.
309
310  @Override
311  public SortedSet<R> rowKeySet() {
312    return super.rowKeySet();
313  }
314
315  @Override
316  public SortedMap<R, Map<C, V>> rowMap() {
317    return super.rowMap();
318  }
319
320  /**
321   * Overridden column iterator to return columns values in globally sorted
322   * order.
323   */
324  @Override
325  Iterator<C> createColumnKeyIterator() {
326    final Comparator<? super C> comparator = columnComparator();
327
328    final Iterator<C> merged =
329        Iterators.mergeSorted(
330            Iterables.transform(
331                backingMap.values(),
332                new Function<Map<C, V>, Iterator<C>>() {
333                  @Override
334                  public Iterator<C> apply(Map<C, V> input) {
335                    return input.keySet().iterator();
336                  }
337                }),
338            comparator);
339
340    return new AbstractIterator<C>() {
341      C lastValue;
342
343      @Override
344      protected C computeNext() {
345        while (merged.hasNext()) {
346          C next = merged.next();
347          boolean duplicate = lastValue != null && comparator.compare(next, lastValue) == 0;
348
349          // Keep looping till we find a non-duplicate value.
350          if (!duplicate) {
351            lastValue = next;
352            return lastValue;
353          }
354        }
355
356        lastValue = null; // clear reference to unused data
357        return endOfData();
358      }
359    };
360  }
361
362  private static final long serialVersionUID = 0;
363}