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