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.checkNotNull;
020
021import com.google.common.annotations.Beta;
022import com.google.common.annotations.GwtCompatible;
023import com.google.common.base.Function;
024import com.google.common.base.Supplier;
025
026import java.io.Serializable;
027import java.util.Comparator;
028import java.util.Iterator;
029import java.util.Map;
030import java.util.PriorityQueue;
031import java.util.Queue;
032import java.util.Set;
033import java.util.SortedMap;
034import java.util.SortedSet;
035import java.util.TreeMap;
036
037import javax.annotation.Nullable;
038
039/**
040 * Implementation of {@code Table} whose row keys and column keys are ordered
041 * by their natural ordering or by supplied comparators. When constructing a
042 * {@code TreeBasedTable}, you may provide comparators for the row keys and
043 * the column keys, or you may use natural ordering for both.
044 *
045 * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link
046 * #rowMap} method returns a {@link SortedMap}, instead of the {@link Set} and
047 * {@link Map} specified by the {@link Table} interface.
048 *
049 * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link
050 * #columnMap()} have iterators that don't support {@code remove()}. Otherwise,
051 * all optional operations are supported. Null row keys, columns keys, and
052 * values are not supported.
053 *
054 * <p>Lookups by row key are often faster than lookups by column key, because
055 * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code
056 * column(columnKey).get(rowKey)} still runs quickly, since the row key is
057 * provided. However, {@code column(columnKey).size()} takes longer, since an
058 * iteration across all row keys occurs.
059 *
060 * <p>Note that this implementation is not synchronized. If multiple threads
061 * access this table concurrently and one of the threads modifies the table, it
062 * must be synchronized externally.
063 *
064 * @author Jared Levy
065 * @since 7
066 */
067@GwtCompatible(serializable = true)
068@Beta
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>
073      implements Supplier<TreeMap<C, V>>, Serializable {
074    final Comparator<? super C> comparator;
075    Factory(Comparator<? super C> comparator) {
076      this.comparator = comparator;
077    }
078    @Override
079    public TreeMap<C, V> get() {
080      return new TreeMap<C, V>(comparator);
081    }
082    private static final long serialVersionUID = 0;
083  }
084
085  /**
086   * Creates an empty {@code TreeBasedTable} that uses the natural orderings
087   * of both row and column keys.
088   *
089   * <p>The method signature specifies {@code R extends Comparable} with a raw
090   * {@link Comparable}, instead of {@code R extends Comparable<? super R>},
091   * and the same for {@code C}. That's necessary to support classes defined
092   * without generics.
093   */
094  @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
095  public static <R extends Comparable, C extends Comparable, V>
096      TreeBasedTable<R, C, V> create() {
097    return new TreeBasedTable<R, C, V>(Ordering.natural(),
098        Ordering.natural());
099  }
100
101  /**
102   * Creates an empty {@code TreeBasedTable} that is ordered by the specified
103   * comparators.
104   *
105   * @param rowComparator the comparator that orders the row keys
106   * @param columnComparator the comparator that orders the column keys
107   */
108  public static <R, C, V> TreeBasedTable<R, C, V> create(
109      Comparator<? super R> rowComparator,
110      Comparator<? super C> columnComparator) {
111    checkNotNull(rowComparator);
112    checkNotNull(columnComparator);
113    return new TreeBasedTable<R, C, V>(rowComparator, columnComparator);
114  }
115
116  /**
117   * Creates a {@code TreeBasedTable} with the same mappings and sort order
118   * as the specified {@code TreeBasedTable}.
119   */
120  public static <R, C, V> TreeBasedTable<R, C, V> create(
121      TreeBasedTable<R, C, ? extends V> table) {
122    TreeBasedTable<R, C, V> result
123        = new TreeBasedTable<R, C, V>(
124            table.rowComparator(), table.columnComparator());
125    result.putAll(table);
126    return result;
127  }
128
129  TreeBasedTable(Comparator<? super R> rowComparator,
130      Comparator<? super C> columnComparator) {
131    super(new TreeMap<R, Map<C, V>>(rowComparator),
132        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  // rowKeySet() and rowMap() are defined here so they appear in the Javadoc.
155
156  @Override public SortedSet<R> rowKeySet() {
157    return super.rowKeySet();
158  }
159
160  @Override public SortedMap<R, Map<C, V>> rowMap() {
161    return super.rowMap();
162  }
163
164  // Overriding so NullPointerTester test passes.
165
166  @Override public boolean contains(
167      @Nullable Object rowKey, @Nullable Object columnKey) {
168    return super.contains(rowKey, columnKey);
169  }
170
171  @Override public boolean containsColumn(@Nullable Object columnKey) {
172    return super.containsColumn(columnKey);
173  }
174
175  @Override public boolean containsRow(@Nullable Object rowKey) {
176    return super.containsRow(rowKey);
177  }
178
179  @Override public boolean containsValue(@Nullable Object value) {
180    return super.containsValue(value);
181  }
182
183  @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
184    return super.get(rowKey, columnKey);
185  }
186
187  @Override public boolean equals(@Nullable Object obj) {
188    return super.equals(obj);
189  }
190
191  @Override public V remove(
192      @Nullable Object rowKey, @Nullable Object columnKey) {
193    return super.remove(rowKey, columnKey);
194  }
195
196  /**
197   * Overridden column iterator to return columns values in globally sorted
198   * order.
199   */
200  @Override Iterator<C> createColumnKeyIterator() {
201    return new MergingIterator<C>(
202        Iterables.transform(backingMap.values(),
203            new Function<Map<C, V>, Iterator<C>>() {
204                @Override
205                public Iterator<C> apply(Map<C, V> input) {
206                  return input.keySet().iterator();
207                }
208              }), columnComparator());
209  }
210
211  /**
212   * An iterator that performs a lazy N-way merge, calculating the next value
213   * each time the iterator is polled. This amortizes the sorting cost over the
214   * iteration and requires less memory than sorting all elements at once.
215   * Duplicate values are omitted.
216   *
217   * <p>Retrieving a single element takes approximately O(log(M)) time, where M
218   * is the number of iterators. (Retrieving all elements takes approximately
219   * O(N*log(M)) time, where N is the total number of elements.)
220   */
221  // TODO(user): Push this into OrderedIterators or somewhere more generic.
222  private static class MergingIterator<T> extends AbstractIterator<T> {
223    private final Queue<PeekingIterator<T>> queue;
224    private final Comparator<? super T> comparator;
225
226    // The last value we returned, used for removing duplicate values.
227    private T lastValue = null;
228
229    public MergingIterator(
230        Iterable<? extends Iterator<T>> iterators,
231        Comparator<? super T> itemComparator) {
232//    checkNotNull(iterators, "iterators");
233//    checkNotNull(comparator, "comparator");
234      this.comparator = itemComparator;
235
236      // A comparator that's used by the heap, allowing the heap
237      // to be sorted based on the top of each iterator.
238      Comparator<PeekingIterator<T>> heapComparator =
239          new Comparator<PeekingIterator<T>>() {
240            @Override
241            public int compare(PeekingIterator<T> o1, PeekingIterator<T> o2) {
242              return comparator.compare(o1.peek(), o2.peek());
243            }
244          };
245
246      // Construct the heap with a minimum size of 1, because
247      // Because PriorityQueue will fail if it's 0.
248      queue = new PriorityQueue<PeekingIterator<T>>(
249          Math.max(1, Iterables.size(iterators)), heapComparator);
250      for (Iterator<T> iterator : iterators) {
251        if (iterator.hasNext()) {
252          queue.add(Iterators.peekingIterator(iterator));
253        }
254      }
255    }
256
257    @Override protected T computeNext() {
258      while (!queue.isEmpty()) {
259        PeekingIterator<T> nextIter = queue.poll();
260
261        T next = nextIter.next();
262        boolean duplicate =
263            lastValue != null
264            && comparator.compare(next, lastValue) == 0;
265
266        if (nextIter.hasNext()) {
267          queue.add(nextIter);
268        }
269        // Keep looping till we find a non-duplicate value.
270        if (!duplicate) {
271          lastValue = next;
272          return lastValue;
273        }
274      }
275
276      lastValue = null; // clear reference to unused data
277      return endOfData();
278    }
279  }
280
281  private static final long serialVersionUID = 0;
282}