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;
021import static java.util.Objects.requireNonNull;
022
023import com.google.common.annotations.GwtCompatible;
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.CheckForNull;
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)
069@ElementTypesAreNonnullByDefault
070public class TreeBasedTable<R, C, V> extends StandardRowSortedTable<R, C, V> {
071  private final Comparator<? super C> columnComparator;
072
073  private static class Factory<C, V> implements Supplier<Map<C, V>>, Serializable {
074    final Comparator<? super C> comparator;
075
076    Factory(Comparator<? super C> comparator) {
077      this.comparator = comparator;
078    }
079
080    @Override
081    public Map<C, V> get() {
082      return new TreeMap<>(comparator);
083    }
084
085    private static final long serialVersionUID = 0;
086  }
087
088  /**
089   * Creates an empty {@code TreeBasedTable} that uses the natural orderings of both row and column
090   * keys.
091   *
092   * <p>The method signature specifies {@code R extends Comparable} with a raw {@link Comparable},
093   * instead of {@code R extends Comparable<? super R>}, and the same for {@code C}. That's
094   * necessary to support classes defined without generics.
095   */
096  @SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989
097  public static <R extends Comparable, C extends Comparable, V> TreeBasedTable<R, C, V> create() {
098    return new TreeBasedTable<>(Ordering.natural(), Ordering.natural());
099  }
100
101  /**
102   * Creates an empty {@code TreeBasedTable} that is ordered by the specified comparators.
103   *
104   * @param rowComparator the comparator that orders the row keys
105   * @param columnComparator the comparator that orders the column keys
106   */
107  public static <R, C, V> TreeBasedTable<R, C, V> create(
108      Comparator<? super R> rowComparator, Comparator<? super C> columnComparator) {
109    checkNotNull(rowComparator);
110    checkNotNull(columnComparator);
111    return new TreeBasedTable<>(rowComparator, columnComparator);
112  }
113
114  /**
115   * Creates a {@code TreeBasedTable} with the same mappings and sort order as the specified {@code
116   * TreeBasedTable}.
117   */
118  public static <R, C, V> TreeBasedTable<R, C, V> create(TreeBasedTable<R, C, ? extends V> table) {
119    TreeBasedTable<R, C, V> result =
120        new TreeBasedTable<>(table.rowComparator(), table.columnComparator());
121    result.putAll(table);
122    return result;
123  }
124
125  TreeBasedTable(Comparator<? super R> rowComparator, Comparator<? super C> columnComparator) {
126    super(new TreeMap<R, Map<C, V>>(rowComparator), new Factory<C, V>(columnComparator));
127    this.columnComparator = columnComparator;
128  }
129
130  // TODO(jlevy): Move to StandardRowSortedTable?
131
132  /**
133   * Returns the comparator that orders the rows. With natural ordering, {@link Ordering#natural()}
134   * is returned.
135   *
136   * @deprecated Use {@code table.rowKeySet().comparator()} instead.
137   */
138  @Deprecated
139  public Comparator<? super R> rowComparator() {
140    /*
141     * requireNonNull is safe because the factories require non-null Comparators, which they pass on
142     * to the backing collections.
143     */
144    return requireNonNull(rowKeySet().comparator());
145  }
146
147  /**
148   * Returns the comparator that orders the columns. With natural ordering, {@link
149   * Ordering#natural()} is returned.
150   *
151   * @deprecated Store the {@link Comparator} alongside the {@link Table}. Or, if you know that the
152   *     {@link Table} contains at least one value, you can retrieve the {@link Comparator} with:
153   *     {@code ((SortedMap<C, V>) table.rowMap().values().iterator().next()).comparator();}.
154   */
155  @Deprecated
156  public Comparator<? super C> columnComparator() {
157    return columnComparator;
158  }
159
160  // TODO(lowasser): make column return a SortedMap
161
162  /**
163   * {@inheritDoc}
164   *
165   * <p>Because a {@code TreeBasedTable} has unique sorted values for a given row, this method
166   * returns a {@link SortedMap}, instead of the {@link Map} specified in the {@link Table}
167   * interface.
168   *
169   * @since 10.0 (<a href="https://github.com/google/guava/wiki/Compatibility" >mostly
170   *     source-compatible</a> since 7.0)
171   */
172  @Override
173  public SortedMap<C, V> row(R rowKey) {
174    return new TreeRow(rowKey);
175  }
176
177  private class TreeRow extends Row implements SortedMap<C, V> {
178    @CheckForNull final C lowerBound;
179    @CheckForNull final C upperBound;
180
181    TreeRow(R rowKey) {
182      this(rowKey, null, null);
183    }
184
185    TreeRow(R rowKey, @CheckForNull C lowerBound, @CheckForNull C upperBound) {
186      super(rowKey);
187      this.lowerBound = lowerBound;
188      this.upperBound = upperBound;
189      checkArgument(
190          lowerBound == null || upperBound == null || compare(lowerBound, upperBound) <= 0);
191    }
192
193    @Override
194    public SortedSet<C> keySet() {
195      return new Maps.SortedKeySet<>(this);
196    }
197
198    @Override
199    public Comparator<? super C> comparator() {
200      return columnComparator();
201    }
202
203    int compare(Object a, Object b) {
204      // pretend we can compare anything
205      @SuppressWarnings("unchecked")
206      Comparator<Object> cmp = (Comparator<Object>) comparator();
207      return cmp.compare(a, b);
208    }
209
210    boolean rangeContains(@CheckForNull Object o) {
211      return o != null
212          && (lowerBound == null || compare(lowerBound, o) <= 0)
213          && (upperBound == null || compare(upperBound, o) > 0);
214    }
215
216    @Override
217    public SortedMap<C, V> subMap(C fromKey, C toKey) {
218      checkArgument(rangeContains(checkNotNull(fromKey)) && rangeContains(checkNotNull(toKey)));
219      return new TreeRow(rowKey, fromKey, toKey);
220    }
221
222    @Override
223    public SortedMap<C, V> headMap(C toKey) {
224      checkArgument(rangeContains(checkNotNull(toKey)));
225      return new TreeRow(rowKey, lowerBound, toKey);
226    }
227
228    @Override
229    public SortedMap<C, V> tailMap(C fromKey) {
230      checkArgument(rangeContains(checkNotNull(fromKey)));
231      return new TreeRow(rowKey, fromKey, upperBound);
232    }
233
234    @Override
235    public C firstKey() {
236      updateBackingRowMapField();
237      if (backingRowMap == null) {
238        throw new NoSuchElementException();
239      }
240      return ((SortedMap<C, V>) backingRowMap).firstKey();
241    }
242
243    @Override
244    public C lastKey() {
245      updateBackingRowMapField();
246      if (backingRowMap == null) {
247        throw new NoSuchElementException();
248      }
249      return ((SortedMap<C, V>) backingRowMap).lastKey();
250    }
251
252    @CheckForNull transient SortedMap<C, V> wholeRow;
253
254    // If the row was previously empty, we check if there's a new row here every time we're queried.
255    void updateWholeRowField() {
256      if (wholeRow == null || (wholeRow.isEmpty() && backingMap.containsKey(rowKey))) {
257        wholeRow = (SortedMap<C, V>) backingMap.get(rowKey);
258      }
259    }
260
261    @Override
262    @CheckForNull
263    SortedMap<C, V> computeBackingRowMap() {
264      updateWholeRowField();
265      SortedMap<C, V> map = wholeRow;
266      if (map != null) {
267        if (lowerBound != null) {
268          map = map.tailMap(lowerBound);
269        }
270        if (upperBound != null) {
271          map = map.headMap(upperBound);
272        }
273        return map;
274      }
275      return null;
276    }
277
278    @Override
279    void maintainEmptyInvariant() {
280      updateWholeRowField();
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(@CheckForNull Object key) {
290      return rangeContains(key) && super.containsKey(key);
291    }
292
293    @Override
294    @CheckForNull
295    public V put(C key, V value) {
296      checkArgument(rangeContains(checkNotNull(key)));
297      return super.put(key, value);
298    }
299  }
300
301  // rowKeySet() and rowMap() are defined here so they appear in the Javadoc.
302
303  @Override
304  public SortedSet<R> rowKeySet() {
305    return super.rowKeySet();
306  }
307
308  @Override
309  public SortedMap<R, Map<C, V>> rowMap() {
310    return super.rowMap();
311  }
312
313  /** Overridden column iterator to return columns values in globally sorted order. */
314  @Override
315  Iterator<C> createColumnKeyIterator() {
316    Comparator<? super C> comparator = columnComparator();
317
318    Iterator<C> merged =
319        Iterators.mergeSorted(
320            Iterables.transform(
321                backingMap.values(), (Map<C, V> input) -> input.keySet().iterator()),
322            comparator);
323
324    return new AbstractIterator<C>() {
325      @CheckForNull C lastValue;
326
327      @Override
328      @CheckForNull
329      protected C computeNext() {
330        while (merged.hasNext()) {
331          C next = merged.next();
332          boolean duplicate = lastValue != null && comparator.compare(next, lastValue) == 0;
333
334          // Keep looping till we find a non-duplicate value.
335          if (!duplicate) {
336            lastValue = next;
337            return lastValue;
338          }
339        }
340
341        lastValue = null; // clear reference to unused data
342        return endOfData();
343      }
344    };
345  }
346
347  private static final long serialVersionUID = 0;
348}