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 com.google.common.annotations.GwtCompatible;
18
19import java.util.LinkedHashMap;
20import java.util.Map;
21
22import javax.annotation.concurrent.Immutable;
23
24/**
25 * A {@code RegularImmutableTable} optimized for sparse data.
26 */
27@GwtCompatible
28@Immutable
29final class SparseImmutableTable<R, C, V>
30    extends RegularImmutableTable<R, C, V> {
31
32  private final ImmutableMap<R, Map<C, V>> rowMap;
33  private final ImmutableMap<C, Map<R, V>> columnMap;
34  private final int[] iterationOrderRow;
35  private final int[] iterationOrderColumn;
36
37  SparseImmutableTable(ImmutableList<Cell<R, C, V>> cellList,
38      ImmutableSet<R> rowSpace, ImmutableSet<C> columnSpace) {
39    Map<R, Integer> rowIndex = Maps.newHashMap();
40    Map<R, Map<C, V>> rows = Maps.newLinkedHashMap();
41    for (R row : rowSpace) {
42      rowIndex.put(row, rows.size());
43      rows.put(row, new LinkedHashMap<C, V>());
44    }
45    Map<C, Map<R, V>> columns = Maps.newLinkedHashMap();
46    for (C col : columnSpace) {
47      columns.put(col, new LinkedHashMap<R, V>());
48    }
49    int[] iterationOrderRow = new int[cellList.size()];
50    int[] iterationOrderColumn = new int[cellList.size()];
51    for (int i = 0; i < cellList.size(); i++) {
52      Cell<R, C, V> cell = cellList.get(i);
53      R rowKey = cell.getRowKey();
54      C columnKey = cell.getColumnKey();
55      V value = cell.getValue();
56
57      iterationOrderRow[i] = rowIndex.get(rowKey);
58      Map<C, V> thisRow = rows.get(rowKey);
59      iterationOrderColumn[i] = thisRow.size();
60      V oldValue = thisRow.put(columnKey, value);
61      if (oldValue != null) {
62        throw new IllegalArgumentException("Duplicate value for row=" + rowKey + ", column="
63            + columnKey + ": " + value + ", " + oldValue);
64      }
65      columns.get(columnKey).put(rowKey, value);
66    }
67    this.iterationOrderRow = iterationOrderRow;
68    this.iterationOrderColumn = iterationOrderColumn;
69    ImmutableMap.Builder<R, Map<C, V>> rowBuilder = ImmutableMap.builder();
70    for (Map.Entry<R, Map<C, V>> row : rows.entrySet()) {
71      rowBuilder.put(row.getKey(), ImmutableMap.copyOf(row.getValue()));
72    }
73    this.rowMap = rowBuilder.build();
74
75    ImmutableMap.Builder<C, Map<R, V>> columnBuilder = ImmutableMap.builder();
76    for (Map.Entry<C, Map<R, V>> col : columns.entrySet()) {
77      columnBuilder.put(col.getKey(), ImmutableMap.copyOf(col.getValue()));
78    }
79    this.columnMap = columnBuilder.build();
80  }
81
82  @Override public ImmutableMap<C, Map<R, V>> columnMap() {
83    return columnMap;
84  }
85
86  @Override public ImmutableMap<R, Map<C, V>> rowMap() {
87    return rowMap;
88  }
89
90  @Override
91  public int size() {
92    return iterationOrderRow.length;
93  }
94
95  @Override
96  Cell<R, C, V> getCell(int index) {
97    int rowIndex = iterationOrderRow[index];
98    Map.Entry<R, Map<C, V>> rowEntry = rowMap.entrySet().asList().get(rowIndex);
99    ImmutableMap<C, V> row = (ImmutableMap<C, V>) rowEntry.getValue();
100    int columnIndex = iterationOrderColumn[index];
101    Map.Entry<C, V> colEntry = row.entrySet().asList().get(columnIndex);
102    return cellOf(rowEntry.getKey(), colEntry.getKey(), colEntry.getValue());
103  }
104
105  @Override
106  V getValue(int index) {
107    int rowIndex = iterationOrderRow[index];
108    ImmutableMap<C, V> row = (ImmutableMap<C, V>) rowMap.values().asList().get(rowIndex);
109    int columnIndex = iterationOrderColumn[index];
110    return row.values().asList().get(columnIndex);
111  }
112}
113