11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * use this file except in compliance with the License. You may obtain a copy of 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * License for the specific language governing permissions and limitations under 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collection; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.SortedSet; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A {@link Multiset} which maintains the ordering of its elements, according to 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * either their natural order or an explicit {@link Comparator}. In all cases, 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this implementation uses {@link Comparable#compareTo} or 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Comparator#compare} instead of {@link Object#equals} to determine 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equivalence of instances. 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> The comparison must be <i>consistent with equals</i> as 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * explained by the {@link Comparable} class specification. Otherwise, the 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * resulting multiset will violate the {@link Collection} contract, which it is 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * specified in terms of {@link Object#equals}. 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@Beta 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic interface SortedMultiset<E> extends Multiset<E>, SortedIterable<E> { 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the comparator that orders this multiset, or 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Ordering#natural()} if the natural ordering of the elements is used. 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator(); 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the entry of the first element in this multiset, or {@code null} if 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this multiset is empty. 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> firstEntry(); 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the entry of the last element in this multiset, or {@code null} if 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this multiset is empty. 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> lastEntry(); 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns and removes the entry associated with the lowest element in this 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiset, or returns {@code null} if this multiset is empty. 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> pollFirstEntry(); 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns and removes the entry associated with the greatest element in this 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiset, or returns {@code null} if this multiset is empty. 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> pollLastEntry(); 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a {@link SortedSet} view of the distinct elements in this multiset. 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override SortedSet<E> elementSet(); 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@inheritDoc} 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The iterator returns the elements in ascending order according to this 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiset's comparator. 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override Iterator<E> iterator(); 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a descending view of this multiset. Modifications made to either 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * map will be reflected in the other. 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMultiset<E> descendingMultiset(); 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a view of this multiset restricted to the elements less than 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code upperBound}, optionally including {@code upperBound} itself. The 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned multiset is a view of this multiset, so changes to one will be 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * reflected in the other. The returned multiset supports all operations that 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this multiset supports. 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned multiset will throw an {@link IllegalArgumentException} on 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * attempts to add elements outside its range. 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMultiset<E> headMultiset(E upperBound, BoundType boundType); 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a view of this multiset restricted to the range between 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code lowerBound} and {@code upperBound}. The returned multiset is a view 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of this multiset, so changes to one will be reflected in the other. The 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned multiset supports all operations that this multiset supports. 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned multiset will throw an {@link IllegalArgumentException} on 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * attempts to add elements outside its range. 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method is equivalent to 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * upperBoundType)}. 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMultiset<E> subMultiset(E lowerBound, BoundType lowerBoundType, 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E upperBound, BoundType upperBoundType); 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a view of this multiset restricted to the elements greater than 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code lowerBound}, optionally including {@code lowerBound} itself. The 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned multiset is a view of this multiset, so changes to one will be 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * reflected in the other. The returned multiset supports all operations that 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this multiset supports. 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned multiset will throw an {@link IllegalArgumentException} on 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * attempts to add elements outside its range. 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType); 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 134