/* * 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.checkNotNull; import com.google.common.annotations.GwtCompatible; import java.util.Collections; import java.util.Comparator; import java.util.List; import javax.annotation.Nullable; /** * An implementation of {@link ImmutableTable} holding an arbitrary number of * cells. * * @author Gregory Kick */ @GwtCompatible abstract class RegularImmutableTable extends ImmutableTable { RegularImmutableTable() {} abstract Cell getCell(int iterationIndex); @Override final ImmutableSet> createCellSet() { return isEmpty() ? ImmutableSet.>of() : new CellSet(); } private final class CellSet extends ImmutableSet> { @Override public int size() { return RegularImmutableTable.this.size(); } @Override public UnmodifiableIterator> iterator() { return asList().iterator(); } @Override ImmutableList> createAsList() { return new ImmutableAsList>() { @Override public Cell get(int index) { return getCell(index); } @Override ImmutableCollection> delegateCollection() { return CellSet.this; } }; } @Override public boolean contains(@Nullable Object object) { if (object instanceof Cell) { Cell cell = (Cell) object; Object value = get(cell.getRowKey(), cell.getColumnKey()); return value != null && value.equals(cell.getValue()); } return false; } @Override boolean isPartialView() { return false; } } abstract V getValue(int iterationIndex); @Override final ImmutableCollection createValues() { return isEmpty() ? ImmutableList.of() : new Values(); } private final class Values extends ImmutableList { @Override public int size() { return RegularImmutableTable.this.size(); } @Override public V get(int index) { return getValue(index); } @Override boolean isPartialView() { return true; } } static 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 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 rowSpaceBuilder = ImmutableSet.builder(); ImmutableSet.Builder columnSpaceBuilder = ImmutableSet.builder(); ImmutableList> cellList = ImmutableList.copyOf(cells); for (Cell cell : cellList) { rowSpaceBuilder.add(cell.getRowKey()); columnSpaceBuilder.add(cell.getColumnKey()); } 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 (cellList.size() > (((long) rowSpace.size() * columnSpace.size()) / 2)) ? new DenseImmutableTable(cellList, rowSpace, columnSpace) : new SparseImmutableTable(cellList, rowSpace, columnSpace); } }