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.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.Beta;
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.base.Function;
025 import com.google.common.base.Objects;
026 import com.google.common.base.Supplier;
027 import com.google.common.collect.Collections2.TransformedCollection;
028 import com.google.common.collect.Table.Cell;
029
030 import java.io.Serializable;
031 import java.util.Collection;
032 import java.util.Map;
033 import java.util.Set;
034
035 import javax.annotation.Nullable;
036
037 /**
038 * Provides static methods that involve a {@code Table}.
039 *
040 * @author Jared Levy
041 * @since 7.0
042 */
043 @GwtCompatible
044 @Beta
045 public final class Tables {
046 private Tables() {}
047
048 /**
049 * Returns an immutable cell with the specified row key, column key, and
050 * value.
051 *
052 * <p>The returned cell is serializable.
053 *
054 * @param rowKey the row key to be associated with the returned cell
055 * @param columnKey the column key to be associated with the returned cell
056 * @param value the value to be associated with the returned cell
057 */
058 public static <R, C, V> Cell<R, C, V> immutableCell(
059 @Nullable R rowKey, @Nullable C columnKey, @Nullable V value) {
060 return new ImmutableCell<R, C, V>(rowKey, columnKey, value);
061 }
062
063 static final class ImmutableCell<R, C, V>
064 extends AbstractCell<R, C, V> implements Serializable {
065 private final R rowKey;
066 private final C columnKey;
067 private final V value;
068
069 ImmutableCell(
070 @Nullable R rowKey, @Nullable C columnKey, @Nullable V value) {
071 this.rowKey = rowKey;
072 this.columnKey = columnKey;
073 this.value = value;
074 }
075
076 @Override
077 public R getRowKey() {
078 return rowKey;
079 }
080 @Override
081 public C getColumnKey() {
082 return columnKey;
083 }
084 @Override
085 public V getValue() {
086 return value;
087 }
088
089 private static final long serialVersionUID = 0;
090 }
091
092 abstract static class AbstractCell<R, C, V> implements Cell<R, C, V> {
093 // needed for serialization
094 AbstractCell() {}
095
096 @Override public boolean equals(Object obj) {
097 if (obj == this) {
098 return true;
099 }
100 if (obj instanceof Cell) {
101 Cell<?, ?, ?> other = (Cell<?, ?, ?>) obj;
102 return Objects.equal(getRowKey(), other.getRowKey())
103 && Objects.equal(getColumnKey(), other.getColumnKey())
104 && Objects.equal(getValue(), other.getValue());
105 }
106 return false;
107 }
108
109 @Override public int hashCode() {
110 return Objects.hashCode(getRowKey(), getColumnKey(), getValue());
111 }
112
113 @Override public String toString() {
114 return "(" + getRowKey() + "," + getColumnKey() + ")=" + getValue();
115 }
116 }
117
118 /**
119 * Creates a transposed view of a given table that flips its row and column
120 * keys. In other words, calling {@code get(columnKey, rowKey)} on the
121 * generated table always returns the same value as calling {@code
122 * get(rowKey, columnKey)} on the original table. Updating the original table
123 * changes the contents of the transposed table and vice versa.
124 *
125 * <p>The returned table supports update operations as long as the input table
126 * supports the analogous operation with swapped rows and columns. For
127 * example, in a {@link HashBasedTable} instance, {@code
128 * rowKeySet().iterator()} supports {@code remove()} but {@code
129 * columnKeySet().iterator()} doesn't. With a transposed {@link
130 * HashBasedTable}, it's the other way around.
131 */
132 public static <R, C, V> Table<C, R, V> transpose(Table<R, C, V> table) {
133 return (table instanceof TransposeTable)
134 ? ((TransposeTable<R, C, V>) table).original
135 : new TransposeTable<C, R, V>(table);
136 }
137
138 private static class TransposeTable<C, R, V> implements Table<C, R, V> {
139 final Table<R, C, V> original;
140
141 TransposeTable(Table<R, C, V> original) {
142 this.original = checkNotNull(original);
143 }
144
145 @Override
146 public void clear() {
147 original.clear();
148 }
149
150 @Override
151 public Map<C, V> column(R columnKey) {
152 return original.row(columnKey);
153 }
154
155 @Override
156 public Set<R> columnKeySet() {
157 return original.rowKeySet();
158 }
159
160 @Override
161 public Map<R, Map<C, V>> columnMap() {
162 return original.rowMap();
163 }
164
165 @Override
166 public boolean contains(
167 @Nullable Object rowKey, @Nullable Object columnKey) {
168 return original.contains(columnKey, rowKey);
169 }
170
171 @Override
172 public boolean containsColumn(@Nullable Object columnKey) {
173 return original.containsRow(columnKey);
174 }
175
176 @Override
177 public boolean containsRow(@Nullable Object rowKey) {
178 return original.containsColumn(rowKey);
179 }
180
181 @Override
182 public boolean containsValue(@Nullable Object value) {
183 return original.containsValue(value);
184 }
185
186 @Override
187 public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
188 return original.get(columnKey, rowKey);
189 }
190
191 @Override
192 public boolean isEmpty() {
193 return original.isEmpty();
194 }
195
196 @Override
197 public V put(C rowKey, R columnKey, V value) {
198 return original.put(columnKey, rowKey, value);
199 }
200
201 @Override
202 public void putAll(Table<? extends C, ? extends R, ? extends V> table) {
203 original.putAll(transpose(table));
204 }
205
206 @Override
207 public V remove(@Nullable Object rowKey, @Nullable Object columnKey) {
208 return original.remove(columnKey, rowKey);
209 }
210
211 @Override
212 public Map<R, V> row(C rowKey) {
213 return original.column(rowKey);
214 }
215
216 @Override
217 public Set<C> rowKeySet() {
218 return original.columnKeySet();
219 }
220
221 @Override
222 public Map<C, Map<R, V>> rowMap() {
223 return original.columnMap();
224 }
225
226 @Override
227 public int size() {
228 return original.size();
229 }
230
231 @Override
232 public Collection<V> values() {
233 return original.values();
234 }
235
236 @Override public boolean equals(@Nullable Object obj) {
237 if (obj == this) {
238 return true;
239 }
240 if (obj instanceof Table) {
241 Table<?, ?, ?> other = (Table<?, ?, ?>) obj;
242 return cellSet().equals(other.cellSet());
243 }
244 return false;
245 }
246
247 @Override public int hashCode() {
248 return cellSet().hashCode();
249 }
250
251 @Override public String toString() {
252 return rowMap().toString();
253 }
254
255 // Will cast TRANSPOSE_CELL to a type that always succeeds
256 private static final Function<Cell<?, ?, ?>, Cell<?, ?, ?>> TRANSPOSE_CELL =
257 new Function<Cell<?, ?, ?>, Cell<?, ?, ?>>() {
258 @Override
259 public Cell<?, ?, ?> apply(Cell<?, ?, ?> cell) {
260 return immutableCell(
261 cell.getColumnKey(), cell.getRowKey(), cell.getValue());
262 }
263 };
264
265 CellSet cellSet;
266
267 @Override
268 public Set<Cell<C, R, V>> cellSet() {
269 CellSet result = cellSet;
270 return (result == null) ? cellSet = new CellSet() : result;
271 }
272
273 class CellSet extends TransformedCollection<Cell<R, C, V>, Cell<C, R, V>>
274 implements Set<Cell<C, R, V>> {
275 // Casting TRANSPOSE_CELL to a type that always succeeds
276 @SuppressWarnings("unchecked")
277 CellSet() {
278 super(original.cellSet(), (Function) TRANSPOSE_CELL);
279 }
280
281 @Override public boolean equals(Object obj) {
282 if (obj == this) {
283 return true;
284 }
285 if (!(obj instanceof Set)) {
286 return false;
287 }
288 Set<?> os = (Set<?>) obj;
289 if (os.size() != size()) {
290 return false;
291 }
292 return containsAll(os);
293 }
294
295 @Override public int hashCode() {
296 return Sets.hashCodeImpl(this);
297 }
298
299 @Override public boolean contains(Object obj) {
300 if (obj instanceof Cell) {
301 Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
302 return original.cellSet().contains(immutableCell(
303 cell.getColumnKey(), cell.getRowKey(), cell.getValue()));
304 }
305 return false;
306 }
307
308 @Override public boolean remove(Object obj) {
309 if (obj instanceof Cell) {
310 Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
311 return original.cellSet().remove(immutableCell(
312 cell.getColumnKey(), cell.getRowKey(), cell.getValue()));
313 }
314 return false;
315 }
316 }
317 }
318
319 /**
320 * Creates a table that uses the specified backing map and factory. It can
321 * generate a table based on arbitrary {@link Map} classes.
322 *
323 * <p>The {@code factory}-generated and {@code backingMap} classes determine
324 * the table iteration order. However, the table's {@code row()} method
325 * returns instances of a different class than {@code factory.get()} does.
326 *
327 * <p>Call this method only when the simpler factory methods in classes like
328 * {@link HashBasedTable} and {@link TreeBasedTable} won't suffice.
329 *
330 * <p>The views returned by the {@code Table} methods {@link Table#column},
331 * {@link Table#columnKeySet}, and {@link Table#columnMap} have iterators that
332 * don't support {@code remove()}. Otherwise, all optional operations are
333 * supported. Null row keys, columns keys, and values are not supported.
334 *
335 * <p>Lookups by row key are often faster than lookups by column key, because
336 * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like
337 * {@code column(columnKey).get(rowKey)} still runs quickly, since the row key
338 * is provided. However, {@code column(columnKey).size()} takes longer, since
339 * an iteration across all row keys occurs.
340 *
341 * <p>Note that this implementation is not synchronized. If multiple threads
342 * access this table concurrently and one of the threads modifies the table,
343 * it must be synchronized externally.
344 *
345 * <p>The table is serializable if {@code backingMap}, {@code factory}, the
346 * maps generated by {@code factory}, and the table contents are all
347 * serializable.
348 *
349 * <p>Note: the table assumes complete ownership over of {@code backingMap}
350 * and the maps returned by {@code factory}. Those objects should not be
351 * manually updated and they should not use soft, weak, or phantom references.
352 *
353 * @param backingMap place to store the mapping from each row key to its
354 * corresponding column key / value map
355 * @param factory supplier of new, empty maps that will each hold all column
356 * key / value mappings for a given row key
357 * @throws IllegalArgumentException if {@code backingMap} is not empty
358 * @since 10.0
359 */
360 public static <R, C, V> Table<R, C, V> newCustomTable(
361 Map<R, Map<C, V>> backingMap, Supplier<? extends Map<C, V>> factory) {
362 checkArgument(backingMap.isEmpty());
363 checkNotNull(factory);
364 // TODO(jlevy): Wrap factory to validate that the supplied maps are empty?
365 return new StandardTable<R, C, V>(backingMap, factory);
366 }
367
368 /**
369 * Returns a view of a table where each value is transformed by a function.
370 * All other properties of the table, such as iteration order, are left
371 * intact.
372 *
373 * <p>Changes in the underlying table are reflected in this view. Conversely,
374 * this view supports removal operations, and these are reflected in the
375 * underlying table.
376 *
377 * <p>It's acceptable for the underlying table to contain null keys, and even
378 * null values provided that the function is capable of accepting null input.
379 * The transformed table might contain null values, if the function sometimes
380 * gives a null result.
381 *
382 * <p>The returned table is not thread-safe or serializable, even if the
383 * underlying table is.
384 *
385 * <p>The function is applied lazily, invoked when needed. This is necessary
386 * for the returned table to be a view, but it means that the function will be
387 * applied many times for bulk operations like {@link Table#containsValue} and
388 * {@code Table.toString()}. For this to perform well, {@code function} should
389 * be fast. To avoid lazy evaluation when the returned table doesn't need to
390 * be a view, copy the returned table into a new table of your choosing.
391 *
392 * @since 10.0
393 */
394 public static <R, C, V1, V2> Table<R, C, V2> transformValues(
395 Table<R, C, V1> fromTable, Function<? super V1, V2> function) {
396 return new TransformedTable<R, C, V1, V2>(fromTable, function);
397 }
398
399 private static class TransformedTable<R, C, V1, V2>
400 implements Table<R, C, V2> {
401 final Table<R, C, V1> fromTable;
402 final Function<? super V1, V2> function;
403
404 TransformedTable(
405 Table<R, C, V1> fromTable, Function<? super V1, V2> function) {
406 this.fromTable = checkNotNull(fromTable);
407 this.function = checkNotNull(function);
408 }
409
410 @Override public boolean contains(Object rowKey, Object columnKey) {
411 return fromTable.contains(rowKey, columnKey);
412 }
413
414 @Override public boolean containsRow(Object rowKey) {
415 return fromTable.containsRow(rowKey);
416 }
417
418 @Override public boolean containsColumn(Object columnKey) {
419 return fromTable.containsColumn(columnKey);
420 }
421
422 @Override public boolean containsValue(Object value) {
423 return values().contains(value);
424 }
425
426 @Override public V2 get(Object rowKey, Object columnKey) {
427 // The function is passed a null input only when the table contains a null
428 // value.
429 return contains(rowKey, columnKey)
430 ? function.apply(fromTable.get(rowKey, columnKey)) : null;
431 }
432
433 @Override public boolean isEmpty() {
434 return fromTable.isEmpty();
435 }
436
437 @Override public int size() {
438 return fromTable.size();
439 }
440
441 @Override public void clear() {
442 fromTable.clear();
443 }
444
445 @Override public V2 put(R rowKey, C columnKey, V2 value) {
446 throw new UnsupportedOperationException();
447 }
448
449 @Override public void putAll(
450 Table<? extends R, ? extends C, ? extends V2> table) {
451 throw new UnsupportedOperationException();
452 }
453
454 @Override public V2 remove(Object rowKey, Object columnKey) {
455 return contains(rowKey, columnKey)
456 ? function.apply(fromTable.remove(rowKey, columnKey)) : null;
457 }
458
459 @Override public Map<C, V2> row(R rowKey) {
460 return Maps.transformValues(fromTable.row(rowKey), function);
461 }
462
463 @Override public Map<R, V2> column(C columnKey) {
464 return Maps.transformValues(fromTable.column(columnKey), function);
465 }
466
467 Function<Cell<R, C, V1>, Cell<R, C, V2>> cellFunction() {
468 return new Function<Cell<R, C, V1>, Cell<R, C, V2>>() {
469 @Override public Cell<R, C, V2> apply(Cell<R, C, V1> cell) {
470 return immutableCell(
471 cell.getRowKey(), cell.getColumnKey(),
472 function.apply(cell.getValue()));
473 }
474 };
475 }
476
477 class CellSet extends TransformedCollection<Cell<R, C, V1>, Cell<R, C, V2>>
478 implements Set<Cell<R, C, V2>> {
479 CellSet() {
480 super(fromTable.cellSet(), cellFunction());
481 }
482 @Override public boolean equals(Object obj) {
483 return Sets.equalsImpl(this, obj);
484 }
485 @Override public int hashCode() {
486 return Sets.hashCodeImpl(this);
487 }
488 @Override public boolean contains(Object obj) {
489 if (obj instanceof Cell) {
490 Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
491 if (!Objects.equal(
492 cell.getValue(), get(cell.getRowKey(), cell.getColumnKey()))) {
493 return false;
494 }
495 return cell.getValue() != null
496 || fromTable.contains(cell.getRowKey(), cell.getColumnKey());
497 }
498 return false;
499 }
500 @Override public boolean remove(Object obj) {
501 if (contains(obj)) {
502 Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
503 fromTable.remove(cell.getRowKey(), cell.getColumnKey());
504 return true;
505 }
506 return false;
507 }
508 }
509
510 CellSet cellSet;
511
512 @Override public Set<Cell<R, C, V2>> cellSet() {
513 return (cellSet == null) ? cellSet = new CellSet() : cellSet;
514 }
515
516 @Override public Set<R> rowKeySet() {
517 return fromTable.rowKeySet();
518 }
519
520 @Override public Set<C> columnKeySet() {
521 return fromTable.columnKeySet();
522 }
523
524 Collection<V2> values;
525
526 @Override public Collection<V2> values() {
527 return (values == null)
528 ? values = Collections2.transform(fromTable.values(), function)
529 : values;
530 }
531
532 Map<R, Map<C, V2>> createRowMap() {
533 Function<Map<C, V1>, Map<C, V2>> rowFunction =
534 new Function<Map<C, V1>, Map<C, V2>>() {
535 @Override public Map<C, V2> apply(Map<C, V1> row) {
536 return Maps.transformValues(row, function);
537 }
538 };
539 return Maps.transformValues(fromTable.rowMap(), rowFunction);
540 }
541
542 Map<R, Map<C, V2>> rowMap;
543
544 @Override public Map<R, Map<C, V2>> rowMap() {
545 return (rowMap == null) ? rowMap = createRowMap() : rowMap;
546 }
547
548 Map<C, Map<R, V2>> createColumnMap() {
549 Function<Map<R, V1>, Map<R, V2>> columnFunction =
550 new Function<Map<R, V1>, Map<R, V2>>() {
551 @Override public Map<R, V2> apply(Map<R, V1> column) {
552 return Maps.transformValues(column, function);
553 }
554 };
555 return Maps.transformValues(fromTable.columnMap(), columnFunction);
556 }
557
558 Map<C, Map<R, V2>> columnMap;
559
560 @Override public Map<C, Map<R, V2>> columnMap() {
561 return (columnMap == null) ? columnMap = createColumnMap() : columnMap;
562 }
563
564 @Override public boolean equals(@Nullable Object obj) {
565 if (obj == this) {
566 return true;
567 }
568 if (obj instanceof Table) {
569 Table<?, ?, ?> other = (Table<?, ?, ?>) obj;
570 return cellSet().equals(other.cellSet());
571 }
572 return false;
573 }
574
575 @Override public int hashCode() {
576 return cellSet().hashCode();
577 }
578
579 @Override public String toString() {
580 return rowMap().toString();
581 }
582 }
583 }