11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2008 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Supplier; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.Serializable; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.HashMap; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Implementation of {@link Table} using hash tables. 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * #columnMap()} have iterators that don't support {@code remove()}. Otherwise, 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * all optional operations are supported. Null row keys, columns keys, and 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * values are not supported. 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Lookups by row key are often faster than lookups by column key, because 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * column(columnKey).get(rowKey)} still runs quickly, since the row key is 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * provided. However, {@code column(columnKey).size()} takes longer, since an 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * iteration across all row keys occurs. 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Note that this implementation is not synchronized. If multiple threads 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * access this table concurrently and one of the threads modifies the table, it 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * must be synchronized externally. 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Jared Levy 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 7.0 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true) 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@Beta 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class HashBasedTable<R, C, V> extends StandardTable<R, C, V> { 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static class Factory<C, V> 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert implements Supplier<Map<C, V>>, Serializable { 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final int expectedSize; 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Factory(int expectedSize) { 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.expectedSize = expectedSize; 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Map<C, V> get() { 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Maps.newHashMapWithExpectedSize(expectedSize); 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 0; 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates an empty {@code HashBasedTable}. 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <R, C, V> HashBasedTable<R, C, V> create() { 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new HashBasedTable<R, C, V>( 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new HashMap<R, Map<C, V>>(), new Factory<C, V>(0)); 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates an empty {@code HashBasedTable} with the specified map sizes. 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param expectedRows the expected number of distinct row keys 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param expectedCellsPerRow the expected number of column key / value 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mappings in each row 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code expectedRows} or {@code 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * expectedCellsPerRow} is negative 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <R, C, V> HashBasedTable<R, C, V> create( 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int expectedRows, int expectedCellsPerRow) { 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(expectedCellsPerRow >= 0); 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<R, Map<C, V>> backingMap = 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Maps.newHashMapWithExpectedSize(expectedRows); 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new HashBasedTable<R, C, V>( 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingMap, new Factory<C, V>(expectedCellsPerRow)); 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a {@code HashBasedTable} with the same mappings as the specified 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * table. 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param table the table to copy 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any of the row keys, column keys, or values 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in {@code table} is null 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <R, C, V> HashBasedTable<R, C, V> create( 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Table<? extends R, ? extends C, ? extends V> table) { 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert HashBasedTable<R, C, V> result = create(); 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert result.putAll(table); 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert HashBasedTable(Map<R, Map<C, V>> backingMap, Factory<C, V> factory) { 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(backingMap, factory); 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Overriding so NullPointerTester test passes. 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean contains( 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable Object rowKey, @Nullable Object columnKey) { 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.contains(rowKey, columnKey); 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean containsColumn(@Nullable Object columnKey) { 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.containsColumn(columnKey); 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean containsRow(@Nullable Object rowKey) { 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.containsRow(rowKey); 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean containsValue(@Nullable Object value) { 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.containsValue(value); 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) { 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.get(rowKey, columnKey); 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean equals(@Nullable Object obj) { 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.equals(obj); 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public V remove( 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable Object rowKey, @Nullable Object columnKey) { 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.remove(rowKey, columnKey); 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 0; 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 147