11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of 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, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkState; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.BstSide.LEFT; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.BstSide.RIGHT; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.IOException; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.ObjectInputStream; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.ObjectOutputStream; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.Serializable; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.ConcurrentModificationException; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A multiset which maintains the ordering of its elements, according to either 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * their natural order or an explicit {@link Comparator}. In all cases, this 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * implementation uses {@link Comparable#compareTo} or {@link 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Comparator#compare} instead of {@link Object#equals} to determine 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equivalence of instances. 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> The comparison must be <i>consistent with equals</i> as 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * explained by the {@link Comparable} class specification. Otherwise, the 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * resulting multiset will violate the {@link java.util.Collection} contract, 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * which is specified in terms of {@link Object#equals}. 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Jared Levy 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(emulated = true) 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic final class TreeMultiset<E> extends AbstractSortedMultiset<E> 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert implements Serializable { 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a new, empty multiset, sorted according to the elements' natural 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * order. All elements inserted into the multiset must implement the 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Comparable} interface. Furthermore, all such elements must be 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code ClassCastException} for any elements {@code e1} and {@code e2} in 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the multiset. If the user attempts to add an element to the multiset that 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * violates this constraint (for example, the user attempts to add a string 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * element to a set whose elements are integers), the {@code add(Object)} 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * call will throw a {@code ClassCastException}. 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The type specification is {@code <E extends Comparable>}, instead of the 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * more specific {@code <E extends Comparable<? super E>>}, to support 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * classes defined without generics. 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E extends Comparable> TreeMultiset<E> create() { 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new TreeMultiset<E>(Ordering.natural()); 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a new, empty multiset, sorted according to the specified 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparator. All elements inserted into the multiset must be <i>mutually 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparable</i> by the specified comparator: {@code comparator.compare(e1, 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * e2)} must not throw a {@code ClassCastException} for any elements {@code 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * e1} and {@code e2} in the multiset. If the user attempts to add an element 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * to the multiset that violates this constraint, the {@code add(Object)} call 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * will throw a {@code ClassCastException}. 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param comparator the comparator that will be used to sort this multiset. A 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * null value indicates that the elements' <i>natural ordering</i> should 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * be used. 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> TreeMultiset<E> create( 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable Comparator<? super E> comparator) { 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (comparator == null) 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ? new TreeMultiset<E>((Comparator) Ordering.natural()) 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert : new TreeMultiset<E>(comparator); 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates an empty multiset containing the given initial elements, sorted 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * according to the elements' natural order. 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This implementation is highly efficient when {@code elements} is itself 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * a {@link Multiset}. 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The type specification is {@code <E extends Comparable>}, instead of the 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * more specific {@code <E extends Comparable<? super E>>}, to support 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * classes defined without generics. 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E extends Comparable> TreeMultiset<E> create( 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterable<? extends E> elements) { 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert TreeMultiset<E> multiset = create(); 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterables.addAll(multiset, elements); 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return multiset; 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an iterator over the elements contained in this collection. 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Iterator<E> iterator() { 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Needed to avoid Javadoc bug. 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.iterator(); 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private TreeMultiset(Comparator<? super E> comparator) { 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(comparator); 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.range = GeneralRange.all(comparator); 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.rootReference = new Reference<Node<E>>(); 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private TreeMultiset(GeneralRange<E> range, Reference<Node<E>> root) { 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(range.comparator()); 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.range = range; 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.rootReference = root; 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E checkElement(Object o) { 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (E) o; 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient final GeneralRange<E> range; 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient final Reference<Node<E>> rootReference; 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final class Reference<T> { 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert T value; 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Reference() {} 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public T get() { 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return value; 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean compareAndSet(T expected, T newValue) { 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (value == expected) { 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert value = newValue; 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int distinctElements() { 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<E> root = rootReference.get(); 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Ints.checkedCast(BstRangeOps.totalInRange(distinctAggregate(), range, root)); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int size() { 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<E> root = rootReference.get(); 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Ints.saturatedCast(BstRangeOps.totalInRange(sizeAggregate(), range, root)); 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int count(@Nullable Object element) { 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E e = checkElement(element); 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (range.contains(e)) { 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<E> node = BstOperations.seek(comparator(), rootReference.get(), e); 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return countOrZero(node); 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NullPointerException e) { 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private int mutate(@Nullable E e, MultisetModifier modifier) { 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstMutationRule<E, Node<E>> mutationRule = BstMutationRule.createRule( 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert modifier, 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstCountBasedBalancePolicies. 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert <E, Node<E>>singleRebalancePolicy(distinctAggregate()), 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert nodeFactory()); 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstMutationResult<E, Node<E>> mutationResult = 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstOperations.mutate(comparator(), mutationRule, rootReference.get(), e); 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!rootReference.compareAndSet( 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mutationResult.getOriginalRoot(), mutationResult.getChangedRoot())) { 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new ConcurrentModificationException(); 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<E> original = mutationResult.getOriginalTarget(); 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return countOrZero(original); 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int add(E element, int occurrences) { 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkElement(element); 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (occurrences == 0) { 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count(element); 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(range.contains(element)); 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return mutate(element, new AddModifier(occurrences)); 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int remove(@Nullable Object element, int occurrences) { 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (element == null) { 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (occurrences == 0) { 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count(element); 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E e = checkElement(element); 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return range.contains(e) ? mutate(e, new RemoveModifier(occurrences)) : 0; 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean setCount(E element, int oldCount, int newCount) { 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkElement(element); 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(range.contains(element)); 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return mutate(element, new ConditionalSetCountModifier(oldCount, newCount)) 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert == oldCount; 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int setCount(E element, int count) { 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkElement(element); 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(range.contains(element)); 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return mutate(element, new SetCountModifier(count)); 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private BstPathFactory<Node<E>, BstInOrderPath<Node<E>>> pathFactory() { 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return BstInOrderPath.inOrderFactory(); 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Entry<E>> entryIterator() { 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<E> root = rootReference.get(); 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final BstInOrderPath<Node<E>> startingPath = 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstRangeOps.furthestPath(range, LEFT, pathFactory(), root); 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return iteratorInDirection(startingPath, RIGHT); 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Entry<E>> descendingEntryIterator() { 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<E> root = rootReference.get(); 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final BstInOrderPath<Node<E>> startingPath = 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstRangeOps.furthestPath(range, RIGHT, pathFactory(), root); 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return iteratorInDirection(startingPath, LEFT); 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Iterator<Entry<E>> iteratorInDirection( 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable BstInOrderPath<Node<E>> start, final BstSide direction) { 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Iterator<BstInOrderPath<Node<E>>> pathIterator = 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new AbstractLinkedIterator<BstInOrderPath<Node<E>>>(start) { 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert protected BstInOrderPath<Node<E>> computeNext(BstInOrderPath<Node<E>> previous) { 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!previous.hasNext(direction)) { 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return null; 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstInOrderPath<Node<E>> next = previous.next(direction); 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(user): only check against one side 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return range.contains(next.getTip().getKey()) ? next : null; 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Iterator<Entry<E>>() { 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E toRemove = null; 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean hasNext() { 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return pathIterator.hasNext(); 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Entry<E> next() { 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstInOrderPath<Node<E>> path = pathIterator.next(); 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new LiveEntry( 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert toRemove = path.getTip().getKey(), path.getTip().elemCount()); 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void remove() { 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkState(toRemove != null); 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert setCount(toRemove, 0); 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert toRemove = null; 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert class LiveEntry extends Multisets.AbstractEntry<E> { 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Node<E> expectedRoot; 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final E element; 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private int count; 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private LiveEntry(E element, int count) { 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.expectedRoot = rootReference.get(); 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.element = element; 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.count = count; 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public E getElement() { 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return element; 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int getCount() { 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (rootReference.get() == expectedRoot) { 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count; 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // check for updates 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert expectedRoot = rootReference.get(); 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count = TreeMultiset.this.count(element); 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void clear() { 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<E> root = rootReference.get(); 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<E> cleared = BstRangeOps.minusRange(range, 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstCountBasedBalancePolicies.<E, Node<E>>fullRebalancePolicy(distinctAggregate()), 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert nodeFactory(), root); 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!rootReference.compareAndSet(root, cleared)) { 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new ConcurrentModificationException(); 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedMultiset<E> headMultiset(E upperBound, BoundType boundType) { 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(upperBound); 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new TreeMultiset<E>( 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert range.intersect(GeneralRange.upTo(comparator, upperBound, boundType)), rootReference); 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType) { 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(lowerBound); 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new TreeMultiset<E>( 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert range.intersect(GeneralRange.downTo(comparator, lowerBound, boundType)), rootReference); 3581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@inheritDoc} 3621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 3641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Comparator<? super E> comparator() { 3671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.comparator(); 3681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final class Node<E> extends BstNode<E, Node<E>> implements Serializable { 3711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final long size; 3721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final int distinct; 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Node(E key, int elemCount, @Nullable Node<E> left, 3751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable Node<E> right) { 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(key, left, right); 3771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(elemCount > 0); 3781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.size = (long) elemCount + sizeOrZero(left) + sizeOrZero(right); 3791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.distinct = 1 + distinctOrZero(left) + distinctOrZero(right); 3801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int elemCount() { 3831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = size - sizeOrZero(childOrNull(LEFT)) 3841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert - sizeOrZero(childOrNull(RIGHT)); 3851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Ints.checkedCast(result); 3861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Node(E key, int elemCount) { 3891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this(key, elemCount, null, null); 3901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 0; 3931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static long sizeOrZero(@Nullable Node<?> node) { 3961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (node == null) ? 0 : node.size; 3971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static int distinctOrZero(@Nullable Node<?> node) { 4001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (node == null) ? 0 : node.distinct; 4011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static int countOrZero(@Nullable Node<?> entry) { 4041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (entry == null) ? 0 : entry.elemCount(); 4051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 4081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private BstAggregate<Node<E>> distinctAggregate() { 4091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (BstAggregate) DISTINCT_AGGREGATE; 4101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final BstAggregate<Node<Object>> DISTINCT_AGGREGATE = 4131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new BstAggregate<Node<Object>>() { 4141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int entryValue(Node<Object> entry) { 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1; 4171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public long treeValue(@Nullable Node<Object> tree) { 4211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return distinctOrZero(tree); 4221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 4241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 4261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private BstAggregate<Node<E>> sizeAggregate() { 4271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (BstAggregate) SIZE_AGGREGATE; 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final BstAggregate<Node<Object>> SIZE_AGGREGATE = 4311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new BstAggregate<Node<Object>>() { 4321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int entryValue(Node<Object> entry) { 4341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entry.elemCount(); 4351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public long treeValue(@Nullable Node<Object> tree) { 4391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sizeOrZero(tree); 4401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 4421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 4441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private BstNodeFactory<Node<E>> nodeFactory() { 4451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (BstNodeFactory) NODE_FACTORY; 4461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final BstNodeFactory<Node<Object>> NODE_FACTORY = 4491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new BstNodeFactory<Node<Object>>() { 4501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Node<Object> createNode(Node<Object> source, @Nullable Node<Object> left, 4521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable Node<Object> right) { 4531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Node<Object>(source.getKey(), source.elemCount(), left, right); 4541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 4561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private abstract class MultisetModifier implements BstModifier<E, Node<E>> { 4581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract int newCount(int oldCount); 4591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable 4611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public BstModificationResult<Node<E>> modify(E key, @Nullable Node<E> originalEntry) { 4631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int oldCount = countOrZero(originalEntry); 4641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int newCount = newCount(oldCount); 4651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (oldCount == newCount) { 4661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return BstModificationResult.identity(originalEntry); 4671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (newCount == 0) { 4681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return BstModificationResult.rebalancingChange(originalEntry, null); 4691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (oldCount == 0) { 4701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return BstModificationResult.rebalancingChange(null, new Node<E>(key, newCount)); 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 4721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return BstModificationResult.rebuildingChange(originalEntry, 4731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new Node<E>(originalEntry.getKey(), newCount)); 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final class AddModifier extends MultisetModifier { 4791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final int countToAdd; 4801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private AddModifier(int countToAdd) { 4821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(countToAdd > 0); 4831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.countToAdd = countToAdd; 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int newCount(int oldCount) { 4881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(countToAdd <= Integer.MAX_VALUE - oldCount, "Cannot add this many elements"); 4891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return oldCount + countToAdd; 4901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final class RemoveModifier extends MultisetModifier { 4941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final int countToRemove; 4951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private RemoveModifier(int countToRemove) { 4971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(countToRemove > 0); 4981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.countToRemove = countToRemove; 4991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 5021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int newCount(int oldCount) { 5031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Math.max(0, oldCount - countToRemove); 5041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final class SetCountModifier extends MultisetModifier { 5081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final int countToSet; 5091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private SetCountModifier(int countToSet) { 5111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(countToSet >= 0); 5121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.countToSet = countToSet; 5131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 5161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int newCount(int oldCount) { 5171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return countToSet; 5181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final class ConditionalSetCountModifier extends MultisetModifier { 5221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final int expectedCount; 5231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final int setCount; 5241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private ConditionalSetCountModifier(int expectedCount, int setCount) { 5261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(setCount >= 0 & expectedCount >= 0); 5271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.expectedCount = expectedCount; 5281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.setCount = setCount; 5291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 5321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int newCount(int oldCount) { 5331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (oldCount == expectedCount) ? setCount : oldCount; 5341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 5381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * TODO(jlevy): Decide whether entrySet() should return entries with an 5391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equals() method that calls the comparator to compare the two keys. If that 5401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * change is made, AbstractMultiset.equals() can simply check whether two 5411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multisets have equal entry sets. 5421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 5451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @serialData the comparator, the number of distinct elements, the first 5461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * element, its count, the second element, its count, and so on 5471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectOutputStream") 5491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void writeObject(ObjectOutputStream stream) throws IOException { 5501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert stream.defaultWriteObject(); 5511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert stream.writeObject(elementSet().comparator()); 5521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Serialization.writeMultiset(this, stream); 5531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectInputStream") 5561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void readObject(ObjectInputStream stream) 5571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throws IOException, ClassNotFoundException { 5581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert stream.defaultReadObject(); 5591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") // reading data stored by writeObject 5601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator = (Comparator<? super E>) stream.readObject(); 5611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Serialization.getFieldSetter(AbstractSortedMultiset.class, "comparator").set(this, comparator); 5621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Serialization.getFieldSetter(TreeMultiset.class, "range").set(this, 5631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert GeneralRange.all(comparator)); 5641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Serialization.getFieldSetter(TreeMultiset.class, "rootReference").set(this, 5651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new Reference<Node<E>>()); 5661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Serialization.populateMultiset(this, stream); 5671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("not needed in emulated source") 5701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 1; 5711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 572