1/*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkArgument;
20import static com.google.common.base.Preconditions.checkNotNull;
21
22import com.google.common.annotations.Beta;
23import com.google.common.annotations.GwtCompatible;
24import com.google.common.base.Function;
25import com.google.common.base.Supplier;
26
27import java.io.Serializable;
28import java.util.Comparator;
29import java.util.Iterator;
30import java.util.Map;
31import java.util.NoSuchElementException;
32import java.util.Set;
33import java.util.SortedMap;
34import java.util.SortedSet;
35import java.util.TreeMap;
36
37import javax.annotation.Nullable;
38
39/**
40 * Implementation of {@code Table} whose row keys and column keys are ordered
41 * by their natural ordering or by supplied comparators. When constructing a
42 * {@code TreeBasedTable}, you may provide comparators for the row keys and
43 * the column keys, or you may use natural ordering for both.
44 *
45 * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link
46 * #rowMap} method returns a {@link SortedMap}, instead of the {@link Set} and
47 * {@link Map} specified by the {@link Table} interface.
48 *
49 * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link
50 * #columnMap()} have iterators that don't support {@code remove()}. Otherwise,
51 * all optional operations are supported. Null row keys, columns keys, and
52 * values are not supported.
53 *
54 * <p>Lookups by row key are often faster than lookups by column key, because
55 * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code
56 * column(columnKey).get(rowKey)} still runs quickly, since the row key is
57 * provided. However, {@code column(columnKey).size()} takes longer, since an
58 * iteration across all row keys occurs.
59 *
60 * <p>Because a {@code TreeBasedTable} has unique sorted values for a given
61 * row, both {@code row(rowKey)} and {@code rowMap().get(rowKey)} are {@link
62 * SortedMap} instances, instead of the {@link Map} specified in the {@link
63 * Table} interface.
64 *
65 * <p>Note that this implementation is not synchronized. If multiple threads
66 * access this table concurrently and one of the threads modifies the table, it
67 * must be synchronized externally.
68 *
69 * @author Jared Levy
70 * @author Louis Wasserman
71 * @since 7.0
72 */
73@GwtCompatible(serializable = true)
74@Beta
75public class TreeBasedTable<R, C, V> extends StandardRowSortedTable<R, C, V> {
76  private final Comparator<? super C> columnComparator;
77
78  private static class Factory<C, V>
79      implements Supplier<TreeMap<C, V>>, Serializable {
80    final Comparator<? super C> comparator;
81    Factory(Comparator<? super C> comparator) {
82      this.comparator = comparator;
83    }
84    @Override
85    public TreeMap<C, V> get() {
86      return new TreeMap<C, V>(comparator);
87    }
88    private static final long serialVersionUID = 0;
89  }
90
91  /**
92   * Creates an empty {@code TreeBasedTable} that uses the natural orderings
93   * of both row and column keys.
94   *
95   * <p>The method signature specifies {@code R extends Comparable} with a raw
96   * {@link Comparable}, instead of {@code R extends Comparable<? super R>},
97   * and the same for {@code C}. That's necessary to support classes defined
98   * without generics.
99   */
100  public static <R extends Comparable, C extends Comparable, V>
101      TreeBasedTable<R, C, V> create() {
102    return new TreeBasedTable<R, C, V>(Ordering.natural(),
103        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,
115      Comparator<? super C> columnComparator) {
116    checkNotNull(rowComparator);
117    checkNotNull(columnComparator);
118    return new TreeBasedTable<R, C, V>(rowComparator, columnComparator);
119  }
120
121  /**
122   * Creates a {@code TreeBasedTable} with the same mappings and sort order
123   * as the specified {@code TreeBasedTable}.
124   */
125  public static <R, C, V> TreeBasedTable<R, C, V> create(
126      TreeBasedTable<R, C, ? extends V> table) {
127    TreeBasedTable<R, C, V> result
128        = new TreeBasedTable<R, C, V>(
129            table.rowComparator(), table.columnComparator());
130    result.putAll(table);
131    return result;
132  }
133
134  TreeBasedTable(Comparator<? super R> rowComparator,
135      Comparator<? super C> columnComparator) {
136    super(new TreeMap<R, Map<C, V>>(rowComparator),
137        new Factory<C, V>(columnComparator));
138    this.columnComparator = columnComparator;
139  }
140
141  // TODO(jlevy): Move to StandardRowSortedTable?
142
143  /**
144   * Returns the comparator that orders the rows. With natural ordering,
145   * {@link Ordering#natural()} is returned.
146   */
147  public Comparator<? super R> rowComparator() {
148    return rowKeySet().comparator();
149  }
150
151  /**
152   * Returns the comparator that orders the columns. With natural ordering,
153   * {@link Ordering#natural()} is returned.
154   */
155  public Comparator<? super C> columnComparator() {
156    return columnComparator;
157  }
158
159  // TODO(user): make column return a SortedMap
160
161  /**
162   * {@inheritDoc}
163   *
164   * <p>Because a {@code TreeBasedTable} has unique sorted values for a given
165   * row, this method returns a {@link SortedMap}, instead of the {@link Map}
166   * specified in the {@link Table} interface.
167   * @since 10.0
168   *     (<a href="http://code.google.com/p/guava-libraries/wiki/Compatibility"
169   *     >mostly source-compatible</a> since 7.0)
170   */
171  @Override
172  public SortedMap<C, V> row(R rowKey) {
173    return new TreeRow(rowKey);
174  }
175
176  private class TreeRow extends Row implements SortedMap<C, V> {
177    @Nullable final C lowerBound;
178    @Nullable final C upperBound;
179
180    TreeRow(R rowKey) {
181      this(rowKey, null, null);
182    }
183
184    TreeRow(R rowKey, @Nullable C lowerBound, @Nullable C upperBound) {
185      super(rowKey);
186      this.lowerBound = lowerBound;
187      this.upperBound = upperBound;
188      checkArgument(lowerBound == null || upperBound == null
189          || compare(lowerBound, upperBound) <= 0);
190    }
191
192    @Override public Comparator<? super C> comparator() {
193      return columnComparator();
194    }
195
196    int compare(Object a, Object b) {
197      // pretend we can compare anything
198      @SuppressWarnings({"rawtypes", "unchecked"})
199      Comparator<Object> cmp = (Comparator) comparator();
200      return cmp.compare(a, b);
201    }
202
203    boolean rangeContains(@Nullable Object o) {
204      return o != null && (lowerBound == null || compare(lowerBound, o) <= 0)
205          && (upperBound == null || compare(upperBound, o) > 0);
206    }
207
208    @Override public SortedMap<C, V> subMap(C fromKey, C toKey) {
209      checkArgument(rangeContains(checkNotNull(fromKey))
210          && rangeContains(checkNotNull(toKey)));
211      return new TreeRow(rowKey, fromKey, toKey);
212    }
213
214    @Override public SortedMap<C, V> headMap(C toKey) {
215      checkArgument(rangeContains(checkNotNull(toKey)));
216      return new TreeRow(rowKey, lowerBound, toKey);
217    }
218
219    @Override public SortedMap<C, V> tailMap(C fromKey) {
220      checkArgument(rangeContains(checkNotNull(fromKey)));
221      return new TreeRow(rowKey, fromKey, upperBound);
222    }
223
224    @Override public C firstKey() {
225      SortedMap<C, V> backing = backingRowMap();
226      if (backing == null) {
227        throw new NoSuchElementException();
228      }
229      return backingRowMap().firstKey();
230    }
231
232    @Override public C lastKey() {
233      SortedMap<C, V> backing = backingRowMap();
234      if (backing == null) {
235        throw new NoSuchElementException();
236      }
237      return backingRowMap().lastKey();
238    }
239
240    transient SortedMap<C, V> wholeRow;
241
242    /*
243     * If the row was previously empty, we check if there's a new row here every
244     * time we're queried.
245     */
246    SortedMap<C, V> wholeRow() {
247      if (wholeRow == null
248          || (wholeRow.isEmpty() && backingMap.containsKey(rowKey))) {
249        wholeRow = (SortedMap<C, V>) backingMap.get(rowKey);
250      }
251      return wholeRow;
252    }
253
254    @Override
255    SortedMap<C, V> backingRowMap() {
256      return (SortedMap<C, V>) super.backingRowMap();
257    }
258
259    @Override
260    SortedMap<C, V> computeBackingRowMap() {
261      SortedMap<C, V> map = wholeRow();
262      if (map != null) {
263        if (lowerBound != null) {
264          map = map.tailMap(lowerBound);
265        }
266        if (upperBound != null) {
267          map = map.headMap(upperBound);
268        }
269        return map;
270      }
271      return null;
272    }
273
274    @Override
275    void maintainEmptyInvariant() {
276      if (wholeRow() != null && wholeRow.isEmpty()) {
277        backingMap.remove(rowKey);
278        wholeRow = null;
279        backingRowMap = null;
280      }
281    }
282
283    @Override public boolean containsKey(Object key) {
284      return rangeContains(key) && super.containsKey(key);
285    }
286
287    @Override public V put(C key, V value) {
288      checkArgument(rangeContains(checkNotNull(key)));
289      return super.put(key, value);
290    }
291  }
292
293  // rowKeySet() and rowMap() are defined here so they appear in the Javadoc.
294
295  @Override public SortedSet<R> rowKeySet() {
296    return super.rowKeySet();
297  }
298
299  @Override public SortedMap<R, Map<C, V>> rowMap() {
300    return super.rowMap();
301  }
302
303  // Overriding so NullPointerTester test passes.
304
305  @Override public boolean contains(
306      @Nullable Object rowKey, @Nullable Object columnKey) {
307    return super.contains(rowKey, columnKey);
308  }
309
310  @Override public boolean containsColumn(@Nullable Object columnKey) {
311    return super.containsColumn(columnKey);
312  }
313
314  @Override public boolean containsRow(@Nullable Object rowKey) {
315    return super.containsRow(rowKey);
316  }
317
318  @Override public boolean containsValue(@Nullable Object value) {
319    return super.containsValue(value);
320  }
321
322  @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
323    return super.get(rowKey, columnKey);
324  }
325
326  @Override public boolean equals(@Nullable Object obj) {
327    return super.equals(obj);
328  }
329
330  @Override public V remove(
331      @Nullable Object rowKey, @Nullable Object columnKey) {
332    return super.remove(rowKey, columnKey);
333  }
334
335  /**
336   * Overridden column iterator to return columns values in globally sorted
337   * order.
338   */
339  @Override
340  Iterator<C> createColumnKeyIterator() {
341    final Comparator<? super C> comparator = columnComparator();
342
343    final Iterator<C> merged =
344        Iterators.mergeSorted(Iterables.transform(backingMap.values(),
345            new Function<Map<C, V>, Iterator<C>>() {
346              @Override
347              public Iterator<C> apply(Map<C, V> input) {
348                return input.keySet().iterator();
349              }
350            }), comparator);
351
352    return new AbstractIterator<C>() {
353      C lastValue;
354
355      @Override
356      protected C computeNext() {
357        while (merged.hasNext()) {
358          C next = merged.next();
359          boolean duplicate =
360              lastValue != null && comparator.compare(next, lastValue) == 0;
361
362          // Keep looping till we find a non-duplicate value.
363          if (!duplicate) {
364            lastValue = next;
365            return lastValue;
366          }
367        }
368
369        lastValue = null; // clear reference to unused data
370        return endOfData();
371      }
372    };
373  }
374
375  private static final long serialVersionUID = 0;
376}
377