StandardTable.java revision 7dd252788645e940eada959bdde927426e2531c9
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.checkNotNull; 20import static com.google.common.collect.Maps.safeContainsKey; 21import static com.google.common.collect.Maps.safeGet; 22 23import com.google.common.annotations.GwtCompatible; 24import com.google.common.base.Predicate; 25import com.google.common.base.Predicates; 26import com.google.common.base.Supplier; 27 28import java.io.Serializable; 29import java.util.AbstractCollection; 30import java.util.AbstractMap; 31import java.util.AbstractSet; 32import java.util.Collection; 33import java.util.Iterator; 34import java.util.LinkedHashMap; 35import java.util.Map; 36import java.util.Map.Entry; 37import java.util.Set; 38 39import javax.annotation.Nullable; 40 41/** 42 * {@link Table} implementation backed by a map that associates row keys with 43 * column key / value secondary maps. This class provides rapid access to 44 * records by the row key alone or by both keys, but not by just the column key. 45 * 46 * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link 47 * #columnMap()} have iterators that don't support {@code remove()}. Otherwise, 48 * all optional operations are supported. Null row keys, columns keys, and 49 * values are not supported. 50 * 51 * <p>Lookups by row key are often faster than lookups by column key, because 52 * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code 53 * column(columnKey).get(rowKey)} still runs quickly, since the row key is 54 * provided. However, {@code column(columnKey).size()} takes longer, since an 55 * iteration across all row keys occurs. 56 * 57 * <p>Note that this implementation is not synchronized. If multiple threads 58 * access this table concurrently and one of the threads modifies the table, it 59 * must be synchronized externally. 60 * 61 * @author Jared Levy 62 */ 63@GwtCompatible 64class StandardTable<R, C, V> implements Table<R, C, V>, Serializable { 65 @GwtTransient 66 final Map<R, Map<C, V>> backingMap; 67 @GwtTransient 68 final Supplier<? extends Map<C, V>> factory; 69 70 StandardTable(Map<R, Map<C, V>> backingMap, Supplier<? extends Map<C, V>> factory) { 71 this.backingMap = backingMap; 72 this.factory = factory; 73 } 74 75 // Accessors 76 77 public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) { 78 if ((rowKey == null) || (columnKey == null)) { 79 return false; 80 } 81 Map<C, V> map = safeGet(backingMap, rowKey); 82 return map != null && safeContainsKey(map, columnKey); 83 } 84 85 public boolean containsColumn(@Nullable Object columnKey) { 86 if (columnKey == null) { 87 return false; 88 } 89 for (Map<C, V> map : backingMap.values()) { 90 if (safeContainsKey(map, columnKey)) { 91 return true; 92 } 93 } 94 return false; 95 } 96 97 public boolean containsRow(@Nullable Object rowKey) { 98 return rowKey != null && safeContainsKey(backingMap, rowKey); 99 } 100 101 public boolean containsValue(@Nullable Object value) { 102 if (value == null) { 103 return false; 104 } 105 for (Map<C, V> map : backingMap.values()) { 106 if (map.containsValue(value)) { 107 return true; 108 } 109 } 110 return false; 111 } 112 113 public V get(@Nullable Object rowKey, @Nullable Object columnKey) { 114 if ((rowKey == null) || (columnKey == null)) { 115 return null; 116 } 117 Map<C, V> map = safeGet(backingMap, rowKey); 118 return map == null ? null : safeGet(map, columnKey); 119 } 120 121 public boolean isEmpty() { 122 return backingMap.isEmpty(); 123 } 124 125 public int size() { 126 int size = 0; 127 for (Map<C, V> map : backingMap.values()) { 128 size += map.size(); 129 } 130 return size; 131 } 132 133 @Override 134 public boolean equals(@Nullable Object obj) { 135 if (obj == this) { 136 return true; 137 } 138 if (obj instanceof Table) { 139 Table<?, ?, ?> other = (Table<?, ?, ?>) obj; 140 return cellSet().equals(other.cellSet()); 141 } 142 return false; 143 } 144 145 @Override 146 public int hashCode() { 147 return cellSet().hashCode(); 148 } 149 150 /** 151 * Returns the string representation {@code rowMap().toString()}. 152 */ 153 @Override 154 public String toString() { 155 return rowMap().toString(); 156 } 157 158 // Mutators 159 160 public void clear() { 161 backingMap.clear(); 162 } 163 164 private Map<C, V> getOrCreate(R rowKey) { 165 Map<C, V> map = backingMap.get(rowKey); 166 if (map == null) { 167 map = factory.get(); 168 backingMap.put(rowKey, map); 169 } 170 return map; 171 } 172 173 public V put(R rowKey, C columnKey, V value) { 174 checkNotNull(rowKey); 175 checkNotNull(columnKey); 176 checkNotNull(value); 177 return getOrCreate(rowKey).put(columnKey, value); 178 } 179 180 public void putAll(Table<? extends R, ? extends C, ? extends V> table) { 181 for (Cell<? extends R, ? extends C, ? extends V> cell : table.cellSet()) { 182 put(cell.getRowKey(), cell.getColumnKey(), cell.getValue()); 183 } 184 } 185 186 public V remove(@Nullable Object rowKey, @Nullable Object columnKey) { 187 if ((rowKey == null) || (columnKey == null)) { 188 return null; 189 } 190 Map<C, V> map = safeGet(backingMap, rowKey); 191 if (map == null) { 192 return null; 193 } 194 V value = map.remove(columnKey); 195 if (map.isEmpty()) { 196 backingMap.remove(rowKey); 197 } 198 return value; 199 } 200 201 private Map<R, V> removeColumn(Object column) { 202 Map<R, V> output = new LinkedHashMap<R, V>(); 203 Iterator<Entry<R, Map<C, V>>> iterator = backingMap.entrySet().iterator(); 204 while (iterator.hasNext()) { 205 Entry<R, Map<C, V>> entry = iterator.next(); 206 V value = entry.getValue().remove(column); 207 if (value != null) { 208 output.put(entry.getKey(), value); 209 if (entry.getValue().isEmpty()) { 210 iterator.remove(); 211 } 212 } 213 } 214 return output; 215 } 216 217 private boolean containsMapping(Object rowKey, Object columnKey, Object value) { 218 return value != null && value.equals(get(rowKey, columnKey)); 219 } 220 221 /** Remove a row key / column key / value mapping, if present. */ 222 private boolean removeMapping(Object rowKey, Object columnKey, Object value) { 223 if (containsMapping(rowKey, columnKey, value)) { 224 remove(rowKey, columnKey); 225 return true; 226 } 227 return false; 228 } 229 230 // Views 231 232 /** 233 * Abstract collection whose {@code isEmpty()} returns whether the table is 234 * empty and whose {@code clear()} clears all table mappings. 235 */ 236 private abstract class TableCollection<T> extends AbstractCollection<T> { 237 @Override 238 public boolean isEmpty() { 239 return backingMap.isEmpty(); 240 } 241 242 @Override 243 public void clear() { 244 backingMap.clear(); 245 } 246 } 247 248 /** 249 * Abstract set whose {@code isEmpty()} returns whether the table is empty and 250 * whose {@code clear()} clears all table mappings. 251 */ 252 private abstract class TableSet<T> extends AbstractSet<T> { 253 @Override 254 public boolean isEmpty() { 255 return backingMap.isEmpty(); 256 } 257 258 @Override 259 public void clear() { 260 backingMap.clear(); 261 } 262 } 263 264 private transient CellSet cellSet; 265 266 /** 267 * {@inheritDoc} 268 * 269 * <p>The set's iterator traverses the mappings for the first row, the 270 * mappings for the second row, and so on. 271 * 272 * <p>Each cell is an immutable snapshot of a row key / column key / value 273 * mapping, taken at the time the cell is returned by a method call to the 274 * set or its iterator. 275 */ 276 public Set<Cell<R, C, V>> cellSet() { 277 CellSet result = cellSet; 278 return (result == null) ? cellSet = new CellSet() : result; 279 } 280 281 private class CellSet extends TableSet<Cell<R, C, V>> { 282 @Override 283 public Iterator<Cell<R, C, V>> iterator() { 284 return new CellIterator(); 285 } 286 287 @Override 288 public int size() { 289 return StandardTable.this.size(); 290 } 291 292 @Override 293 public boolean contains(Object obj) { 294 if (obj instanceof Cell) { 295 Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj; 296 return containsMapping(cell.getRowKey(), cell.getColumnKey(), cell.getValue()); 297 } 298 return false; 299 } 300 301 @Override 302 public boolean remove(Object obj) { 303 if (obj instanceof Cell) { 304 Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj; 305 return removeMapping(cell.getRowKey(), cell.getColumnKey(), cell.getValue()); 306 } 307 return false; 308 } 309 } 310 311 private class CellIterator implements Iterator<Cell<R, C, V>> { 312 final Iterator<Entry<R, Map<C, V>>> rowIterator = backingMap.entrySet().iterator(); 313 Entry<R, Map<C, V>> rowEntry; 314 Iterator<Entry<C, V>> columnIterator = Iterators.emptyModifiableIterator(); 315 316 public boolean hasNext() { 317 return rowIterator.hasNext() || columnIterator.hasNext(); 318 } 319 320 public Cell<R, C, V> next() { 321 if (!columnIterator.hasNext()) { 322 rowEntry = rowIterator.next(); 323 columnIterator = rowEntry.getValue().entrySet().iterator(); 324 } 325 Entry<C, V> columnEntry = columnIterator.next(); 326 return Tables.immutableCell(rowEntry.getKey(), columnEntry.getKey(), columnEntry.getValue()); 327 } 328 329 public void remove() { 330 columnIterator.remove(); 331 if (rowEntry.getValue().isEmpty()) { 332 rowIterator.remove(); 333 } 334 } 335 } 336 337 public Map<C, V> row(R rowKey) { 338 return new Row(rowKey); 339 } 340 341 class Row extends AbstractMap<C, V> { 342 final R rowKey; 343 344 Row(R rowKey) { 345 this.rowKey = checkNotNull(rowKey); 346 } 347 348 Map<C, V> backingRowMap; 349 350 Map<C, V> backingRowMap() { 351 return (backingRowMap == null || (backingRowMap.isEmpty() && backingMap.containsKey(rowKey))) ? backingRowMap = computeBackingRowMap() 352 : backingRowMap; 353 } 354 355 Map<C, V> computeBackingRowMap() { 356 return backingMap.get(rowKey); 357 } 358 359 // Call this every time we perform a removal. 360 void maintainEmptyInvariant() { 361 if (backingRowMap() != null && backingRowMap.isEmpty()) { 362 backingMap.remove(rowKey); 363 backingRowMap = null; 364 } 365 } 366 367 @Override 368 public boolean containsKey(Object key) { 369 Map<C, V> backingRowMap = backingRowMap(); 370 return (key != null && backingRowMap != null) && Maps.safeContainsKey(backingRowMap, key); 371 } 372 373 @Override 374 public V get(Object key) { 375 Map<C, V> backingRowMap = backingRowMap(); 376 return (key != null && backingRowMap != null) ? Maps.safeGet(backingRowMap, key) : null; 377 } 378 379 @Override 380 public V put(C key, V value) { 381 checkNotNull(key); 382 checkNotNull(value); 383 if (backingRowMap != null && !backingRowMap.isEmpty()) { 384 return backingRowMap.put(key, value); 385 } 386 return StandardTable.this.put(rowKey, key, value); 387 } 388 389 @Override 390 public V remove(Object key) { 391 Map<C, V> backingRowMap = backingRowMap(); 392 if (backingRowMap == null) { 393 return null; 394 } 395 V result = Maps.safeRemove(backingRowMap, key); 396 maintainEmptyInvariant(); 397 return result; 398 } 399 400 @Override 401 public void clear() { 402 Map<C, V> backingRowMap = backingRowMap(); 403 if (backingRowMap != null) { 404 backingRowMap.clear(); 405 } 406 maintainEmptyInvariant(); 407 } 408 409 Set<C> keySet; 410 411 @Override 412 public Set<C> keySet() { 413 Set<C> result = keySet; 414 if (result == null) { 415 return keySet = new Maps.KeySet<C, V>() { 416 417 @Override 418 Map<C, V> map() { 419 return Row.this; 420 } 421 }; 422 } 423 return result; 424 } 425 426 Set<Entry<C, V>> entrySet; 427 428 @Override 429 public Set<Entry<C, V>> entrySet() { 430 Set<Entry<C, V>> result = entrySet; 431 if (result == null) { 432 return entrySet = new RowEntrySet(); 433 } 434 return result; 435 } 436 437 private class RowEntrySet extends Maps.EntrySet<C, V> { 438 439 @Override 440 Map<C, V> map() { 441 return Row.this; 442 } 443 444 @Override 445 public int size() { 446 Map<C, V> map = backingRowMap(); 447 return (map == null) ? 0 : map.size(); 448 } 449 450 @Override 451 public Iterator<Entry<C, V>> iterator() { 452 final Map<C, V> map = backingRowMap(); 453 if (map == null) { 454 return Iterators.emptyModifiableIterator(); 455 } 456 final Iterator<Entry<C, V>> iterator = map.entrySet().iterator(); 457 return new Iterator<Entry<C, V>>() { 458 public boolean hasNext() { 459 return iterator.hasNext(); 460 } 461 462 public Entry<C, V> next() { 463 final Entry<C, V> entry = iterator.next(); 464 return new ForwardingMapEntry<C, V>() { 465 @Override 466 protected Entry<C, V> delegate() { 467 return entry; 468 } 469 470 @Override 471 public V setValue(V value) { 472 return super.setValue(checkNotNull(value)); 473 } 474 475 @Override 476 public boolean equals(Object object) { 477 // TODO(user): identify why this affects GWT tests 478 return standardEquals(object); 479 } 480 }; 481 } 482 483 public void remove() { 484 iterator.remove(); 485 maintainEmptyInvariant(); 486 } 487 }; 488 } 489 } 490 } 491 492 /** 493 * {@inheritDoc} 494 * 495 * <p>The returned map's views have iterators that don't support 496 * {@code remove()}. 497 */ 498 public Map<R, V> column(C columnKey) { 499 return new Column(columnKey); 500 } 501 502 private class Column extends Maps.ImprovedAbstractMap<R, V> { 503 final C columnKey; 504 505 Column(C columnKey) { 506 this.columnKey = checkNotNull(columnKey); 507 } 508 509 @Override 510 public V put(R key, V value) { 511 return StandardTable.this.put(key, columnKey, value); 512 } 513 514 @Override 515 public V get(Object key) { 516 return StandardTable.this.get(key, columnKey); 517 } 518 519 @Override 520 public boolean containsKey(Object key) { 521 return StandardTable.this.contains(key, columnKey); 522 } 523 524 @Override 525 public V remove(Object key) { 526 return StandardTable.this.remove(key, columnKey); 527 } 528 529 @Override 530 public Set<Entry<R, V>> createEntrySet() { 531 return new EntrySet(); 532 } 533 534 Values columnValues; 535 536 @Override 537 public Collection<V> values() { 538 Values result = columnValues; 539 return (result == null) ? columnValues = new Values() : result; 540 } 541 542 /** 543 * Removes all {@code Column} mappings whose row key and value satisfy the 544 * given predicate. 545 */ 546 boolean removePredicate(Predicate<? super Entry<R, V>> predicate) { 547 boolean changed = false; 548 Iterator<Entry<R, Map<C, V>>> iterator = backingMap.entrySet().iterator(); 549 while (iterator.hasNext()) { 550 Entry<R, Map<C, V>> entry = iterator.next(); 551 Map<C, V> map = entry.getValue(); 552 V value = map.get(columnKey); 553 if (value != null && predicate.apply(new ImmutableEntry<R, V>(entry.getKey(), value))) { 554 map.remove(columnKey); 555 changed = true; 556 if (map.isEmpty()) { 557 iterator.remove(); 558 } 559 } 560 } 561 return changed; 562 } 563 564 class EntrySet extends Sets.ImprovedAbstractSet<Entry<R, V>> { 565 @Override 566 public Iterator<Entry<R, V>> iterator() { 567 return new EntrySetIterator(); 568 } 569 570 @Override 571 public int size() { 572 int size = 0; 573 for (Map<C, V> map : backingMap.values()) { 574 if (map.containsKey(columnKey)) { 575 size++; 576 } 577 } 578 return size; 579 } 580 581 @Override 582 public boolean isEmpty() { 583 return !containsColumn(columnKey); 584 } 585 586 @Override 587 public void clear() { 588 Predicate<Entry<R, V>> predicate = Predicates.alwaysTrue(); 589 removePredicate(predicate); 590 } 591 592 @Override 593 public boolean contains(Object o) { 594 if (o instanceof Entry) { 595 Entry<?, ?> entry = (Entry<?, ?>) o; 596 return containsMapping(entry.getKey(), columnKey, entry.getValue()); 597 } 598 return false; 599 } 600 601 @Override 602 public boolean remove(Object obj) { 603 if (obj instanceof Entry) { 604 Entry<?, ?> entry = (Entry<?, ?>) obj; 605 return removeMapping(entry.getKey(), columnKey, entry.getValue()); 606 } 607 return false; 608 } 609 610 @Override 611 public boolean retainAll(Collection<?> c) { 612 return removePredicate(Predicates.not(Predicates.in(c))); 613 } 614 } 615 616 class EntrySetIterator extends AbstractIterator<Entry<R, V>> { 617 final Iterator<Entry<R, Map<C, V>>> iterator = backingMap.entrySet().iterator(); 618 619 @Override 620 protected Entry<R, V> computeNext() { 621 while (iterator.hasNext()) { 622 final Entry<R, Map<C, V>> entry = iterator.next(); 623 if (entry.getValue().containsKey(columnKey)) { 624 return new AbstractMapEntry<R, V>() { 625 @Override 626 public R getKey() { 627 return entry.getKey(); 628 } 629 630 @Override 631 public V getValue() { 632 return entry.getValue().get(columnKey); 633 } 634 635 @Override 636 public V setValue(V value) { 637 return entry.getValue().put(columnKey, checkNotNull(value)); 638 } 639 }; 640 } 641 } 642 return endOfData(); 643 } 644 } 645 646 KeySet keySet; 647 648 @Override 649 public Set<R> keySet() { 650 KeySet result = keySet; 651 return result == null ? keySet = new KeySet() : result; 652 } 653 654 class KeySet extends Sets.ImprovedAbstractSet<R> { 655 @Override 656 public Iterator<R> iterator() { 657 return Maps.keyIterator(Column.this.entrySet().iterator()); 658 } 659 660 @Override 661 public int size() { 662 return entrySet().size(); 663 } 664 665 @Override 666 public boolean isEmpty() { 667 return !containsColumn(columnKey); 668 } 669 670 @Override 671 public boolean contains(Object obj) { 672 return StandardTable.this.contains(obj, columnKey); 673 } 674 675 @Override 676 public boolean remove(Object obj) { 677 return StandardTable.this.remove(obj, columnKey) != null; 678 } 679 680 @Override 681 public void clear() { 682 entrySet().clear(); 683 } 684 685 @Override 686 public boolean retainAll(final Collection<?> c) { 687 checkNotNull(c); 688 Predicate<Entry<R, V>> predicate = new Predicate<Entry<R, V>>() { 689 690 public boolean apply(Entry<R, V> entry) { 691 return !c.contains(entry.getKey()); 692 } 693 }; 694 return removePredicate(predicate); 695 } 696 } 697 698 class Values extends AbstractCollection<V> { 699 @Override 700 public Iterator<V> iterator() { 701 return Maps.valueIterator(Column.this.entrySet().iterator()); 702 } 703 704 @Override 705 public int size() { 706 return entrySet().size(); 707 } 708 709 @Override 710 public boolean isEmpty() { 711 return !containsColumn(columnKey); 712 } 713 714 @Override 715 public void clear() { 716 entrySet().clear(); 717 } 718 719 @Override 720 public boolean remove(Object obj) { 721 if (obj == null) { 722 return false; 723 } 724 Iterator<Map<C, V>> iterator = backingMap.values().iterator(); 725 while (iterator.hasNext()) { 726 Map<C, V> map = iterator.next(); 727 if (map.entrySet().remove(new ImmutableEntry<C, Object>(columnKey, obj))) { 728 if (map.isEmpty()) { 729 iterator.remove(); 730 } 731 return true; 732 } 733 } 734 return false; 735 } 736 737 @Override 738 public boolean removeAll(final Collection<?> c) { 739 checkNotNull(c); 740 Predicate<Entry<R, V>> predicate = new Predicate<Entry<R, V>>() { 741 742 public boolean apply(Entry<R, V> entry) { 743 return c.contains(entry.getValue()); 744 } 745 }; 746 return removePredicate(predicate); 747 } 748 749 @Override 750 public boolean retainAll(final Collection<?> c) { 751 checkNotNull(c); 752 Predicate<Entry<R, V>> predicate = new Predicate<Entry<R, V>>() { 753 754 public boolean apply(Entry<R, V> entry) { 755 return !c.contains(entry.getValue()); 756 } 757 }; 758 return removePredicate(predicate); 759 } 760 } 761 } 762 763 private transient RowKeySet rowKeySet; 764 765 public Set<R> rowKeySet() { 766 Set<R> result = rowKeySet; 767 return (result == null) ? rowKeySet = new RowKeySet() : result; 768 } 769 770 class RowKeySet extends TableSet<R> { 771 @Override 772 public Iterator<R> iterator() { 773 return Maps.keyIterator(rowMap().entrySet().iterator()); 774 } 775 776 @Override 777 public int size() { 778 return backingMap.size(); 779 } 780 781 @Override 782 public boolean contains(Object obj) { 783 return containsRow(obj); 784 } 785 786 @Override 787 public boolean remove(Object obj) { 788 return (obj != null) && backingMap.remove(obj) != null; 789 } 790 } 791 792 private transient Set<C> columnKeySet; 793 794 /** 795 * {@inheritDoc} 796 * 797 * <p>The returned set has an iterator that does not support {@code remove()}. 798 * 799 * <p>The set's iterator traverses the columns of the first row, the 800 * columns of the second row, etc., skipping any columns that have 801 * appeared previously. 802 */ 803 804 public Set<C> columnKeySet() { 805 Set<C> result = columnKeySet; 806 return (result == null) ? columnKeySet = new ColumnKeySet() : result; 807 } 808 809 private class ColumnKeySet extends TableSet<C> { 810 @Override 811 public Iterator<C> iterator() { 812 return createColumnKeyIterator(); 813 } 814 815 @Override 816 public int size() { 817 return Iterators.size(iterator()); 818 } 819 820 @Override 821 public boolean remove(Object obj) { 822 if (obj == null) { 823 return false; 824 } 825 boolean changed = false; 826 Iterator<Map<C, V>> iterator = backingMap.values().iterator(); 827 while (iterator.hasNext()) { 828 Map<C, V> map = iterator.next(); 829 if (map.keySet().remove(obj)) { 830 changed = true; 831 if (map.isEmpty()) { 832 iterator.remove(); 833 } 834 } 835 } 836 return changed; 837 } 838 839 @Override 840 public boolean removeAll(Collection<?> c) { 841 checkNotNull(c); 842 boolean changed = false; 843 Iterator<Map<C, V>> iterator = backingMap.values().iterator(); 844 while (iterator.hasNext()) { 845 Map<C, V> map = iterator.next(); 846 // map.keySet().removeAll(c) can throw a NPE when map is a TreeMap with 847 // natural ordering and c contains a null. 848 if (Iterators.removeAll(map.keySet().iterator(), c)) { 849 changed = true; 850 if (map.isEmpty()) { 851 iterator.remove(); 852 } 853 } 854 } 855 return changed; 856 } 857 858 @Override 859 public boolean retainAll(Collection<?> c) { 860 checkNotNull(c); 861 boolean changed = false; 862 Iterator<Map<C, V>> iterator = backingMap.values().iterator(); 863 while (iterator.hasNext()) { 864 Map<C, V> map = iterator.next(); 865 if (map.keySet().retainAll(c)) { 866 changed = true; 867 if (map.isEmpty()) { 868 iterator.remove(); 869 } 870 } 871 } 872 return changed; 873 } 874 875 @Override 876 public boolean contains(Object obj) { 877 if (obj == null) { 878 return false; 879 } 880 for (Map<C, V> map : backingMap.values()) { 881 if (map.containsKey(obj)) { 882 return true; 883 } 884 } 885 return false; 886 } 887 } 888 889 /** 890 * Creates an iterator that returns each column value with duplicates 891 * omitted. 892 */ 893 Iterator<C> createColumnKeyIterator() { 894 return new ColumnKeyIterator(); 895 } 896 897 private class ColumnKeyIterator extends AbstractIterator<C> { 898 // Use the same map type to support TreeMaps with comparators that aren't 899 // consistent with equals(). 900 final Map<C, V> seen = factory.get(); 901 final Iterator<Map<C, V>> mapIterator = backingMap.values().iterator(); 902 Iterator<Entry<C, V>> entryIterator = Iterators.emptyIterator(); 903 904 @Override 905 protected C computeNext() { 906 while (true) { 907 if (entryIterator.hasNext()) { 908 Entry<C, V> entry = entryIterator.next(); 909 if (!seen.containsKey(entry.getKey())) { 910 seen.put(entry.getKey(), entry.getValue()); 911 return entry.getKey(); 912 } 913 } else if (mapIterator.hasNext()) { 914 entryIterator = mapIterator.next().entrySet().iterator(); 915 } else { 916 return endOfData(); 917 } 918 } 919 } 920 } 921 922 private transient Values values; 923 924 /** 925 * {@inheritDoc} 926 * 927 * <p>The collection's iterator traverses the values for the first row, 928 * the values for the second row, and so on. 929 */ 930 public Collection<V> values() { 931 Values result = values; 932 return (result == null) ? values = new Values() : result; 933 } 934 935 private class Values extends TableCollection<V> { 936 @Override 937 public Iterator<V> iterator() { 938 return new TransformedIterator<Cell<R, C, V>, V>(cellSet().iterator()) { 939 940 @Override 941 V transform(Cell<R, C, V> cell) { 942 return cell.getValue(); 943 } 944 }; 945 } 946 947 @Override 948 public int size() { 949 return StandardTable.this.size(); 950 } 951 } 952 953 private transient RowMap rowMap; 954 955 public Map<R, Map<C, V>> rowMap() { 956 RowMap result = rowMap; 957 return (result == null) ? rowMap = new RowMap() : result; 958 } 959 960 class RowMap extends Maps.ImprovedAbstractMap<R, Map<C, V>> { 961 @Override 962 public boolean containsKey(Object key) { 963 return containsRow(key); 964 } 965 966 // performing cast only when key is in backing map and has the correct type 967 @Override 968 @SuppressWarnings("unchecked") 969 public Map<C, V> get(Object key) { 970 return containsRow(key) ? row((R) key) : null; 971 } 972 973 @Override 974 public Set<R> keySet() { 975 return rowKeySet(); 976 } 977 978 @Override 979 public Map<C, V> remove(Object key) { 980 return (key == null) ? null : backingMap.remove(key); 981 } 982 983 @Override 984 protected Set<Entry<R, Map<C, V>>> createEntrySet() { 985 return new EntrySet(); 986 } 987 988 class EntrySet extends TableSet<Entry<R, Map<C, V>>> { 989 @Override 990 public Iterator<Entry<R, Map<C, V>>> iterator() { 991 return new TransformedIterator<R, Entry<R, Map<C, V>>>(backingMap.keySet().iterator()) { 992 993 @Override 994 Entry<R, Map<C, V>> transform(R rowKey) { 995 return new ImmutableEntry<R, Map<C, V>>(rowKey, row(rowKey)); 996 } 997 }; 998 } 999 1000 @Override 1001 public int size() { 1002 return backingMap.size(); 1003 } 1004 1005 @Override 1006 public boolean contains(Object obj) { 1007 if (obj instanceof Entry) { 1008 Entry<?, ?> entry = (Entry<?, ?>) obj; 1009 return entry.getKey() != null && entry.getValue() instanceof Map 1010 && Collections2.safeContains(backingMap.entrySet(), entry); 1011 } 1012 return false; 1013 } 1014 1015 @Override 1016 public boolean remove(Object obj) { 1017 if (obj instanceof Entry) { 1018 Entry<?, ?> entry = (Entry<?, ?>) obj; 1019 return entry.getKey() != null && entry.getValue() instanceof Map 1020 && backingMap.entrySet().remove(entry); 1021 } 1022 return false; 1023 } 1024 } 1025 } 1026 1027 private transient ColumnMap columnMap; 1028 1029 public Map<C, Map<R, V>> columnMap() { 1030 ColumnMap result = columnMap; 1031 return (result == null) ? columnMap = new ColumnMap() : result; 1032 } 1033 1034 private class ColumnMap extends Maps.ImprovedAbstractMap<C, Map<R, V>> { 1035 // The cast to C occurs only when the key is in the map, implying that it 1036 // has the correct type. 1037 @Override 1038 @SuppressWarnings("unchecked") 1039 public Map<R, V> get(Object key) { 1040 return containsColumn(key) ? column((C) key) : null; 1041 } 1042 1043 @Override 1044 public boolean containsKey(Object key) { 1045 return containsColumn(key); 1046 } 1047 1048 @Override 1049 public Map<R, V> remove(Object key) { 1050 return containsColumn(key) ? removeColumn(key) : null; 1051 } 1052 1053 @Override 1054 public Set<Entry<C, Map<R, V>>> createEntrySet() { 1055 return new ColumnMapEntrySet(); 1056 } 1057 1058 @Override 1059 public Set<C> keySet() { 1060 return columnKeySet(); 1061 } 1062 1063 ColumnMapValues columnMapValues; 1064 1065 @Override 1066 public Collection<Map<R, V>> values() { 1067 ColumnMapValues result = columnMapValues; 1068 return (result == null) ? columnMapValues = new ColumnMapValues() : result; 1069 } 1070 1071 class ColumnMapEntrySet extends TableSet<Entry<C, Map<R, V>>> { 1072 @Override 1073 public Iterator<Entry<C, Map<R, V>>> iterator() { 1074 return new TransformedIterator<C, Entry<C, Map<R, V>>>(columnKeySet().iterator()) { 1075 1076 @Override 1077 Entry<C, Map<R, V>> transform(C columnKey) { 1078 return new ImmutableEntry<C, Map<R, V>>(columnKey, column(columnKey)); 1079 } 1080 }; 1081 } 1082 1083 @Override 1084 public int size() { 1085 return columnKeySet().size(); 1086 } 1087 1088 @Override 1089 public boolean contains(Object obj) { 1090 if (obj instanceof Entry) { 1091 Entry<?, ?> entry = (Entry<?, ?>) obj; 1092 if (containsColumn(entry.getKey())) { 1093 // The cast to C occurs only when the key is in the map, implying 1094 // that it has the correct type. 1095 @SuppressWarnings("unchecked") 1096 C columnKey = (C) entry.getKey(); 1097 return get(columnKey).equals(entry.getValue()); 1098 } 1099 } 1100 return false; 1101 } 1102 1103 @Override 1104 public boolean remove(Object obj) { 1105 if (contains(obj)) { 1106 Entry<?, ?> entry = (Entry<?, ?>) obj; 1107 removeColumn(entry.getKey()); 1108 return true; 1109 } 1110 return false; 1111 } 1112 1113 @Override 1114 public boolean removeAll(Collection<?> c) { 1115 boolean changed = false; 1116 for (Object obj : c) { 1117 changed |= remove(obj); 1118 } 1119 return changed; 1120 } 1121 1122 @Override 1123 public boolean retainAll(Collection<?> c) { 1124 boolean changed = false; 1125 for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) { 1126 if (!c.contains(new ImmutableEntry<C, Map<R, V>>(columnKey, column(columnKey)))) { 1127 removeColumn(columnKey); 1128 changed = true; 1129 } 1130 } 1131 return changed; 1132 } 1133 } 1134 1135 private class ColumnMapValues extends TableCollection<Map<R, V>> { 1136 @Override 1137 public Iterator<Map<R, V>> iterator() { 1138 return Maps.valueIterator(ColumnMap.this.entrySet().iterator()); 1139 } 1140 1141 @Override 1142 public boolean remove(Object obj) { 1143 for (Entry<C, Map<R, V>> entry : ColumnMap.this.entrySet()) { 1144 if (entry.getValue().equals(obj)) { 1145 removeColumn(entry.getKey()); 1146 return true; 1147 } 1148 } 1149 return false; 1150 } 1151 1152 @Override 1153 public boolean removeAll(Collection<?> c) { 1154 checkNotNull(c); 1155 boolean changed = false; 1156 for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) { 1157 if (c.contains(column(columnKey))) { 1158 removeColumn(columnKey); 1159 changed = true; 1160 } 1161 } 1162 return changed; 1163 } 1164 1165 @Override 1166 public boolean retainAll(Collection<?> c) { 1167 checkNotNull(c); 1168 boolean changed = false; 1169 for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) { 1170 if (!c.contains(column(columnKey))) { 1171 removeColumn(columnKey); 1172 changed = true; 1173 } 1174 } 1175 return changed; 1176 } 1177 1178 @Override 1179 public int size() { 1180 return columnKeySet().size(); 1181 } 1182 } 1183 } 1184 1185 private static final long serialVersionUID = 0; 1186} 1187