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. 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<>(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}