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; 25dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffinimport java.util.SortedSet; 260888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Set; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A {@link Multiset} which maintains the ordering of its elements, according to 300888a09821a98ac0680fad765217302858e70fa4Paul Duffin * either their natural order or an explicit {@link Comparator}. This order is 310888a09821a98ac0680fad765217302858e70fa4Paul Duffin * reflected when iterating over the sorted multiset, either directly, or through 320888a09821a98ac0680fad765217302858e70fa4Paul Duffin * its {@code elementSet} or {@code entrySet} views. In all cases, 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this implementation uses {@link Comparable#compareTo} or 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Comparator#compare} instead of {@link Object#equals} to determine 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equivalence of instances. 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> The comparison must be <i>consistent with equals</i> as 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * explained by the {@link Comparable} class specification. Otherwise, the 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * resulting multiset will violate the {@link Collection} contract, which it is 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * specified in terms of {@link Object#equals}. 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 427dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>See the Guava User Guide article on <a href= 437dd252788645e940eada959bdde927426e2531c9Paul Duffin * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multiset"> 447dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code Multiset}</a>. 457dd252788645e940eada959bdde927426e2531c9Paul Duffin * 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@Beta 507dd252788645e940eada959bdde927426e2531c9Paul Duffin@GwtCompatible(emulated = true) 517dd252788645e940eada959bdde927426e2531c9Paul Duffinpublic interface SortedMultiset<E> extends SortedMultisetBridge<E>, SortedIterable<E> { 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the comparator that orders this multiset, or 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Ordering#natural()} if the natural ordering of the elements is used. 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator(); 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the entry of the first element in this multiset, or {@code null} if 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this multiset is empty. 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> firstEntry(); 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the entry of the last element in this multiset, or {@code null} if 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this multiset is empty. 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> lastEntry(); 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns and removes the entry associated with the lowest element in this 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiset, or returns {@code null} if this multiset is empty. 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> pollFirstEntry(); 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns and removes the entry associated with the greatest element in this 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiset, or returns {@code null} if this multiset is empty. 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> pollLastEntry(); 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns a {@link SortedSet} view of the distinct elements in this multiset. 847dd252788645e940eada959bdde927426e2531c9Paul Duffin * 850888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 14.0 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 870888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override SortedSet<E> elementSet(); 880888a09821a98ac0680fad765217302858e70fa4Paul Duffin 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@inheritDoc} 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>The {@code entrySet}'s iterator returns entries in ascending element 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * order according to the this multiset's comparator. 940888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override Set<Entry<E>> entrySet(); 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@inheritDoc} 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The iterator returns the elements in ascending order according to this 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiset's comparator. 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1030888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override Iterator<E> iterator(); 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a descending view of this multiset. Modifications made to either 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * map will be reflected in the other. 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMultiset<E> descendingMultiset(); 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a view of this multiset restricted to the elements less than 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code upperBound}, optionally including {@code upperBound} itself. The 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned multiset is a view of this multiset, so changes to one will be 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * reflected in the other. The returned multiset supports all operations that 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this multiset supports. 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned multiset will throw an {@link IllegalArgumentException} on 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * attempts to add elements outside its range. 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMultiset<E> headMultiset(E upperBound, BoundType boundType); 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a view of this multiset restricted to the range between 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code lowerBound} and {@code upperBound}. The returned multiset is a view 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of this multiset, so changes to one will be reflected in the other. The 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned multiset supports all operations that 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 * <p>This method is equivalent to 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * upperBoundType)}. 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1360888a09821a98ac0680fad765217302858e70fa4Paul Duffin SortedMultiset<E> subMultiset(E lowerBound, BoundType lowerBoundType, 1370888a09821a98ac0680fad765217302858e70fa4Paul Duffin E upperBound, BoundType upperBoundType); 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a view of this multiset restricted to the elements greater than 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code lowerBound}, optionally including {@code lowerBound} itself. The 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned multiset is a view of this multiset, so changes to one will be 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * reflected in the other. The returned multiset supports all operations that 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this multiset supports. 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned multiset will throw an {@link IllegalArgumentException} on 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * attempts to add elements outside its range. 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType); 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 151