/* * 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.GwtCompatible; import com.google.common.annotations.VisibleForTesting; import com.google.common.base.Function; import com.google.common.base.Objects; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Map; import javax.annotation.Nullable; import javax.annotation.concurrent.Immutable; /** * An implementation of {@link ImmutableTable} holding an arbitrary number of * cells. * * @author Gregory Kick */ @GwtCompatible abstract class RegularImmutableTable extends ImmutableTable { // TODO(user): split DenseImmutableTable, SparseImmutableTable into their own classes private final ImmutableSet> cellSet; private RegularImmutableTable(ImmutableSet> cellSet) { this.cellSet = cellSet; } private static final Function, Object> GET_VALUE_FUNCTION = new Function, Object>() { @Override public Object apply(Cell from) { return from.getValue(); } }; @SuppressWarnings("unchecked") private Function, V> getValueFunction() { return (Function) GET_VALUE_FUNCTION; } @Nullable private transient volatile ImmutableList valueList; @Override public final ImmutableCollection values() { ImmutableList result = valueList; if (result == null) { valueList = result = ImmutableList.copyOf( Iterables.transform(cellSet(), getValueFunction())); } return result; } @Override public final int size() { return cellSet().size(); } @Override public final boolean containsValue(@Nullable Object value) { return values().contains(value); } @Override public final boolean isEmpty() { return false; } @Override public final ImmutableSet> cellSet() { return cellSet; } static final RegularImmutableTable forCells( List> cells, @Nullable final Comparator rowComparator, @Nullable final Comparator columnComparator) { checkNotNull(cells); if (rowComparator != null || columnComparator != null) { /* * This sorting logic leads to a cellSet() ordering that may not be * expected and that isn't documented in the Javadoc. If a row Comparator * is provided, cellSet() iterates across the columns in the first row, * the columns in the second row, etc. If a column Comparator is provided * but a row Comparator isn't, cellSet() iterates across the rows in the * first column, the rows in the second column, etc. */ Comparator> comparator = new Comparator>() { @Override public int compare(Cell cell1, Cell cell2) { int rowCompare = (rowComparator == null) ? 0 : rowComparator.compare(cell1.getRowKey(), cell2.getRowKey()); if (rowCompare != 0) { return rowCompare; } return (columnComparator == null) ? 0 : columnComparator.compare( cell1.getColumnKey(), cell2.getColumnKey()); } }; Collections.sort(cells, comparator); } return forCellsInternal(cells, rowComparator, columnComparator); } static final RegularImmutableTable forCells( Iterable> cells) { return forCellsInternal(cells, null, null); } /** * A factory that chooses the most space-efficient representation of the * table. */ private static final RegularImmutableTable forCellsInternal(Iterable> cells, @Nullable Comparator rowComparator, @Nullable Comparator columnComparator) { ImmutableSet.Builder> cellSetBuilder = ImmutableSet.builder(); ImmutableSet.Builder rowSpaceBuilder = ImmutableSet.builder(); ImmutableSet.Builder columnSpaceBuilder = ImmutableSet.builder(); for (Cell cell : cells) { cellSetBuilder.add(cell); rowSpaceBuilder.add(cell.getRowKey()); columnSpaceBuilder.add(cell.getColumnKey()); } ImmutableSet> cellSet = cellSetBuilder.build(); ImmutableSet rowSpace = rowSpaceBuilder.build(); if (rowComparator != null) { List rowList = Lists.newArrayList(rowSpace); Collections.sort(rowList, rowComparator); rowSpace = ImmutableSet.copyOf(rowList); } ImmutableSet columnSpace = columnSpaceBuilder.build(); if (columnComparator != null) { List columnList = Lists.newArrayList(columnSpace); Collections.sort(columnList, columnComparator); columnSpace = ImmutableSet.copyOf(columnList); } // use a dense table if more than half of the cells have values // TODO(gak): tune this condition based on empirical evidence return (cellSet.size() > ((rowSpace.size() * columnSpace.size()) / 2 )) ? new DenseImmutableTable(cellSet, rowSpace, columnSpace) : new SparseImmutableTable(cellSet, rowSpace, columnSpace); } /** * A {@code RegularImmutableTable} optimized for sparse data. */ @Immutable @VisibleForTesting static final class SparseImmutableTable extends RegularImmutableTable { private final ImmutableMap> rowMap; private final ImmutableMap> columnMap; /** * Creates a {@link Map} over the key space with * {@link ImmutableMap.Builder}s ready for values. */ private static final Map> makeIndexBuilder(ImmutableSet keySpace) { Map> indexBuilder = Maps.newLinkedHashMap(); for (A key : keySpace) { indexBuilder.put(key, ImmutableMap.builder()); } return indexBuilder; } /** * Builds the value maps of the index and creates an immutable copy of the * map. */ private static final ImmutableMap> buildIndex( Map> indexBuilder) { return ImmutableMap.copyOf(Maps.transformValues(indexBuilder, new Function, Map>() { @Override public Map apply(ImmutableMap.Builder from) { return from.build(); } })); } SparseImmutableTable(ImmutableSet> cellSet, ImmutableSet rowSpace, ImmutableSet columnSpace) { super(cellSet); Map> rowIndexBuilder = makeIndexBuilder(rowSpace); Map> columnIndexBuilder = makeIndexBuilder(columnSpace); for (Cell cell : cellSet) { R rowKey = cell.getRowKey(); C columnKey = cell.getColumnKey(); V value = cell.getValue(); rowIndexBuilder.get(rowKey).put(columnKey, value); columnIndexBuilder.get(columnKey).put(rowKey, value); } this.rowMap = buildIndex(rowIndexBuilder); this.columnMap = buildIndex(columnIndexBuilder); } @Override public ImmutableMap column(C columnKey) { checkNotNull(columnKey); // value maps are guaranteed to be immutable maps return Objects.firstNonNull((ImmutableMap) columnMap.get(columnKey), ImmutableMap.of()); } @Override public ImmutableSet columnKeySet() { return columnMap.keySet(); } @Override public ImmutableMap> columnMap() { return columnMap; } @Override public ImmutableMap row(R rowKey) { checkNotNull(rowKey); // value maps are guaranteed to be immutable maps return Objects.firstNonNull((ImmutableMap) rowMap.get(rowKey), ImmutableMap.of()); } @Override public ImmutableSet rowKeySet() { return rowMap.keySet(); } @Override public ImmutableMap> rowMap() { return rowMap; } @Override public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) { Map row = rowMap.get(rowKey); return (row != null) && row.containsKey(columnKey); } @Override public boolean containsColumn(@Nullable Object columnKey) { return columnMap.containsKey(columnKey); } @Override public boolean containsRow(@Nullable Object rowKey) { return rowMap.containsKey(rowKey); } @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) { Map row = rowMap.get(rowKey); return (row == null) ? null : row.get(columnKey); } } /** * An immutable map implementation backed by an indexed nullable array, used in * DenseImmutableTable. */ private abstract static class ImmutableArrayMap extends ImmutableMap { private final int size; ImmutableArrayMap(int size) { this.size = size; } abstract ImmutableMap keyToIndex(); // True if getValue never returns null. private boolean isFull() { return size == keyToIndex().size(); } K getKey(int index) { return keyToIndex().keySet().asList().get(index); } @Nullable abstract V getValue(int keyIndex); @Override ImmutableSet createKeySet() { return isFull() ? keyToIndex().keySet() : super.createKeySet(); } @Override public int size() { return size; } @Override public V get(@Nullable Object key) { Integer keyIndex = keyToIndex().get(key); return (keyIndex == null) ? null : getValue(keyIndex); } @Override ImmutableSet> createEntrySet() { if (isFull()) { return new ImmutableMapEntrySet() { @Override ImmutableMap map() { return ImmutableArrayMap.this; } @Override public UnmodifiableIterator> iterator() { return new AbstractIndexedListIterator>(size()) { @Override protected Entry get(int index) { return Maps.immutableEntry(getKey(index), getValue(index)); } }; } }; } else { return new ImmutableMapEntrySet() { @Override ImmutableMap map() { return ImmutableArrayMap.this; } @Override public UnmodifiableIterator> iterator() { return new AbstractIterator>() { private int index = -1; private final int maxIndex = keyToIndex().size(); @Override protected Entry computeNext() { for (index++; index < maxIndex; index++) { V value = getValue(index); if (value != null) { return Maps.immutableEntry(getKey(index), value); } } return endOfData(); } }; } }; } } } /** * A {@code RegularImmutableTable} optimized for dense data. */ @Immutable @VisibleForTesting static final class DenseImmutableTable extends RegularImmutableTable { private final ImmutableMap rowKeyToIndex; private final ImmutableMap columnKeyToIndex; private final ImmutableMap> rowMap; private final ImmutableMap> columnMap; private final int[] rowCounts; private final int[] columnCounts; private final V[][] values; private static ImmutableMap makeIndex( ImmutableSet set) { ImmutableMap.Builder indexBuilder = ImmutableMap.builder(); int i = 0; for (E key : set) { indexBuilder.put(key, i); i++; } return indexBuilder.build(); } DenseImmutableTable(ImmutableSet> cellSet, ImmutableSet rowSpace, ImmutableSet columnSpace) { super(cellSet); @SuppressWarnings("unchecked") V[][] array = (V[][]) new Object[rowSpace.size()][columnSpace.size()]; this.values = array; this.rowKeyToIndex = makeIndex(rowSpace); this.columnKeyToIndex = makeIndex(columnSpace); rowCounts = new int[rowKeyToIndex.size()]; columnCounts = new int[columnKeyToIndex.size()]; for (Cell cell : cellSet) { R rowKey = cell.getRowKey(); C columnKey = cell.getColumnKey(); int rowIndex = rowKeyToIndex.get(rowKey); int columnIndex = columnKeyToIndex.get(columnKey); V existingValue = values[rowIndex][columnIndex]; checkArgument(existingValue == null, "duplicate key: (%s, %s)", rowKey, columnKey); values[rowIndex][columnIndex] = cell.getValue(); rowCounts[rowIndex]++; columnCounts[columnIndex]++; } this.rowMap = new RowMap(); this.columnMap = new ColumnMap(); } private final class Row extends ImmutableArrayMap { private final int rowIndex; Row(int rowIndex) { super(rowCounts[rowIndex]); this.rowIndex = rowIndex; } @Override ImmutableMap keyToIndex() { return columnKeyToIndex; } @Override V getValue(int keyIndex) { return values[rowIndex][keyIndex]; } @Override boolean isPartialView() { return true; } } private final class Column extends ImmutableArrayMap { private final int columnIndex; Column(int columnIndex) { super(columnCounts[columnIndex]); this.columnIndex = columnIndex; } @Override ImmutableMap keyToIndex() { return rowKeyToIndex; } @Override V getValue(int keyIndex) { return values[keyIndex][columnIndex]; } @Override boolean isPartialView() { return true; } } private final class RowMap extends ImmutableArrayMap> { private RowMap() { super(rowCounts.length); } @Override ImmutableMap keyToIndex() { return rowKeyToIndex; } @Override Map getValue(int keyIndex) { return new Row(keyIndex); } @Override boolean isPartialView() { return false; } } private final class ColumnMap extends ImmutableArrayMap> { private ColumnMap() { super(columnCounts.length); } @Override ImmutableMap keyToIndex() { return columnKeyToIndex; } @Override Map getValue(int keyIndex) { return new Column(keyIndex); } @Override boolean isPartialView() { return false; } } @Override public ImmutableMap column(C columnKey) { Integer columnIndex = columnKeyToIndex.get(checkNotNull(columnKey)); if (columnIndex == null) { return ImmutableMap.of(); } else { return new Column(columnIndex); } } @Override public ImmutableSet columnKeySet() { return columnKeyToIndex.keySet(); } @Override public ImmutableMap> columnMap() { return columnMap; } @Override public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) { return (get(rowKey, columnKey) != null); } @Override public boolean containsColumn(@Nullable Object columnKey) { return columnKeyToIndex.containsKey(columnKey); } @Override public boolean containsRow(@Nullable Object rowKey) { return rowKeyToIndex.containsKey(rowKey); } @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 : values[rowIndex][columnIndex]; } @Override public ImmutableMap row(R rowKey) { checkNotNull(rowKey); Integer rowIndex = rowKeyToIndex.get(rowKey); if (rowIndex == null) { return ImmutableMap.of(); } else { return new Row(rowIndex); } } @Override public ImmutableSet rowKeySet() { return rowKeyToIndex.keySet(); } @Override public ImmutableMap> rowMap() { return rowMap; } } }