Find Usages Diff Raw Download HTML Widget
Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions 
1
  /*
2
   * Copyright (C) 2007 The Guava Authors
3
   *
4
   * Licensed under the Apache License, Version 2.0 (the "License");
5
   * you may not use this file except in compliance with the License.
6
   * You may obtain a copy of the License at
7
   *
8
   * http://www.apache.org/licenses/LICENSE-2.0
9
   *
10
  * Unless required by applicable law or agreed to in writing, software
11
  * distributed under the License is distributed on an "AS IS" BASIS,
12
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
  * See the License for the specific language governing permissions and
14
  * limitations under the License.
15
  */
16
 
17
 package com.google.common.collect;
18
 
19
 import static com.google.common.base.Preconditions.checkArgument;
20
 import static com.google.common.base.Preconditions.checkState;
21
 
26
 
35
 
36
 import  javax.annotation.Nullable;

A multiset which maintains the ordering of its elements, according to either their natural order or an explicit Comparator. In all cases, this implementation uses Comparable.compareTo or Comparator.compare instead of Object.equals to determine equivalence of instances.

Warning: The comparison must be consistent with equals as explained by the Comparable class specification. Otherwise, the resulting multiset will violate the java.util.Collection contract, which is specified in terms of Object.equals.

See the Guava User Guide article on Multiset.

Author(s):
Louis Wasserman
Jared Levy
Since:
2.0 (imported from Google Collections Library)
55
 
56
 @GwtCompatible(emulated = true)
57
 public final class TreeMultiset<E> extends AbstractSortedMultiset<E> implements Serializable {

  
Creates a new, empty multiset, sorted according to the elements' natural order. All elements inserted into the multiset must implement the Comparable interface. Furthermore, all such elements must be mutually comparable: e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the multiset. If the user attempts to add an element to the multiset that violates this constraint (for example, the user attempts to add a string element to a set whose elements are integers), the add(Object) call will throw a ClassCastException.

The type specification is <E extends Comparable>, instead of the more specific <E extends Comparable<? super E>>, to support classes defined without generics. 

70
 
71
   public static <E extends Comparable> TreeMultiset<E> create() {
72
     return new TreeMultiset<E>(Ordering.natural());
73
   }

  
Creates a new, empty multiset, sorted according to the specified comparator. All elements inserted into the multiset must be mutually comparable by the specified comparator: comparator.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the multiset. If the user attempts to add an element to the multiset that violates this constraint, the add(Object) call will throw a ClassCastException.

Parameters:
comparator the comparator that will be used to sort this multiset. A null value indicates that the elements' natural ordering should be used.
86
 
87
   @SuppressWarnings("unchecked")
88
   public static <E> TreeMultiset<E> create(@Nullable Comparator<? super E> comparator) {
89
     return (comparator == null)
90
         ? new TreeMultiset<E>((Comparator) Ordering.natural())
91
         : new TreeMultiset<E>(comparator);
92
   }

  
Creates an empty multiset containing the given initial elements, sorted according to the elements' natural order.

This implementation is highly efficient when elements is itself a Multiset.

The type specification is <E extends Comparable>, instead of the more specific <E extends Comparable<? super E>>, to support classes defined without generics. 

103
  public static <E extends Comparable> TreeMultiset<E> create(Iterable<? extends E> elements) {
104
    TreeMultiset<E> multiset = create();
105
    Iterables.addAll(multiset, elements);
106
    return multiset;
107
  }
109
  private final transient Reference<AvlNode<E>> rootReference;
110
  private final transient GeneralRange<E> range;
111
  private final transient AvlNode<E> header;
113
  TreeMultiset(Reference<AvlNode<E>> rootReference, GeneralRange<E> range, AvlNode<E> endLink) {
114
    super(range.comparator());
115
    this. = rootReference;
116
    this. = range;
117
    this. = endLink;
118
  }
120
  TreeMultiset(Comparator<? super E> comparator) {
121
    super(comparator);
122
    this. = GeneralRange.all(comparator);
123
    this. = new AvlNode<E>(null, 1);
125
    this. = new Reference<AvlNode<E>>();
126
  }

  
A function which can be summed across a subtree. 
131
  private enum Aggregate {
132
    SIZE {
133
      @Override
134
      int nodeAggregate(AvlNode<?> node) {
135
        return node.elemCount;
136
      }
138
      @Override
139
      long treeAggregate(@Nullable AvlNode<?> root) {
140
        return (root == null) ? 0 : root.totalCount;
141
      }
142
    },
143
    DISTINCT {
144
      @Override
145
      int nodeAggregate(AvlNode<?> node) {
146
        return 1;
147
      }
149
      @Override
150
      long treeAggregate(@Nullable AvlNode<?> root) {
151
        return (root == null) ? 0 : root.distinctElements;
152
      }
153
    };
154
    abstract int nodeAggregate(AvlNode<?> node);
156
    abstract long treeAggregate(@Nullable AvlNode<?> root);
157
  }
159
  private long aggregateForEntries(Aggregate aggr) {
160
    AvlNode<E> root = .get();
161
    long total = aggr.treeAggregate(root);
162
    if (.hasLowerBound()) {
163
      total -= aggregateBelowRange(aggr, root);
164
    }
165
    if (.hasUpperBound()) {
166
      total -= aggregateAboveRange(aggr, root);
167
    }
168
    return total;
169
  }
171
  private long aggregateBelowRange(Aggregate aggr, @Nullable AvlNode<E> node) {
172
    if (node == null) {
173
      return 0;
174
    }
175
    int cmp = comparator().compare(.getLowerEndpoint(), node.elem);
176
    if (cmp < 0) {
177
      return aggregateBelowRange(aggr, node.left);
178
    } else if (cmp == 0) {
179
      switch (.getLowerBoundType()) {
180
        case :
181
          return aggr.nodeAggregate(node) + aggr.treeAggregate(node.left);
182
        case :
183
          return aggr.treeAggregate(node.left);
184
        default:
185
          throw new AssertionError();
186
      }
187
    } else {
188
      return aggr.treeAggregate(node.left) + aggr.nodeAggregate(node)
189
          + aggregateBelowRange(aggr, node.right);
190
    }
191
  }
193
  private long aggregateAboveRange(Aggregate aggr, @Nullable AvlNode<E> node) {
194
    if (node == null) {
195
      return 0;
196
    }
197
    int cmp = comparator().compare(.getUpperEndpoint(), node.elem);
198
    if (cmp > 0) {
199
      return aggregateAboveRange(aggr, node.right);
200
    } else if (cmp == 0) {
201
      switch (.getUpperBoundType()) {
202
        case :
203
          return aggr.nodeAggregate(node) + aggr.treeAggregate(node.right);
204
        case :
205
          return aggr.treeAggregate(node.right);
206
        default:
207
          throw new AssertionError();
208
      }
209
    } else {
210
      return aggr.treeAggregate(node.right) + aggr.nodeAggregate(node)
211
          + aggregateAboveRange(aggr, node.left);
212
    }
213
  }
216
  public int size() {
218
  }
221
  int distinctElements() {
223
  }
226
  public int count(@Nullable Object element) {
227
    try {
228
      @SuppressWarnings("unchecked")
229
      E e = (E) element;
230
      AvlNode<E> root = .get();
231
      if (!.contains(e) || root == null) {
232
        return 0;
233
      }
234
      return root.count(comparator(), e);
235
    } catch (ClassCastException e) {
236
      return 0;
237
    } catch (NullPointerException e) {
238
      return 0;
239
    }
240
  }
243
  public int add(@Nullable E element, int occurrences) {
244
    checkArgument(occurrences >= 0, "occurrences must be >= 0 but was %s", occurrences);
245
    if (occurrences == 0) {
246
      return count(element);
247
    }
248
    checkArgument(.contains(element));
249
    AvlNode<E> root = .get();
250
    if (root == null) {
251
      comparator().compare(element, element);
252
      AvlNode<E> newRoot = new AvlNode<E>(element, occurrences);
253
      successor(, newRoot, );
254
      .checkAndSet(root, newRoot);
255
      return 0;
256
    }
257
    int[] result = new int[1]; // used as a mutable int reference to hold result
258
    AvlNode<E> newRoot = root.add(comparator(), element, occurrences, result);
259
    .checkAndSet(root, newRoot);
260
    return result[0];
261
  }
264
  public int remove(@Nullable Object element, int occurrences) {
265
    checkArgument(occurrences >= 0, "occurrences must be >= 0 but was %s", occurrences);
266
    if (occurrences == 0) {
267
      return count(element);
268
    }
269
    AvlNode<E> root = .get();
270
    int[] result = new int[1]; // used as a mutable int reference to hold result
271
    AvlNode<E> newRoot;
272
    try {
273
      @SuppressWarnings("unchecked")
274
      E e = (E) element;
275
      if (!.contains(e) || root == null) {
276
        return 0;
277
      }
278
      newRoot = root.remove(comparator(), e, occurrences, result);
279
    } catch (ClassCastException e) {
280
      return 0;
281
    } catch (NullPointerException e) {
282
      return 0;
283
    }
284
    .checkAndSet(root, newRoot);
285
    return result[0];
286
  }
289
  public int setCount(@Nullable E element, int count) {
290
    checkArgument(count >= 0);
291
    if (!.contains(element)) {
292
      checkArgument(count == 0);
293
      return 0;
294
    }
296
    AvlNode<E> root = .get();
297
    if (root == null) {
298
      if (count > 0) {
299
        add(element, count);
300
      }
301
      return 0;
302
    }
303
    int[] result = new int[1]; // used as a mutable int reference to hold result
304
    AvlNode<E> newRoot = root.setCount(comparator(), element, count, result);
305
    .checkAndSet(root, newRoot);
306
    return result[0];
307
  }
310
  public boolean setCount(@Nullable E element, int oldCount, int newCount) {
311
    checkArgument(newCount >= 0);
312
    checkArgument(oldCount >= 0);
313
    checkArgument(.contains(element));
315
    AvlNode<E> root = .get();
316
    if (root == null) {
317
      if (oldCount == 0) {
318
        if (newCount > 0) {
319
          add(element, newCount);
320
        }
321
        return true;
322
      } else {
323
        return false;
324
      }
325
    }
326
    int[] result = new int[1]; // used as a mutable int reference to hold result
327
    AvlNode<E> newRoot = root.setCount(comparator(), element, oldCount, newCount, result);
328
    .checkAndSet(root, newRoot);
329
    return result[0] == oldCount;
330
  }
332
  private Entry<E> wrapEntry(final AvlNode<E> baseEntry) {
333
    return new Multisets.AbstractEntry<E>() {
334
      @Override
335
      public E getElement() {
336
        return baseEntry.getElement();
337
      }
339
      @Override
340
      public int getCount() {
341
        int result = baseEntry.getCount();
342
        if (result == 0) {
343
          return count(getElement());
344
        } else {
345
          return result;
346
        }
347
      }
348
    };
349
  }

  
Returns the first node in the tree that is in range. 
354
  @Nullable private AvlNode<E> firstNode() {
355
    AvlNode<E> root = .get();
356
    if (root == null) {
357
      return null;
358
    }
359
    AvlNode<E> node;
360
    if (.hasLowerBound()) {
361
      E endpoint = .getLowerEndpoint();
362
      node = .get().ceiling(comparator(), endpoint);
363
      if (node == null) {
364
        return null;
365
      }
366
      if (.getLowerBoundType() == .
367
          && comparator().compare(endpoint, node.getElement()) == 0) {
368
        node = node.succ;
369
      }
370
    } else {
371
      node = .;
372
    }
373
    return (node ==  || !.contains(node.getElement())) ? null : node;
374
  }
376
  @Nullable private AvlNode<E> lastNode() {
377
    AvlNode<E> root = .get();
378
    if (root == null) {
379
      return null;
380
    }
381
    AvlNode<E> node;
382
    if (.hasUpperBound()) {
383
      E endpoint = .getUpperEndpoint();
384
      node = .get().floor(comparator(), endpoint);
385
      if (node == null) {
386
        return null;
387
      }
388
      if (.getUpperBoundType() == .
389
          && comparator().compare(endpoint, node.getElement()) == 0) {
390
        node = node.pred;
391
      }
392
    } else {
393
      node = .;
394
    }
395
    return (node ==  || !.contains(node.getElement())) ? null : node;
396
  }
400
    return new Iterator<Entry<E>>() {
401
      AvlNode<E> current = firstNode();
402
      Entry<E> prevEntry;
404
      @Override
405
      public boolean hasNext() {
406
        if ( == null) {
407
          return false;
408
        } else if (.tooHigh(.getElement())) {
409
           = null;
410
          return false;
411
        } else {
412
          return true;
413
        }
414
      }
416
      @Override
417
      public Entry<E> next() {
418
        if (!hasNext()) {
419
          throw new NoSuchElementException();
420
        }
421
        Entry<E> result = wrapEntry();
422
         = result;
423
        if (. == ) {
424
           = null;
425
        } else {
426
           = .;
427
        }
428
        return result;
429
      }
431
      @Override
432
      public void remove() {
433
        checkState( != null);
434
        setCount(.getElement(), 0);
435
         = null;
436
      }
437
    };
438
  }
442
    return new Iterator<Entry<E>>() {
443
      AvlNode<E> current = lastNode();
444
      Entry<E> prevEntry = null;
446
      @Override
447
      public boolean hasNext() {
448
        if ( == null) {
449
          return false;
450
        } else if (.tooLow(.getElement())) {
451
           = null;
452
          return false;
453
        } else {
454
          return true;
455
        }
456
      }
458
      @Override
459
      public Entry<E> next() {
460
        if (!hasNext()) {
461
          throw new NoSuchElementException();
462
        }
463
        Entry<E> result = wrapEntry();
464
         = result;
465
        if (. == ) {
466
           = null;
467
        } else {
468
           = .;
469
        }
470
        return result;
471
      }
473
      @Override
474
      public void remove() {
475
        checkState( != null);
476
        setCount(.getElement(), 0);
477
         = null;
478
      }
479
    };
480
  }
483
  public SortedMultiset<E> headMultiset(@Nullable E upperBound, BoundType boundType) {
484
    return new TreeMultiset<E>(, .intersect(GeneralRange.upTo(
485
        comparator(),
486
        upperBound,
487
        boundType)), );
488
  }
491
  public SortedMultiset<E> tailMultiset(@Nullable E lowerBound, BoundType boundType) {
492
    return new TreeMultiset<E>(, .intersect(GeneralRange.downTo(
493
        comparator(),
494
        lowerBound,
495
        boundType)), );
496
  }
498
  static int distinctElements(@Nullable AvlNode<?> node) {
499
    return (node == null) ? 0 : node.distinctElements;
500
  }
502
  private static final class Reference<T> {
503
    @Nullable private T value;
505
    @Nullable public T get() {
506
      return ;
507
    }
509
    public void checkAndSet(@Nullable T expected, T newValue) {
510
      if ( != expected) {
511
        throw new ConcurrentModificationException();
512
      }
513
       = newValue;
514
    }
515
  }
517
  private static final class AvlNode<E> extends Multisets.AbstractEntry<E> {
518
    @Nullable private final E elem;
520
    // elemCount is 0 iff this node has been deleted.
521
    private int elemCount;
523
    private int distinctElements;
524
    private long totalCount;
525
    private int height;
526
    private AvlNode<E> left;
527
    private AvlNode<E> right;
528
    private AvlNode<E> pred;
529
    private AvlNode<E> succ;
531
    AvlNode(@Nullable E elem, int elemCount) {
532
      checkArgument(elemCount > 0);
533
      this. = elem;
534
      this. = elemCount;
535
      this. = elemCount;
536
      this. = 1;
537
      this. = 1;
538
      this. = null;
539
      this. = null;
540
    }
542
    public int count(Comparator<? super E> comparator, E e) {
543
      int cmp = comparator.compare(e, );
544
      if (cmp < 0) {
545
        return ( == null) ? 0 : .count(comparator, e);
546
      } else if (cmp > 0) {
547
        return ( == null) ? 0 : .count(comparator, e);
548
      } else {
549
        return ;
550
      }
551
    }
553
    private AvlNode<E> addRightChild(E e, int count) {
554
       = new AvlNode<E>(e, count);
555
      successor(this, , );
556
       = Math.max(2, );
557
      ++;
558
       += count;
559
      return this;
560
    }
562
    private AvlNode<E> addLeftChild(E e, int count) {
563
       = new AvlNode<E>(e, count);
564
      successor(, , this);
565
       = Math.max(2, );
566
      ++;
567
       += count;
568
      return this;
569
    }
571
    AvlNode<E> add(Comparator<? super E> comparator, @Nullable E e, int count, int[] result) {
572
      /*
573
       * It speeds things up considerably to unconditionally add count to totalCount here,
574
       * but that destroys failure atomicity in the case of count overflow. =(
575
       */
576
      int cmp = comparator.compare(e, );
577
      if (cmp < 0) {
578
        AvlNode<E> initLeft = ;
579
        if (initLeft == null) {
580
          result[0] = 0;
581
          return addLeftChild(e, count);
582
        }
583
        int initHeight = initLeft.height;
585
         = initLeft.add(comparator, e, count, result);
586
        if (result[0] == 0) {
587
          ++;
588
        }
589
        this. += count;
590
        return (. == initHeight) ? this : rebalance();
591
      } else if (cmp > 0) {
592
        AvlNode<E> initRight = ;
593
        if (initRight == null) {
594
          result[0] = 0;
595
          return addRightChild(e, count);
596
        }
597
        int initHeight = initRight.height;
599
         = initRight.add(comparator, e, count, result);
600
        if (result[0] == 0) {
601
          ++;
602
        }
603
        this. += count;
604
        return (. == initHeight) ? this : rebalance();
605
      }
607
      // adding count to me!  No rebalance possible.
608
      result[0] = ;
609
      long resultCount = (long)  + count;
610
      checkArgument(resultCount <= .);
611
      this. += count;
612
      this. += count;
613
      return this;
614
    }
616
    AvlNode<E> remove(Comparator<? super E> comparator, @Nullable E e, int count, int[] result) {
617
      int cmp = comparator.compare(e, );
618
      if (cmp < 0) {
619
        AvlNode<E> initLeft = ;
620
        if (initLeft == null) {
621
          result[0] = 0;
622
          return this;
623
        }
625
         = initLeft.remove(comparator, e, count, result);
627
        if (result[0] > 0) {
628
          if (count >= result[0]) {
629
            this.--;
630
            this. -= result[0];
631
          } else {
632
            this. -= count;
633
          }
634
        }
635
        return (result[0] == 0) ? this : rebalance();
636
      } else if (cmp > 0) {
637
        AvlNode<E> initRight = ;
638
        if (initRight == null) {
639
          result[0] = 0;
640
          return this;
641
        }
643
         = initRight.remove(comparator, e, count, result);
645
        if (result[0] > 0) {
646
          if (count >= result[0]) {
647
            this.--;
648
            this. -= result[0];
649
          } else {
650
            this. -= count;
651
          }
652
        }
653
        return rebalance();
654
      }
656
      // removing count from me!
657
      result[0] = ;
658
      if (count >= ) {
659
        return deleteMe();
660
      } else {
661
        this. -= count;
662
        this. -= count;
663
        return this;
664
      }
665
    }
667
    AvlNode<E> setCount(Comparator<? super E> comparator, @Nullable E e, int count, int[] result) {
668
      int cmp = comparator.compare(e, );
669
      if (cmp < 0) {
670
        AvlNode<E> initLeft = ;
671
        if (initLeft == null) {
672
          result[0] = 0;
673
          return (count > 0) ? addLeftChild(e, count) : this;
674
        }
676
         = initLeft.setCount(comparator, e, count, result);
678
        if (count == 0 && result[0] != 0) {
679
          this.--;
680
        } else if (count > 0 && result[0] == 0) {
681
          this.++;
682
        }
684
        this. += count - result[0];
685
        return rebalance();
686
      } else if (cmp > 0) {
687
        AvlNode<E> initRight = ;
688
        if (initRight == null) {
689
          result[0] = 0;
690
          return (count > 0) ? addRightChild(e, count) : this;
691
        }
693
         = initRight.setCount(comparator, e, count, result);
695
        if (count == 0 && result[0] != 0) {
696
          this.--;
697
        } else if (count > 0 && result[0] == 0) {
698
          this.++;
699
        }
701
        this. += count - result[0];
702
        return rebalance();
703
      }
705
      // setting my count
706
      result[0] = ;
707
      if (count == 0) {
708
        return deleteMe();
709
      }
710
      this. += count - ;
711
      this. = count;
712
      return this;
713
    }
715
    AvlNode<E> setCount(
716
        Comparator<? super E> comparator,
717
        @Nullable E e,
718
        int expectedCount,
719
        int newCount,
720
        int[] result) {
721
      int cmp = comparator.compare(e, );
722
      if (cmp < 0) {
723
        AvlNode<E> initLeft = ;
724
        if (initLeft == null) {
725
          result[0] = 0;
726
          if (expectedCount == 0 && newCount > 0) {
727
            return addLeftChild(e, newCount);
728
          }
729
          return this;
730
        }
732
         = initLeft.setCount(comparator, e, expectedCount, newCount, result);
734
        if (result[0] == expectedCount) {
735
          if (newCount == 0 && result[0] != 0) {
736
            this.--;
737
          } else if (newCount > 0 && result[0] == 0) {
738
            this.++;
739
          }
740
          this. += newCount - result[0];
741
        }
742
        return rebalance();
743
      } else if (cmp > 0) {
744
        AvlNode<E> initRight = ;
745
        if (initRight == null) {
746
          result[0] = 0;
747
          if (expectedCount == 0 && newCount > 0) {
748
            return addRightChild(e, newCount);
749
          }
750
          return this;
751
        }
753
         = initRight.setCount(comparator, e, expectedCount, newCount, result);
755
        if (result[0] == expectedCount) {
756
          if (newCount == 0 && result[0] != 0) {
757
            this.--;
758
          } else if (newCount > 0 && result[0] == 0) {
759
            this.++;
760
          }
761
          this. += newCount - result[0];
762
        }
763
        return rebalance();
764
      }
766
      // setting my count
767
      result[0] = ;
768
      if (expectedCount == ) {
769
        if (newCount == 0) {
770
          return deleteMe();
771
        }
772
        this. += newCount - ;
773
        this. = newCount;
774
      }
775
      return this;
776
    }
778
    private AvlNode<E> deleteMe() {
779
      int oldElemCount = this.;
780
      this. = 0;
781
      successor(, );
782
      if ( == null) {
783
        return ;
784
      } else if ( == null) {
785
        return ;
786
      } else if (. >= .) {
787
        AvlNode<E> newTop = ;
788
        // newTop is the maximum node in my left subtree
789
        newTop.left = .removeMax(newTop);
790
        newTop.right = ;
791
        newTop.distinctElements =  - 1;
792
        newTop.totalCount =  - oldElemCount;
793
        return newTop.rebalance();
794
      } else {
795
        AvlNode<E> newTop = ;
796
        newTop.right = .removeMin(newTop);
797
        newTop.left = ;
798
        newTop.distinctElements =  - 1;
799
        newTop.totalCount =  - oldElemCount;
800
        return newTop.rebalance();
801
      }
802
    }
804
    // Removes the minimum node from this subtree to be reused elsewhere
805
    private AvlNode<E> removeMin(AvlNode<E> node) {
806
      if ( == null) {
807
        return ;
808
      } else {
809
         = .removeMin(node);
810
        --;
811
         -= node.elemCount;
812
        return rebalance();
813
      }
814
    }
816
    // Removes the maximum node from this subtree to be reused elsewhere
817
    private AvlNode<E> removeMax(AvlNode<E> node) {
818
      if ( == null) {
819
        return ;
820
      } else {
821
         = .removeMax(node);
822
        --;
823
         -= node.elemCount;
824
        return rebalance();
825
      }
826
    }
828
    private void recomputeMultiset() {
829
      this. = 1 + TreeMultiset.distinctElements()
830
          + TreeMultiset.distinctElements();
831
      this. =  + totalCount() + totalCount();
832
    }
834
    private void recomputeHeight() {
835
      this. = 1 + Math.max(height(), height());
836
    }
838
    private void recompute() {
839
      recomputeMultiset();
840
      recomputeHeight();
841
    }
843
    private AvlNode<E> rebalance() {
844
      switch (balanceFactor()) {
845
        case -2:
846
          if (.balanceFactor() > 0) {
847
             = .rotateRight();
848
          }
849
          return rotateLeft();
850
        case 2:
851
          if (.balanceFactor() < 0) {
852
             = .rotateLeft();
853
          }
854
          return rotateRight();
855
        default:
856
          recomputeHeight();
857
          return this;
858
      }
859
    }
861
    private int balanceFactor() {
862
      return height() - height();
863
    }
865
    private AvlNode<E> rotateLeft() {
866
      checkState( != null);
867
      AvlNode<E> newTop = ;
868
      this. = newTop.left;
869
      newTop.left = this;
870
      newTop.totalCount = this.;
871
      newTop.distinctElements = this.;
872
      this.recompute();
873
      newTop.recomputeHeight();
874
      return newTop;
875
    }
877
    private AvlNode<E> rotateRight() {
878
      checkState( != null);
879
      AvlNode<E> newTop = ;
880
      this. = newTop.right;
881
      newTop.right = this;
882
      newTop.totalCount = this.;
883
      newTop.distinctElements = this.;
884
      this.recompute();
885
      newTop.recomputeHeight();
886
      return newTop;
887
    }
889
    private static long totalCount(@Nullable AvlNode<?> node) {
890
      return (node == null) ? 0 : node.totalCount;
891
    }
893
    private static int height(@Nullable AvlNode<?> node) {
894
      return (node == null) ? 0 : node.height;
895
    }
897
    @Nullable private AvlNode<E> ceiling(Comparator<? super E> comparator, E e) {
898
      int cmp = comparator.compare(e, );
899
      if (cmp < 0) {
900
        return ( == null) ? this : Objects.firstNonNull(.ceiling(comparator, e), this);
901
      } else if (cmp == 0) {
902
        return this;
903
      } else {
904
        return ( == null) ? null : .ceiling(comparator, e);
905
      }
906
    }
908
    @Nullable private AvlNode<E> floor(Comparator<? super E> comparator, E e) {
909
      int cmp = comparator.compare(e, );
910
      if (cmp > 0) {
911
        return ( == null) ? this : Objects.firstNonNull(.floor(comparator, e), this);
912
      } else if (cmp == 0) {
913
        return this;
914
      } else {
915
        return ( == null) ? null : .floor(comparator, e);
916
      }
917
    }
919
    @Override
920
    public E getElement() {
921
      return ;
922
    }
924
    @Override
925
    public int getCount() {
926
      return ;
927
    }
929
    @Override
930
    public String toString() {
931
      return Multisets.immutableEntry(getElement(), getCount()).toString();
932
    }
933
  }
935
  private static <T> void successor(AvlNode<T> a, AvlNode<T> b) {
936
    a.succ = b;
937
    b.pred = a;
938
  }
940
  private static <T> void successor(AvlNode<T> a, AvlNode<T> b, AvlNode<T> c) {
941
    successor(a, b);
942
    successor(b, c);
943
  }
945
  /*
946
   * TODO(jlevy): Decide whether entrySet() should return entries with an equals() method that
947
   * calls the comparator to compare the two keys. If that change is made,
948
   * AbstractMultiset.equals() can simply check whether two multisets have equal entry sets.
949
   */

  

SerialData:
the comparator, the number of distinct elements, the first element, its count, the second element, its count, and so on
955
  @GwtIncompatible("java.io.ObjectOutputStream")
956
  private void writeObject(ObjectOutputStream stream) throws IOException {
957
    stream.defaultWriteObject();
958
    stream.writeObject(elementSet().comparator());
959
    Serialization.writeMultiset(this, stream);
960
  }
962
  @GwtIncompatible("java.io.ObjectInputStream")
963
  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
964
    stream.defaultReadObject();
965
    @SuppressWarnings("unchecked")
966
    // reading data stored by writeObject
967
    Comparator<? super E> comparator = (Comparator<? super E>) stream.readObject();
968
    Serialization.getFieldSetter(AbstractSortedMultiset.class, "comparator").set(this, comparator);
969
    Serialization.getFieldSetter(TreeMultiset.class, "range").set(
970
        this,
971
        GeneralRange.all(comparator));
972
    Serialization.getFieldSetter(TreeMultiset.class, "rootReference").set(
973
        this,
974
        new Reference<AvlNode<E>>());
975
    AvlNode<E> header = new AvlNode<E>(null, 1);
976
    Serialization.getFieldSetter(TreeMultiset.class, "header").set(this, header);
977
    successor(header, header);
978
    Serialization.populateMultiset(this, stream);
979
  }
981
  @GwtIncompatible("not needed in emulated source") private static final long serialVersionUID = 1;