1/* 2 * Copyright (C) 2009 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15package com.google.common.collect; 16 17import static com.google.common.base.Preconditions.checkNotNull; 18 19import com.google.common.annotations.GwtCompatible; 20 21import java.util.Collections; 22import java.util.Comparator; 23import java.util.List; 24 25import javax.annotation.Nullable; 26 27/** 28 * An implementation of {@link ImmutableTable} holding an arbitrary number of 29 * cells. 30 * 31 * @author Gregory Kick 32 */ 33@GwtCompatible 34abstract class RegularImmutableTable<R, C, V> extends ImmutableTable<R, C, V> { 35 RegularImmutableTable() {} 36 37 abstract Cell<R, C, V> getCell(int iterationIndex); 38 39 @Override 40 final ImmutableSet<Cell<R, C, V>> createCellSet() { 41 return isEmpty() ? ImmutableSet.<Cell<R, C, V>>of() : new CellSet(); 42 } 43 44 private final class CellSet extends ImmutableSet<Cell<R, C, V>> { 45 @Override 46 public int size() { 47 return RegularImmutableTable.this.size(); 48 } 49 50 @Override 51 public UnmodifiableIterator<Cell<R, C, V>> iterator() { 52 return asList().iterator(); 53 } 54 55 @Override 56 ImmutableList<Cell<R, C, V>> createAsList() { 57 return new ImmutableAsList<Cell<R, C, V>>() { 58 @Override 59 public Cell<R, C, V> get(int index) { 60 return getCell(index); 61 } 62 63 @Override 64 ImmutableCollection<Cell<R, C, V>> delegateCollection() { 65 return CellSet.this; 66 } 67 }; 68 } 69 70 @Override 71 public boolean contains(@Nullable Object object) { 72 if (object instanceof Cell) { 73 Cell<?, ?, ?> cell = (Cell<?, ?, ?>) object; 74 Object value = get(cell.getRowKey(), cell.getColumnKey()); 75 return value != null && value.equals(cell.getValue()); 76 } 77 return false; 78 } 79 80 @Override 81 boolean isPartialView() { 82 return false; 83 } 84 } 85 86 abstract V getValue(int iterationIndex); 87 88 @Override 89 final ImmutableCollection<V> createValues() { 90 return isEmpty() ? ImmutableList.<V>of() : new Values(); 91 } 92 93 private final class Values extends ImmutableList<V> { 94 @Override 95 public int size() { 96 return RegularImmutableTable.this.size(); 97 } 98 99 @Override 100 public V get(int index) { 101 return getValue(index); 102 } 103 104 @Override 105 boolean isPartialView() { 106 return true; 107 } 108 } 109 110 static <R, C, V> RegularImmutableTable<R, C, V> forCells( 111 List<Cell<R, C, V>> cells, 112 @Nullable final Comparator<? super R> rowComparator, 113 @Nullable final Comparator<? super C> columnComparator) { 114 checkNotNull(cells); 115 if (rowComparator != null || columnComparator != null) { 116 /* 117 * This sorting logic leads to a cellSet() ordering that may not be expected and that isn't 118 * documented in the Javadoc. If a row Comparator is provided, cellSet() iterates across the 119 * columns in the first row, the columns in the second row, etc. If a column Comparator is 120 * provided but a row Comparator isn't, cellSet() iterates across the rows in the first 121 * column, the rows in the second column, etc. 122 */ 123 Comparator<Cell<R, C, V>> comparator = new Comparator<Cell<R, C, V>>() { 124 @Override public int compare(Cell<R, C, V> cell1, Cell<R, C, V> cell2) { 125 int rowCompare = (rowComparator == null) ? 0 126 : rowComparator.compare(cell1.getRowKey(), cell2.getRowKey()); 127 if (rowCompare != 0) { 128 return rowCompare; 129 } 130 return (columnComparator == null) ? 0 131 : columnComparator.compare(cell1.getColumnKey(), cell2.getColumnKey()); 132 } 133 }; 134 Collections.sort(cells, comparator); 135 } 136 return forCellsInternal(cells, rowComparator, columnComparator); 137 } 138 139 static <R, C, V> RegularImmutableTable<R, C, V> forCells( 140 Iterable<Cell<R, C, V>> cells) { 141 return forCellsInternal(cells, null, null); 142 } 143 144 /** 145 * A factory that chooses the most space-efficient representation of the 146 * table. 147 */ 148 private static final <R, C, V> RegularImmutableTable<R, C, V> 149 forCellsInternal(Iterable<Cell<R, C, V>> cells, 150 @Nullable Comparator<? super R> rowComparator, 151 @Nullable Comparator<? super C> columnComparator) { 152 ImmutableSet.Builder<R> rowSpaceBuilder = ImmutableSet.builder(); 153 ImmutableSet.Builder<C> columnSpaceBuilder = ImmutableSet.builder(); 154 ImmutableList<Cell<R, C, V>> cellList = ImmutableList.copyOf(cells); 155 for (Cell<R, C, V> cell : cellList) { 156 rowSpaceBuilder.add(cell.getRowKey()); 157 columnSpaceBuilder.add(cell.getColumnKey()); 158 } 159 160 ImmutableSet<R> rowSpace = rowSpaceBuilder.build(); 161 if (rowComparator != null) { 162 List<R> rowList = Lists.newArrayList(rowSpace); 163 Collections.sort(rowList, rowComparator); 164 rowSpace = ImmutableSet.copyOf(rowList); 165 } 166 ImmutableSet<C> columnSpace = columnSpaceBuilder.build(); 167 if (columnComparator != null) { 168 List<C> columnList = Lists.newArrayList(columnSpace); 169 Collections.sort(columnList, columnComparator); 170 columnSpace = ImmutableSet.copyOf(columnList); 171 } 172 173 // use a dense table if more than half of the cells have values 174 // TODO(gak): tune this condition based on empirical evidence 175 return (cellList.size() > (((long) rowSpace.size() * columnSpace.size()) / 2)) ? 176 new DenseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace) : 177 new SparseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace); 178 } 179} 180