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("unchecked")
200      Comparator<Object> cmp = (Comparator<Object>) 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}