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.errorprone.annotations.CanIgnoreReturnValue; 022import com.google.errorprone.annotations.DoNotCall; 023import com.google.errorprone.annotations.concurrent.LazyInit; 024import java.io.Serializable; 025import java.util.Arrays; 026import java.util.Collection; 027import java.util.Collections; 028import java.util.Comparator; 029import java.util.Iterator; 030import java.util.List; 031import java.util.function.Function; 032import java.util.function.ToIntFunction; 033import java.util.stream.Collector; 034import javax.annotation.CheckForNull; 035import org.checkerframework.checker.nullness.qual.Nullable; 036 037/** 038 * A {@link SortedMultiset} whose contents will never change, with many other important properties 039 * detailed at {@link ImmutableCollection}. 040 * 041 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link 042 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with 043 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero 044 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting 045 * collection will not correctly obey its specification. 046 * 047 * <p>See the Guava User Guide article on <a href= 048 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>. 049 * 050 * @author Louis Wasserman 051 * @since 12.0 052 */ 053@GwtIncompatible // hasn't been tested yet 054@ElementTypesAreNonnullByDefault 055public abstract class ImmutableSortedMultiset<E> extends ImmutableSortedMultisetFauxverideShim<E> 056 implements SortedMultiset<E> { 057 // TODO(lowasser): GWT compatibility 058 059 /** 060 * Returns a {@code Collector} that accumulates the input elements into a new {@code 061 * ImmutableMultiset}. Elements are sorted by the specified comparator. 062 * 063 * <p><b>Warning:</b> {@code comparator} should be <i>consistent with {@code equals}</i> as 064 * explained in the {@link Comparator} documentation. 065 * 066 * @since 21.0 067 */ 068 public static <E> Collector<E, ?, ImmutableSortedMultiset<E>> toImmutableSortedMultiset( 069 Comparator<? super E> comparator) { 070 return toImmutableSortedMultiset(comparator, Function.identity(), e -> 1); 071 } 072 073 /** 074 * Returns a {@code Collector} that accumulates elements into an {@code ImmutableSortedMultiset} 075 * whose elements are the result of applying {@code elementFunction} to the inputs, with counts 076 * equal to the result of applying {@code countFunction} to the inputs. 077 * 078 * <p>If the mapped elements contain duplicates (according to {@code comparator}), the first 079 * occurrence in encounter order appears in the resulting multiset, with count equal to the sum of 080 * the outputs of {@code countFunction.applyAsInt(t)} for each {@code t} mapped to that element. 081 * 082 * @since 22.0 083 */ 084 public static <T extends @Nullable Object, E> 085 Collector<T, ?, ImmutableSortedMultiset<E>> toImmutableSortedMultiset( 086 Comparator<? super E> comparator, 087 Function<? super T, ? extends E> elementFunction, 088 ToIntFunction<? super T> countFunction) { 089 checkNotNull(comparator); 090 checkNotNull(elementFunction); 091 checkNotNull(countFunction); 092 return Collector.of( 093 () -> TreeMultiset.create(comparator), 094 (multiset, t) -> 095 multiset.add(checkNotNull(elementFunction.apply(t)), countFunction.applyAsInt(t)), 096 (multiset1, multiset2) -> { 097 multiset1.addAll(multiset2); 098 return multiset1; 099 }, 100 (Multiset<E> multiset) -> copyOfSortedEntries(comparator, multiset.entrySet())); 101 } 102 103 /** 104 * Returns the empty immutable sorted multiset. 105 * 106 * <p><b>Performance note:</b> the instance returned is a singleton. 107 */ 108 @SuppressWarnings("unchecked") 109 public static <E> ImmutableSortedMultiset<E> of() { 110 return (ImmutableSortedMultiset) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET; 111 } 112 113 /** Returns an immutable sorted multiset containing a single element. */ 114 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) { 115 RegularImmutableSortedSet<E> elementSet = 116 (RegularImmutableSortedSet<E>) ImmutableSortedSet.of(element); 117 long[] cumulativeCounts = {0, 1}; 118 return new RegularImmutableSortedMultiset<E>(elementSet, cumulativeCounts, 0, 1); 119 } 120 121 /** 122 * Returns an immutable sorted multiset containing the given elements sorted by their natural 123 * ordering. 124 * 125 * @throws NullPointerException if any element is null 126 */ 127 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) { 128 return copyOf(Ordering.natural(), Arrays.asList(e1, e2)); 129 } 130 131 /** 132 * Returns an immutable sorted multiset containing the given elements sorted by their natural 133 * ordering. 134 * 135 * @throws NullPointerException if any element is null 136 */ 137 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) { 138 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3)); 139 } 140 141 /** 142 * Returns an immutable sorted multiset containing the given elements sorted by their natural 143 * ordering. 144 * 145 * @throws NullPointerException if any element is null 146 */ 147 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 148 E e1, E e2, E e3, E e4) { 149 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4)); 150 } 151 152 /** 153 * Returns an immutable sorted multiset containing the given elements sorted by their natural 154 * ordering. 155 * 156 * @throws NullPointerException if any element is null 157 */ 158 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 159 E e1, E e2, E e3, E e4, E e5) { 160 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5)); 161 } 162 163 /** 164 * Returns an immutable sorted multiset containing the given elements sorted by their natural 165 * ordering. 166 * 167 * @throws NullPointerException if any element is null 168 */ 169 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 170 E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) { 171 int size = remaining.length + 6; 172 List<E> all = Lists.newArrayListWithCapacity(size); 173 Collections.addAll(all, e1, e2, e3, e4, e5, e6); 174 Collections.addAll(all, remaining); 175 return copyOf(Ordering.natural(), all); 176 } 177 178 /** 179 * Returns an immutable sorted multiset containing the given elements sorted by their natural 180 * ordering. 181 * 182 * @throws NullPointerException if any of {@code elements} is null 183 */ 184 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> copyOf(E[] elements) { 185 return copyOf(Ordering.natural(), Arrays.asList(elements)); 186 } 187 188 /** 189 * Returns an immutable sorted multiset containing the given elements sorted by their natural 190 * ordering. To create a copy of a {@code SortedMultiset} that preserves the comparator, call 191 * {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once. 192 * 193 * <p>Note that if {@code s} is a {@code Multiset<String>}, then {@code 194 * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>} 195 * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)} 196 * returns an {@code ImmutableSortedMultiset<Multiset<String>>} containing one element (the given 197 * multiset itself). 198 * 199 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 200 * safe to do so. The exact circumstances under which a copy will or will not be performed are 201 * undocumented and subject to change. 202 * 203 * <p>This method is not type-safe, as it may be called on elements that are not mutually 204 * comparable. 205 * 206 * @throws ClassCastException if the elements are not mutually comparable 207 * @throws NullPointerException if any of {@code elements} is null 208 */ 209 public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) { 210 // Hack around E not being a subtype of Comparable. 211 // Unsafe, see ImmutableSortedMultisetFauxverideShim. 212 @SuppressWarnings("unchecked") 213 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 214 return copyOf(naturalOrder, elements); 215 } 216 217 /** 218 * Returns an immutable sorted multiset containing the given elements sorted by their natural 219 * ordering. 220 * 221 * <p>This method is not type-safe, as it may be called on elements that are not mutually 222 * comparable. 223 * 224 * @throws ClassCastException if the elements are not mutually comparable 225 * @throws NullPointerException if any of {@code elements} is null 226 */ 227 public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) { 228 // Hack around E not being a subtype of Comparable. 229 // Unsafe, see ImmutableSortedMultisetFauxverideShim. 230 @SuppressWarnings("unchecked") 231 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 232 return copyOf(naturalOrder, elements); 233 } 234 235 /** 236 * Returns an immutable sorted multiset containing the given elements sorted by the given {@code 237 * Comparator}. 238 * 239 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 240 */ 241 public static <E> ImmutableSortedMultiset<E> copyOf( 242 Comparator<? super E> comparator, Iterator<? extends E> elements) { 243 checkNotNull(comparator); 244 return new Builder<E>(comparator).addAll(elements).build(); 245 } 246 247 /** 248 * Returns an immutable sorted multiset containing the given elements sorted by the given {@code 249 * Comparator}. This method iterates over {@code elements} at most once. 250 * 251 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 252 * safe to do so. The exact circumstances under which a copy will or will not be performed are 253 * undocumented and subject to change. 254 * 255 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 256 */ 257 public static <E> ImmutableSortedMultiset<E> copyOf( 258 Comparator<? super E> comparator, Iterable<? extends E> elements) { 259 if (elements instanceof ImmutableSortedMultiset) { 260 @SuppressWarnings("unchecked") // immutable collections are always safe for covariant casts 261 ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) elements; 262 if (comparator.equals(multiset.comparator())) { 263 if (multiset.isPartialView()) { 264 return copyOfSortedEntries(comparator, multiset.entrySet().asList()); 265 } else { 266 return multiset; 267 } 268 } 269 } 270 elements = Lists.newArrayList(elements); // defensive copy 271 TreeMultiset<E> sortedCopy = TreeMultiset.create(checkNotNull(comparator)); 272 Iterables.addAll(sortedCopy, elements); 273 return copyOfSortedEntries(comparator, sortedCopy.entrySet()); 274 } 275 276 /** 277 * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by 278 * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always 279 * uses the natural ordering of the elements. 280 * 281 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 282 * safe to do so. The exact circumstances under which a copy will or will not be performed are 283 * undocumented and subject to change. 284 * 285 * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent 286 * collection that is currently being modified by another thread. 287 * 288 * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null 289 */ 290 public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) { 291 return copyOfSortedEntries( 292 sortedMultiset.comparator(), Lists.newArrayList(sortedMultiset.entrySet())); 293 } 294 295 private static <E> ImmutableSortedMultiset<E> copyOfSortedEntries( 296 Comparator<? super E> comparator, Collection<Entry<E>> entries) { 297 if (entries.isEmpty()) { 298 return emptyMultiset(comparator); 299 } 300 ImmutableList.Builder<E> elementsBuilder = new ImmutableList.Builder<E>(entries.size()); 301 long[] cumulativeCounts = new long[entries.size() + 1]; 302 int i = 0; 303 for (Entry<E> entry : entries) { 304 elementsBuilder.add(entry.getElement()); 305 cumulativeCounts[i + 1] = cumulativeCounts[i] + entry.getCount(); 306 i++; 307 } 308 return new RegularImmutableSortedMultiset<E>( 309 new RegularImmutableSortedSet<E>(elementsBuilder.build(), comparator), 310 cumulativeCounts, 311 0, 312 entries.size()); 313 } 314 315 @SuppressWarnings("unchecked") 316 static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) { 317 if (Ordering.natural().equals(comparator)) { 318 return (ImmutableSortedMultiset<E>) RegularImmutableSortedMultiset.NATURAL_EMPTY_MULTISET; 319 } else { 320 return new RegularImmutableSortedMultiset<E>(comparator); 321 } 322 } 323 324 ImmutableSortedMultiset() {} 325 326 @Override 327 public final Comparator<? super E> comparator() { 328 return elementSet().comparator(); 329 } 330 331 @Override 332 public abstract ImmutableSortedSet<E> elementSet(); 333 334 @LazyInit @CheckForNull transient ImmutableSortedMultiset<E> descendingMultiset; 335 336 @Override 337 public ImmutableSortedMultiset<E> descendingMultiset() { 338 ImmutableSortedMultiset<E> result = descendingMultiset; 339 if (result == null) { 340 return descendingMultiset = 341 this.isEmpty() 342 ? emptyMultiset(Ordering.from(comparator()).reverse()) 343 : new DescendingImmutableSortedMultiset<E>(this); 344 } 345 return result; 346 } 347 348 /** 349 * {@inheritDoc} 350 * 351 * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. 352 * 353 * @throws UnsupportedOperationException always 354 * @deprecated Unsupported operation. 355 */ 356 @CanIgnoreReturnValue 357 @Deprecated 358 @Override 359 @DoNotCall("Always throws UnsupportedOperationException") 360 @CheckForNull 361 public final Entry<E> pollFirstEntry() { 362 throw new UnsupportedOperationException(); 363 } 364 365 /** 366 * {@inheritDoc} 367 * 368 * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. 369 * 370 * @throws UnsupportedOperationException always 371 * @deprecated Unsupported operation. 372 */ 373 @CanIgnoreReturnValue 374 @Deprecated 375 @Override 376 @DoNotCall("Always throws UnsupportedOperationException") 377 @CheckForNull 378 public final Entry<E> pollLastEntry() { 379 throw new UnsupportedOperationException(); 380 } 381 382 @Override 383 public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType); 384 385 @Override 386 public ImmutableSortedMultiset<E> subMultiset( 387 E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) { 388 checkArgument( 389 comparator().compare(lowerBound, upperBound) <= 0, 390 "Expected lowerBound <= upperBound but %s > %s", 391 lowerBound, 392 upperBound); 393 return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType); 394 } 395 396 @Override 397 public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType); 398 399 /** 400 * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the 401 * comparator has a more general type than the set being generated, such as creating a {@code 402 * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor 403 * instead. 404 * 405 * @throws NullPointerException if {@code comparator} is null 406 */ 407 public static <E> Builder<E> orderedBy(Comparator<E> comparator) { 408 return new Builder<E>(comparator); 409 } 410 411 /** 412 * Returns a builder that creates immutable sorted multisets whose elements are ordered by the 413 * reverse of their natural ordering. 414 * 415 * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code 416 * Comparable<? super E>} as a workaround for javac <a 417 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. 418 */ 419 public static <E extends Comparable<?>> Builder<E> reverseOrder() { 420 return new Builder<E>(Ordering.natural().reverse()); 421 } 422 423 /** 424 * Returns a builder that creates immutable sorted multisets whose elements are ordered by their 425 * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This 426 * method provides more type-safety than {@link #builder}, as it can be called only for classes 427 * that implement {@link Comparable}. 428 * 429 * <p>Note: the type parameter {@code E} extends {@code Comparable<?>} rather than {@code 430 * Comparable<? super E>} as a workaround for javac <a 431 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. 432 */ 433 public static <E extends Comparable<?>> Builder<E> naturalOrder() { 434 return new Builder<E>(Ordering.natural()); 435 } 436 437 /** 438 * A builder for creating immutable multiset instances, especially {@code public static final} 439 * multisets ("constant multisets"). Example: 440 * 441 * <pre>{@code 442 * public static final ImmutableSortedMultiset<Bean> BEANS = 443 * new ImmutableSortedMultiset.Builder<Bean>(colorComparator()) 444 * .addCopies(Bean.COCOA, 4) 445 * .addCopies(Bean.GARDEN, 6) 446 * .addCopies(Bean.RED, 8) 447 * .addCopies(Bean.BLACK_EYED, 10) 448 * .build(); 449 * }</pre> 450 * 451 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 452 * multiple multisets in series. 453 * 454 * @since 12.0 455 */ 456 public static class Builder<E> extends ImmutableMultiset.Builder<E> { 457 /** 458 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 459 * ImmutableSortedMultiset#orderedBy(Comparator)}. 460 */ 461 public Builder(Comparator<? super E> comparator) { 462 super(TreeMultiset.<E>create(checkNotNull(comparator))); 463 } 464 465 /** 466 * Adds {@code element} to the {@code ImmutableSortedMultiset}. 467 * 468 * @param element the element to add 469 * @return this {@code Builder} object 470 * @throws NullPointerException if {@code element} is null 471 */ 472 @CanIgnoreReturnValue 473 @Override 474 public Builder<E> add(E element) { 475 super.add(element); 476 return this; 477 } 478 479 /** 480 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 481 * 482 * @param elements the elements to add 483 * @return this {@code Builder} object 484 * @throws NullPointerException if {@code elements} is null or contains a null element 485 */ 486 @CanIgnoreReturnValue 487 @Override 488 public Builder<E> add(E... elements) { 489 super.add(elements); 490 return this; 491 } 492 493 /** 494 * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}. 495 * 496 * @param element the element to add 497 * @param occurrences the number of occurrences of the element to add. May be zero, in which 498 * case no change will be made. 499 * @return this {@code Builder} object 500 * @throws NullPointerException if {@code element} is null 501 * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation 502 * would result in more than {@link Integer#MAX_VALUE} occurrences of the element 503 */ 504 @CanIgnoreReturnValue 505 @Override 506 public Builder<E> addCopies(E element, int occurrences) { 507 super.addCopies(element, occurrences); 508 return this; 509 } 510 511 /** 512 * Adds or removes the necessary occurrences of an element such that the element attains the 513 * desired count. 514 * 515 * @param element the element to add or remove occurrences of 516 * @param count the desired count of the element in this multiset 517 * @return this {@code Builder} object 518 * @throws NullPointerException if {@code element} is null 519 * @throws IllegalArgumentException if {@code count} is negative 520 */ 521 @CanIgnoreReturnValue 522 @Override 523 public Builder<E> setCount(E element, int count) { 524 super.setCount(element, count); 525 return this; 526 } 527 528 /** 529 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 530 * 531 * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset} 532 * @return this {@code Builder} object 533 * @throws NullPointerException if {@code elements} is null or contains a null element 534 */ 535 @CanIgnoreReturnValue 536 @Override 537 public Builder<E> addAll(Iterable<? extends E> elements) { 538 super.addAll(elements); 539 return this; 540 } 541 542 /** 543 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 544 * 545 * @param elements the elements to add to the {@code ImmutableSortedMultiset} 546 * @return this {@code Builder} object 547 * @throws NullPointerException if {@code elements} is null or contains a null element 548 */ 549 @CanIgnoreReturnValue 550 @Override 551 public Builder<E> addAll(Iterator<? extends E> elements) { 552 super.addAll(elements); 553 return this; 554 } 555 556 /** 557 * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code 558 * Builder}. 559 */ 560 @Override 561 public ImmutableSortedMultiset<E> build() { 562 return copyOfSorted((SortedMultiset<E>) contents); 563 } 564 } 565 566 private static final class SerializedForm<E> implements Serializable { 567 final Comparator<? super E> comparator; 568 final E[] elements; 569 final int[] counts; 570 571 @SuppressWarnings("unchecked") 572 SerializedForm(SortedMultiset<E> multiset) { 573 this.comparator = multiset.comparator(); 574 int n = multiset.entrySet().size(); 575 elements = (E[]) new Object[n]; 576 counts = new int[n]; 577 int i = 0; 578 for (Entry<E> entry : multiset.entrySet()) { 579 elements[i] = entry.getElement(); 580 counts[i] = entry.getCount(); 581 i++; 582 } 583 } 584 585 Object readResolve() { 586 int n = elements.length; 587 Builder<E> builder = new Builder<>(comparator); 588 for (int i = 0; i < n; i++) { 589 builder.addCopies(elements[i], counts[i]); 590 } 591 return builder.build(); 592 } 593 } 594 595 @Override 596 Object writeReplace() { 597 return new SerializedForm<E>(this); 598 } 599}