    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
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkArgument;
    020    import static com.google.common.base.Preconditions.checkNotNull;
    021
    022    import com.google.common.annotations.Beta;
    023    import com.google.common.annotations.GwtCompatible;
    024    import com.google.common.base.Function;
    025    import com.google.common.base.Supplier;
    026
    027    import java.io.Serializable;
    028    import java.util.Comparator;
    029    import java.util.Iterator;
    030    import java.util.Map;
    031    import java.util.NoSuchElementException;
    032    import java.util.PriorityQueue;
    033    import java.util.Queue;
    034    import java.util.Set;
    035    import java.util.SortedMap;
    036    import java.util.SortedSet;
    037    import java.util.TreeMap;
    038
    039    import javax.annotation.Nullable;
    040
    041    /**
    042     * Implementation of {@code Table} whose row keys and column keys are ordered
    043     * by their natural ordering or by supplied comparators. When constructing a
    044     * {@code TreeBasedTable}, you may provide comparators for the row keys and
    045     * the column keys, or you may use natural ordering for both.
    046     *
    047     * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link
    048     * #rowMap} method returns a {@link SortedMap}, instead of the {@link Set} and
    049     * {@link Map} specified by the {@link Table} interface.
    050     *
    051     * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link
    052     * #columnMap()} have iterators that don't support {@code remove()}. Otherwise,
    053     * all optional operations are supported. Null row keys, columns keys, and
    054     * values are not supported.
    055     *
    056     * <p>Lookups by row key are often faster than lookups by column key, because
    057     * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code
    058     * column(columnKey).get(rowKey)} still runs quickly, since the row key is
    059     * provided. However, {@code column(columnKey).size()} takes longer, since an
    060     * iteration across all row keys occurs.
    061     *
    062     * <p>Because a {@code TreeBasedTable} has unique sorted values for a given
    063     * row, both {@code row(rowKey)} and {@code rowMap().get(rowKey)} are {@link
    064     * SortedMap} instances, instead of the {@link Map} specified in the {@link
    065     * Table} interface.
    066     *
    067     * <p>Note that this implementation is not synchronized. If multiple threads
    068     * access this table concurrently and one of the threads modifies the table, it
    069     * must be synchronized externally.
    070     *
    071     * @author Jared Levy
    072     * @author Louis Wasserman
    073     * @since 7.0
    074     */
    075    @GwtCompatible(serializable = true)
    076    @Beta
    077    public class TreeBasedTable<R, C, V> extends StandardRowSortedTable<R, C, V> {
    078      private final Comparator<? super C> columnComparator;
    079
    080      private static class Factory<C, V>
    081          implements Supplier<TreeMap<C, V>>, Serializable {
    082        final Comparator<? super C> comparator;
    083        Factory(Comparator<? super C> comparator) {
    084          this.comparator = comparator;
    085        }
    086        @Override
    087        public TreeMap<C, V> get() {
    088          return new TreeMap<C, V>(comparator);
    089        }
    090        private static final long serialVersionUID = 0;
    091      }
    092
    093      /**
    094       * Creates an empty {@code TreeBasedTable} that uses the natural orderings
    095       * of both row and column keys.
    096       *
    097       * <p>The method signature specifies {@code R extends Comparable} with a raw
    098       * {@link Comparable}, instead of {@code R extends Comparable<? super R>},
    099       * and the same for {@code C}. That's necessary to support classes defined
    100       * without generics.
    101       */
    102      public static <R extends Comparable, C extends Comparable, V>
    103          TreeBasedTable<R, C, V> create() {
    104        return new TreeBasedTable<R, C, V>(Ordering.natural(),
    105            Ordering.natural());
    106      }
    107
    108      /**
    109       * Creates an empty {@code TreeBasedTable} that is ordered by the specified
    110       * comparators.
    111       *
    112       * @param rowComparator the comparator that orders the row keys
    113       * @param columnComparator the comparator that orders the column keys
    114       */
    115      public static <R, C, V> TreeBasedTable<R, C, V> create(
    116          Comparator<? super R> rowComparator,
    117          Comparator<? super C> columnComparator) {
    118        checkNotNull(rowComparator);
    119        checkNotNull(columnComparator);
    120        return new TreeBasedTable<R, C, V>(rowComparator, columnComparator);
    121      }
    122
    123      /**
    124       * Creates a {@code TreeBasedTable} with the same mappings and sort order
    125       * as the specified {@code TreeBasedTable}.
    126       */
    127      public static <R, C, V> TreeBasedTable<R, C, V> create(
    128          TreeBasedTable<R, C, ? extends V> table) {
    129        TreeBasedTable<R, C, V> result
    130            = new TreeBasedTable<R, C, V>(
    131                table.rowComparator(), table.columnComparator());
    132        result.putAll(table);
    133        return result;
    134      }
    135
    136      TreeBasedTable(Comparator<? super R> rowComparator,
    137          Comparator<? super C> columnComparator) {
    138        super(new TreeMap<R, Map<C, V>>(rowComparator),
    139            new Factory<C, V>(columnComparator));
    140        this.columnComparator = columnComparator;
    141      }
    142
    143      // TODO(jlevy): Move to StandardRowSortedTable?
    144
    145      /**
    146       * Returns the comparator that orders the rows. With natural ordering,
    147       * {@link Ordering#natural()} is returned.
    148       */
    149      public Comparator<? super R> rowComparator() {
    150        return rowKeySet().comparator();
    151      }
    152
    153      /**
    154       * Returns the comparator that orders the columns. With natural ordering,
    155       * {@link Ordering#natural()} is returned.
    156       */
    157      public Comparator<? super C> columnComparator() {
    158        return columnComparator;
    159      }
    160
    161      // TODO(user): make column return a SortedMap
    162
    163      /**
    164       * {@inheritDoc}
    165       *
    166       * <p>Because a {@code TreeBasedTable} has unique sorted values for a given
    167       * row, this method returns a {@link SortedMap}, instead of the {@link Map}
    168       * specified in the {@link Table} interface.
    169       * @since 10.0
    170       *     (<a href="http://code.google.com/p/guava-libraries/wiki/Compatibility"
    171       *     >mostly source-compatible</a> since 7.0)
    172       */
    173      @Override
    174      public SortedMap<C, V> row(R rowKey) {
    175        return new TreeRow(rowKey);
    176      }
    177
    178      private class TreeRow extends Row implements SortedMap<C, V> {
    179        @Nullable final C lowerBound;
    180        @Nullable final C upperBound;
    181
    182        TreeRow(R rowKey) {
    183          this(rowKey, null, null);
    184        }
    185
    186        TreeRow(R rowKey, @Nullable C lowerBound, @Nullable C upperBound) {
    187          super(rowKey);
    188          this.lowerBound = lowerBound;
    189          this.upperBound = upperBound;
    190          checkArgument(lowerBound == null || upperBound == null
    191              || compare(lowerBound, upperBound) <= 0);
    192        }
    193
    194        @Override public Comparator<? super C> comparator() {
    195          return columnComparator();
    196        }
    197
    198        int compare(Object a, Object b) {
    199          // pretend we can compare anything
    200          @SuppressWarnings({"rawtypes", "unchecked"})
    201          Comparator<Object> cmp = (Comparator) comparator();
    202          return cmp.compare(a, b);
    203        }
    204
    205        boolean rangeContains(@Nullable Object o) {
    206          return o != null && (lowerBound == null || compare(lowerBound, o) <= 0)
    207              && (upperBound == null || compare(upperBound, o) > 0);
    208        }
    209
    210        @Override public SortedMap<C, V> subMap(C fromKey, C toKey) {
    211          checkArgument(rangeContains(checkNotNull(fromKey))
    212              && rangeContains(checkNotNull(toKey)));
    213          return new TreeRow(rowKey, fromKey, toKey);
    214        }
    215
    216        @Override public SortedMap<C, V> headMap(C toKey) {
    217          checkArgument(rangeContains(checkNotNull(toKey)));
    218          return new TreeRow(rowKey, lowerBound, toKey);
    219        }
    220
    221        @Override public SortedMap<C, V> tailMap(C fromKey) {
    222          checkArgument(rangeContains(checkNotNull(fromKey)));
    223          return new TreeRow(rowKey, fromKey, upperBound);
    224        }
    225
    226        @Override public C firstKey() {
    227          SortedMap<C, V> backing = backingRowMap();
    228          if (backing == null) {
    229            throw new NoSuchElementException();
    230          }
    231          return backingRowMap().firstKey();
    232        }
    233
    234        @Override public C lastKey() {
    235          SortedMap<C, V> backing = backingRowMap();
    236          if (backing == null) {
    237            throw new NoSuchElementException();
    238          }
    239          return backingRowMap().lastKey();
    240        }
    241
    242        transient SortedMap<C, V> wholeRow;
    243
    244        /*
    245         * If the row was previously empty, we check if there's a new row here every
    246         * time we're queried.
    247         */
    248        SortedMap<C, V> wholeRow() {
    249          if (wholeRow == null
    250              || (wholeRow.isEmpty() && backingMap.containsKey(rowKey))) {
    251            wholeRow = (SortedMap<C, V>) backingMap.get(rowKey);
    252          }
    253          return wholeRow;
    254        }
    255
    256        @Override
    257        SortedMap<C, V> backingRowMap() {
    258          return (SortedMap<C, V>) super.backingRowMap();
    259        }
    260
    261        @Override
    262        SortedMap<C, V> computeBackingRowMap() {
    263          SortedMap<C, V> map = wholeRow();
    264          if (map != null) {
    265            if (lowerBound != null) {
    266              map = map.tailMap(lowerBound);
    267            }
    268            if (upperBound != null) {
    269              map = map.headMap(upperBound);
    270            }
    271            return map;
    272          }
    273          return null;
    274        }
    275
    276        @Override
    277        void maintainEmptyInvariant() {
    278          if (wholeRow() != null && wholeRow.isEmpty()) {
    279            backingMap.remove(rowKey);
    280            wholeRow = null;
    281            backingRowMap = null;
    282          }
    283        }
    284
    285        @Override public boolean containsKey(Object key) {
    286          return rangeContains(key) && super.containsKey(key);
    287        }
    288
    289        @Override public V put(C key, V value) {
    290          checkArgument(rangeContains(checkNotNull(key)));
    291          return super.put(key, value);
    292        }
    293      }
    294
    295      // rowKeySet() and rowMap() are defined here so they appear in the Javadoc.
    296
    297      @Override public SortedSet<R> rowKeySet() {
    298        return super.rowKeySet();
    299      }
    300
    301      @Override public SortedMap<R, Map<C, V>> rowMap() {
    302        return super.rowMap();
    303      }
    304
    305      // Overriding so NullPointerTester test passes.
    306
    307      @Override public boolean contains(
    308          @Nullable Object rowKey, @Nullable Object columnKey) {
    309        return super.contains(rowKey, columnKey);
    310      }
    311
    312      @Override public boolean containsColumn(@Nullable Object columnKey) {
    313        return super.containsColumn(columnKey);
    314      }
    315
    316      @Override public boolean containsRow(@Nullable Object rowKey) {
    317        return super.containsRow(rowKey);
    318      }
    319
    320      @Override public boolean containsValue(@Nullable Object value) {
    321        return super.containsValue(value);
    322      }
    323
    324      @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
    325        return super.get(rowKey, columnKey);
    326      }
    327
    328      @Override public boolean equals(@Nullable Object obj) {
    329        return super.equals(obj);
    330      }
    331
    332      @Override public V remove(
    333          @Nullable Object rowKey, @Nullable Object columnKey) {
    334        return super.remove(rowKey, columnKey);
    335      }
    336
    337      /**
    338       * Overridden column iterator to return columns values in globally sorted
    339       * order.
    340       */
    341      @Override Iterator<C> createColumnKeyIterator() {
    342        return new MergingIterator<C>(
    343            Iterables.transform(backingMap.values(),
    344                new Function<Map<C, V>, Iterator<C>>() {
    345                    @Override
    346                    public Iterator<C> apply(Map<C, V> input) {
    347                      return input.keySet().iterator();
    348                    }
    349                  }), columnComparator());
    350      }
    351
    352      /**
    353       * An iterator that performs a lazy N-way merge, calculating the next value
    354       * each time the iterator is polled. This amortizes the sorting cost over the
    355       * iteration and requires less memory than sorting all elements at once.
    356       * Duplicate values are omitted.
    357       *
    358       * <p>Retrieving a single element takes approximately O(log(M)) time, where M
    359       * is the number of iterators. (Retrieving all elements takes approximately
    360       * O(N*log(M)) time, where N is the total number of elements.)
    361       */
    362      // TODO(user): Push this into OrderedIterators or somewhere more generic.
    363      private static class MergingIterator<T> extends AbstractIterator<T> {
    364        private final Queue<PeekingIterator<T>> queue;
    365        private final Comparator<? super T> comparator;
    366
    367        // The last value we returned, used for removing duplicate values.
    368        private T lastValue = null;
    369
    370        public MergingIterator(
    371            Iterable<? extends Iterator<T>> iterators,
    372            Comparator<? super T> itemComparator) {
    373    //    checkNotNull(iterators, "iterators");
    374    //    checkNotNull(comparator, "comparator");
    375          this.comparator = itemComparator;
    376
    377          // A comparator that's used by the heap, allowing the heap
    378          // to be sorted based on the top of each iterator.
    379          Comparator<PeekingIterator<T>> heapComparator =
    380              new Comparator<PeekingIterator<T>>() {
    381                @Override
    382                public int compare(PeekingIterator<T> o1, PeekingIterator<T> o2) {
    383                  return comparator.compare(o1.peek(), o2.peek());
    384                }
    385              };
    386
    387          // Construct the heap with a minimum size of 1, because
    388          // Because PriorityQueue will fail if it's 0.
    389          queue = new PriorityQueue<PeekingIterator<T>>(
    390              Math.max(1, Iterables.size(iterators)), heapComparator);
    391          for (Iterator<T> iterator : iterators) {
    392            if (iterator.hasNext()) {
    393              queue.add(Iterators.peekingIterator(iterator));
    394            }
    395          }
    396        }
    397
    398        @Override protected T computeNext() {
    399          while (!queue.isEmpty()) {
    400            PeekingIterator<T> nextIter = queue.poll();
    401
    402            T next = nextIter.next();
    403            boolean duplicate =
    404                lastValue != null
    405                && comparator.compare(next, lastValue) == 0;
    406
    407            if (nextIter.hasNext()) {
    408              queue.add(nextIter);
    409            }
    410            // Keep looping till we find a non-duplicate value.
    411            if (!duplicate) {
    412              lastValue = next;
    413              return lastValue;
    414            }
    415          }
    416
    417          lastValue = null; // clear reference to unused data
    418          return endOfData();
    419        }
    420      }
    421
    422      private static final long serialVersionUID = 0;
    423    }