1/*
2 * Copyright (C) 2009 Google Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkArgument;
20import static com.google.common.base.Preconditions.checkNotNull;
21
22import com.google.common.annotations.GwtCompatible;
23import com.google.common.annotations.VisibleForTesting;
24import com.google.common.base.Function;
25import com.google.common.base.Objects;
26
27import java.util.Collections;
28import java.util.Comparator;
29import java.util.List;
30import java.util.Map;
31
32import javax.annotation.Nullable;
33import javax.annotation.concurrent.Immutable;
34
35/**
36 * An implementation of {@link ImmutableTable} holding an arbitrary number of
37 * cells.
38 *
39 * @author gak@google.com (Gregory Kick)
40 */
41@GwtCompatible
42abstract class RegularImmutableTable<R, C, V> extends ImmutableTable<R, C, V> {
43  private final ImmutableSet<Cell<R, C, V>> cellSet;
44
45  private RegularImmutableTable(ImmutableSet<Cell<R, C, V>> cellSet) {
46    this.cellSet = cellSet;
47  }
48
49  private static final Function<Cell<Object, Object, Object>, Object>
50      GET_VALUE_FUNCTION =
51          new Function<Cell<Object, Object, Object>, Object>() {
52            @Override public Object apply(Cell<Object, Object, Object> from) {
53              return from.getValue();
54            }
55          };
56
57  @SuppressWarnings("unchecked")
58  private Function<Cell<R, C, V>, V> getValueFunction() {
59    return (Function) GET_VALUE_FUNCTION;
60  }
61
62  @Nullable private transient volatile ImmutableList<V> valueList;
63
64  @Override public final ImmutableCollection<V> values() {
65    ImmutableList<V> result = valueList;
66    if (result == null) {
67      valueList = result = ImmutableList.copyOf(
68          Iterables.transform(cellSet(), getValueFunction()));
69    }
70    return result;
71  }
72
73  @Override public final int size() {
74    return cellSet().size();
75  }
76
77  @Override public final boolean containsValue(@Nullable Object value) {
78    return values().contains(value);
79  }
80
81  @Override public final boolean isEmpty() {
82    return false;
83  }
84
85  @Override public final ImmutableSet<Cell<R, C, V>> cellSet() {
86    return cellSet;
87  }
88
89  static final <R, C, V> RegularImmutableTable<R, C, V> forCells(
90      List<Cell<R, C, V>> cells,
91      @Nullable final Comparator<? super R> rowComparator,
92      @Nullable final Comparator<? super C> columnComparator) {
93    checkNotNull(cells);
94    if (rowComparator != null || columnComparator != null) {
95      /*
96       * This sorting logic leads to a cellSet() ordering that may not be
97       * expected and that isn't documented in the Javadoc. If a row Comparator
98       * is provided, cellSet() iterates across the columns in the first row,
99       * the columns in the second row, etc. If a column Comparator is provided
100       * but a row Comparator isn't, cellSet() iterates across the rows in the
101       * first column, the rows in the second column, etc.
102       */
103      Comparator<Cell<R, C, V>> comparator = new Comparator<Cell<R, C, V>>() {
104        @Override public int compare(Cell<R, C, V> cell1, Cell<R, C, V> cell2) {
105          int rowCompare = (rowComparator == null) ? 0
106            : rowComparator.compare(cell1.getRowKey(), cell2.getRowKey());
107          if (rowCompare != 0) {
108            return rowCompare;
109          }
110          return (columnComparator == null) ? 0
111              : columnComparator.compare(
112                  cell1.getColumnKey(), cell2.getColumnKey());
113        }
114      };
115      Collections.sort(cells, comparator);
116    }
117    return forCellsInternal(cells, rowComparator, columnComparator);
118  }
119
120  static final <R, C, V> RegularImmutableTable<R, C, V> forCells(
121      Iterable<Cell<R, C, V>> cells) {
122    return forCellsInternal(cells, null, null);
123  }
124
125  /**
126   * A factory that chooses the most space-efficient representation of the
127   * table.
128   */
129  private static final <R, C, V> RegularImmutableTable<R, C, V>
130      forCellsInternal(Iterable<Cell<R, C, V>> cells,
131          @Nullable Comparator<? super R> rowComparator,
132          @Nullable Comparator<? super C> columnComparator) {
133    ImmutableSet.Builder<Cell<R, C, V>> cellSetBuilder = ImmutableSet.builder();
134    ImmutableSet.Builder<R> rowSpaceBuilder = ImmutableSet.builder();
135    ImmutableSet.Builder<C> columnSpaceBuilder = ImmutableSet.builder();
136    for (Cell<R, C, V> cell : cells) {
137      cellSetBuilder.add(cell);
138      rowSpaceBuilder.add(cell.getRowKey());
139      columnSpaceBuilder.add(cell.getColumnKey());
140    }
141    ImmutableSet<Cell<R, C, V>> cellSet = cellSetBuilder.build();
142
143    ImmutableSet<R> rowSpace = rowSpaceBuilder.build();
144    if (rowComparator != null) {
145      List<R> rowList = Lists.newArrayList(rowSpace);
146      Collections.sort(rowList, rowComparator);
147      rowSpace = ImmutableSet.copyOf(rowList);
148    }
149    ImmutableSet<C> columnSpace = columnSpaceBuilder.build();
150    if (columnComparator != null) {
151      List<C> columnList = Lists.newArrayList(columnSpace);
152      Collections.sort(columnList, columnComparator);
153      columnSpace = ImmutableSet.copyOf(columnList);
154    }
155
156    // use a dense table if more than half of the cells have values
157    // TODO(gak): tune this condition based on empirical evidence
158    return (cellSet.size() > ((rowSpace.size() * columnSpace.size()) / 2 )) ?
159        new DenseImmutableTable<R, C, V>(cellSet, rowSpace, columnSpace) :
160        new SparseImmutableTable<R, C, V>(cellSet, rowSpace, columnSpace);
161  }
162
163  /**
164   * A {@code RegularImmutableTable} optimized for sparse data.
165   */
166  @Immutable
167  @VisibleForTesting
168  static final class SparseImmutableTable<R, C, V>
169      extends RegularImmutableTable<R, C, V> {
170
171    private final ImmutableMap<R, Map<C, V>> rowMap;
172    private final ImmutableMap<C, Map<R, V>> columnMap;
173
174    /**
175     * Creates a {@link Map} over the key space with
176     * {@link ImmutableMap.Builder}s ready for values.
177     */
178    private static final <A, B, V> Map<A, ImmutableMap.Builder<B, V>>
179        makeIndexBuilder(ImmutableSet<A> keySpace) {
180      Map<A, ImmutableMap.Builder<B, V>> indexBuilder = Maps.newLinkedHashMap();
181      for (A key : keySpace) {
182        indexBuilder.put(key, ImmutableMap.<B, V>builder());
183      }
184      return indexBuilder;
185    }
186
187    /**
188     * Builds the value maps of the index and creates an immutable copy of the
189     * map.
190     */
191    private static final <A, B, V> ImmutableMap<A, Map<B, V>> buildIndex(
192        Map<A, ImmutableMap.Builder<B, V>> indexBuilder) {
193      return ImmutableMap.copyOf(Maps.transformValues(indexBuilder,
194          new Function<ImmutableMap.Builder<B, V>, Map<B, V>>() {
195            @Override public Map<B, V> apply(ImmutableMap.Builder<B, V> from) {
196              return from.build();
197            }
198          }));
199    }
200
201    SparseImmutableTable(ImmutableSet<Cell<R, C, V>> cellSet,
202        ImmutableSet<R> rowSpace, ImmutableSet<C> columnSpace) {
203      super(cellSet);
204      Map<R, ImmutableMap.Builder<C, V>> rowIndexBuilder
205          = makeIndexBuilder(rowSpace);
206      Map<C, ImmutableMap.Builder<R, V>> columnIndexBuilder
207          = makeIndexBuilder(columnSpace);
208      for (Cell<R, C, V> cell : cellSet) {
209        R rowKey = cell.getRowKey();
210        C columnKey = cell.getColumnKey();
211        V value = cell.getValue();
212        rowIndexBuilder.get(rowKey).put(columnKey, value);
213        columnIndexBuilder.get(columnKey).put(rowKey, value);
214      }
215      this.rowMap = buildIndex(rowIndexBuilder);
216      this.columnMap = buildIndex(columnIndexBuilder);
217    }
218
219    @Override public ImmutableMap<R, V> column(C columnKey) {
220      checkNotNull(columnKey);
221      // value maps are guaranteed to be immutable maps
222      return Objects.firstNonNull((ImmutableMap<R, V>) columnMap.get(columnKey),
223          ImmutableMap.<R, V>of());
224    }
225
226    @Override public ImmutableSet<C> columnKeySet() {
227      return columnMap.keySet();
228    }
229
230    @Override public ImmutableMap<C, Map<R, V>> columnMap() {
231      return columnMap;
232    }
233
234    @Override public ImmutableMap<C, V> row(R rowKey) {
235      checkNotNull(rowKey);
236      // value maps are guaranteed to be immutable maps
237      return Objects.firstNonNull((ImmutableMap<C, V>) rowMap.get(rowKey),
238          ImmutableMap.<C, V>of());
239    }
240
241    @Override public ImmutableSet<R> rowKeySet() {
242      return rowMap.keySet();
243    }
244
245    @Override public ImmutableMap<R, Map<C, V>> rowMap() {
246      return rowMap;
247    }
248
249    @Override public boolean contains(@Nullable Object rowKey,
250        @Nullable Object columnKey) {
251      Map<C, V> row = rowMap.get(rowKey);
252      return (row != null) && row.containsKey(columnKey);
253    }
254
255    @Override public boolean containsColumn(@Nullable Object columnKey) {
256      return columnMap.containsKey(columnKey);
257    }
258
259    @Override public boolean containsRow(@Nullable Object rowKey) {
260      return rowMap.containsKey(rowKey);
261    }
262
263    @Override public V get(@Nullable Object rowKey,
264        @Nullable Object columnKey) {
265      Map<C, V> row = rowMap.get(rowKey);
266      return (row == null) ? null : row.get(columnKey);
267    }
268  }
269
270  /**
271   * A {@code RegularImmutableTable} optimized for dense data.
272   */
273  @Immutable @VisibleForTesting
274  static final class DenseImmutableTable<R, C, V>
275      extends RegularImmutableTable<R, C, V> {
276
277    private final ImmutableBiMap<R, Integer> rowKeyToIndex;
278    private final ImmutableBiMap<C, Integer> columnKeyToIndex;
279    private final V[][] values;
280
281    private static <E> ImmutableBiMap<E, Integer> makeIndex(
282        ImmutableSet<E> set) {
283      ImmutableBiMap.Builder<E, Integer> indexBuilder =
284          ImmutableBiMap.builder();
285      int i = 0;
286      for (E key : set) {
287        indexBuilder.put(key, i);
288        i++;
289      }
290      return indexBuilder.build();
291    }
292
293    DenseImmutableTable(ImmutableSet<Cell<R, C, V>> cellSet,
294        ImmutableSet<R> rowSpace, ImmutableSet<C> columnSpace) {
295      super(cellSet);
296      @SuppressWarnings("unchecked")
297      V[][] array = (V[][]) new Object[rowSpace.size()][columnSpace.size()];
298      this.values = array;
299      this.rowKeyToIndex = makeIndex(rowSpace);
300      this.columnKeyToIndex = makeIndex(columnSpace);
301      for (Cell<R, C, V> cell : cellSet) {
302        R rowKey = cell.getRowKey();
303        C columnKey = cell.getColumnKey();
304        int rowIndex = rowKeyToIndex.get(rowKey);
305        int columnIndex = columnKeyToIndex.get(columnKey);
306        V existingValue = values[rowIndex][columnIndex];
307        checkArgument(existingValue == null, "duplicate key: (%s, %s)", rowKey,
308            columnKey);
309        values[rowIndex][columnIndex] = cell.getValue();
310      }
311    }
312
313    @Override public ImmutableMap<R, V> column(C columnKey) {
314      checkNotNull(columnKey);
315      Integer columnIndexInteger = columnKeyToIndex.get(columnKey);
316      if (columnIndexInteger == null) {
317        return ImmutableMap.of();
318      } else {
319        // unbox only once
320        int columnIndex = columnIndexInteger;
321        ImmutableMap.Builder<R, V> columnBuilder = ImmutableMap.builder();
322        for (int i = 0; i < values.length; i++) {
323          V value = values[i][columnIndex];
324          if (value != null) {
325            columnBuilder.put(rowKeyToIndex.inverse().get(i), value);
326          }
327        }
328        return columnBuilder.build();
329      }
330    }
331
332    @Override public ImmutableSet<C> columnKeySet() {
333      return columnKeyToIndex.keySet();
334    }
335
336    private transient volatile ImmutableMap<C, Map<R, V>> columnMap;
337
338    private ImmutableMap<C, Map<R, V>> makeColumnMap() {
339      ImmutableMap.Builder<C, Map<R, V>> columnMapBuilder =
340          ImmutableMap.builder();
341      for (int c = 0; c < columnKeyToIndex.size(); c++) {
342        ImmutableMap.Builder<R, V> rowMapBuilder = ImmutableMap.builder();
343        for (int r = 0; r < rowKeyToIndex.size(); r++) {
344          V value = values[r][c];
345          if (value != null) {
346            rowMapBuilder.put(rowKeyToIndex.inverse().get(r), value);
347          }
348        }
349        columnMapBuilder.put(columnKeyToIndex.inverse().get(c),
350            rowMapBuilder.build());
351      }
352      return columnMapBuilder.build();
353    }
354
355    @Override public ImmutableMap<C, Map<R, V>> columnMap() {
356      ImmutableMap<C, Map<R, V>> result = columnMap;
357      if (result == null) {
358        columnMap = result = makeColumnMap();
359      }
360      return result;
361    }
362
363    @Override public boolean contains(@Nullable Object rowKey,
364        @Nullable Object columnKey) {
365      return (get(rowKey, columnKey) != null);
366    }
367
368    @Override public boolean containsColumn(@Nullable Object columnKey) {
369      return columnKeyToIndex.containsKey(columnKey);
370    }
371
372    @Override public boolean containsRow(@Nullable Object rowKey) {
373      return rowKeyToIndex.containsKey(rowKey);
374    }
375
376    @Override public V get(@Nullable Object rowKey,
377        @Nullable Object columnKey) {
378      Integer rowIndex = rowKeyToIndex.get(rowKey);
379      Integer columnIndex = columnKeyToIndex.get(columnKey);
380      return ((rowIndex == null) || (columnIndex == null)) ? null
381          : values[rowIndex][columnIndex];
382    }
383
384    @Override public ImmutableMap<C, V> row(R rowKey) {
385      checkNotNull(rowKey);
386      Integer rowIndex = rowKeyToIndex.get(rowKey);
387      if (rowIndex == null) {
388        return ImmutableMap.of();
389      } else {
390        ImmutableMap.Builder<C, V> rowBuilder = ImmutableMap.builder();
391        V[] row = values[rowIndex];
392        for (int r = 0; r < row.length; r++) {
393          V value = row[r];
394          if (value != null) {
395            rowBuilder.put(columnKeyToIndex.inverse().get(r), value);
396          }
397        }
398        return rowBuilder.build();
399      }
400    }
401
402    @Override public ImmutableSet<R> rowKeySet() {
403      return rowKeyToIndex.keySet();
404    }
405
406    private transient volatile ImmutableMap<R, Map<C, V>> rowMap;
407
408    private ImmutableMap<R, Map<C, V>> makeRowMap() {
409      ImmutableMap.Builder<R, Map<C, V>> rowMapBuilder = ImmutableMap.builder();
410      for (int r = 0; r < values.length; r++) {
411        V[] row = values[r];
412        ImmutableMap.Builder<C, V> columnMapBuilder = ImmutableMap.builder();
413        for (int c = 0; c < row.length; c++) {
414          V value = row[c];
415          if (value != null) {
416            columnMapBuilder.put(columnKeyToIndex.inverse().get(c), value);
417          }
418        }
419        rowMapBuilder.put(rowKeyToIndex.inverse().get(r),
420            columnMapBuilder.build());
421      }
422      return rowMapBuilder.build();
423    }
424
425    @Override public ImmutableMap<R, Map<C, V>> rowMap() {
426      ImmutableMap<R, Map<C, V>> result = rowMap;
427      if (result == null) {
428        rowMap = result = makeRowMap();
429      }
430      return result;
431    }
432  }
433}
434