001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005 * use this file except in compliance with the License. You may obtain a copy of
006 * 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, WITHOUT
012 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013 * License for the specific language governing permissions and limitations under
014 * the License.
015 */
016
017package com.google.common.collect;
018
019import com.google.common.annotations.Beta;
020import com.google.common.annotations.GwtCompatible;
021
022import java.util.Collection;
023import java.util.Comparator;
024import java.util.Iterator;
025import java.util.NavigableSet;
026import java.util.Set;
027
028/**
029 * A {@link Multiset} which maintains the ordering of its elements, according to
030 * either their natural order or an explicit {@link Comparator}. This order is
031 * reflected when iterating over the sorted multiset, either directly, or through
032 * its {@code elementSet} or {@code entrySet} views.  In all cases,
033 * this implementation uses {@link Comparable#compareTo} or
034 * {@link Comparator#compare} instead of {@link Object#equals} to determine
035 * equivalence of instances.
036 *
037 * <p><b>Warning:</b> The comparison must be <i>consistent with equals</i> as
038 * explained by the {@link Comparable} class specification. Otherwise, the
039 * resulting multiset will violate the {@link Collection} contract, which it is
040 * specified in terms of {@link Object#equals}.
041 *
042 * <p>See the Guava User Guide article on <a href=
043 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multiset">
044 * {@code Multiset}</a>.
045 *
046 * @author Louis Wasserman
047 * @since 11.0
048 */
049@Beta
050@GwtCompatible(emulated = true)
051public interface SortedMultiset<E> extends SortedMultisetBridge<E>, SortedIterable<E> {
052  /**
053   * Returns the comparator that orders this multiset, or
054   * {@link Ordering#natural()} if the natural ordering of the elements is used.
055   */
056  Comparator<? super E> comparator();
057
058  /**
059   * Returns the entry of the first element in this multiset, or {@code null} if
060   * this multiset is empty.
061   */
062  Entry<E> firstEntry();
063
064  /**
065   * Returns the entry of the last element in this multiset, or {@code null} if
066   * this multiset is empty.
067   */
068  Entry<E> lastEntry();
069
070  /**
071   * Returns and removes the entry associated with the lowest element in this
072   * multiset, or returns {@code null} if this multiset is empty.
073   */
074  Entry<E> pollFirstEntry();
075
076  /**
077   * Returns and removes the entry associated with the greatest element in this
078   * multiset, or returns {@code null} if this multiset is empty.
079   */
080  Entry<E> pollLastEntry();
081
082  /**
083   * Returns a {@link NavigableSet} view of the distinct elements in this multiset.
084   *
085   * @since 14.0 (present with return type {@code SortedSet} since 11.0)
086   */
087  @Override
088  NavigableSet<E> elementSet();
089
090  /**
091   * {@inheritDoc}
092   *
093   * <p>The {@code entrySet}'s iterator returns entries in ascending element
094   * order according to the this multiset's comparator.
095   */
096  @Override
097  Set<Entry<E>> entrySet();
098
099  /**
100   * {@inheritDoc}
101   *
102   * <p>The iterator returns the elements in ascending order according to this
103   * multiset's comparator.
104   */
105  @Override
106  Iterator<E> iterator();
107
108  /**
109   * Returns a descending view of this multiset. Modifications made to either
110   * map will be reflected in the other.
111   */
112  SortedMultiset<E> descendingMultiset();
113
114  /**
115   * Returns a view of this multiset restricted to the elements less than
116   * {@code upperBound}, optionally including {@code upperBound} itself. The
117   * returned multiset is a view of this multiset, so changes to one will be
118   * reflected in the other. The returned multiset supports all operations that
119   * this multiset supports.
120   *
121   * <p>The returned multiset will throw an {@link IllegalArgumentException} on
122   * attempts to add elements outside its range.
123   */
124  SortedMultiset<E> headMultiset(E upperBound, BoundType boundType);
125
126  /**
127   * Returns a view of this multiset restricted to the range between
128   * {@code lowerBound} and {@code upperBound}. The returned multiset is a view
129   * of this multiset, so changes to one will be reflected in the other. The
130   * returned multiset supports all operations that this multiset supports.
131   *
132   * <p>The returned multiset will throw an {@link IllegalArgumentException} on
133   * attempts to add elements outside its range.
134   *
135   * <p>This method is equivalent to
136   * {@code tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound,
137   * upperBoundType)}.
138   */
139  SortedMultiset<E> subMultiset(
140      E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType);
141
142  /**
143   * Returns a view of this multiset restricted to the elements greater than
144   * {@code lowerBound}, optionally including {@code lowerBound} itself. The
145   * returned multiset is a view of this multiset, so changes to one will be
146   * reflected in the other. The returned multiset supports all operations that
147   * this multiset supports.
148   *
149   * <p>The returned multiset will throw an {@link IllegalArgumentException} on
150   * attempts to add elements outside its range.
151   */
152  SortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType);
153}