1/* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 15package com.google.common.collect; 16 17import static com.google.common.base.Preconditions.checkNotNull; 18 19import com.google.common.annotations.GwtIncompatible; 20 21import java.io.Serializable; 22import java.util.ArrayList; 23import java.util.Arrays; 24import java.util.Collection; 25import java.util.Collections; 26import java.util.Comparator; 27import java.util.Iterator; 28import java.util.List; 29 30/** 31 * An immutable {@code SortedMultiset} that stores its elements in a sorted array. Some instances 32 * are ordered by an explicit comparator, while others follow the natural sort ordering of their 33 * elements. Either way, null elements are not supported. 34 * 35 * <p>Unlike {@link Multisets#unmodifiableSortedMultiset}, which is a <i>view</i> of a separate 36 * collection that can still change, an instance of {@code ImmutableSortedMultiset} contains its 37 * own private data and will <i>never</i> change. This class is convenient for {@code public static 38 * final} multisets ("constant multisets") and also lets you easily make a "defensive copy" of a 39 * set provided to your class by a caller. 40 * 41 * <p>The multisets returned by the {@link #headMultiset}, {@link #tailMultiset}, and 42 * {@link #subMultiset} methods share the same array as the original multiset, preventing that 43 * array from being garbage collected. If this is a concern, the data may be copied into a 44 * correctly-sized array by calling {@link #copyOfSorted}. 45 * 46 * <p><b>Note on element equivalence:</b> The {@link #contains(Object)}, 47 * {@link #containsAll(Collection)}, and {@link #equals(Object)} implementations must check whether 48 * a provided object is equivalent to an element in the collection. Unlike most collections, an 49 * {@code ImmutableSortedMultiset} doesn't use {@link Object#equals} to determine if two elements 50 * are equivalent. Instead, with an explicit comparator, the following relation determines whether 51 * elements {@code x} and {@code y} are equivalent: 52 * 53 * <pre> {@code 54 * 55 * {(x, y) | comparator.compare(x, y) == 0}}</pre> 56 * 57 * With natural ordering of elements, the following relation determines whether two elements are 58 * equivalent: 59 * 60 * <pre> {@code 61 * 62 * {(x, y) | x.compareTo(y) == 0}}</pre> 63 * 64 * <b>Warning:</b> Like most multisets, an {@code ImmutableSortedMultiset} will not function 65 * correctly if an element is modified after being placed in the multiset. For this reason, and to 66 * avoid general confusion, it is strongly recommended to place only immutable objects into this 67 * collection. 68 * 69 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as it has no public or 70 * protected constructors. Thus, instances of this type are guaranteed to be immutable. 71 * 72 * @author Louis Wasserman 73 */ 74@GwtIncompatible("hasn't been tested yet") 75abstract class ImmutableSortedMultiset<E> extends ImmutableSortedMultisetFauxverideShim<E> 76 implements SortedMultiset<E> { 77 // TODO(user): GWT compatibility 78 79 private static final Comparator<Comparable> NATURAL_ORDER = Ordering.natural(); 80 81 private static final ImmutableSortedMultiset<Comparable> NATURAL_EMPTY_MULTISET = 82 new EmptyImmutableSortedMultiset<Comparable>(NATURAL_ORDER); 83 84 /** 85 * Returns the empty immutable sorted multiset. 86 */ 87 @SuppressWarnings("unchecked") 88 public static <E> ImmutableSortedMultiset<E> of() { 89 return (ImmutableSortedMultiset) NATURAL_EMPTY_MULTISET; 90 } 91 92 /** 93 * Returns an immutable sorted multiset containing a single element. 94 */ 95 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E element) { 96 return RegularImmutableSortedMultiset.createFromSorted( 97 NATURAL_ORDER, ImmutableList.of(Multisets.immutableEntry(checkNotNull(element), 1))); 98 } 99 100 /** 101 * Returns an immutable sorted multiset containing the given elements sorted by their natural 102 * ordering. 103 * 104 * @throws NullPointerException if any element is null 105 */ 106 @SuppressWarnings("unchecked") 107 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2) { 108 return copyOf(Ordering.natural(), Arrays.asList(e1, e2)); 109 } 110 111 /** 112 * Returns an immutable sorted multiset containing the given elements sorted by their natural 113 * ordering. 114 * 115 * @throws NullPointerException if any element is null 116 */ 117 @SuppressWarnings("unchecked") 118 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of(E e1, E e2, E e3) { 119 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3)); 120 } 121 122 /** 123 * Returns an immutable sorted multiset containing the given elements sorted by their natural 124 * ordering. 125 * 126 * @throws NullPointerException if any element is null 127 */ 128 @SuppressWarnings("unchecked") 129 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> of( 130 E e1, E e2, E e3, E e4) { 131 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4)); 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, E e5) { 143 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5)); 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, 155 E e2, 156 E e3, 157 E e4, 158 E e5, 159 E e6, 160 E... remaining) { 161 int size = remaining.length + 6; 162 List<E> all = new ArrayList<E>(size); 163 Collections.addAll(all, e1, e2, e3, e4, e5, e6); 164 Collections.addAll(all, remaining); 165 return copyOf(Ordering.natural(), all); 166 } 167 168 /** 169 * Returns an immutable sorted multiset containing the given elements sorted by their natural 170 * ordering. 171 * 172 * @throws NullPointerException if any of {@code elements} is null 173 */ 174 public static <E extends Comparable<? super E>> ImmutableSortedMultiset<E> copyOf(E[] elements) { 175 return copyOf(Ordering.natural(), Arrays.asList(elements)); 176 } 177 178 /** 179 * Returns an immutable sorted multiset containing the given elements sorted by their natural 180 * ordering. To create a copy of a {@code SortedMultiset} that preserves the 181 * comparator, call {@link #copyOfSorted} instead. This method iterates over {@code elements} at 182 * most once. 183 * 184 * <p>Note that if {@code s} is a {@code multiset<String>}, then {@code 185 * ImmutableSortedMultiset.copyOf(s)} returns an {@code ImmutableSortedMultiset<String>} 186 * containing each of the strings in {@code s}, while {@code ImmutableSortedMultiset.of(s)} 187 * returns an {@code ImmutableSortedMultiset<multiset<String>>} containing one element (the given 188 * multiset itself). 189 * 190 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 191 * safe to do so. The exact circumstances under which a copy will or will not be performed are 192 * undocumented and subject to change. 193 * 194 * <p>This method is not type-safe, as it may be called on elements that are not mutually 195 * comparable. 196 * 197 * @throws ClassCastException if the elements are not mutually comparable 198 * @throws NullPointerException if any of {@code elements} is null 199 */ 200 public static <E> ImmutableSortedMultiset<E> copyOf(Iterable<? extends E> elements) { 201 // Hack around E not being a subtype of Comparable. 202 // Unsafe, see ImmutableSortedMultisetFauxverideShim. 203 @SuppressWarnings("unchecked") 204 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 205 return copyOf(naturalOrder, elements); 206 } 207 208 /** 209 * Returns an immutable sorted multiset containing the given elements sorted by their natural 210 * ordering. 211 * 212 * <p>This method is not type-safe, as it may be called on elements that are not mutually 213 * comparable. 214 * 215 * @throws ClassCastException if the elements are not mutually comparable 216 * @throws NullPointerException if any of {@code elements} is null 217 */ 218 public static <E> ImmutableSortedMultiset<E> copyOf(Iterator<? extends E> elements) { 219 // Hack around E not being a subtype of Comparable. 220 // Unsafe, see ImmutableSortedMultisetFauxverideShim. 221 @SuppressWarnings("unchecked") 222 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 223 return copyOfInternal(naturalOrder, elements); 224 } 225 226 /** 227 * Returns an immutable sorted multiset containing the given elements sorted by the given {@code 228 * Comparator}. 229 * 230 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 231 */ 232 public static <E> ImmutableSortedMultiset<E> copyOf( 233 Comparator<? super E> comparator, Iterator<? extends E> elements) { 234 checkNotNull(comparator); 235 return copyOfInternal(comparator, elements); 236 } 237 238 /** 239 * Returns an immutable sorted multiset containing the given elements sorted by the given {@code 240 * Comparator}. This method iterates over {@code elements} at most once. 241 * 242 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 243 * safe to do so. The exact circumstances under which a copy will or will not be performed are 244 * undocumented and subject to change. 245 * 246 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 247 */ 248 public static <E> ImmutableSortedMultiset<E> copyOf( 249 Comparator<? super E> comparator, Iterable<? extends E> elements) { 250 checkNotNull(comparator); 251 return copyOfInternal(comparator, elements); 252 } 253 254 /** 255 * Returns an immutable sorted multiset containing the elements of a sorted multiset, sorted by 256 * the same {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which 257 * always uses the natural ordering of the elements. 258 * 259 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 260 * safe to do so. The exact circumstances under which a copy will or will not be performed are 261 * undocumented and subject to change. 262 * 263 * <p>This method is safe to use even when {@code sortedMultiset} is a synchronized or concurrent 264 * collection that is currently being modified by another thread. 265 * 266 * @throws NullPointerException if {@code sortedMultiset} or any of its elements is null 267 */ 268 @SuppressWarnings("unchecked") 269 public static <E> ImmutableSortedMultiset<E> copyOfSorted(SortedMultiset<E> sortedMultiset) { 270 Comparator<? super E> comparator = sortedMultiset.comparator(); 271 if (comparator == null) { 272 comparator = (Comparator<? super E>) NATURAL_ORDER; 273 } 274 return copyOfInternal(comparator, sortedMultiset); 275 } 276 277 @SuppressWarnings("unchecked") 278 private static <E> ImmutableSortedMultiset<E> copyOfInternal( 279 Comparator<? super E> comparator, Iterable<? extends E> iterable) { 280 if (SortedIterables.hasSameComparator(comparator, iterable) 281 && iterable instanceof ImmutableSortedMultiset<?>) { 282 ImmutableSortedMultiset<E> multiset = (ImmutableSortedMultiset<E>) iterable; 283 if (!multiset.isPartialView()) { 284 return (ImmutableSortedMultiset<E>) iterable; 285 } 286 } 287 ImmutableList<Entry<E>> entries = 288 (ImmutableList) ImmutableList.copyOf(SortedIterables.sortedCounts(comparator, iterable)); 289 if (entries.isEmpty()) { 290 return emptyMultiset(comparator); 291 } 292 verifyEntries(entries); 293 return RegularImmutableSortedMultiset.createFromSorted(comparator, entries); 294 } 295 296 private static <E> ImmutableSortedMultiset<E> copyOfInternal( 297 Comparator<? super E> comparator, Iterator<? extends E> iterator) { 298 @SuppressWarnings("unchecked") // We can safely cast from IL<Entry<? extends E>> to IL<Entry<E>> 299 ImmutableList<Entry<E>> entries = 300 (ImmutableList) ImmutableList.copyOf(SortedIterables.sortedCounts(comparator, iterator)); 301 if (entries.isEmpty()) { 302 return emptyMultiset(comparator); 303 } 304 verifyEntries(entries); 305 return RegularImmutableSortedMultiset.createFromSorted(comparator, entries); 306 } 307 308 private static <E> void verifyEntries(Collection<Entry<E>> entries) { 309 for (Entry<E> entry : entries) { 310 checkNotNull(entry.getElement()); 311 } 312 } 313 314 @SuppressWarnings("unchecked") 315 static <E> ImmutableSortedMultiset<E> emptyMultiset(Comparator<? super E> comparator) { 316 if (NATURAL_ORDER.equals(comparator)) { 317 return (ImmutableSortedMultiset) NATURAL_EMPTY_MULTISET; 318 } 319 return new EmptyImmutableSortedMultiset<E>(comparator); 320 } 321 322 private final transient Comparator<? super E> comparator; 323 324 ImmutableSortedMultiset(Comparator<? super E> comparator) { 325 this.comparator = checkNotNull(comparator); 326 } 327 328 @Override 329 public Comparator<? super E> comparator() { 330 return comparator; 331 } 332 333 // Pretend the comparator can compare anything. If it turns out it can't 334 // compare two elements, it'll throw a CCE. Only methods that are specified to 335 // throw CCE should call this. 336 @SuppressWarnings("unchecked") 337 Comparator<Object> unsafeComparator() { 338 return (Comparator<Object>) comparator; 339 } 340 341 private transient Comparator<? super E> reverseComparator; 342 343 Comparator<? super E> reverseComparator() { 344 Comparator<? super E> result = reverseComparator; 345 if (result == null) { 346 return reverseComparator = Ordering.from(comparator).<E>reverse(); 347 } 348 return result; 349 } 350 351 private transient ImmutableSortedSet<E> elementSet; 352 353 @Override 354 public ImmutableSortedSet<E> elementSet() { 355 ImmutableSortedSet<E> result = elementSet; 356 if (result == null) { 357 return elementSet = createElementSet(); 358 } 359 return result; 360 } 361 362 abstract ImmutableSortedSet<E> createElementSet(); 363 364 abstract ImmutableSortedSet<E> createDescendingElementSet(); 365 366 transient ImmutableSortedMultiset<E> descendingMultiset; 367 368 @Override 369 public ImmutableSortedMultiset<E> descendingMultiset() { 370 ImmutableSortedMultiset<E> result = descendingMultiset; 371 if (result == null) { 372 return descendingMultiset = new DescendingImmutableSortedMultiset<E>(this); 373 } 374 return result; 375 } 376 377 abstract UnmodifiableIterator<Entry<E>> descendingEntryIterator(); 378 379 /** 380 * {@inheritDoc} 381 * 382 * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. 383 */ 384 @Override 385 public final Entry<E> pollFirstEntry() { 386 throw new UnsupportedOperationException(); 387 } 388 389 /** 390 * {@inheritDoc} 391 * 392 * <p>This implementation is guaranteed to throw an {@link UnsupportedOperationException}. 393 */ 394 @Override 395 public Entry<E> pollLastEntry() { 396 throw new UnsupportedOperationException(); 397 } 398 399 @Override 400 public abstract ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType); 401 402 @Override 403 public ImmutableSortedMultiset<E> subMultiset( 404 E lowerBound, BoundType lowerBoundType, E upperBound, BoundType upperBoundType) { 405 return tailMultiset(lowerBound, lowerBoundType).headMultiset(upperBound, upperBoundType); 406 } 407 408 @Override 409 public abstract ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType); 410 411 /** 412 * Returns a builder that creates immutable sorted multisets with an explicit comparator. If the 413 * comparator has a more general type than the set being generated, such as creating a {@code 414 * SortedMultiset<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} 415 * constructor instead. 416 * 417 * @throws NullPointerException if {@code comparator} is null 418 */ 419 public static <E> Builder<E> orderedBy(Comparator<E> comparator) { 420 return new Builder<E>(comparator); 421 } 422 423 /** 424 * Returns a builder that creates immutable sorted multisets whose elements are ordered by the 425 * reverse of their natural ordering. 426 * 427 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather than {@code 428 * Comparable<? super E>} as a workaround for javac <a 429 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. 430 */ 431 public static <E extends Comparable<E>> Builder<E> reverseOrder() { 432 return new Builder<E>(Ordering.natural().reverse()); 433 } 434 435 /** 436 * Returns a builder that creates immutable sorted multisets whose elements are ordered by their 437 * natural ordering. The sorted multisets use {@link Ordering#natural()} as the comparator. This 438 * method provides more type-safety than {@link #builder}, as it can be called only for classes 439 * that implement {@link Comparable}. 440 * 441 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather than {@code 442 * Comparable<? super E>} as a workaround for javac <a 443 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 6468354</a>. 444 */ 445 public static <E extends Comparable<E>> Builder<E> naturalOrder() { 446 return new Builder<E>(Ordering.natural()); 447 } 448 449 /** 450 * A builder for creating immutable multiset instances, especially {@code public static final} 451 * multisets ("constant multisets"). Example: 452 * 453 * <pre> {@code 454 * 455 * public static final ImmutableSortedMultiset<Bean> BEANS = 456 * new ImmutableSortedMultiset.Builder<Bean>() 457 * .addCopies(Bean.COCOA, 4) 458 * .addCopies(Bean.GARDEN, 6) 459 * .addCopies(Bean.RED, 8) 460 * .addCopies(Bean.BLACK_EYED, 10) 461 * .build();}</pre> 462 * 463 * Builder instances can be reused; it is safe to call {@link #build} multiple times to build 464 * multiple multisets in series. 465 */ 466 public static class Builder<E> extends ImmutableMultiset.Builder<E> { 467 private final Comparator<? super E> comparator; 468 469 /** 470 * Creates a new builder. The returned builder is equivalent to the builder generated by 471 * {@link ImmutableSortedMultiset#orderedBy(Comparator)}. 472 */ 473 public Builder(Comparator<? super E> comparator) { 474 super(TreeMultiset.<E>create(comparator)); 475 this.comparator = checkNotNull(comparator); 476 } 477 478 /** 479 * Adds {@code element} to the {@code ImmutableSortedMultiset}. 480 * 481 * @param element the element to add 482 * @return this {@code Builder} object 483 * @throws NullPointerException if {@code element} is null 484 */ 485 @Override 486 public Builder<E> add(E element) { 487 super.add(element); 488 return this; 489 } 490 491 /** 492 * Adds a number of occurrences of an element to this {@code ImmutableSortedMultiset}. 493 * 494 * @param element the element to add 495 * @param occurrences the number of occurrences of the element to add. May be zero, in which 496 * case no change will be made. 497 * @return this {@code Builder} object 498 * @throws NullPointerException if {@code element} is null 499 * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation 500 * would result in more than {@link Integer#MAX_VALUE} occurrences of the element 501 */ 502 @Override 503 public Builder<E> addCopies(E element, int occurrences) { 504 super.addCopies(element, occurrences); 505 return this; 506 } 507 508 /** 509 * Adds or removes the necessary occurrences of an element such that the element attains the 510 * desired count. 511 * 512 * @param element the element to add or remove occurrences of 513 * @param count the desired count of the element in this multiset 514 * @return this {@code Builder} object 515 * @throws NullPointerException if {@code element} is null 516 * @throws IllegalArgumentException if {@code count} is negative 517 */ 518 @Override 519 public Builder<E> setCount(E element, int count) { 520 super.setCount(element, count); 521 return this; 522 } 523 524 /** 525 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 526 * 527 * @param elements the elements to add 528 * @return this {@code Builder} object 529 * @throws NullPointerException if {@code elements} is null or contains a null element 530 */ 531 @Override 532 public Builder<E> add(E... elements) { 533 super.add(elements); 534 return this; 535 } 536 537 /** 538 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 539 * 540 * @param elements the {@code Iterable} to add to the {@code ImmutableSortedMultiset} 541 * @return this {@code Builder} object 542 * @throws NullPointerException if {@code elements} is null or contains a null element 543 */ 544 @Override 545 public Builder<E> addAll(Iterable<? extends E> elements) { 546 super.addAll(elements); 547 return this; 548 } 549 550 /** 551 * Adds each element of {@code elements} to the {@code ImmutableSortedMultiset}. 552 * 553 * @param elements the elements to add to the {@code ImmutableSortedMultiset} 554 * @return this {@code Builder} object 555 * @throws NullPointerException if {@code elements} is null or contains a null element 556 */ 557 @Override 558 public Builder<E> addAll(Iterator<? extends E> elements) { 559 super.addAll(elements); 560 return this; 561 } 562 563 /** 564 * Returns a newly-created {@code ImmutableSortedMultiset} based on the contents of the {@code 565 * Builder}. 566 */ 567 @Override 568 public ImmutableSortedMultiset<E> build() { 569 return copyOf(comparator, contents); 570 } 571 } 572 573 private static final class SerializedForm implements Serializable { 574 Comparator comparator; 575 Object[] elements; 576 int[] counts; 577 578 SerializedForm(SortedMultiset<?> multiset) { 579 this.comparator = multiset.comparator(); 580 int n = multiset.entrySet().size(); 581 elements = new Object[n]; 582 counts = new int[n]; 583 int i = 0; 584 for (Entry<?> entry : multiset.entrySet()) { 585 elements[i] = entry.getElement(); 586 counts[i] = entry.getCount(); 587 i++; 588 } 589 } 590 591 @SuppressWarnings("unchecked") 592 Object readResolve() { 593 int n = elements.length; 594 Builder<Object> builder = orderedBy(comparator); 595 for (int i = 0; i < n; i++) { 596 builder.addCopies(elements[i], counts[i]); 597 } 598 return builder.build(); 599 } 600 } 601 602 @Override 603 Object writeReplace() { 604 return new SerializedForm(this); 605 } 606} 607