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