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