001/*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.collect.CollectPreconditions.checkNonnegative;
020
021import com.google.common.annotations.GwtCompatible;
022import com.google.common.base.Supplier;
023import com.google.errorprone.annotations.CanIgnoreReturnValue;
024import java.io.Serializable;
025import java.util.LinkedHashMap;
026import java.util.Map;
027import javax.annotation.Nullable;
028
029/**
030 * Implementation of {@link Table} using linked hash tables. This guarantees predictable iteration
031 * order of the various views.
032 *
033 * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link
034 * #columnMap()} have iterators that don't support {@code remove()}. Otherwise,
035 * all optional operations are supported. Null row keys, columns keys, and
036 * values are not supported.
037 *
038 * <p>Lookups by row key are often faster than lookups by column key, because
039 * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code
040 * column(columnKey).get(rowKey)} still runs quickly, since the row key is
041 * provided. However, {@code column(columnKey).size()} takes longer, since an
042 * iteration across all row keys occurs.
043 *
044 * <p>Note that this implementation is not synchronized. If multiple threads
045 * access this table concurrently and one of the threads modifies the table, it
046 * must be synchronized externally.
047 *
048 * <p>See the Guava User Guide article on <a href=
049 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#table">
050 * {@code Table}</a>.
051 *
052 * @author Jared Levy
053 * @since 7.0
054 */
055@GwtCompatible(serializable = true)
056public class HashBasedTable<R, C, V> extends StandardTable<R, C, V> {
057  private static class Factory<C, V> implements Supplier<Map<C, V>>, Serializable {
058    final int expectedSize;
059
060    Factory(int expectedSize) {
061      this.expectedSize = expectedSize;
062    }
063
064    @Override
065    public Map<C, V> get() {
066      return Maps.newLinkedHashMapWithExpectedSize(expectedSize);
067    }
068
069    private static final long serialVersionUID = 0;
070  }
071
072  /**
073   * Creates an empty {@code HashBasedTable}.
074   */
075  public static <R, C, V> HashBasedTable<R, C, V> create() {
076    return new HashBasedTable<>(new LinkedHashMap<R, Map<C, V>>(), new Factory<C, V>(0));
077  }
078
079  /**
080   * Creates an empty {@code HashBasedTable} with the specified map sizes.
081   *
082   * @param expectedRows the expected number of distinct row keys
083   * @param expectedCellsPerRow the expected number of column key / value
084   *     mappings in each row
085   * @throws IllegalArgumentException if {@code expectedRows} or {@code
086   *     expectedCellsPerRow} is negative
087   */
088  public static <R, C, V> HashBasedTable<R, C, V> create(
089      int expectedRows, int expectedCellsPerRow) {
090    checkNonnegative(expectedCellsPerRow, "expectedCellsPerRow");
091    Map<R, Map<C, V>> backingMap = Maps.newLinkedHashMapWithExpectedSize(expectedRows);
092    return new HashBasedTable<>(backingMap, new Factory<C, V>(expectedCellsPerRow));
093  }
094
095  /**
096   * Creates a {@code HashBasedTable} with the same mappings as the specified
097   * table.
098   *
099   * @param table the table to copy
100   * @throws NullPointerException if any of the row keys, column keys, or values
101   *     in {@code table} is null
102   */
103  public static <R, C, V> HashBasedTable<R, C, V> create(
104      Table<? extends R, ? extends C, ? extends V> table) {
105    HashBasedTable<R, C, V> result = create();
106    result.putAll(table);
107    return result;
108  }
109
110  HashBasedTable(Map<R, Map<C, V>> backingMap, Factory<C, V> factory) {
111    super(backingMap, factory);
112  }
113
114  // Overriding so NullPointerTester test passes.
115
116  @Override
117  public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) {
118    return super.contains(rowKey, columnKey);
119  }
120
121  @Override
122  public boolean containsColumn(@Nullable Object columnKey) {
123    return super.containsColumn(columnKey);
124  }
125
126  @Override
127  public boolean containsRow(@Nullable Object rowKey) {
128    return super.containsRow(rowKey);
129  }
130
131  @Override
132  public boolean containsValue(@Nullable Object value) {
133    return super.containsValue(value);
134  }
135
136  @Override
137  public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
138    return super.get(rowKey, columnKey);
139  }
140
141  @Override
142  public boolean equals(@Nullable Object obj) {
143    return super.equals(obj);
144  }
145
146  @CanIgnoreReturnValue
147  @Override
148  public V remove(@Nullable Object rowKey, @Nullable Object columnKey) {
149    return super.remove(rowKey, columnKey);
150  }
151
152  private static final long serialVersionUID = 0;
153}