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 use this file except 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in compliance with the License. You may obtain a copy of the License at 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software distributed under the 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * express or implied. See the License for the specific language governing permissions and 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 177dd252788645e940eada959bdde927426e2531c9Paul Duffinimport static com.google.common.base.Preconditions.checkArgument; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 207dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.annotations.Beta; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.Serializable; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Arrays; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collection; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collections; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An immutable {@code SortedMultiset} that stores its elements in a sorted array. Some instances 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * are ordered by an explicit comparator, while others follow the natural sort ordering of their 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements. Either way, null elements are not supported. 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Unlike {@link Multisets#unmodifiableSortedMultiset}, which is a <i>view</i> of a separate 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * collection that can still change, an instance of {@code ImmutableSortedMultiset} contains its 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * own private data and will <i>never</i> change. This class is convenient for {@code public static 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * final} multisets ("constant multisets") and also lets you easily make a "defensive copy" of a 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * set provided to your class by a caller. 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The multisets returned by the {@link #headMultiset}, {@link #tailMultiset}, and 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link #subMultiset} methods share the same array as the original multiset, preventing that 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * array from being garbage collected. If this is a concern, the data may be copied into a 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * correctly-sized array by calling {@link #copyOfSorted}. 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Note on element equivalence:</b> The {@link #contains(Object)}, 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link #containsAll(Collection)}, and {@link #equals(Object)} implementations must check whether 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * a provided object is equivalent to an element in the collection. Unlike most collections, an 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code ImmutableSortedMultiset} doesn't use {@link Object#equals} to determine if two elements 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * are equivalent. Instead, with an explicit comparator, the following relation determines whether 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements {@code x} and {@code y} are equivalent: 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <pre> {@code 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {(x, y) | comparator.compare(x, y) == 0}}</pre> 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>With natural ordering of elements, the following relation determines whether two elements are 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equivalent: 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <pre> {@code 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {(x, y) | x.compareTo(y) == 0}}</pre> 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 657dd252788645e940eada959bdde927426e2531c9Paul Duffin * <b>Warning:</b> Like most multisets, an {@code ImmutableSortedMultiset} will not function 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * correctly if an element is modified after being placed in the multiset. For this reason, and to 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * avoid general confusion, it is strongly recommended to place only immutable objects into this 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * collection. 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as it has no public or 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * protected constructors. Thus, instances of this type are guaranteed to be immutable. 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 737dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>See the Guava User Guide article on <a href= 747dd252788645e940eada959bdde927426e2531c9Paul Duffin * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained"> 757dd252788645e940eada959bdde927426e2531c9Paul Duffin * immutable collections</a>. 767dd252788645e940eada959bdde927426e2531c9Paul Duffin * 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 787dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 807dd252788645e940eada959bdde927426e2531c9Paul Duffin@Beta 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtIncompatible("hasn't been tested yet") 827dd252788645e940eada959bdde927426e2531c9Paul Duffinpublic abstract class ImmutableSortedMultiset<E> extends ImmutableSortedMultisetFauxverideShim<E> 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert implements SortedMultiset<E> { 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(user): GWT compatibility 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final Comparator<Comparable> NATURAL_ORDER = Ordering.natural(); 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 880888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final ImmutableSortedMultiset<Comparable> NATURAL_EMPTY_MULTISET = 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin new EmptyImmutableSortedMultiset<Comparable>(NATURAL_ORDER); 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the empty immutable sorted multiset. 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ImmutableSortedMultiset<E> of() { 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (ImmutableSortedMultiset) NATURAL_EMPTY_MULTISET; 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing a single element. 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) { 1030888a09821a98ac0680fad765217302858e70fa4Paul Duffin RegularImmutableSortedSet<E> elementSet = 1040888a09821a98ac0680fad765217302858e70fa4Paul Duffin (RegularImmutableSortedSet<E>) ImmutableSortedSet.of(element); 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin int[] counts = {1}; 1060888a09821a98ac0680fad765217302858e70fa4Paul Duffin long[] cumulativeCounts = {0, 1}; 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin return new RegularImmutableSortedMultiset<E>(elementSet, counts, cumulativeCounts, 0, 1); 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by their natural 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordering. 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any element is null 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) { 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(Ordering.natural(), Arrays.asList(e1, e2)); 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by their natural 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordering. 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any element is null 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) { 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3)); 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by their natural 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordering. 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any element is null 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 1400888a09821a98ac0680fad765217302858e70fa4Paul Duffin E e1, E e2, E e3, E e4) { 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4)); 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by their natural 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordering. 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any element is null 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1510888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 1520888a09821a98ac0680fad765217302858e70fa4Paul Duffin E e1, E e2, E e3, E e4, E e5) { 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5)); 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by their natural 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordering. 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any element is null 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1630888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 1640888a09821a98ac0680fad765217302858e70fa4Paul Duffin E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) { 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int size = remaining.length + 6; 1667dd252788645e940eada959bdde927426e2531c9Paul Duffin List<E> all = Lists.newArrayListWithCapacity(size); 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collections.addAll(all, e1, e2, e3, e4, e5, e6); 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collections.addAll(all, remaining); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(Ordering.natural(), all); 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by their natural 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordering. 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any of {@code elements} is null 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> copyOf(E[] elements) { 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(Ordering.natural(), Arrays.asList(elements)); 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by their natural 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordering. To create a copy of a {@code SortedMultiset} that preserves the 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparator, call {@link #copyOfSorted} instead. This method iterates over {@code elements} at 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * most once. 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Note that if {@code s} is a {@code multiset<String>}, then {@code 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>} 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)} 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returns an {@code ImmutableSortedMultiset<multiset<String>>} containing one element (the given 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiset itself). 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * safe to do so. The exact circumstances under which a copy will or will not be performed are 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * undocumented and subject to change. 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method is not type-safe, as it may be called on elements that are not mutually 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparable. 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ClassCastException if the elements are not mutually comparable 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any of {@code elements} is null 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) { 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Hack around E not being a subtype of Comparable. 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Unsafe, see ImmutableSortedMultisetFauxverideShim. 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 2080888a09821a98ac0680fad765217302858e70fa4Paul Duffin Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(naturalOrder, elements); 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by their natural 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordering. 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method is not type-safe, as it may be called on elements that are not mutually 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparable. 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ClassCastException if the elements are not mutually comparable 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any of {@code elements} is null 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) { 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Hack around E not being a subtype of Comparable. 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Unsafe, see ImmutableSortedMultisetFauxverideShim. 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 2260888a09821a98ac0680fad765217302858e70fa4Paul Duffin Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 2277dd252788645e940eada959bdde927426e2531c9Paul Duffin return copyOf(naturalOrder, elements); 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by the given {@code 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Comparator}. 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2360888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ImmutableSortedMultiset<E> copyOf( 2370888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator, Iterator<? extends E> elements) { 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(comparator); 2397dd252788645e940eada959bdde927426e2531c9Paul Duffin return new Builder<E>(comparator).addAll(elements).build(); 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the given elements sorted by the given {@code 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Comparator}. This method iterates over {@code elements} at most once. 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * safe to do so. The exact circumstances under which a copy will or will not be performed are 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * undocumented and subject to change. 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2520888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ImmutableSortedMultiset<E> copyOf( 2530888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator, Iterable<? extends E> elements) { 2547dd252788645e940eada959bdde927426e2531c9Paul Duffin if (elements instanceof ImmutableSortedMultiset) { 2550888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // immutable collections are always safe for covariant casts 2567dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) elements; 2577dd252788645e940eada959bdde927426e2531c9Paul Duffin if (comparator.equals(multiset.comparator())) { 2587dd252788645e940eada959bdde927426e2531c9Paul Duffin if (multiset.isPartialView()) { 2597dd252788645e940eada959bdde927426e2531c9Paul Duffin return copyOfSortedEntries(comparator, multiset.entrySet().asList()); 2607dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 2617dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset; 2627dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2637dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2647dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2657dd252788645e940eada959bdde927426e2531c9Paul Duffin elements = Lists.newArrayList(elements); // defensive copy 2667dd252788645e940eada959bdde927426e2531c9Paul Duffin TreeMultiset<E> sortedCopy = TreeMultiset.create(checkNotNull(comparator)); 2677dd252788645e940eada959bdde927426e2531c9Paul Duffin Iterables.addAll(sortedCopy, elements); 2687dd252788645e940eada959bdde927426e2531c9Paul Duffin return copyOfSortedEntries(comparator, sortedCopy.entrySet()); 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * always uses the natural ordering of the elements. 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * safe to do so. The exact circumstances under which a copy will or will not be performed are 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * undocumented and subject to change. 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * collection that is currently being modified by another thread. 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) { 2867dd252788645e940eada959bdde927426e2531c9Paul Duffin return copyOfSortedEntries(sortedMultiset.comparator(), 2877dd252788645e940eada959bdde927426e2531c9Paul Duffin Lists.newArrayList(sortedMultiset.entrySet())); 288dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 289dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 2907dd252788645e940eada959bdde927426e2531c9Paul Duffin private static <E> ImmutableSortedMultiset<E> copyOfSortedEntries( 2917dd252788645e940eada959bdde927426e2531c9Paul Duffin Comparator<? super E> comparator, Collection<Entry<E>> entries) { 292dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin if (entries.isEmpty()) { 293dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin return emptyMultiset(comparator); 294dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 2957dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableList.Builder<E> elementsBuilder = new ImmutableList.Builder<E>(entries.size()); 2967dd252788645e940eada959bdde927426e2531c9Paul Duffin int[] counts = new int[entries.size()]; 2977dd252788645e940eada959bdde927426e2531c9Paul Duffin long[] cumulativeCounts = new long[entries.size() + 1]; 2987dd252788645e940eada959bdde927426e2531c9Paul Duffin int i = 0; 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Entry<E> entry : entries) { 3007dd252788645e940eada959bdde927426e2531c9Paul Duffin elementsBuilder.add(entry.getElement()); 3017dd252788645e940eada959bdde927426e2531c9Paul Duffin counts[i] = entry.getCount(); 3027dd252788645e940eada959bdde927426e2531c9Paul Duffin cumulativeCounts[i + 1] = cumulativeCounts[i] + counts[i]; 3037dd252788645e940eada959bdde927426e2531c9Paul Duffin i++; 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3050888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new RegularImmutableSortedMultiset<E>( 3060888a09821a98ac0680fad765217302858e70fa4Paul Duffin new RegularImmutableSortedSet<E>(elementsBuilder.build(), comparator), 3070888a09821a98ac0680fad765217302858e70fa4Paul Duffin counts, cumulativeCounts, 0, entries.size()); 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) { 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (NATURAL_ORDER.equals(comparator)) { 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (ImmutableSortedMultiset) NATURAL_EMPTY_MULTISET; 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new EmptyImmutableSortedMultiset<E>(comparator); 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3187dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSortedMultiset() {} 319dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 3200888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3217dd252788645e940eada959bdde927426e2531c9Paul Duffin public final Comparator<? super E> comparator() { 3227dd252788645e940eada959bdde927426e2531c9Paul Duffin return elementSet().comparator(); 323dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 324dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 3250888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3267dd252788645e940eada959bdde927426e2531c9Paul Duffin public abstract ImmutableSortedSet<E> elementSet(); 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert transient ImmutableSortedMultiset<E> descendingMultiset; 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3300888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public ImmutableSortedMultiset<E> descendingMultiset() { 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedMultiset<E> result = descendingMultiset; 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (result == null) { 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return descendingMultiset = new DescendingImmutableSortedMultiset<E>(this); 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@inheritDoc} 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. 3437dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3447dd252788645e940eada959bdde927426e2531c9Paul Duffin * @throws UnsupportedOperationException always 3457dd252788645e940eada959bdde927426e2531c9Paul Duffin * @deprecated Unsupported operation. 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3477dd252788645e940eada959bdde927426e2531c9Paul Duffin @Deprecated 3480888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public final Entry<E> pollFirstEntry() { 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@inheritDoc} 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. 3577dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3587dd252788645e940eada959bdde927426e2531c9Paul Duffin * @throws UnsupportedOperationException always 3597dd252788645e940eada959bdde927426e2531c9Paul Duffin * @deprecated Unsupported operation. 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3617dd252788645e940eada959bdde927426e2531c9Paul Duffin @Deprecated 3620888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3637dd252788645e940eada959bdde927426e2531c9Paul Duffin public final Entry<E> pollLastEntry() { 3641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 3651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3670888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType); 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3700888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3710888a09821a98ac0680fad765217302858e70fa4Paul Duffin public ImmutableSortedMultiset<E> subMultiset( 3720888a09821a98ac0680fad765217302858e70fa4Paul Duffin E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) { 3737dd252788645e940eada959bdde927426e2531c9Paul Duffin checkArgument(comparator().compare(lowerBound, upperBound) <= 0, 3747dd252788645e940eada959bdde927426e2531c9Paul Duffin "Expected lowerBound <= upperBound but %s > %s", lowerBound, upperBound); 3751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType); 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3780888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType); 3801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the 3831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparator has a more general type than the set being generated, such as creating a {@code 3841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} 3851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * constructor instead. 3861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code comparator} is null 3881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> Builder<E> orderedBy(Comparator<E> comparator) { 3901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Builder<E>(comparator); 3911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a builder that creates immutable sorted multisets whose elements are ordered by the 3951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * reverse of their natural ordering. 3961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather than {@code 3981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Comparable<? super E>} as a workaround for javac <a 3991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. 4001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E extends Comparable<E>> Builder<E> reverseOrder() { 4021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Builder<E>(Ordering.natural().reverse()); 4031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a builder that creates immutable sorted multisets whose elements are ordered by their 4071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This 4081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * method provides more type-safety than {@link #builder}, as it can be called only for classes 4091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * that implement {@link Comparable}. 4101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather than {@code 4121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Comparable<? super E>} as a workaround for javac <a 4131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. 4141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E extends Comparable<E>> Builder<E> naturalOrder() { 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Builder<E>(Ordering.natural()); 4171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A builder for creating immutable multiset instances, especially {@code public static final} 4211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multisets ("constant multisets"). Example: 4221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <pre> {@code 4241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * public static final ImmutableSortedMultiset<Bean> BEANS = 4261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * new ImmutableSortedMultiset.Builder<Bean>() 4271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * .addCopies(Bean.COCOA, 4) 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * .addCopies(Bean.GARDEN, 6) 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * .addCopies(Bean.RED, 8) 4301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * .addCopies(Bean.BLACK_EYED, 10) 4311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * .build();}</pre> 4321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4330888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 4341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiple multisets in series. 4357dd252788645e940eada959bdde927426e2531c9Paul Duffin * 4367dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 4371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static class Builder<E> extends ImmutableMultiset.Builder<E> { 4391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a new builder. The returned builder is equivalent to the builder generated by 4411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link ImmutableSortedMultiset#orderedBy(Comparator)}. 4421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Builder(Comparator<? super E> comparator) { 4440888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(TreeMultiset.<E>create(checkNotNull(comparator))); 4451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Adds {@code element} to the {@code ImmutableSortedMultiset}. 4491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param element the element to add 4511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return this {@code Builder} object 4521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code element} is null 4531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Builder<E> add(E element) { 4561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super.add(element); 4571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this; 4581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}. 4621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param element the element to add 4641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param occurrences the number of occurrences of the element to add. May be zero, in which 4651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * case no change will be made. 4661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return this {@code Builder} object 4671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code element} is null 4681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation 4691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * would result in more than {@link Integer#MAX_VALUE} occurrences of the element 4701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Builder<E> addCopies(E element, int occurrences) { 4731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super.addCopies(element, occurrences); 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this; 4751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Adds or removes the necessary occurrences of an element such that the element attains the 4791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * desired count. 4801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param element the element to add or remove occurrences of 4821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param count the desired count of the element in this multiset 4831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return this {@code Builder} object 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code element} is null 4851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code count} is negative 4861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Builder<E> setCount(E element, int count) { 4891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super.setCount(element, count); 4901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this; 4911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 4951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param elements the elements to add 4971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return this {@code Builder} object 4981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code elements} is null or contains a null element 4991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 5011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Builder<E> add(E... elements) { 5021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super.add(elements); 5031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this; 5041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 5071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 5081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 5091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset} 5101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return this {@code Builder} object 5111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code elements} is null or contains a null element 5121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 5141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Builder<E> addAll(Iterable<? extends E> elements) { 5151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super.addAll(elements); 5161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this; 5171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 5201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 5211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 5221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param elements the elements to add to the {@code ImmutableSortedMultiset} 5231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return this {@code Builder} object 5241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code elements} is null or contains a null element 5251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 5271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Builder<E> addAll(Iterator<? extends E> elements) { 5281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super.addAll(elements); 5291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this; 5301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 5331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code 5341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Builder}. 5351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 5371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public ImmutableSortedMultiset<E> build() { 5387dd252788645e940eada959bdde927426e2531c9Paul Duffin return copyOfSorted((SortedMultiset<E>) contents); 5391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5420888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final class SerializedForm<E> implements Serializable { 5430888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator; 5440888a09821a98ac0680fad765217302858e70fa4Paul Duffin E[] elements; 5451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int[] counts; 5461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5470888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") 5480888a09821a98ac0680fad765217302858e70fa4Paul Duffin SerializedForm(SortedMultiset<E> multiset) { 5491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.comparator = multiset.comparator(); 5501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int n = multiset.entrySet().size(); 5510888a09821a98ac0680fad765217302858e70fa4Paul Duffin elements = (E[]) new Object[n]; 5521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert counts = new int[n]; 5531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int i = 0; 5540888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (Entry<E> entry : multiset.entrySet()) { 5551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements[i] = entry.getElement(); 5561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert counts[i] = entry.getCount(); 5571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert i++; 5581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object readResolve() { 5621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int n = elements.length; 5630888a09821a98ac0680fad765217302858e70fa4Paul Duffin Builder<E> builder = new Builder<E>(comparator); 5641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < n; i++) { 5651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert builder.addCopies(elements[i], counts[i]); 5661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return builder.build(); 5681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 5721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object writeReplace() { 5730888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new SerializedForm<E>(this); 5741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 576