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 org.checkerframework.checker.nullness.qual.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 #columnMap()} have
034 * iterators that don't support {@code remove()}. Otherwise, all optional operations are supported.
035 * Null row keys, columns keys, and values are not supported.
036 *
037 * <p>Lookups by row key are often faster than lookups by column key, because the data is stored in
038 * a {@code Map<R, Map<C, V>>}. A method call like {@code column(columnKey).get(rowKey)} still runs
039 * quickly, since the row key is provided. However, {@code column(columnKey).size()} takes longer,
040 * since an iteration across all row keys occurs.
041 *
042 * <p>Note that this implementation is not synchronized. If multiple threads access this table
043 * concurrently and one of the threads modifies the table, it must be synchronized externally.
044 *
045 * <p>See the Guava User Guide article on <a href=
046 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#table"> {@code Table}</a>.
047 *
048 * @author Jared Levy
049 * @since 7.0
050 */
051@GwtCompatible(serializable = true)
052public class HashBasedTable<R, C, V> extends StandardTable<R, C, V> {
053  private static class Factory<C, V> implements Supplier<Map<C, V>>, Serializable {
054    final int expectedSize;
055
056    Factory(int expectedSize) {
057      this.expectedSize = expectedSize;
058    }
059
060    @Override
061    public Map<C, V> get() {
062      return Maps.newLinkedHashMapWithExpectedSize(expectedSize);
063    }
064
065    private static final long serialVersionUID = 0;
066  }
067
068  /** Creates an empty {@code HashBasedTable}. */
069  public static <R, C, V> HashBasedTable<R, C, V> create() {
070    return new HashBasedTable<>(new LinkedHashMap<R, Map<C, V>>(), new Factory<C, V>(0));
071  }
072
073  /**
074   * Creates an empty {@code HashBasedTable} with the specified map sizes.
075   *
076   * @param expectedRows the expected number of distinct row keys
077   * @param expectedCellsPerRow the expected number of column key / value mappings in each row
078   * @throws IllegalArgumentException if {@code expectedRows} or {@code expectedCellsPerRow} is
079   *     negative
080   */
081  public static <R, C, V> HashBasedTable<R, C, V> create(
082      int expectedRows, int expectedCellsPerRow) {
083    checkNonnegative(expectedCellsPerRow, "expectedCellsPerRow");
084    Map<R, Map<C, V>> backingMap = Maps.newLinkedHashMapWithExpectedSize(expectedRows);
085    return new HashBasedTable<>(backingMap, new Factory<C, V>(expectedCellsPerRow));
086  }
087
088  /**
089   * Creates a {@code HashBasedTable} with the same mappings as the specified table.
090   *
091   * @param table the table to copy
092   * @throws NullPointerException if any of the row keys, column keys, or values in {@code table} is
093   *     null
094   */
095  public static <R, C, V> HashBasedTable<R, C, V> create(
096      Table<? extends R, ? extends C, ? extends V> table) {
097    HashBasedTable<R, C, V> result = create();
098    result.putAll(table);
099    return result;
100  }
101
102  HashBasedTable(Map<R, Map<C, V>> backingMap, Factory<C, V> factory) {
103    super(backingMap, factory);
104  }
105
106  // Overriding so NullPointerTester test passes.
107
108  @Override
109  public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) {
110    return super.contains(rowKey, columnKey);
111  }
112
113  @Override
114  public boolean containsColumn(@Nullable Object columnKey) {
115    return super.containsColumn(columnKey);
116  }
117
118  @Override
119  public boolean containsRow(@Nullable Object rowKey) {
120    return super.containsRow(rowKey);
121  }
122
123  @Override
124  public boolean containsValue(@Nullable Object value) {
125    return super.containsValue(value);
126  }
127
128  @Override
129  public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
130    return super.get(rowKey, columnKey);
131  }
132
133  @Override
134  public boolean equals(@Nullable Object obj) {
135    return super.equals(obj);
136  }
137
138  @CanIgnoreReturnValue
139  @Override
140  public V remove(@Nullable Object rowKey, @Nullable Object columnKey) {
141    return super.remove(rowKey, columnKey);
142  }
143
144  private static final long serialVersionUID = 0;
145}