001/* 002 * Copyright (C) 2009 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.base.Preconditions.checkNotNull; 020 021import com.google.common.annotations.GwtCompatible; 022import com.google.common.base.MoreObjects; 023import com.google.common.collect.Tables.AbstractCell; 024import com.google.errorprone.annotations.CanIgnoreReturnValue; 025import java.io.Serializable; 026import java.util.ArrayList; 027import java.util.Comparator; 028import java.util.Iterator; 029import java.util.List; 030import java.util.Map; 031import java.util.Spliterator; 032import java.util.function.BinaryOperator; 033import java.util.function.Function; 034import java.util.stream.Collector; 035import org.checkerframework.checker.nullness.qual.MonotonicNonNull; 036import org.checkerframework.checker.nullness.qual.Nullable; 037 038/** 039 * A {@link Table} whose contents will never change, with many other important properties detailed 040 * at {@link ImmutableCollection}. 041 * 042 * <p>See the Guava User Guide article on <a href= 043 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>. 044 * 045 * @author Gregory Kick 046 * @since 11.0 047 */ 048@GwtCompatible 049public abstract class ImmutableTable<R, C, V> extends AbstractTable<R, C, V> 050 implements Serializable { 051 052 /** 053 * Returns a {@code Collector} that accumulates elements into an {@code ImmutableTable}. Each 054 * input element is mapped to one cell in the returned table, with the rows, columns, and values 055 * generated by applying the specified functions. 056 * 057 * <p>The returned {@code Collector} will throw a {@code NullPointerException} at collection time 058 * if the row, column, or value functions return null on any input. 059 * 060 * @since 21.0 061 */ 062 public static <T, R, C, V> Collector<T, ?, ImmutableTable<R, C, V>> toImmutableTable( 063 Function<? super T, ? extends R> rowFunction, 064 Function<? super T, ? extends C> columnFunction, 065 Function<? super T, ? extends V> valueFunction) { 066 checkNotNull(rowFunction, "rowFunction"); 067 checkNotNull(columnFunction, "columnFunction"); 068 checkNotNull(valueFunction, "valueFunction"); 069 return Collector.of( 070 () -> new ImmutableTable.Builder<R, C, V>(), 071 (builder, t) -> 072 builder.put(rowFunction.apply(t), columnFunction.apply(t), valueFunction.apply(t)), 073 (b1, b2) -> b1.combine(b2), 074 b -> b.build()); 075 } 076 077 /** 078 * Returns a {@code Collector} that accumulates elements into an {@code ImmutableTable}. Each 079 * input element is mapped to one cell in the returned table, with the rows, columns, and values 080 * generated by applying the specified functions. If multiple inputs are mapped to the same row 081 * and column pair, they will be combined with the specified merging function in encounter order. 082 * 083 * <p>The returned {@code Collector} will throw a {@code NullPointerException} at collection time 084 * if the row, column, value, or merging functions return null on any input. 085 * 086 * @since 21.0 087 */ 088 public static <T, R, C, V> Collector<T, ?, ImmutableTable<R, C, V>> toImmutableTable( 089 Function<? super T, ? extends R> rowFunction, 090 Function<? super T, ? extends C> columnFunction, 091 Function<? super T, ? extends V> valueFunction, 092 BinaryOperator<V> mergeFunction) { 093 094 checkNotNull(rowFunction, "rowFunction"); 095 checkNotNull(columnFunction, "columnFunction"); 096 checkNotNull(valueFunction, "valueFunction"); 097 checkNotNull(mergeFunction, "mergeFunction"); 098 099 /* 100 * No mutable Table exactly matches the insertion order behavior of ImmutableTable.Builder, but 101 * the Builder can't efficiently support merging of duplicate values. Getting around this 102 * requires some work. 103 */ 104 105 return Collector.of( 106 () -> new CollectorState<R, C, V>() 107 /* GWT isn't currently playing nicely with constructor references? */ , 108 (state, input) -> 109 state.put( 110 rowFunction.apply(input), 111 columnFunction.apply(input), 112 valueFunction.apply(input), 113 mergeFunction), 114 (s1, s2) -> s1.combine(s2, mergeFunction), 115 state -> state.toTable()); 116 } 117 118 private static final class CollectorState<R, C, V> { 119 final List<MutableCell<R, C, V>> insertionOrder = new ArrayList<>(); 120 final Table<R, C, MutableCell<R, C, V>> table = HashBasedTable.create(); 121 122 void put(R row, C column, V value, BinaryOperator<V> merger) { 123 MutableCell<R, C, V> oldCell = table.get(row, column); 124 if (oldCell == null) { 125 MutableCell<R, C, V> cell = new MutableCell<>(row, column, value); 126 insertionOrder.add(cell); 127 table.put(row, column, cell); 128 } else { 129 oldCell.merge(value, merger); 130 } 131 } 132 133 CollectorState<R, C, V> combine(CollectorState<R, C, V> other, BinaryOperator<V> merger) { 134 for (MutableCell<R, C, V> cell : other.insertionOrder) { 135 put(cell.getRowKey(), cell.getColumnKey(), cell.getValue(), merger); 136 } 137 return this; 138 } 139 140 ImmutableTable<R, C, V> toTable() { 141 return copyOf(insertionOrder); 142 } 143 } 144 145 private static final class MutableCell<R, C, V> extends AbstractCell<R, C, V> { 146 private final R row; 147 private final C column; 148 private V value; 149 150 MutableCell(R row, C column, V value) { 151 this.row = checkNotNull(row, "row"); 152 this.column = checkNotNull(column, "column"); 153 this.value = checkNotNull(value, "value"); 154 } 155 156 @Override 157 public R getRowKey() { 158 return row; 159 } 160 161 @Override 162 public C getColumnKey() { 163 return column; 164 } 165 166 @Override 167 public V getValue() { 168 return value; 169 } 170 171 void merge(V value, BinaryOperator<V> mergeFunction) { 172 checkNotNull(value, "value"); 173 this.value = checkNotNull(mergeFunction.apply(this.value, value), "mergeFunction.apply"); 174 } 175 } 176 177 /** Returns an empty immutable table. */ 178 @SuppressWarnings("unchecked") 179 public static <R, C, V> ImmutableTable<R, C, V> of() { 180 return (ImmutableTable<R, C, V>) SparseImmutableTable.EMPTY; 181 } 182 183 /** Returns an immutable table containing a single cell. */ 184 public static <R, C, V> ImmutableTable<R, C, V> of(R rowKey, C columnKey, V value) { 185 return new SingletonImmutableTable<>(rowKey, columnKey, value); 186 } 187 188 /** 189 * Returns an immutable copy of the provided table. 190 * 191 * <p>The {@link Table#cellSet()} iteration order of the provided table determines the iteration 192 * ordering of all views in the returned table. Note that some views of the original table and the 193 * copied table may have different iteration orders. For more control over the ordering, create a 194 * {@link Builder} and call {@link Builder#orderRowsBy}, {@link Builder#orderColumnsBy}, and 195 * {@link Builder#putAll} 196 * 197 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 198 * safe to do so. The exact circumstances under which a copy will or will not be performed are 199 * undocumented and subject to change. 200 */ 201 public static <R, C, V> ImmutableTable<R, C, V> copyOf( 202 Table<? extends R, ? extends C, ? extends V> table) { 203 if (table instanceof ImmutableTable) { 204 @SuppressWarnings("unchecked") 205 ImmutableTable<R, C, V> parameterizedTable = (ImmutableTable<R, C, V>) table; 206 return parameterizedTable; 207 } else { 208 return copyOf(table.cellSet()); 209 } 210 } 211 212 private static <R, C, V> ImmutableTable<R, C, V> copyOf( 213 Iterable<? extends Cell<? extends R, ? extends C, ? extends V>> cells) { 214 ImmutableTable.Builder<R, C, V> builder = ImmutableTable.builder(); 215 for (Cell<? extends R, ? extends C, ? extends V> cell : cells) { 216 builder.put(cell); 217 } 218 return builder.build(); 219 } 220 221 /** 222 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 223 * Builder#Builder() ImmutableTable.Builder()} constructor. 224 */ 225 public static <R, C, V> Builder<R, C, V> builder() { 226 return new Builder<>(); 227 } 228 229 /** 230 * Verifies that {@code rowKey}, {@code columnKey} and {@code value} are non-null, and returns a 231 * new entry with those values. 232 */ 233 static <R, C, V> Cell<R, C, V> cellOf(R rowKey, C columnKey, V value) { 234 return Tables.immutableCell( 235 checkNotNull(rowKey, "rowKey"), 236 checkNotNull(columnKey, "columnKey"), 237 checkNotNull(value, "value")); 238 } 239 240 /** 241 * A builder for creating immutable table instances, especially {@code public static final} tables 242 * ("constant tables"). Example: 243 * 244 * <pre>{@code 245 * static final ImmutableTable<Integer, Character, String> SPREADSHEET = 246 * new ImmutableTable.Builder<Integer, Character, String>() 247 * .put(1, 'A', "foo") 248 * .put(1, 'B', "bar") 249 * .put(2, 'A', "baz") 250 * .build(); 251 * }</pre> 252 * 253 * <p>By default, the order in which cells are added to the builder determines the iteration 254 * ordering of all views in the returned table, with {@link #putAll} following the {@link 255 * Table#cellSet()} iteration order. However, if {@link #orderRowsBy} or {@link #orderColumnsBy} 256 * is called, the views are sorted by the supplied comparators. 257 * 258 * <p>For empty or single-cell immutable tables, {@link #of()} and {@link #of(Object, Object, 259 * Object)} are even more convenient. 260 * 261 * <p>Builder instances can be reused - it is safe to call {@link #build} multiple times to build 262 * multiple tables in series. Each table is a superset of the tables created before it. 263 * 264 * @since 11.0 265 */ 266 public static final class Builder<R, C, V> { 267 private final List<Cell<R, C, V>> cells = Lists.newArrayList(); 268 @MonotonicNonNull private Comparator<? super R> rowComparator; 269 @MonotonicNonNull private Comparator<? super C> columnComparator; 270 271 /** 272 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 273 * ImmutableTable#builder}. 274 */ 275 public Builder() {} 276 277 /** Specifies the ordering of the generated table's rows. */ 278 @CanIgnoreReturnValue 279 public Builder<R, C, V> orderRowsBy(Comparator<? super R> rowComparator) { 280 this.rowComparator = checkNotNull(rowComparator, "rowComparator"); 281 return this; 282 } 283 284 /** Specifies the ordering of the generated table's columns. */ 285 @CanIgnoreReturnValue 286 public Builder<R, C, V> orderColumnsBy(Comparator<? super C> columnComparator) { 287 this.columnComparator = checkNotNull(columnComparator, "columnComparator"); 288 return this; 289 } 290 291 /** 292 * Associates the ({@code rowKey}, {@code columnKey}) pair with {@code value} in the built 293 * table. Duplicate key pairs are not allowed and will cause {@link #build} to fail. 294 */ 295 @CanIgnoreReturnValue 296 public Builder<R, C, V> put(R rowKey, C columnKey, V value) { 297 cells.add(cellOf(rowKey, columnKey, value)); 298 return this; 299 } 300 301 /** 302 * Adds the given {@code cell} to the table, making it immutable if necessary. Duplicate key 303 * pairs are not allowed and will cause {@link #build} to fail. 304 */ 305 @CanIgnoreReturnValue 306 public Builder<R, C, V> put(Cell<? extends R, ? extends C, ? extends V> cell) { 307 if (cell instanceof Tables.ImmutableCell) { 308 checkNotNull(cell.getRowKey(), "row"); 309 checkNotNull(cell.getColumnKey(), "column"); 310 checkNotNull(cell.getValue(), "value"); 311 @SuppressWarnings("unchecked") // all supported methods are covariant 312 Cell<R, C, V> immutableCell = (Cell<R, C, V>) cell; 313 cells.add(immutableCell); 314 } else { 315 put(cell.getRowKey(), cell.getColumnKey(), cell.getValue()); 316 } 317 return this; 318 } 319 320 /** 321 * Associates all of the given table's keys and values in the built table. Duplicate row key 322 * column key pairs are not allowed, and will cause {@link #build} to fail. 323 * 324 * @throws NullPointerException if any key or value in {@code table} is null 325 */ 326 @CanIgnoreReturnValue 327 public Builder<R, C, V> putAll(Table<? extends R, ? extends C, ? extends V> table) { 328 for (Cell<? extends R, ? extends C, ? extends V> cell : table.cellSet()) { 329 put(cell); 330 } 331 return this; 332 } 333 334 Builder<R, C, V> combine(Builder<R, C, V> other) { 335 this.cells.addAll(other.cells); 336 return this; 337 } 338 339 /** 340 * Returns a newly-created immutable table. 341 * 342 * @throws IllegalArgumentException if duplicate key pairs were added 343 */ 344 public ImmutableTable<R, C, V> build() { 345 int size = cells.size(); 346 switch (size) { 347 case 0: 348 return of(); 349 case 1: 350 return new SingletonImmutableTable<>(Iterables.getOnlyElement(cells)); 351 default: 352 return RegularImmutableTable.forCells(cells, rowComparator, columnComparator); 353 } 354 } 355 } 356 357 ImmutableTable() {} 358 359 @Override 360 public ImmutableSet<Cell<R, C, V>> cellSet() { 361 return (ImmutableSet<Cell<R, C, V>>) super.cellSet(); 362 } 363 364 @Override 365 abstract ImmutableSet<Cell<R, C, V>> createCellSet(); 366 367 @Override 368 final UnmodifiableIterator<Cell<R, C, V>> cellIterator() { 369 throw new AssertionError("should never be called"); 370 } 371 372 @Override 373 final Spliterator<Cell<R, C, V>> cellSpliterator() { 374 throw new AssertionError("should never be called"); 375 } 376 377 @Override 378 public ImmutableCollection<V> values() { 379 return (ImmutableCollection<V>) super.values(); 380 } 381 382 @Override 383 abstract ImmutableCollection<V> createValues(); 384 385 @Override 386 final Iterator<V> valuesIterator() { 387 throw new AssertionError("should never be called"); 388 } 389 390 /** 391 * {@inheritDoc} 392 * 393 * @throws NullPointerException if {@code columnKey} is {@code null} 394 */ 395 @Override 396 public ImmutableMap<R, V> column(C columnKey) { 397 checkNotNull(columnKey, "columnKey"); 398 return MoreObjects.firstNonNull( 399 (ImmutableMap<R, V>) columnMap().get(columnKey), ImmutableMap.<R, V>of()); 400 } 401 402 @Override 403 public ImmutableSet<C> columnKeySet() { 404 return columnMap().keySet(); 405 } 406 407 /** 408 * {@inheritDoc} 409 * 410 * <p>The value {@code Map<R, V>} instances in the returned map are {@link ImmutableMap} instances 411 * as well. 412 */ 413 @Override 414 public abstract ImmutableMap<C, Map<R, V>> columnMap(); 415 416 /** 417 * {@inheritDoc} 418 * 419 * @throws NullPointerException if {@code rowKey} is {@code null} 420 */ 421 @Override 422 public ImmutableMap<C, V> row(R rowKey) { 423 checkNotNull(rowKey, "rowKey"); 424 return MoreObjects.firstNonNull( 425 (ImmutableMap<C, V>) rowMap().get(rowKey), ImmutableMap.<C, V>of()); 426 } 427 428 @Override 429 public ImmutableSet<R> rowKeySet() { 430 return rowMap().keySet(); 431 } 432 433 /** 434 * {@inheritDoc} 435 * 436 * <p>The value {@code Map<C, V>} instances in the returned map are {@link ImmutableMap} instances 437 * as well. 438 */ 439 @Override 440 public abstract ImmutableMap<R, Map<C, V>> rowMap(); 441 442 @Override 443 public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) { 444 return get(rowKey, columnKey) != null; 445 } 446 447 @Override 448 public boolean containsValue(@Nullable Object value) { 449 return values().contains(value); 450 } 451 452 /** 453 * Guaranteed to throw an exception and leave the table unmodified. 454 * 455 * @throws UnsupportedOperationException always 456 * @deprecated Unsupported operation. 457 */ 458 @Deprecated 459 @Override 460 public final void clear() { 461 throw new UnsupportedOperationException(); 462 } 463 464 /** 465 * Guaranteed to throw an exception and leave the table unmodified. 466 * 467 * @throws UnsupportedOperationException always 468 * @deprecated Unsupported operation. 469 */ 470 @CanIgnoreReturnValue 471 @Deprecated 472 @Override 473 public final V put(R rowKey, C columnKey, V value) { 474 throw new UnsupportedOperationException(); 475 } 476 477 /** 478 * Guaranteed to throw an exception and leave the table unmodified. 479 * 480 * @throws UnsupportedOperationException always 481 * @deprecated Unsupported operation. 482 */ 483 @Deprecated 484 @Override 485 public final void putAll(Table<? extends R, ? extends C, ? extends V> table) { 486 throw new UnsupportedOperationException(); 487 } 488 489 /** 490 * Guaranteed to throw an exception and leave the table unmodified. 491 * 492 * @throws UnsupportedOperationException always 493 * @deprecated Unsupported operation. 494 */ 495 @CanIgnoreReturnValue 496 @Deprecated 497 @Override 498 public final V remove(Object rowKey, Object columnKey) { 499 throw new UnsupportedOperationException(); 500 } 501 502 /** Creates the common serialized form for this table. */ 503 abstract SerializedForm createSerializedForm(); 504 505 /** 506 * Serialized type for all ImmutableTable instances. It captures the logical contents and 507 * preserves iteration order of all views. 508 */ 509 static final class SerializedForm implements Serializable { 510 private final Object[] rowKeys; 511 private final Object[] columnKeys; 512 513 private final Object[] cellValues; 514 private final int[] cellRowIndices; 515 private final int[] cellColumnIndices; 516 517 private SerializedForm( 518 Object[] rowKeys, 519 Object[] columnKeys, 520 Object[] cellValues, 521 int[] cellRowIndices, 522 int[] cellColumnIndices) { 523 this.rowKeys = rowKeys; 524 this.columnKeys = columnKeys; 525 this.cellValues = cellValues; 526 this.cellRowIndices = cellRowIndices; 527 this.cellColumnIndices = cellColumnIndices; 528 } 529 530 static SerializedForm create( 531 ImmutableTable<?, ?, ?> table, int[] cellRowIndices, int[] cellColumnIndices) { 532 return new SerializedForm( 533 table.rowKeySet().toArray(), 534 table.columnKeySet().toArray(), 535 table.values().toArray(), 536 cellRowIndices, 537 cellColumnIndices); 538 } 539 540 Object readResolve() { 541 if (cellValues.length == 0) { 542 return of(); 543 } 544 if (cellValues.length == 1) { 545 return of(rowKeys[0], columnKeys[0], cellValues[0]); 546 } 547 ImmutableList.Builder<Cell<Object, Object, Object>> cellListBuilder = 548 new ImmutableList.Builder<>(cellValues.length); 549 for (int i = 0; i < cellValues.length; i++) { 550 cellListBuilder.add( 551 cellOf(rowKeys[cellRowIndices[i]], columnKeys[cellColumnIndices[i]], cellValues[i])); 552 } 553 return RegularImmutableTable.forOrderedComponents( 554 cellListBuilder.build(), ImmutableSet.copyOf(rowKeys), ImmutableSet.copyOf(columnKeys)); 555 } 556 557 private static final long serialVersionUID = 0; 558 } 559 560 final Object writeReplace() { 561 return createSerializedForm(); 562 } 563}