1/*
2 * Copyright (C) 2008 The Guava Authors
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;
20
21import com.google.common.annotations.Beta;
22import com.google.common.annotations.GwtCompatible;
23import com.google.common.base.Supplier;
24
25import java.io.Serializable;
26import java.util.HashMap;
27import java.util.Map;
28
29import javax.annotation.Nullable;
30
31/**
32 * Implementation of {@link Table} using hash tables.
33 *
34 * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link
35 * #columnMap()} have iterators that don't support {@code remove()}. Otherwise,
36 * all optional operations are supported. Null row keys, columns keys, and
37 * values are not supported.
38 *
39 * <p>Lookups by row key are often faster than lookups by column key, because
40 * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code
41 * column(columnKey).get(rowKey)} still runs quickly, since the row key is
42 * provided. However, {@code column(columnKey).size()} takes longer, since an
43 * iteration across all row keys occurs.
44 *
45 * <p>Note that this implementation is not synchronized. If multiple threads
46 * access this table concurrently and one of the threads modifies the table, it
47 * must be synchronized externally.
48 *
49 * @author Jared Levy
50 * @since 7.0
51 */
52@GwtCompatible(serializable = true)
53@Beta
54public class HashBasedTable<R, C, V> extends StandardTable<R, C, V> {
55  private static class Factory<C, V>
56      implements Supplier<Map<C, V>>, Serializable {
57    final int expectedSize;
58    Factory(int expectedSize) {
59      this.expectedSize = expectedSize;
60    }
61    @Override
62    public Map<C, V> get() {
63      return Maps.newHashMapWithExpectedSize(expectedSize);
64    }
65    private static final long serialVersionUID = 0;
66  }
67
68  /**
69   * Creates an empty {@code HashBasedTable}.
70   */
71  public static <R, C, V> HashBasedTable<R, C, V> create() {
72    return new HashBasedTable<R, C, V>(
73        new HashMap<R, Map<C, V>>(), new Factory<C, V>(0));
74  }
75
76  /**
77   * Creates an empty {@code HashBasedTable} with the specified map sizes.
78   *
79   * @param expectedRows the expected number of distinct row keys
80   * @param expectedCellsPerRow the expected number of column key / value
81   *     mappings in each row
82   * @throws IllegalArgumentException if {@code expectedRows} or {@code
83   *     expectedCellsPerRow} is negative
84   */
85  public static <R, C, V> HashBasedTable<R, C, V> create(
86      int expectedRows, int expectedCellsPerRow) {
87    checkArgument(expectedCellsPerRow >= 0);
88    Map<R, Map<C, V>> backingMap =
89        Maps.newHashMapWithExpectedSize(expectedRows);
90    return new HashBasedTable<R, C, V>(
91        backingMap, new Factory<C, V>(expectedCellsPerRow));
92  }
93
94  /**
95   * Creates a {@code HashBasedTable} with the same mappings as the specified
96   * table.
97   *
98   * @param table the table to copy
99   * @throws NullPointerException if any of the row keys, column keys, or values
100   *     in {@code table} is null
101   */
102  public static <R, C, V> HashBasedTable<R, C, V> create(
103      Table<? extends R, ? extends C, ? extends V> table) {
104    HashBasedTable<R, C, V> result = create();
105    result.putAll(table);
106    return result;
107  }
108
109  HashBasedTable(Map<R, Map<C, V>> backingMap, Factory<C, V> factory) {
110    super(backingMap, factory);
111  }
112
113  // Overriding so NullPointerTester test passes.
114
115  @Override public boolean contains(
116      @Nullable Object rowKey, @Nullable Object columnKey) {
117    return super.contains(rowKey, columnKey);
118  }
119
120  @Override public boolean containsColumn(@Nullable Object columnKey) {
121    return super.containsColumn(columnKey);
122  }
123
124  @Override public boolean containsRow(@Nullable Object rowKey) {
125    return super.containsRow(rowKey);
126  }
127
128  @Override public boolean containsValue(@Nullable Object value) {
129    return super.containsValue(value);
130  }
131
132  @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
133    return super.get(rowKey, columnKey);
134  }
135
136  @Override public boolean equals(@Nullable Object obj) {
137    return super.equals(obj);
138  }
139
140  @Override public V remove(
141      @Nullable Object rowKey, @Nullable Object columnKey) {
142    return super.remove(rowKey, columnKey);
143  }
144
145  private static final long serialVersionUID = 0;
146}
147