001 /*
002 * Copyright (C) 2008 Google Inc.
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.Supplier;
024
025 import java.io.Serializable;
026 import java.util.Comparator;
027 import java.util.Map;
028 import java.util.Set;
029 import java.util.SortedMap;
030 import java.util.SortedSet;
031 import java.util.TreeMap;
032
033 import javax.annotation.Nullable;
034
035 /**
036 * Implementation of {@code Table} whose row keys and column keys are ordered
037 * by their natural ordering or by supplied comparators. When constructing a
038 * {@code TreeBasedTable}, you may provide comparators for the row keys and
039 * the column keys, or you may use natural ordering for both.
040 *
041 * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link
042 * #rowMap} method returns a {@link SortedMap}, instead of the {@link Set} and
043 * {@link Map} specified by the {@link Table} interface.
044 *
045 * <p>Note that the column keys as returned by {@link #columnKeySet()} and
046 * {@link #columnMap()} are <i>not</i> sorted. Sorted column keys can be
047 * observed in {@link Table#row(Object)} and the values of {@link #rowMap()}.
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 public TreeMap<C, V> get() {
079 return new TreeMap<C, V>(comparator);
080 }
081 private static final long serialVersionUID = 0;
082 }
083
084 /**
085 * Creates an empty {@code TreeBasedTable} that uses the natural orderings
086 * of both row and column keys.
087 *
088 * <p>The method signature specifies {@code R extends Comparable} with a raw
089 * {@link Comparable}, instead of {@code R extends Comparable<? super R>},
090 * and the same for {@code C}. That's necessary to support classes defined
091 * without generics.
092 */
093 @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
094 public static <R extends Comparable, C extends Comparable, V>
095 TreeBasedTable<R, C, V> create() {
096 return new TreeBasedTable<R, C, V>(Ordering.natural(),
097 Ordering.natural());
098 }
099
100 /**
101 * Creates an empty {@code TreeBasedTable} that is ordered by the specified
102 * comparators.
103 *
104 * @param rowComparator the comparator that orders the row keys
105 * @param columnComparator the comparator that orders the column keys
106 */
107 public static <R, C, V> TreeBasedTable<R, C, V> create(
108 Comparator<? super R> rowComparator,
109 Comparator<? super C> columnComparator) {
110 checkNotNull(rowComparator);
111 checkNotNull(columnComparator);
112 return new TreeBasedTable<R, C, V>(rowComparator, columnComparator);
113 }
114
115 /**
116 * Creates a {@code TreeBasedTable} with the same mappings and sort order
117 * as the specified {@code TreeBasedTable}.
118 */
119 public static <R, C, V> TreeBasedTable<R, C, V> create(
120 TreeBasedTable<R, C, ? extends V> table) {
121 TreeBasedTable<R, C, V> result
122 = new TreeBasedTable<R, C, V>(
123 table.rowComparator(), table.columnComparator());
124 result.putAll(table);
125 return result;
126 }
127
128 TreeBasedTable(Comparator<? super R> rowComparator,
129 Comparator<? super C> columnComparator) {
130 super(new TreeMap<R, Map<C, V>>(rowComparator),
131 new Factory<C, V>(columnComparator));
132 this.columnComparator = columnComparator;
133 }
134
135 // TODO(jlevy): Move to StandardRowSortedTable?
136
137 /**
138 * Returns the comparator that orders the rows. With natural ordering,
139 * {@link Ordering#natural()} is returned.
140 */
141 public Comparator<? super R> rowComparator() {
142 return rowKeySet().comparator();
143 }
144
145 /**
146 * Returns the comparator that orders the columns. With natural ordering,
147 * {@link Ordering#natural()} is returned.
148 */
149 public Comparator<? super C> columnComparator() {
150 return columnComparator;
151 }
152
153 // rowKeySet() and rowMap() are defined here so they appear in the Javadoc.
154
155 @Override public SortedSet<R> rowKeySet() {
156 return super.rowKeySet();
157 }
158
159 @Override public SortedMap<R, Map<C, V>> rowMap() {
160 return super.rowMap();
161 }
162
163 // Overriding so NullPointerTester test passes.
164
165 @Override public boolean contains(
166 @Nullable Object rowKey, @Nullable Object columnKey) {
167 return super.contains(rowKey, columnKey);
168 }
169
170 @Override public boolean containsColumn(@Nullable Object columnKey) {
171 return super.containsColumn(columnKey);
172 }
173
174 @Override public boolean containsRow(@Nullable Object rowKey) {
175 return super.containsRow(rowKey);
176 }
177
178 @Override public boolean containsValue(@Nullable Object value) {
179 return super.containsValue(value);
180 }
181
182 @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
183 return super.get(rowKey, columnKey);
184 }
185
186 @Override public boolean equals(@Nullable Object obj) {
187 return super.equals(obj);
188 }
189
190 @Override public V remove(
191 @Nullable Object rowKey, @Nullable Object columnKey) {
192 return super.remove(rowKey, columnKey);
193 }
194
195 private static final long serialVersionUID = 0;
196 }