diff options
Diffstat (limited to 'guava/src/com/google/common/collect/ArrayTable.java')
| -rw-r--r-- | guava/src/com/google/common/collect/ArrayTable.java | 825 |
1 files changed, 825 insertions, 0 deletions
diff --git a/guava/src/com/google/common/collect/ArrayTable.java b/guava/src/com/google/common/collect/ArrayTable.java new file mode 100644 index 0000000..d13f00c --- /dev/null +++ b/guava/src/com/google/common/collect/ArrayTable.java @@ -0,0 +1,825 @@ +/* + * Copyright (C) 2009 The Guava Authors + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.google.common.collect; + +import static com.google.common.base.Preconditions.checkArgument; +import static com.google.common.base.Preconditions.checkNotNull; + +import com.google.common.annotations.Beta; +import com.google.common.base.Objects; + +import java.io.Serializable; +import java.lang.reflect.Array; +import java.util.AbstractCollection; +import java.util.AbstractSet; +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Set; + +import javax.annotation.Nullable; + +/** + * Fixed-size {@link Table} implementation backed by a two-dimensional array. + * + * <p>The allowed row and column keys must be supplied when the table is + * created. The table always contains a mapping for every row key / column pair. + * The value corresponding to a given row and column is null unless another + * value is provided. + * + * <p>The table's size is constant: the product of the number of supplied row + * keys and the number of supplied column keys. The {@code remove} and {@code + * clear} methods are not supported by the table or its views. The {@link + * #erase} and {@link #eraseAll} methods may be used instead. + * + * <p>The ordering of the row and column keys provided when the table is + * constructed determines the iteration ordering across rows and columns in the + * table's views. None of the view iterators support {@link Iterator#remove}. + * If the table is modified after an iterator is created, the iterator remains + * valid. + * + * <p>This class requires less memory than the {@link HashBasedTable} and {@link + * TreeBasedTable} implementations, except when the table is sparse. + * + * <p>Null row keys or column keys are not permitted. + * + * <p>This class provides methods involving the underlying array structure, + * where the array indices correspond to the position of a row or column in the + * lists of allowed keys and values. See the {@link #at}, {@link #set}, {@link + * #toArray}, {@link #rowKeyList}, and {@link #columnKeyList} methods for more + * details. + * + * <p>Note that this implementation is not synchronized. If multiple threads + * access the same cell of an {@code ArrayTable} concurrently and one of the + * threads modifies its value, there is no guarantee that the new value will be + * fully visible to the other threads. To guarantee that modifications are + * visible, synchronize access to the table. Unlike other {@code Table} + * implementations, synchronization is unnecessary between a thread that writes + * to one cell and a thread that reads from another. + * + * <p>See the Guava User Guide article on <a href= + * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Table"> + * {@code Table}</a>. + * + * @author Jared Levy + * @since 10.0 + */ +@Beta +public final class ArrayTable<R, C, V> implements Table<R, C, V>, Serializable { + + /** + * Creates an empty {@code ArrayTable}. + * + * @param rowKeys row keys that may be stored in the generated table + * @param columnKeys column keys that may be stored in the generated table + * @throws NullPointerException if any of the provided keys is null + * @throws IllegalArgumentException if {@code rowKeys} or {@code columnKeys} + * contains duplicates or is empty + */ + public static <R, C, V> ArrayTable<R, C, V> create( + Iterable<? extends R> rowKeys, Iterable<? extends C> columnKeys) { + return new ArrayTable<R, C, V>(rowKeys, columnKeys); + } + + /* + * TODO(jlevy): Add factory methods taking an Enum class, instead of an + * iterable, to specify the allowed row keys and/or column keys. Note that + * custom serialization logic is needed to support different enum sizes during + * serialization and deserialization. + */ + + /** + * Creates an {@code ArrayTable} with the mappings in the provided table. + * + * <p>If {@code table} includes a mapping with row key {@code r} and a + * separate mapping with column key {@code c}, the returned table contains a + * mapping with row key {@code r} and column key {@code c}. If that row key / + * column key pair in not in {@code table}, the pair maps to {@code null} in + * the generated table. + * + * <p>The returned table allows subsequent {@code put} calls with the row keys + * in {@code table.rowKeySet()} and the column keys in {@code + * table.columnKeySet()}. Calling {@link #put} with other keys leads to an + * {@code IllegalArgumentException}. + * + * <p>The ordering of {@code table.rowKeySet()} and {@code + * table.columnKeySet()} determines the row and column iteration ordering of + * the returned table. + * + * @throws NullPointerException if {@code table} has a null key + * @throws IllegalArgumentException if the provided table is empty + */ + public static <R, C, V> ArrayTable<R, C, V> create(Table<R, C, V> table) { + return new ArrayTable<R, C, V>(table); + } + + /** + * Creates an {@code ArrayTable} with the same mappings, allowed keys, and + * iteration ordering as the provided {@code ArrayTable}. + */ + public static <R, C, V> ArrayTable<R, C, V> create( + ArrayTable<R, C, V> table) { + return new ArrayTable<R, C, V>(table); + } + + private final ImmutableList<R> rowList; + private final ImmutableList<C> columnList; + + // TODO(jlevy): Add getters returning rowKeyToIndex and columnKeyToIndex? + private final ImmutableMap<R, Integer> rowKeyToIndex; + private final ImmutableMap<C, Integer> columnKeyToIndex; + private final V[][] array; + + private ArrayTable(Iterable<? extends R> rowKeys, + Iterable<? extends C> columnKeys) { + this.rowList = ImmutableList.copyOf(rowKeys); + this.columnList = ImmutableList.copyOf(columnKeys); + checkArgument(!rowList.isEmpty()); + checkArgument(!columnList.isEmpty()); + + /* + * TODO(jlevy): Support empty rowKeys or columnKeys? If we do, when + * columnKeys is empty but rowKeys isn't, the table is empty but + * containsRow() can return true and rowKeySet() isn't empty. + */ + rowKeyToIndex = index(rowList); + columnKeyToIndex = index(columnList); + + @SuppressWarnings("unchecked") + V[][] tmpArray + = (V[][]) new Object[rowList.size()][columnList.size()]; + array = tmpArray; + } + + private static <E> ImmutableMap<E, Integer> index(List<E> list) { + ImmutableMap.Builder<E, Integer> columnBuilder = ImmutableMap.builder(); + for (int i = 0; i < list.size(); i++) { + columnBuilder.put(list.get(i), i); + } + return columnBuilder.build(); + } + + private ArrayTable(Table<R, C, V> table) { + this(table.rowKeySet(), table.columnKeySet()); + putAll(table); + } + + private ArrayTable(ArrayTable<R, C, V> table) { + rowList = table.rowList; + columnList = table.columnList; + rowKeyToIndex = table.rowKeyToIndex; + columnKeyToIndex = table.columnKeyToIndex; + @SuppressWarnings("unchecked") + V[][] copy = (V[][]) new Object[rowList.size()][columnList.size()]; + array = copy; + for (int i = 0; i < rowList.size(); i++) { + System.arraycopy(table.array[i], 0, copy[i], 0, table.array[i].length); + } + } + + private abstract static class ArrayMap<K, V> extends Maps.ImprovedAbstractMap<K, V> { + private final ImmutableMap<K, Integer> keyIndex; + + private ArrayMap(ImmutableMap<K, Integer> keyIndex) { + this.keyIndex = keyIndex; + } + + @Override + public Set<K> keySet() { + return keyIndex.keySet(); + } + + K getKey(int index) { + return keyIndex.keySet().asList().get(index); + } + + abstract String getKeyRole(); + + @Nullable abstract V getValue(int index); + + @Nullable abstract V setValue(int index, V newValue); + + @Override + public int size() { + return keyIndex.size(); + } + + @Override + public boolean isEmpty() { + return keyIndex.isEmpty(); + } + + @Override + protected Set<Entry<K, V>> createEntrySet() { + return new Maps.EntrySet<K, V>() { + @Override + Map<K, V> map() { + return ArrayMap.this; + } + + @Override + public Iterator<Entry<K, V>> iterator() { + return new AbstractIndexedListIterator<Entry<K, V>>(size()) { + @Override + protected Entry<K, V> get(final int index) { + return new AbstractMapEntry<K, V>() { + @Override + public K getKey() { + return ArrayMap.this.getKey(index); + } + + @Override + public V getValue() { + return ArrayMap.this.getValue(index); + } + + @Override + public V setValue(V value) { + return ArrayMap.this.setValue(index, value); + } + }; + } + }; + } + }; + } + + @Override + public boolean containsKey(@Nullable Object key) { + return keyIndex.containsKey(key); + } + + @Override + public V get(@Nullable Object key) { + Integer index = keyIndex.get(key); + if (index == null) { + return null; + } else { + return getValue(index); + } + } + + @Override + public V put(K key, V value) { + Integer index = keyIndex.get(key); + if (index == null) { + throw new IllegalArgumentException( + getKeyRole() + " " + key + " not in " + keyIndex.keySet()); + } + return setValue(index, value); + } + + @Override + public V remove(Object key) { + throw new UnsupportedOperationException(); + } + + @Override + public void clear() { + throw new UnsupportedOperationException(); + } + } + + /** + * Returns, as an immutable list, the row keys provided when the table was + * constructed, including those that are mapped to null values only. + */ + public ImmutableList<R> rowKeyList() { + return rowList; + } + + /** + * Returns, as an immutable list, the column keys provided when the table was + * constructed, including those that are mapped to null values only. + */ + public ImmutableList<C> columnKeyList() { + return columnList; + } + + /** + * Returns the value corresponding to the specified row and column indices. + * The same value is returned by {@code + * get(rowKeyList().get(rowIndex), columnKeyList().get(columnIndex))}, but + * this method runs more quickly. + * + * @param rowIndex position of the row key in {@link #rowKeyList()} + * @param columnIndex position of the row key in {@link #columnKeyList()} + * @return the value with the specified row and column + * @throws IndexOutOfBoundsException if either index is negative, {@code + * rowIndex} is greater then or equal to the number of allowed row keys, + * or {@code columnIndex} is greater then or equal to the number of + * allowed column keys + */ + public V at(int rowIndex, int columnIndex) { + return array[rowIndex][columnIndex]; + } + + /** + * Associates {@code value} with the specified row and column indices. The + * logic {@code + * put(rowKeyList().get(rowIndex), columnKeyList().get(columnIndex), value)} + * has the same behavior, but this method runs more quickly. + * + * @param rowIndex position of the row key in {@link #rowKeyList()} + * @param columnIndex position of the row key in {@link #columnKeyList()} + * @param value value to store in the table + * @return the previous value with the specified row and column + * @throws IndexOutOfBoundsException if either index is negative, {@code + * rowIndex} is greater then or equal to the number of allowed row keys, + * or {@code columnIndex} is greater then or equal to the number of + * allowed column keys + */ + public V set(int rowIndex, int columnIndex, @Nullable V value) { + V oldValue = array[rowIndex][columnIndex]; + array[rowIndex][columnIndex] = value; + return oldValue; + } + + /** + * Returns a two-dimensional array with the table contents. The row and column + * indices correspond to the positions of the row and column in the iterables + * provided during table construction. If the table lacks a mapping for a + * given row and column, the corresponding array element is null. + * + * <p>Subsequent table changes will not modify the array, and vice versa. + * + * @param valueClass class of values stored in the returned array + */ + public V[][] toArray(Class<V> valueClass) { + // Can change to use varargs in JDK 1.6 if we want + @SuppressWarnings("unchecked") // TODO: safe? + V[][] copy = (V[][]) Array.newInstance( + valueClass, new int[] { rowList.size(), columnList.size() }); + for (int i = 0; i < rowList.size(); i++) { + System.arraycopy(array[i], 0, copy[i], 0, array[i].length); + } + return copy; + } + + /** + * Not supported. Use {@link #eraseAll} instead. + * + * @throws UnsupportedOperationException always + * @deprecated Use {@link #eraseAll} + */ + @Override + @Deprecated public void clear() { + throw new UnsupportedOperationException(); + } + + /** + * Associates the value {@code null} with every pair of allowed row and column + * keys. + */ + public void eraseAll() { + for (V[] row : array) { + Arrays.fill(row, null); + } + } + + /** + * Returns {@code true} if the provided keys are among the keys provided when + * the table was constructed. + */ + @Override + public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) { + return containsRow(rowKey) && containsColumn(columnKey); + } + + /** + * Returns {@code true} if the provided column key is among the column keys + * provided when the table was constructed. + */ + @Override + public boolean containsColumn(@Nullable Object columnKey) { + return columnKeyToIndex.containsKey(columnKey); + } + + /** + * Returns {@code true} if the provided row key is among the row keys + * provided when the table was constructed. + */ + @Override + public boolean containsRow(@Nullable Object rowKey) { + return rowKeyToIndex.containsKey(rowKey); + } + + @Override + public boolean containsValue(@Nullable Object value) { + for (V[] row : array) { + for (V element : row) { + if (Objects.equal(value, element)) { + return true; + } + } + } + return false; + } + + @Override + public V get(@Nullable Object rowKey, @Nullable Object columnKey) { + Integer rowIndex = rowKeyToIndex.get(rowKey); + Integer columnIndex = columnKeyToIndex.get(columnKey); + return (rowIndex == null || columnIndex == null) + ? null : array[rowIndex][columnIndex]; + } + + /** + * Always returns {@code false}. + */ + @Override + public boolean isEmpty() { + return false; + } + + /** + * {@inheritDoc} + * + * @throws IllegalArgumentException if {@code rowKey} is not in {@link + * #rowKeySet()} or {@code columnKey} is not in {@link #columnKeySet()}. + */ + @Override + public V put(R rowKey, C columnKey, @Nullable V value) { + checkNotNull(rowKey); + checkNotNull(columnKey); + Integer rowIndex = rowKeyToIndex.get(rowKey); + checkArgument(rowIndex != null, "Row %s not in %s", rowKey, rowList); + Integer columnIndex = columnKeyToIndex.get(columnKey); + checkArgument(columnIndex != null, + "Column %s not in %s", columnKey, columnList); + return set(rowIndex, columnIndex, value); + } + + /* + * TODO(jlevy): Consider creating a merge() method, similar to putAll() but + * copying non-null values only. + */ + + /** + * {@inheritDoc} + * + * <p>If {@code table} is an {@code ArrayTable}, its null values will be + * stored in this table, possibly replacing values that were previously + * non-null. + * + * @throws NullPointerException if {@code table} has a null key + * @throws IllegalArgumentException if any of the provided table's row keys or + * column keys is not in {@link #rowKeySet()} or {@link #columnKeySet()} + */ + @Override + public void putAll(Table<? extends R, ? extends C, ? extends V> table) { + for (Cell<? extends R, ? extends C, ? extends V> cell : table.cellSet()) { + put(cell.getRowKey(), cell.getColumnKey(), cell.getValue()); + } + } + + /** + * Not supported. Use {@link #erase} instead. + * + * @throws UnsupportedOperationException always + * @deprecated Use {@link #erase} + */ + @Override + @Deprecated public V remove(Object rowKey, Object columnKey) { + throw new UnsupportedOperationException(); + } + + /** + * Associates the value {@code null} with the specified keys, assuming both + * keys are valid. If either key is null or isn't among the keys provided + * during construction, this method has no effect. + * + * <p>This method is equivalent to {@code put(rowKey, columnKey, null)} when + * both provided keys are valid. + * + * @param rowKey row key of mapping to be erased + * @param columnKey column key of mapping to be erased + * @return the value previously associated with the keys, or {@code null} if + * no mapping existed for the keys + */ + public V erase(@Nullable Object rowKey, @Nullable Object columnKey) { + Integer rowIndex = rowKeyToIndex.get(rowKey); + Integer columnIndex = columnKeyToIndex.get(columnKey); + if (rowIndex == null || columnIndex == null) { + return null; + } + return set(rowIndex, columnIndex, null); + } + + // TODO(jlevy): Add eraseRow and eraseColumn methods? + + @Override + public int size() { + return rowList.size() * columnList.size(); + } + + @Override public boolean equals(@Nullable Object obj) { + if (obj instanceof Table) { + Table<?, ?, ?> other = (Table<?, ?, ?>) obj; + return cellSet().equals(other.cellSet()); + } + return false; + } + + @Override public int hashCode() { + return cellSet().hashCode(); + } + + /** + * Returns the string representation {@code rowMap().toString()}. + */ + @Override public String toString() { + return rowMap().toString(); + } + + private transient CellSet cellSet; + + /** + * Returns an unmodifiable set of all row key / column key / value + * triplets. Changes to the table will update the returned set. + * + * <p>The returned set's iterator traverses the mappings with the first row + * key, the mappings with the second row key, and so on. + * + * <p>The value in the returned cells may change if the table subsequently + * changes. + * + * @return set of table cells consisting of row key / column key / value + * triplets + */ + @Override + public Set<Cell<R, C, V>> cellSet() { + CellSet set = cellSet; + return (set == null) ? cellSet = new CellSet() : set; + } + + private class CellSet extends AbstractSet<Cell<R, C, V>> { + + @Override public Iterator<Cell<R, C, V>> iterator() { + return new AbstractIndexedListIterator<Cell<R, C, V>>(size()) { + @Override protected Cell<R, C, V> get(final int index) { + return new Tables.AbstractCell<R, C, V>() { + final int rowIndex = index / columnList.size(); + final int columnIndex = index % columnList.size(); + @Override + public R getRowKey() { + return rowList.get(rowIndex); + } + @Override + public C getColumnKey() { + return columnList.get(columnIndex); + } + @Override + public V getValue() { + return array[rowIndex][columnIndex]; + } + }; + } + }; + } + + @Override public int size() { + return ArrayTable.this.size(); + } + + @Override public boolean contains(Object obj) { + if (obj instanceof Cell) { + Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj; + Integer rowIndex = rowKeyToIndex.get(cell.getRowKey()); + Integer columnIndex = columnKeyToIndex.get(cell.getColumnKey()); + return rowIndex != null + && columnIndex != null + && Objects.equal(array[rowIndex][columnIndex], cell.getValue()); + } + return false; + } + } + + /** + * Returns a view of all mappings that have the given column key. If the + * column key isn't in {@link #columnKeySet()}, an empty immutable map is + * returned. + * + * <p>Otherwise, for each row key in {@link #rowKeySet()}, the returned map + * associates the row key with the corresponding value in the table. Changes + * to the returned map will update the underlying table, and vice versa. + * + * @param columnKey key of column to search for in the table + * @return the corresponding map from row keys to values + */ + @Override + public Map<R, V> column(C columnKey) { + checkNotNull(columnKey); + Integer columnIndex = columnKeyToIndex.get(columnKey); + return (columnIndex == null) + ? ImmutableMap.<R, V>of() : new Column(columnIndex); + } + + private class Column extends ArrayMap<R, V> { + final int columnIndex; + + Column(int columnIndex) { + super(rowKeyToIndex); + this.columnIndex = columnIndex; + } + + @Override + String getKeyRole() { + return "Row"; + } + + @Override + V getValue(int index) { + return at(index, columnIndex); + } + + @Override + V setValue(int index, V newValue) { + return set(index, columnIndex, newValue); + } + } + + /** + * Returns an immutable set of the valid column keys, including those that + * are associated with null values only. + * + * @return immutable set of column keys + */ + @Override + public ImmutableSet<C> columnKeySet() { + return columnKeyToIndex.keySet(); + } + + private transient ColumnMap columnMap; + + @Override + public Map<C, Map<R, V>> columnMap() { + ColumnMap map = columnMap; + return (map == null) ? columnMap = new ColumnMap() : map; + } + + private class ColumnMap extends ArrayMap<C, Map<R, V>> { + private ColumnMap() { + super(columnKeyToIndex); + } + + @Override + String getKeyRole() { + return "Column"; + } + + @Override + Map<R, V> getValue(int index) { + return new Column(index); + } + + @Override + Map<R, V> setValue(int index, Map<R, V> newValue) { + throw new UnsupportedOperationException(); + } + + @Override + public Map<R, V> put(C key, Map<R, V> value) { + throw new UnsupportedOperationException(); + } + } + + /** + * Returns a view of all mappings that have the given row key. If the + * row key isn't in {@link #rowKeySet()}, an empty immutable map is + * returned. + * + * <p>Otherwise, for each column key in {@link #columnKeySet()}, the returned + * map associates the column key with the corresponding value in the + * table. Changes to the returned map will update the underlying table, and + * vice versa. + * + * @param rowKey key of row to search for in the table + * @return the corresponding map from column keys to values + */ + @Override + public Map<C, V> row(R rowKey) { + checkNotNull(rowKey); + Integer rowIndex = rowKeyToIndex.get(rowKey); + return (rowIndex == null) ? ImmutableMap.<C, V>of() : new Row(rowIndex); + } + + private class Row extends ArrayMap<C, V> { + final int rowIndex; + + Row(int rowIndex) { + super(columnKeyToIndex); + this.rowIndex = rowIndex; + } + + @Override + String getKeyRole() { + return "Column"; + } + + @Override + V getValue(int index) { + return at(rowIndex, index); + } + + @Override + V setValue(int index, V newValue) { + return set(rowIndex, index, newValue); + } + } + + /** + * Returns an immutable set of the valid row keys, including those that are + * associated with null values only. + * + * @return immutable set of row keys + */ + @Override + public ImmutableSet<R> rowKeySet() { + return rowKeyToIndex.keySet(); + } + + private transient RowMap rowMap; + + @Override + public Map<R, Map<C, V>> rowMap() { + RowMap map = rowMap; + return (map == null) ? rowMap = new RowMap() : map; + } + + private class RowMap extends ArrayMap<R, Map<C, V>> { + private RowMap() { + super(rowKeyToIndex); + } + + @Override + String getKeyRole() { + return "Row"; + } + + @Override + Map<C, V> getValue(int index) { + return new Row(index); + } + + @Override + Map<C, V> setValue(int index, Map<C, V> newValue) { + throw new UnsupportedOperationException(); + } + + @Override + public Map<C, V> put(R key, Map<C, V> value) { + throw new UnsupportedOperationException(); + } + } + + private transient Collection<V> values; + + /** + * Returns an unmodifiable collection of all values, which may contain + * duplicates. Changes to the table will update the returned collection. + * + * <p>The returned collection's iterator traverses the values of the first row + * key, the values of the second row key, and so on. + * + * @return collection of values + */ + @Override + public Collection<V> values() { + Collection<V> v = values; + return (v == null) ? values = new Values() : v; + } + + private class Values extends AbstractCollection<V> { + @Override public Iterator<V> iterator() { + return new TransformedIterator<Cell<R, C, V>, V>(cellSet().iterator()) { + @Override + V transform(Cell<R, C, V> cell) { + return cell.getValue(); + } + }; + } + + @Override public int size() { + return ArrayTable.this.size(); + } + } + + private static final long serialVersionUID = 0; +} |