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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkNotNull;
020
021 import com.google.common.annotations.Beta;
022 import com.google.common.annotations.GwtCompatible;
023 import com.google.common.base.Function;
024 import com.google.common.base.Supplier;
025
026 import java.io.Serializable;
027 import java.util.Comparator;
028 import java.util.Iterator;
029 import java.util.Map;
030 import java.util.PriorityQueue;
031 import java.util.Queue;
032 import java.util.Set;
033 import java.util.SortedMap;
034 import java.util.SortedSet;
035 import java.util.TreeMap;
036
037 import 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
069 public 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 }