Open Source Repository

Home /guava/guava-10.0 | Repository Home


com/google/common/collect/TreeMultiset.java
/*
 * Copyright (C) 2007 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.checkNotNull;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;

import javax.annotation.Nullable;

/**
 * A multiset which maintains the ordering of its elements, according to either
 * their natural order or an explicit {@link Comparator}. In all cases, this
 * implementation uses {@link Comparable#compareTo} or {@link
 * Comparator#compare} instead of {@link Object#equals} to determine
 * equivalence of instances.
 *
 <p><b>Warning:</b> The comparison must be <i>consistent with equals</i> as
 * explained by the {@link Comparable} class specification. Otherwise, the
 * resulting multiset will violate the {@link java.util.Collection} contract,
 * which is specified in terms of {@link Object#equals}.
 *
 @author Neal Kanodia
 @author Jared Levy
 @since 2.0 (imported from Google Collections Library)
 */
@GwtCompatible(emulated = true)
@SuppressWarnings("serial"// we're overriding default serialization
public final class TreeMultiset<E> extends AbstractMapBasedMultiset<E>
    implements SortedIterable<E> {

  /**
   * Creates a new, empty multiset, sorted according to the elements' natural
   * order. All elements inserted into the multiset must implement the
   * {@code Comparable} interface. Furthermore, all such elements must be
   <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a
   * {@code ClassCastException} for any elements {@code e1} and {@code e2} in
   * the multiset. If the user attempts to add an element to the multiset that
   * violates this constraint (for example, the user attempts to add a string
   * element to a set whose elements are integers), the {@code add(Object)}
   * call will throw a {@code ClassCastException}.
   *
   <p>The type specification is {@code <E extends Comparable>}, instead of the
   * more specific {@code <E extends Comparable<? super E>>}, to support
   * classes defined without generics.
   */
  public static <E extends Comparable> TreeMultiset<E> create() {
    return new TreeMultiset<E>();
  }

  /**
   * Creates a new, empty multiset, sorted according to the specified
   * comparator. All elements inserted into the multiset must be <i>mutually
   * comparable</i> by the specified comparator: {@code comparator.compare(e1,
   * e2)} must not throw a {@code ClassCastException} for any elements {@code
   * e1} and {@code e2} in the multiset. If the user attempts to add an element
   * to the multiset that violates this constraint, the {@code add(Object)} call
   * will throw a {@code ClassCastException}.
   *
   @param comparator the comparator that will be used to sort this multiset. A
   *     null value indicates that the elements' <i>natural ordering</i> should
   *     be used.
   */
  public static <E> TreeMultiset<E> create(
      @Nullable Comparator<? super E> comparator) {

    return (comparator == null
           new TreeMultiset<E>()
           new TreeMultiset<E>(comparator);
  }

  /**
   * Returns an iterator over the elements contained in this collection.
   */
  @Override
  public Iterator<E> iterator() {
    // Needed to avoid Javadoc bug.
    return super.iterator();
  }

  /**
   * Creates an empty multiset containing the given initial elements, sorted
   * according to the elements' natural order.
   *
   <p>This implementation is highly efficient when {@code elements} is itself
   * a {@link Multiset}.
   *
   <p>The type specification is {@code <E extends Comparable>}, instead of the
   * more specific {@code <E extends Comparable<? super E>>}, to support
   * classes defined without generics.
   */
  public static <E extends Comparable> TreeMultiset<E> create(
      Iterable<? extends E> elements) {
    TreeMultiset<E> multiset = create();
    Iterables.addAll(multiset, elements);
    return multiset;
  }

  private final Comparator<? super E> comparator;
  
  @SuppressWarnings("unchecked")
  private TreeMultiset() {
    this((ComparatorOrdering.natural());
  }

  private TreeMultiset(@Nullable Comparator<? super E> comparator) {
    super(new TreeMap<E, Count>(checkNotNull(comparator)));
    this.comparator = comparator;
  }

  /**
   * Returns the comparator associated with this multiset.
   *
   @since 11.0
   */
  @Override
  public Comparator<? super E> comparator() {
    return comparator;
  }

  /**
   * {@inheritDoc}
   *
   <p>In {@code TreeMultiset}, the return type of this method is narrowed
   * from {@link Set} to {@link SortedSet}.
   */
  @Override public SortedSet<E> elementSet() {
    return (SortedSet<E>super.elementSet();
  }

  @Override public int count(@Nullable Object element) {
    try {
      return super.count(element);
    catch (NullPointerException e) {
      return 0;
    catch (ClassCastException e) {
      return 0;
    }
  }

  @Override
  public int add(E element, int occurrences) {
    if (element == null) {
      comparator.compare(element, element);
    }
    return super.add(element, occurrences);
  }

  @Override Set<E> createElementSet() {
    return new SortedMapBasedElementSet(
        (SortedMap<E, Count>backingMap());
  }

  private class SortedMapBasedElementSet extends MapBasedElementSet
      implements SortedSet<E>, SortedIterable<E> {

    SortedMapBasedElementSet(SortedMap<E, Count> map) {
      super(map);
    }

    SortedMap<E, Count> sortedMap() {
      return (SortedMap<E, Count>getMap();
    }

    /**
     * {@inheritDoc}
     *
     @since 10.0
     */
    @Override
    public Comparator<? super E> comparator() {
      return sortedMap().comparator();
    }

    @Override
    public E first() {
      return sortedMap().firstKey();
    }

    @Override
    public E last() {
      return sortedMap().lastKey();
    }

    @Override
    public SortedSet<E> headSet(E toElement) {
      return new SortedMapBasedElementSet(sortedMap().headMap(toElement));
    }

    @Override
    public SortedSet<E> subSet(E fromElement, E toElement) {
      return new SortedMapBasedElementSet(
          sortedMap().subMap(fromElement, toElement));
    }

    @Override
    public SortedSet<E> tailSet(E fromElement) {
      return new SortedMapBasedElementSet(sortedMap().tailMap(fromElement));
    }

    @Override public boolean remove(Object element) {
      try {
        return super.remove(element);
      catch (NullPointerException e) {
        return false;
      catch (ClassCastException e) {
        return false;
      }
    }
  }

  /*
   * TODO(jlevy): Decide whether entrySet() should return entries with an
   * equals() method that calls the comparator to compare the two keys. If that
   * change is made, AbstractMultiset.equals() can simply check whether two
   * multisets have equal entry sets.
   */

  /**
   @serialData the comparator, the number of distinct elements, the first
   *     element, its count, the second element, its count, and so on
   */
  @GwtIncompatible("java.io.ObjectOutputStream")
  private void writeObject(ObjectOutputStream streamthrows IOException {
    stream.defaultWriteObject();
    stream.writeObject(elementSet().comparator());
    Serialization.writeMultiset(this, stream);
  }

  @GwtIncompatible("java.io.ObjectInputStream")
  private void readObject(ObjectInputStream stream)
      throws IOException, ClassNotFoundException {
    stream.defaultReadObject();
    @SuppressWarnings("unchecked"// reading data stored by writeObject
    Comparator<? super E> comparator
        (Comparator<? super E>stream.readObject();
    setBackingMap(new TreeMap<E, Count>(comparator));
    Serialization.populateMultiset(this, stream);
  }

  @GwtIncompatible("not needed in emulated source")
  private static final long serialVersionUID = 0;
}