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<C, V>(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<R, C, V>(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<R, C, V>(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<R, C, V>(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,
140   * {@link Ordering#natural()} is returned.
141   */
142  public Comparator<? super R> rowComparator() {
143    return rowKeySet().comparator();
144  }
145
146  /**
147   * Returns the comparator that orders the columns. With natural ordering,
148   * {@link Ordering#natural()} is returned.
149   */
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
160   * row, this method returns a {@link SortedMap}, instead of the {@link Map}
161   * specified in the {@link Table} interface.
162   * @since 10.0
163   *     (<a href="https://github.com/google/guava/wiki/Compatibility"
164   *     >mostly 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    @Nullable final C lowerBound;
173    @Nullable final 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<C, V>(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 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  /**
313   * Overridden column iterator to return columns values in globally sorted
314   * order.
315   */
316  @Override
317  Iterator<C> createColumnKeyIterator() {
318    final Comparator<? super C> comparator = columnComparator();
319
320    final Iterator<C> merged =
321        Iterators.mergeSorted(
322            Iterables.transform(
323                backingMap.values(),
324                new Function<Map<C, V>, Iterator<C>>() {
325                  @Override
326                  public Iterator<C> apply(Map<C, V> input) {
327                    return input.keySet().iterator();
328                  }
329                }),
330            comparator);
331
332    return new AbstractIterator<C>() {
333      C lastValue;
334
335      @Override
336      protected C computeNext() {
337        while (merged.hasNext()) {
338          C next = merged.next();
339          boolean duplicate = lastValue != null && comparator.compare(next, lastValue) == 0;
340
341          // Keep looping till we find a non-duplicate value.
342          if (!duplicate) {
343            lastValue = next;
344            return lastValue;
345          }
346        }
347
348        lastValue = null; // clear reference to unused data
349        return endOfData();
350      }
351    };
352  }
353
354  private static final long serialVersionUID = 0;
355}