Open Source Repository

Home /guava/guava-10.0 | Repository Home


com/google/common/collect/TreeBasedTable.java
/*
 * Copyright (C) 2008 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Function;
import com.google.common.base.Supplier;

import java.io.Serializable;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;

import javax.annotation.Nullable;

/**
 * Implementation of {@code Table} whose row keys and column keys are ordered
 * by their natural ordering or by supplied comparators. When constructing a
 * {@code TreeBasedTable}, you may provide comparators for the row keys and
 * the column keys, or you may use natural ordering for both.
 *
 <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link
 * #rowMap} method returns a {@link SortedMap}, instead of the {@link Set} and
 {@link Map} specified by the {@link Table} interface.
 *
 <p>The views returned by {@link #column}{@link #columnKeySet()}, and {@link
 * #columnMap()} have iterators that don't support {@code remove()}. Otherwise,
 * all optional operations are supported. Null row keys, columns keys, and
 * values are not supported.
 *
 <p>Lookups by row key are often faster than lookups by column key, because
 * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code
 * column(columnKey).get(rowKey)} still runs quickly, since the row key is
 * provided. However, {@code column(columnKey).size()} takes longer, since an
 * iteration across all row keys occurs.
 *
 <p>Because a {@code TreeBasedTable} has unique sorted values for a given
 * row, both {@code row(rowKey)} and {@code rowMap().get(rowKey)} are {@link
 * SortedMap} instances, instead of the {@link Map} specified in the {@link
 * Table} interface.
 *
 <p>Note that this implementation is not synchronized. If multiple threads
 * access this table concurrently and one of the threads modifies the table, it
 * must be synchronized externally.
 *
 @author Jared Levy
 @author Louis Wasserman
 @since 7.0
 */
@GwtCompatible(serializable = true)
@Beta
public class TreeBasedTable<R, C, V> extends StandardRowSortedTable<R, C, V> {
  private final Comparator<? super C> columnComparator;

  private static class Factory<C, V>
      implements Supplier<TreeMap<C, V>>, Serializable {
    final Comparator<? super C> comparator;
    Factory(Comparator<? super C> comparator) {
      this.comparator = comparator;
    }
    @Override
    public TreeMap<C, V> get() {
      return new TreeMap<C, V>(comparator);
    }
    private static final long serialVersionUID = 0;
  }

  /**
   * Creates an empty {@code TreeBasedTable} that uses the natural orderings
   * of both row and column keys.
   *
   <p>The method signature specifies {@code R extends Comparable} with a raw
   {@link Comparable}, instead of {@code R extends Comparable<? super R>},
   * and the same for {@code C}. That's necessary to support classes defined
   * without generics.
   */
  public static <R extends Comparable, C extends Comparable, V>
      TreeBasedTable<R, C, V> create() {
    return new TreeBasedTable<R, C, V>(Ordering.natural(),
        Ordering.natural());
  }

  /**
   * Creates an empty {@code TreeBasedTable} that is ordered by the specified
   * comparators.
   *
   @param rowComparator the comparator that orders the row keys
   @param columnComparator the comparator that orders the column keys
   */
  public static <R, C, V> TreeBasedTable<R, C, V> create(
      Comparator<? super R> rowComparator,
      Comparator<? super C> columnComparator) {
    checkNotNull(rowComparator);
    checkNotNull(columnComparator);
    return new TreeBasedTable<R, C, V>(rowComparator, columnComparator);
  }

  /**
   * Creates a {@code TreeBasedTable} with the same mappings and sort order
   * as the specified {@code TreeBasedTable}.
   */
  public static <R, C, V> TreeBasedTable<R, C, V> create(
      TreeBasedTable<R, C, ? extends V> table) {
    TreeBasedTable<R, C, V> result
        new TreeBasedTable<R, C, V>(
            table.rowComparator(), table.columnComparator());
    result.putAll(table);
    return result;
  }

  TreeBasedTable(Comparator<? super R> rowComparator,
      Comparator<? super C> columnComparator) {
    super(new TreeMap<R, Map<C, V>>(rowComparator),
        new Factory<C, V>(columnComparator));
    this.columnComparator = columnComparator;
  }

  // TODO(jlevy): Move to StandardRowSortedTable?

  /**
   * Returns the comparator that orders the rows. With natural ordering,
   {@link Ordering#natural()} is returned.
   */
  public Comparator<? super R> rowComparator() {
    return rowKeySet().comparator();
  }

  /**
   * Returns the comparator that orders the columns. With natural ordering,
   {@link Ordering#natural()} is returned.
   */
  public Comparator<? super C> columnComparator() {
    return columnComparator;
  }

  // TODO(user): make column return a SortedMap

  /**
   * {@inheritDoc}
   *
   <p>Because a {@code TreeBasedTable} has unique sorted values for a given
   * row, this method returns a {@link SortedMap}, instead of the {@link Map}
   * specified in the {@link Table} interface.
   @since 10.0
   *     (<a href="http://code.google.com/p/guava-libraries/wiki/Compatibility"
   *     >mostly source-compatible</a> since 7.0)
   */
  @Override
  public SortedMap<C, V> row(R rowKey) {
    return new TreeRow(rowKey);
  }

  private class TreeRow extends Row implements SortedMap<C, V> {
    @Nullable final C lowerBound;
    @Nullable final C upperBound;

    TreeRow(R rowKey) {
      this(rowKey, null, null);
    }

    TreeRow(R rowKey, @Nullable C lowerBound, @Nullable C upperBound) {
      super(rowKey);
      this.lowerBound = lowerBound;
      this.upperBound = upperBound;
      checkArgument(lowerBound == null || upperBound == null
          || compare(lowerBound, upperBound<= 0);
    }

    @Override public Comparator<? super C> comparator() {
      return columnComparator();
    }

    int compare(Object a, Object b) {
      // pretend we can compare anything
      @SuppressWarnings({"rawtypes""unchecked"})
      Comparator<Object> cmp = (Comparatorcomparator();
      return cmp.compare(a, b);
    }

    boolean rangeContains(@Nullable Object o) {
      return o != null && (lowerBound == null || compare(lowerBound, o<= 0)
          && (upperBound == null || compare(upperBound, o0);
    }

    @Override public SortedMap<C, V> subMap(C fromKey, C toKey) {
      checkArgument(rangeContains(checkNotNull(fromKey))
          && rangeContains(checkNotNull(toKey)));
      return new TreeRow(rowKey, fromKey, toKey);
    }

    @Override public SortedMap<C, V> headMap(C toKey) {
      checkArgument(rangeContains(checkNotNull(toKey)));
      return new TreeRow(rowKey, lowerBound, toKey);
    }

    @Override public SortedMap<C, V> tailMap(C fromKey) {
      checkArgument(rangeContains(checkNotNull(fromKey)));
      return new TreeRow(rowKey, fromKey, upperBound);
    }

    @Override public C firstKey() {
      SortedMap<C, V> backing = backingRowMap();
      if (backing == null) {
        throw new NoSuchElementException();
      }
      return backingRowMap().firstKey();
    }

    @Override public C lastKey() {
      SortedMap<C, V> backing = backingRowMap();
      if (backing == null) {
        throw new NoSuchElementException();
      }
      return backingRowMap().lastKey();
    }

    transient SortedMap<C, V> wholeRow;

    /*
     * If the row was previously empty, we check if there's a new row here every
     * time we're queried.
     */
    SortedMap<C, V> wholeRow() {
      if (wholeRow == null
          || (wholeRow.isEmpty() && backingMap.containsKey(rowKey))) {
        wholeRow = (SortedMap<C, V>backingMap.get(rowKey);
      }
      return wholeRow;
    }

    @Override
    SortedMap<C, V> backingRowMap() {
      return (SortedMap<C, V>super.backingRowMap();
    }

    @Override
    SortedMap<C, V> computeBackingRowMap() {
      SortedMap<C, V> map = wholeRow();
      if (map != null) {
        if (lowerBound != null) {
          map = map.tailMap(lowerBound);
        }
        if (upperBound != null) {
          map = map.headMap(upperBound);
        }
        return map;
      }
      return null;
    }

    @Override
    void maintainEmptyInvariant() {
      if (wholeRow() != null && wholeRow.isEmpty()) {
        backingMap.remove(rowKey);
        wholeRow = null;
        backingRowMap = null;
      }
    }

    @Override public boolean containsKey(Object key) {
      return rangeContains(key&& super.containsKey(key);
    }

    @Override public V put(C key, V value) {
      checkArgument(rangeContains(checkNotNull(key)));
      return super.put(key, value);
    }
  }

  // rowKeySet() and rowMap() are defined here so they appear in the Javadoc.

  @Override public SortedSet<R> rowKeySet() {
    return super.rowKeySet();
  }

  @Override public SortedMap<R, Map<C, V>> rowMap() {
    return super.rowMap();
  }

  // Overriding so NullPointerTester test passes.

  @Override public boolean contains(
      @Nullable Object rowKey, @Nullable Object columnKey) {
    return super.contains(rowKey, columnKey);
  }

  @Override public boolean containsColumn(@Nullable Object columnKey) {
    return super.containsColumn(columnKey);
  }

  @Override public boolean containsRow(@Nullable Object rowKey) {
    return super.containsRow(rowKey);
  }

  @Override public boolean containsValue(@Nullable Object value) {
    return super.containsValue(value);
  }

  @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
    return super.get(rowKey, columnKey);
  }

  @Override public boolean equals(@Nullable Object obj) {
    return super.equals(obj);
  }

  @Override public V remove(
      @Nullable Object rowKey, @Nullable Object columnKey) {
    return super.remove(rowKey, columnKey);
  }

  /**
   * Overridden column iterator to return columns values in globally sorted
   * order.
   */
  @Override Iterator<C> createColumnKeyIterator() {
    return new MergingIterator<C>(
        Iterables.transform(backingMap.values(),
            new Function<Map<C, V>, Iterator<C>>() {
                @Override
                public Iterator<C> apply(Map<C, V> input) {
                  return input.keySet().iterator();
                }
              }), columnComparator());
  }

  /**
   * An iterator that performs a lazy N-way merge, calculating the next value
   * each time the iterator is polled. This amortizes the sorting cost over the
   * iteration and requires less memory than sorting all elements at once.
   * Duplicate values are omitted.
   *
   <p>Retrieving a single element takes approximately O(log(M)) time, where M
   * is the number of iterators. (Retrieving all elements takes approximately
   * O(N*log(M)) time, where N is the total number of elements.)
   */
  // TODO(user): Push this into OrderedIterators or somewhere more generic.
  private static class MergingIterator<T> extends AbstractIterator<T> {
    private final Queue<PeekingIterator<T>> queue;
    private final Comparator<? super T> comparator;

    // The last value we returned, used for removing duplicate values.
    private T lastValue = null;

    public MergingIterator(
        Iterable<? extends Iterator<T>> iterators,
        Comparator<? super T> itemComparator) {
//    checkNotNull(iterators, "iterators");
//    checkNotNull(comparator, "comparator");
      this.comparator = itemComparator;

      // A comparator that's used by the heap, allowing the heap
      // to be sorted based on the top of each iterator.
      Comparator<PeekingIterator<T>> heapComparator =
          new Comparator<PeekingIterator<T>>() {
            @Override
            public int compare(PeekingIterator<T> o1, PeekingIterator<T> o2) {
              return comparator.compare(o1.peek(), o2.peek());
            }
          };

      // Construct the heap with a minimum size of 1, because
      // Because PriorityQueue will fail if it's 0.
      queue = new PriorityQueue<PeekingIterator<T>>(
          Math.max(1, Iterables.size(iterators)), heapComparator);
      for (Iterator<T> iterator : iterators) {
        if (iterator.hasNext()) {
          queue.add(Iterators.peekingIterator(iterator));
        }
      }
    }

    @Override protected T computeNext() {
      while (!queue.isEmpty()) {
        PeekingIterator<T> nextIter = queue.poll();

        T next = nextIter.next();
        boolean duplicate =
            lastValue != null
            && comparator.compare(next, lastValue== 0;

        if (nextIter.hasNext()) {
          queue.add(nextIter);
        }
        // Keep looping till we find a non-duplicate value.
        if (!duplicate) {
          lastValue = next;
          return lastValue;
        }
      }

      lastValue = null// clear reference to unused data
      return endOfData();
    }
  }

  private static final long serialVersionUID = 0;
}