001/* 002 * Copyright (C) 2011 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the 010 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 011 * express or implied. See the License for the specific language governing permissions and 012 * limitations under the License. 013 */ 014 015package com.google.common.collect; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkNotNull; 019 020import com.google.common.annotations.GwtIncompatible; 021import com.google.common.annotations.VisibleForTesting; 022import com.google.common.math.IntMath; 023import com.google.errorprone.annotations.CanIgnoreReturnValue; 024import com.google.errorprone.annotations.DoNotCall; 025import com.google.errorprone.annotations.concurrent.LazyInit; 026import java.io.Serializable; 027import java.util.Arrays; 028import java.util.Collection; 029import java.util.Collections; 030import java.util.Comparator; 031import java.util.Iterator; 032import java.util.List; 033import javax.annotation.CheckForNull; 034 035/** 036 * A {@link SortedMultiset} whose contents will never change, with many other important properties 037 * detailed at {@link ImmutableCollection}. 038 * 039 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link 040 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with 041 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero 042 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting 043 * collection will not correctly obey its specification. 044 * 045 * <p>See the Guava User Guide article on <a href= 046 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>. 047 * 048 * @author Louis Wasserman 049 * @since 12.0 050 */ 051@GwtIncompatible // hasn't been tested yet 052@ElementTypesAreNonnullByDefault 053public abstract class ImmutableSortedMultiset<E> extends ImmutableSortedMultisetFauxverideShim<E> 054 implements SortedMultiset<E> { 055 // TODO(lowasser): GWT compatibility 056 057 /** 058 * Returns the empty immutable sorted multiset. 059 * 060 * <p><b>Performance note:</b> the instance returned is a singleton. 061 */ 062 @SuppressWarnings("unchecked") 063 public static <E> ImmutableSortedMultiset<E> of() { 064 return (ImmutableSortedMultiset) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET; 065 } 066 067 /** Returns an immutable sorted multiset containing a single element. */ 068 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) { 069 RegularImmutableSortedSet<E> elementSet = 070 (RegularImmutableSortedSet<E>) ImmutableSortedSet.of(element); 071 long[] cumulativeCounts = {0, 1}; 072 return new RegularImmutableSortedMultiset<E>(elementSet, cumulativeCounts, 0, 1); 073 } 074 075 /** 076 * Returns an immutable sorted multiset containing the given elements sorted by their natural 077 * ordering. 078 * 079 * @throws NullPointerException if any element is null 080 */ 081 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) { 082 return copyOf(Ordering.natural(), Arrays.asList(e1, e2)); 083 } 084 085 /** 086 * Returns an immutable sorted multiset containing the given elements sorted by their natural 087 * ordering. 088 * 089 * @throws NullPointerException if any element is null 090 */ 091 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) { 092 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3)); 093 } 094 095 /** 096 * Returns an immutable sorted multiset containing the given elements sorted by their natural 097 * ordering. 098 * 099 * @throws NullPointerException if any element is null 100 */ 101 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 102 E e1, E e2, E e3, E e4) { 103 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4)); 104 } 105 106 /** 107 * Returns an immutable sorted multiset containing the given elements sorted by their natural 108 * ordering. 109 * 110 * @throws NullPointerException if any element is null 111 */ 112 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 113 E e1, E e2, E e3, E e4, E e5) { 114 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5)); 115 } 116 117 /** 118 * Returns an immutable sorted multiset containing the given elements sorted by their natural 119 * ordering. 120 * 121 * @throws NullPointerException if any element is null 122 */ 123 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 124 E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) { 125 int size = remaining.length + 6; 126 List<E> all = Lists.newArrayListWithCapacity(size); 127 Collections.addAll(all, e1, e2, e3, e4, e5, e6); 128 Collections.addAll(all, remaining); 129 return copyOf(Ordering.natural(), all); 130 } 131 132 /** 133 * Returns an immutable sorted multiset containing the given elements sorted by their natural 134 * ordering. 135 * 136 * @throws NullPointerException if any of {@code elements} is null 137 */ 138 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> copyOf(E[] elements) { 139 return copyOf(Ordering.natural(), Arrays.asList(elements)); 140 } 141 142 /** 143 * Returns an immutable sorted multiset containing the given elements sorted by their natural 144 * ordering. To create a copy of a {@code SortedMultiset} that preserves the comparator, call 145 * {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once. 146 * 147 * <p>Note that if {@code s} is a {@code Multiset<String>}, then {@code 148 * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>} 149 * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)} 150 * returns an {@code ImmutableSortedMultiset<Multiset<String>>} containing one element (the given 151 * multiset itself). 152 * 153 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 154 * safe to do so. The exact circumstances under which a copy will or will not be performed are 155 * undocumented and subject to change. 156 * 157 * <p>This method is not type-safe, as it may be called on elements that are not mutually 158 * comparable. 159 * 160 * @throws ClassCastException if the elements are not mutually comparable 161 * @throws NullPointerException if any of {@code elements} is null 162 */ 163 public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) { 164 // Hack around E not being a subtype of Comparable. 165 // Unsafe, see ImmutableSortedMultisetFauxverideShim. 166 @SuppressWarnings("unchecked") 167 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 168 return copyOf(naturalOrder, elements); 169 } 170 171 /** 172 * Returns an immutable sorted multiset containing the given elements sorted by their natural 173 * ordering. 174 * 175 * <p>This method is not type-safe, as it may be called on elements that are not mutually 176 * comparable. 177 * 178 * @throws ClassCastException if the elements are not mutually comparable 179 * @throws NullPointerException if any of {@code elements} is null 180 */ 181 public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) { 182 // Hack around E not being a subtype of Comparable. 183 // Unsafe, see ImmutableSortedMultisetFauxverideShim. 184 @SuppressWarnings("unchecked") 185 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 186 return copyOf(naturalOrder, elements); 187 } 188 189 /** 190 * Returns an immutable sorted multiset containing the given elements sorted by the given {@code 191 * Comparator}. 192 * 193 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 194 */ 195 public static <E> ImmutableSortedMultiset<E> copyOf( 196 Comparator<? super E> comparator, Iterator<? extends E> elements) { 197 checkNotNull(comparator); 198 return new Builder<E>(comparator).addAll(elements).build(); 199 } 200 201 /** 202 * Returns an immutable sorted multiset containing the given elements sorted by the given {@code 203 * Comparator}. This method iterates over {@code elements} at most once. 204 * 205 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 206 * safe to do so. The exact circumstances under which a copy will or will not be performed are 207 * undocumented and subject to change. 208 * 209 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 210 */ 211 @SuppressWarnings("unchecked") 212 public static <E> ImmutableSortedMultiset<E> copyOf( 213 Comparator<? super E> comparator, Iterable<? extends E> elements) { 214 if (elements instanceof ImmutableSortedMultiset) { 215 @SuppressWarnings("unchecked") // immutable collections are always safe for covariant casts 216 ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) elements; 217 if (comparator.equals(multiset.comparator())) { 218 if (multiset.isPartialView()) { 219 return copyOfSortedEntries(comparator, multiset.entrySet().asList()); 220 } else { 221 return multiset; 222 } 223 } 224 } 225 return new ImmutableSortedMultiset.Builder<E>(comparator).addAll(elements).build(); 226 } 227 228 /** 229 * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by 230 * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always 231 * uses the natural ordering of the elements. 232 * 233 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 234 * safe to do so. The exact circumstances under which a copy will or will not be performed are 235 * undocumented and subject to change. 236 * 237 * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent 238 * collection that is currently being modified by another thread. 239 * 240 * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null 241 */ 242 public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) { 243 return copyOfSortedEntries( 244 sortedMultiset.comparator(), Lists.newArrayList(sortedMultiset.entrySet())); 245 } 246 247 private static <E> ImmutableSortedMultiset<E> copyOfSortedEntries( 248 Comparator<? super E> comparator, Collection<Entry<E>> entries) { 249 if (entries.isEmpty()) { 250 return emptyMultiset(comparator); 251 } 252 ImmutableList.Builder<E> elementsBuilder = new ImmutableList.Builder<E>(entries.size()); 253 long[] cumulativeCounts = new long[entries.size() + 1]; 254 int i = 0; 255 for (Entry<E> entry : entries) { 256 elementsBuilder.add(entry.getElement()); 257 cumulativeCounts[i + 1] = cumulativeCounts[i] + entry.getCount(); 258 i++; 259 } 260 return new RegularImmutableSortedMultiset<E>( 261 new RegularImmutableSortedSet<E>(elementsBuilder.build(), comparator), 262 cumulativeCounts, 263 0, 264 entries.size()); 265 } 266 267 @SuppressWarnings("unchecked") 268 static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) { 269 if (Ordering.natural().equals(comparator)) { 270 return (ImmutableSortedMultiset<E>) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET; 271 } else { 272 return new RegularImmutableSortedMultiset<E>(comparator); 273 } 274 } 275 276 ImmutableSortedMultiset() {} 277 278 @Override 279 public final Comparator<? super E> comparator() { 280 return elementSet().comparator(); 281 } 282 283 @Override 284 public abstract ImmutableSortedSet<E> elementSet(); 285 286 @LazyInit @CheckForNull transient ImmutableSortedMultiset<E> descendingMultiset; 287 288 @Override 289 public ImmutableSortedMultiset<E> descendingMultiset() { 290 ImmutableSortedMultiset<E> result = descendingMultiset; 291 if (result == null) { 292 return descendingMultiset = 293 this.isEmpty() 294 ? emptyMultiset(Ordering.from(comparator()).reverse()) 295 : new DescendingImmutableSortedMultiset<E>(this); 296 } 297 return result; 298 } 299 300 /** 301 * {@inheritDoc} 302 * 303 * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. 304 * 305 * @throws UnsupportedOperationException always 306 * @deprecated Unsupported operation. 307 */ 308 @CanIgnoreReturnValue 309 @Deprecated 310 @Override 311 @DoNotCall("Always throws UnsupportedOperationException") 312 @CheckForNull 313 public final Entry<E> pollFirstEntry() { 314 throw new UnsupportedOperationException(); 315 } 316 317 /** 318 * {@inheritDoc} 319 * 320 * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. 321 * 322 * @throws UnsupportedOperationException always 323 * @deprecated Unsupported operation. 324 */ 325 @CanIgnoreReturnValue 326 @Deprecated 327 @Override 328 @DoNotCall("Always throws UnsupportedOperationException") 329 @CheckForNull 330 public final Entry<E> pollLastEntry() { 331 throw new UnsupportedOperationException(); 332 } 333 334 @Override 335 public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType); 336 337 @Override 338 public ImmutableSortedMultiset<E> subMultiset( 339 E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) { 340 checkArgument( 341 comparator().compare(lowerBound, upperBound) <= 0, 342 "Expected lowerBound <= upperBound but %s > %s", 343 lowerBound, 344 upperBound); 345 return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType); 346 } 347 348 @Override 349 public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType); 350 351 /** 352 * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the 353 * comparator has a more general type than the set being generated, such as creating a {@code 354 * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor 355 * instead. 356 * 357 * @throws NullPointerException if {@code comparator} is null 358 */ 359 public static <E> Builder<E> orderedBy(Comparator<E> comparator) { 360 return new Builder<E>(comparator); 361 } 362 363 /** 364 * Returns a builder that creates immutable sorted multisets whose elements are ordered by the 365 * reverse of their natural ordering. 366 * 367 * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code 368 * Comparable<? super E>} as a workaround for javac <a 369 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. 370 */ 371 public static <E extends Comparable<?>> Builder<E> reverseOrder() { 372 return new Builder<E>(Ordering.natural().reverse()); 373 } 374 375 /** 376 * Returns a builder that creates immutable sorted multisets whose elements are ordered by their 377 * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This 378 * method provides more type-safety than {@link #builder}, as it can be called only for classes 379 * that implement {@link Comparable}. 380 * 381 * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code 382 * Comparable<? super E>} as a workaround for javac <a 383 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. 384 */ 385 public static <E extends Comparable<?>> Builder<E> naturalOrder() { 386 return new Builder<E>(Ordering.natural()); 387 } 388 389 /** 390 * A builder for creating immutable multiset instances, especially {@code public static final} 391 * multisets ("constant multisets"). Example: 392 * 393 * <pre>{@code 394 * public static final ImmutableSortedMultiset<Bean> BEANS = 395 * new ImmutableSortedMultiset.Builder<Bean>(colorComparator()) 396 * .addCopies(Bean.COCOA, 4) 397 * .addCopies(Bean.GARDEN, 6) 398 * .addCopies(Bean.RED, 8) 399 * .addCopies(Bean.BLACK_EYED, 10) 400 * .build(); 401 * }</pre> 402 * 403 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 404 * multiple multisets in series. 405 * 406 * @since 12.0 407 */ 408 public static class Builder<E> extends ImmutableMultiset.Builder<E> { 409 /* 410 * We keep an array of elements and counts. Periodically -- when we need more room in the 411 * array, or when we're building, or the like -- we sort, deduplicate, and combine the counts. 412 * Negative counts indicate a setCount operation with ~counts[i]. 413 */ 414 415 private final Comparator<? super E> comparator; 416 417 @VisibleForTesting E[] elements; 418 private int[] counts; 419 420 /* 421 * The number of used positions in the elements array. We deduplicate periodically, so this 422 * may fluctuate up and down. 423 */ 424 private int length; 425 426 // True if we just called build() and the elements array is being used by a created ISM, meaning 427 // we shouldn't modify that array further. 428 private boolean forceCopyElements; 429 430 /** 431 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 432 * ImmutableSortedMultiset#orderedBy(Comparator)}. 433 */ 434 @SuppressWarnings("unchecked") 435 public Builder(Comparator<? super E> comparator) { 436 super(true); // doesn't allocate hash table in supertype 437 this.comparator = checkNotNull(comparator); 438 this.elements = (E[]) new Object[ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY]; 439 this.counts = new int[ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY]; 440 } 441 442 /** Check if we need to do deduplication and coalescing, and if so, do it. */ 443 private void maintenance() { 444 if (length == elements.length) { 445 dedupAndCoalesce(true); 446 } else if (forceCopyElements) { 447 this.elements = Arrays.copyOf(elements, elements.length); 448 // we don't currently need to copy the counts array, because we don't use it directly 449 // in built ISMs 450 } 451 forceCopyElements = false; 452 } 453 454 private void dedupAndCoalesce(boolean maybeExpand) { 455 if (length == 0) { 456 return; 457 } 458 E[] sortedElements = Arrays.copyOf(elements, length); 459 Arrays.sort(sortedElements, comparator); 460 int uniques = 1; 461 for (int i = 1; i < sortedElements.length; i++) { 462 if (comparator.compare(sortedElements[uniques - 1], sortedElements[i]) < 0) { 463 sortedElements[uniques] = sortedElements[i]; 464 uniques++; 465 } 466 } 467 Arrays.fill(sortedElements, uniques, length, null); 468 if (maybeExpand && uniques * 4 > length * 3) { 469 // lots of nonduplicated elements, expand the array by 50% 470 sortedElements = 471 Arrays.copyOf(sortedElements, IntMath.saturatedAdd(length, length / 2 + 1)); 472 } 473 int[] sortedCounts = new int[sortedElements.length]; 474 for (int i = 0; i < length; i++) { 475 int index = Arrays.binarySearch(sortedElements, 0, uniques, elements[i], comparator); 476 if (counts[i] >= 0) { 477 sortedCounts[index] += counts[i]; 478 } else { 479 sortedCounts[index] = ~counts[i]; 480 } 481 } 482 // Note that we're not getting rid, yet, of elements with count 0. We'll do that in build(). 483 this.elements = sortedElements; 484 this.counts = sortedCounts; 485 this.length = uniques; 486 } 487 488 /** 489 * Adds {@code element} to the {@code ImmutableSortedMultiset}. 490 * 491 * @param element the element to add 492 * @return this {@code Builder} object 493 * @throws NullPointerException if {@code element} is null 494 */ 495 @CanIgnoreReturnValue 496 @Override 497 public Builder<E> add(E element) { 498 return addCopies(element, 1); 499 } 500 501 /** 502 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 503 * 504 * @param elements the elements to add 505 * @return this {@code Builder} object 506 * @throws NullPointerException if {@code elements} is null or contains a null element 507 */ 508 @CanIgnoreReturnValue 509 @Override 510 public Builder<E> add(E... elements) { 511 for (E element : elements) { 512 add(element); 513 } 514 return this; 515 } 516 517 /** 518 * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}. 519 * 520 * @param element the element to add 521 * @param occurrences the number of occurrences of the element to add. May be zero, in which 522 * case no change will be made. 523 * @return this {@code Builder} object 524 * @throws NullPointerException if {@code element} is null 525 * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation 526 * would result in more than {@link Integer#MAX_VALUE} occurrences of the element 527 */ 528 @CanIgnoreReturnValue 529 @Override 530 public Builder<E> addCopies(E element, int occurrences) { 531 checkNotNull(element); 532 CollectPreconditions.checkNonnegative(occurrences, "occurrences"); 533 if (occurrences == 0) { 534 return this; 535 } 536 maintenance(); 537 elements[length] = element; 538 counts[length] = occurrences; 539 length++; 540 return this; 541 } 542 543 /** 544 * Adds or removes the necessary occurrences of an element such that the element attains the 545 * desired count. 546 * 547 * @param element the element to add or remove occurrences of 548 * @param count the desired count of the element in this multiset 549 * @return this {@code Builder} object 550 * @throws NullPointerException if {@code element} is null 551 * @throws IllegalArgumentException if {@code count} is negative 552 */ 553 @CanIgnoreReturnValue 554 @Override 555 public Builder<E> setCount(E element, int count) { 556 checkNotNull(element); 557 CollectPreconditions.checkNonnegative(count, "count"); 558 maintenance(); 559 elements[length] = element; 560 counts[length] = ~count; 561 length++; 562 return this; 563 } 564 565 /** 566 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 567 * 568 * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset} 569 * @return this {@code Builder} object 570 * @throws NullPointerException if {@code elements} is null or contains a null element 571 */ 572 @CanIgnoreReturnValue 573 @Override 574 public Builder<E> addAll(Iterable<? extends E> elements) { 575 if (elements instanceof Multiset) { 576 for (Entry<? extends E> entry : ((Multiset<? extends E>) elements).entrySet()) { 577 addCopies(entry.getElement(), entry.getCount()); 578 } 579 } else { 580 for (E e : elements) { 581 add(e); 582 } 583 } 584 return this; 585 } 586 587 /** 588 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 589 * 590 * @param elements the elements to add to the {@code ImmutableSortedMultiset} 591 * @return this {@code Builder} object 592 * @throws NullPointerException if {@code elements} is null or contains a null element 593 */ 594 @CanIgnoreReturnValue 595 @Override 596 public Builder<E> addAll(Iterator<? extends E> elements) { 597 while (elements.hasNext()) { 598 add(elements.next()); 599 } 600 return this; 601 } 602 603 private void dedupAndCoalesceAndDeleteEmpty() { 604 dedupAndCoalesce(false); 605 606 // If there was a setCount(elem, 0), those elements are still present. Eliminate them. 607 int size = 0; 608 for (int i = 0; i < length; i++) { 609 if (counts[i] > 0) { 610 elements[size] = elements[i]; 611 counts[size] = counts[i]; 612 size++; 613 } 614 } 615 Arrays.fill(elements, size, length, null); 616 Arrays.fill(counts, size, length, 0); 617 length = size; 618 } 619 620 /** 621 * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code 622 * Builder}. 623 */ 624 @Override 625 public ImmutableSortedMultiset<E> build() { 626 dedupAndCoalesceAndDeleteEmpty(); 627 if (length == 0) { 628 return emptyMultiset(comparator); 629 } 630 RegularImmutableSortedSet<E> elementSet = 631 (RegularImmutableSortedSet<E>) ImmutableSortedSet.construct(comparator, length, elements); 632 long[] cumulativeCounts = new long[length + 1]; 633 for (int i = 0; i < length; i++) { 634 cumulativeCounts[i + 1] = cumulativeCounts[i] + counts[i]; 635 } 636 forceCopyElements = true; 637 return new RegularImmutableSortedMultiset<E>(elementSet, cumulativeCounts, 0, length); 638 } 639 } 640 641 private static final class SerializedForm<E> implements Serializable { 642 final Comparator<? super E> comparator; 643 final E[] elements; 644 final int[] counts; 645 646 @SuppressWarnings("unchecked") 647 SerializedForm(SortedMultiset<E> multiset) { 648 this.comparator = multiset.comparator(); 649 int n = multiset.entrySet().size(); 650 elements = (E[]) new Object[n]; 651 counts = new int[n]; 652 int i = 0; 653 for (Entry<E> entry : multiset.entrySet()) { 654 elements[i] = entry.getElement(); 655 counts[i] = entry.getCount(); 656 i++; 657 } 658 } 659 660 Object readResolve() { 661 int n = elements.length; 662 Builder<E> builder = new Builder<>(comparator); 663 for (int i = 0; i < n; i++) { 664 builder.addCopies(elements[i], counts[i]); 665 } 666 return builder.build(); 667 } 668 } 669 670 @Override 671 Object writeReplace() { 672 return new SerializedForm<E>(this); 673 } 674}