1
2
3
4
5
6
7
8
9
10
11
12
13
14
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.checkNotNull;
21 import static com.google.common.base.Preconditions.checkPositionIndex;
22 import static com.google.common.base.Preconditions.checkState;
23 import static com.google.common.collect.CollectPreconditions.checkRemove;
24
25 import com.google.common.annotations.Beta;
26 import com.google.common.annotations.VisibleForTesting;
27 import com.google.common.math.IntMath;
28
29 import java.util.AbstractQueue;
30 import java.util.ArrayDeque;
31 import java.util.ArrayList;
32 import java.util.Collection;
33 import java.util.Collections;
34 import java.util.Comparator;
35 import java.util.ConcurrentModificationException;
36 import java.util.Iterator;
37 import java.util.List;
38 import java.util.NoSuchElementException;
39 import java.util.PriorityQueue;
40 import java.util.Queue;
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90 @Beta
91 public final class MinMaxPriorityQueue<E> extends AbstractQueue<E> {
92
93
94
95
96
97 public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create() {
98 return new Builder<Comparable>(Ordering.natural()).create();
99 }
100
101
102
103
104
105 public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create(
106 Iterable<? extends E> initialContents) {
107 return new Builder<E>(Ordering.<E>natural()).create(initialContents);
108 }
109
110
111
112
113
114
115 public static <B> Builder<B> orderedBy(Comparator<B> comparator) {
116 return new Builder<B>(comparator);
117 }
118
119
120
121
122
123
124 public static Builder<Comparable> expectedSize(int expectedSize) {
125 return new Builder<Comparable>(Ordering.natural())
126 .expectedSize(expectedSize);
127 }
128
129
130
131
132
133
134
135
136 public static Builder<Comparable> maximumSize(int maximumSize) {
137 return new Builder<Comparable>(Ordering.natural())
138 .maximumSize(maximumSize);
139 }
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154 @Beta
155 public static final class Builder<B> {
156
157
158
159
160 private static final int UNSET_EXPECTED_SIZE = -1;
161
162 private final Comparator<B> comparator;
163 private int expectedSize = UNSET_EXPECTED_SIZE;
164 private int maximumSize = Integer.MAX_VALUE;
165
166 private Builder(Comparator<B> comparator) {
167 this.comparator = checkNotNull(comparator);
168 }
169
170
171
172
173
174 public Builder<B> expectedSize(int expectedSize) {
175 checkArgument(expectedSize >= 0);
176 this.expectedSize = expectedSize;
177 return this;
178 }
179
180
181
182
183
184
185
186 public Builder<B> maximumSize(int maximumSize) {
187 checkArgument(maximumSize > 0);
188 this.maximumSize = maximumSize;
189 return this;
190 }
191
192
193
194
195
196 public <T extends B> MinMaxPriorityQueue<T> create() {
197 return create(Collections.<T>emptySet());
198 }
199
200
201
202
203
204 public <T extends B> MinMaxPriorityQueue<T> create(
205 Iterable<? extends T> initialContents) {
206 MinMaxPriorityQueue<T> queue = new MinMaxPriorityQueue<T>(
207 this, initialQueueSize(expectedSize, maximumSize, initialContents));
208 for (T element : initialContents) {
209 queue.offer(element);
210 }
211 return queue;
212 }
213
214 @SuppressWarnings("unchecked")
215 private <T extends B> Ordering<T> ordering() {
216 return Ordering.from((Comparator<T>) comparator);
217 }
218 }
219
220 private final Heap minHeap;
221 private final Heap maxHeap;
222 @VisibleForTesting final int maximumSize;
223 private Object[] queue;
224 private int size;
225 private int modCount;
226
227 private MinMaxPriorityQueue(Builder<? super E> builder, int queueSize) {
228 Ordering<E> ordering = builder.ordering();
229 this.minHeap = new Heap(ordering);
230 this.maxHeap = new Heap(ordering.reverse());
231 minHeap.otherHeap = maxHeap;
232 maxHeap.otherHeap = minHeap;
233
234 this.maximumSize = builder.maximumSize;
235
236 this.queue = new Object[queueSize];
237 }
238
239 @Override public int size() {
240 return size;
241 }
242
243
244
245
246
247
248
249
250
251 @Override public boolean add(E element) {
252 offer(element);
253 return true;
254 }
255
256 @Override public boolean addAll(Collection<? extends E> newElements) {
257 boolean modified = false;
258 for (E element : newElements) {
259 offer(element);
260 modified = true;
261 }
262 return modified;
263 }
264
265
266
267
268
269
270
271 @Override public boolean offer(E element) {
272 checkNotNull(element);
273 modCount++;
274 int insertIndex = size++;
275
276 growIfNeeded();
277
278
279
280 heapForIndex(insertIndex).bubbleUp(insertIndex, element);
281 return size <= maximumSize || pollLast() != element;
282 }
283
284 @Override public E poll() {
285 return isEmpty() ? null : removeAndGet(0);
286 }
287
288 @SuppressWarnings("unchecked")
289 E elementData(int index) {
290 return (E) queue[index];
291 }
292
293 @Override public E peek() {
294 return isEmpty() ? null : elementData(0);
295 }
296
297
298
299
300 private int getMaxElementIndex() {
301 switch (size) {
302 case 1:
303 return 0;
304 case 2:
305 return 1;
306 default:
307
308
309 return (maxHeap.compareElements(1, 2) <= 0) ? 1 : 2;
310 }
311 }
312
313
314
315
316
317 public E pollFirst() {
318 return poll();
319 }
320
321
322
323
324
325
326 public E removeFirst() {
327 return remove();
328 }
329
330
331
332
333
334 public E peekFirst() {
335 return peek();
336 }
337
338
339
340
341
342 public E pollLast() {
343 return isEmpty() ? null : removeAndGet(getMaxElementIndex());
344 }
345
346
347
348
349
350
351 public E removeLast() {
352 if (isEmpty()) {
353 throw new NoSuchElementException();
354 }
355 return removeAndGet(getMaxElementIndex());
356 }
357
358
359
360
361
362 public E peekLast() {
363 return isEmpty() ? null : elementData(getMaxElementIndex());
364 }
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381 @VisibleForTesting MoveDesc<E> removeAt(int index) {
382 checkPositionIndex(index, size);
383 modCount++;
384 size--;
385 if (size == index) {
386 queue[size] = null;
387 return null;
388 }
389 E actualLastElement = elementData(size);
390 int lastElementAt = heapForIndex(size)
391 .getCorrectLastElement(actualLastElement);
392 E toTrickle = elementData(size);
393 queue[size] = null;
394 MoveDesc<E> changes = fillHole(index, toTrickle);
395 if (lastElementAt < index) {
396
397 if (changes == null) {
398
399 return new MoveDesc<E>(actualLastElement, toTrickle);
400 } else {
401
402
403 return new MoveDesc<E>(actualLastElement, changes.replaced);
404 }
405 }
406
407 return changes;
408 }
409
410 private MoveDesc<E> fillHole(int index, E toTrickle) {
411 Heap heap = heapForIndex(index);
412
413
414
415
416
417
418
419 int vacated = heap.fillHoleAt(index);
420
421 int bubbledTo = heap.bubbleUpAlternatingLevels(vacated, toTrickle);
422 if (bubbledTo == vacated) {
423
424
425
426 return heap.tryCrossOverAndBubbleUp(index, vacated, toTrickle);
427 } else {
428 return (bubbledTo < index)
429 ? new MoveDesc<E>(toTrickle, elementData(index))
430 : null;
431 }
432 }
433
434
435 static class MoveDesc<E> {
436 final E toTrickle;
437 final E replaced;
438
439 MoveDesc(E toTrickle, E replaced) {
440 this.toTrickle = toTrickle;
441 this.replaced = replaced;
442 }
443 }
444
445
446
447
448 private E removeAndGet(int index) {
449 E value = elementData(index);
450 removeAt(index);
451 return value;
452 }
453
454 private Heap heapForIndex(int i) {
455 return isEvenLevel(i) ? minHeap : maxHeap;
456 }
457
458 private static final int EVEN_POWERS_OF_TWO = 0x55555555;
459 private static final int ODD_POWERS_OF_TWO = 0xaaaaaaaa;
460
461 @VisibleForTesting static boolean isEvenLevel(int index) {
462 int oneBased = index + 1;
463 checkState(oneBased > 0, "negative index");
464 return (oneBased & EVEN_POWERS_OF_TWO) > (oneBased & ODD_POWERS_OF_TWO);
465 }
466
467
468
469
470
471
472
473 @VisibleForTesting boolean isIntact() {
474 for (int i = 1; i < size; i++) {
475 if (!heapForIndex(i).verifyIndex(i)) {
476 return false;
477 }
478 }
479 return true;
480 }
481
482
483
484
485
486
487
488 private class Heap {
489 final Ordering<E> ordering;
490 Heap otherHeap;
491
492 Heap(Ordering<E> ordering) {
493 this.ordering = ordering;
494 }
495
496 int compareElements(int a, int b) {
497 return ordering.compare(elementData(a), elementData(b));
498 }
499
500
501
502
503
504
505 MoveDesc<E> tryCrossOverAndBubbleUp(
506 int removeIndex, int vacated, E toTrickle) {
507 int crossOver = crossOver(vacated, toTrickle);
508 if (crossOver == vacated) {
509 return null;
510 }
511
512
513 E parent;
514
515
516
517 if (crossOver < removeIndex) {
518
519
520 parent = elementData(removeIndex);
521 } else {
522 parent = elementData(getParentIndex(removeIndex));
523 }
524
525 if (otherHeap.bubbleUpAlternatingLevels(crossOver, toTrickle)
526 < removeIndex) {
527 return new MoveDesc<E>(toTrickle, parent);
528 } else {
529 return null;
530 }
531 }
532
533
534
535
536 void bubbleUp(int index, E x) {
537 int crossOver = crossOverUp(index, x);
538
539 Heap heap;
540 if (crossOver == index) {
541 heap = this;
542 } else {
543 index = crossOver;
544 heap = otherHeap;
545 }
546 heap.bubbleUpAlternatingLevels(index, x);
547 }
548
549
550
551
552
553 int bubbleUpAlternatingLevels(int index, E x) {
554 while (index > 2) {
555 int grandParentIndex = getGrandparentIndex(index);
556 E e = elementData(grandParentIndex);
557 if (ordering.compare(e, x) <= 0) {
558 break;
559 }
560 queue[index] = e;
561 index = grandParentIndex;
562 }
563 queue[index] = x;
564 return index;
565 }
566
567
568
569
570
571
572 int findMin(int index, int len) {
573 if (index >= size) {
574 return -1;
575 }
576 checkState(index > 0);
577 int limit = Math.min(index, size - len) + len;
578 int minIndex = index;
579 for (int i = index + 1; i < limit; i++) {
580 if (compareElements(i, minIndex) < 0) {
581 minIndex = i;
582 }
583 }
584 return minIndex;
585 }
586
587
588
589
590 int findMinChild(int index) {
591 return findMin(getLeftChildIndex(index), 2);
592 }
593
594
595
596
597 int findMinGrandChild(int index) {
598 int leftChildIndex = getLeftChildIndex(index);
599 if (leftChildIndex < 0) {
600 return -1;
601 }
602 return findMin(getLeftChildIndex(leftChildIndex), 4);
603 }
604
605
606
607
608
609
610 int crossOverUp(int index, E x) {
611 if (index == 0) {
612 queue[0] = x;
613 return 0;
614 }
615 int parentIndex = getParentIndex(index);
616 E parentElement = elementData(parentIndex);
617 if (parentIndex != 0) {
618
619
620
621
622 int grandparentIndex = getParentIndex(parentIndex);
623 int uncleIndex = getRightChildIndex(grandparentIndex);
624 if (uncleIndex != parentIndex
625 && getLeftChildIndex(uncleIndex) >= size) {
626 E uncleElement = elementData(uncleIndex);
627 if (ordering.compare(uncleElement, parentElement) < 0) {
628 parentIndex = uncleIndex;
629 parentElement = uncleElement;
630 }
631 }
632 }
633 if (ordering.compare(parentElement, x) < 0) {
634 queue[index] = parentElement;
635 queue[parentIndex] = x;
636 return parentIndex;
637 }
638 queue[index] = x;
639 return index;
640 }
641
642
643
644
645
646
647
648
649
650
651 int getCorrectLastElement(E actualLastElement) {
652 int parentIndex = getParentIndex(size);
653 if (parentIndex != 0) {
654 int grandparentIndex = getParentIndex(parentIndex);
655 int uncleIndex = getRightChildIndex(grandparentIndex);
656 if (uncleIndex != parentIndex
657 && getLeftChildIndex(uncleIndex) >= size) {
658 E uncleElement = elementData(uncleIndex);
659 if (ordering.compare(uncleElement, actualLastElement) < 0) {
660 queue[uncleIndex] = actualLastElement;
661 queue[size] = uncleElement;
662 return uncleIndex;
663 }
664 }
665 }
666 return size;
667 }
668
669
670
671
672
673
674
675 int crossOver(int index, E x) {
676 int minChildIndex = findMinChild(index);
677
678
679 if ((minChildIndex > 0)
680 && (ordering.compare(elementData(minChildIndex), x) < 0)) {
681 queue[index] = elementData(minChildIndex);
682 queue[minChildIndex] = x;
683 return minChildIndex;
684 }
685 return crossOverUp(index, x);
686 }
687
688
689
690
691
692
693
694
695
696 int fillHoleAt(int index) {
697 int minGrandchildIndex;
698 while ((minGrandchildIndex = findMinGrandChild(index)) > 0) {
699 queue[index] = elementData(minGrandchildIndex);
700 index = minGrandchildIndex;
701 }
702 return index;
703 }
704
705 private boolean verifyIndex(int i) {
706 if ((getLeftChildIndex(i) < size)
707 && (compareElements(i, getLeftChildIndex(i)) > 0)) {
708 return false;
709 }
710 if ((getRightChildIndex(i) < size)
711 && (compareElements(i, getRightChildIndex(i)) > 0)) {
712 return false;
713 }
714 if ((i > 0) && (compareElements(i, getParentIndex(i)) > 0)) {
715 return false;
716 }
717 if ((i > 2) && (compareElements(getGrandparentIndex(i), i) > 0)) {
718 return false;
719 }
720 return true;
721 }
722
723
724
725 private int getLeftChildIndex(int i) {
726 return i * 2 + 1;
727 }
728
729 private int getRightChildIndex(int i) {
730 return i * 2 + 2;
731 }
732
733 private int getParentIndex(int i) {
734 return (i - 1) / 2;
735 }
736
737 private int getGrandparentIndex(int i) {
738 return getParentIndex(getParentIndex(i));
739 }
740 }
741
742
743
744
745
746
747
748 private class QueueIterator implements Iterator<E> {
749 private int cursor = -1;
750 private int expectedModCount = modCount;
751 private Queue<E> forgetMeNot;
752 private List<E> skipMe;
753 private E lastFromForgetMeNot;
754 private boolean canRemove;
755
756 @Override public boolean hasNext() {
757 checkModCount();
758 return (nextNotInSkipMe(cursor + 1) < size())
759 || ((forgetMeNot != null) && !forgetMeNot.isEmpty());
760 }
761
762 @Override public E next() {
763 checkModCount();
764 int tempCursor = nextNotInSkipMe(cursor + 1);
765 if (tempCursor < size()) {
766 cursor = tempCursor;
767 canRemove = true;
768 return elementData(cursor);
769 } else if (forgetMeNot != null) {
770 cursor = size();
771 lastFromForgetMeNot = forgetMeNot.poll();
772 if (lastFromForgetMeNot != null) {
773 canRemove = true;
774 return lastFromForgetMeNot;
775 }
776 }
777 throw new NoSuchElementException(
778 "iterator moved past last element in queue.");
779 }
780
781 @Override public void remove() {
782 checkRemove(canRemove);
783 checkModCount();
784 canRemove = false;
785 expectedModCount++;
786 if (cursor < size()) {
787 MoveDesc<E> moved = removeAt(cursor);
788 if (moved != null) {
789 if (forgetMeNot == null) {
790 forgetMeNot = new ArrayDeque<E>();
791 skipMe = new ArrayList<E>(3);
792 }
793 forgetMeNot.add(moved.toTrickle);
794 skipMe.add(moved.replaced);
795 }
796 cursor--;
797 } else {
798 checkState(removeExact(lastFromForgetMeNot));
799 lastFromForgetMeNot = null;
800 }
801 }
802
803
804 private boolean containsExact(Iterable<E> elements, E target) {
805 for (E element : elements) {
806 if (element == target) {
807 return true;
808 }
809 }
810 return false;
811 }
812
813
814 boolean removeExact(Object target) {
815 for (int i = 0; i < size; i++) {
816 if (queue[i] == target) {
817 removeAt(i);
818 return true;
819 }
820 }
821 return false;
822 }
823
824 void checkModCount() {
825 if (modCount != expectedModCount) {
826 throw new ConcurrentModificationException();
827 }
828 }
829
830
831
832
833
834 private int nextNotInSkipMe(int c) {
835 if (skipMe != null) {
836 while (c < size() && containsExact(skipMe, elementData(c))) {
837 c++;
838 }
839 }
840 return c;
841 }
842 }
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866 @Override public Iterator<E> iterator() {
867 return new QueueIterator();
868 }
869
870 @Override public void clear() {
871 for (int i = 0; i < size; i++) {
872 queue[i] = null;
873 }
874 size = 0;
875 }
876
877 @Override public Object[] toArray() {
878 Object[] copyTo = new Object[size];
879 System.arraycopy(queue, 0, copyTo, 0, size);
880 return copyTo;
881 }
882
883
884
885
886
887
888 public Comparator<? super E> comparator() {
889 return minHeap.ordering;
890 }
891
892 @VisibleForTesting int capacity() {
893 return queue.length;
894 }
895
896
897
898 private static final int DEFAULT_CAPACITY = 11;
899
900 @VisibleForTesting static int initialQueueSize(int configuredExpectedSize,
901 int maximumSize, Iterable<?> initialContents) {
902
903 int result = (configuredExpectedSize == Builder.UNSET_EXPECTED_SIZE)
904 ? DEFAULT_CAPACITY
905 : configuredExpectedSize;
906
907
908 if (initialContents instanceof Collection) {
909 int initialSize = ((Collection<?>) initialContents).size();
910 result = Math.max(result, initialSize);
911 }
912
913
914 return capAtMaximumSize(result, maximumSize);
915 }
916
917 private void growIfNeeded() {
918 if (size > queue.length) {
919 int newCapacity = calculateNewCapacity();
920 Object[] newQueue = new Object[newCapacity];
921 System.arraycopy(queue, 0, newQueue, 0, queue.length);
922 queue = newQueue;
923 }
924 }
925
926
927 private int calculateNewCapacity() {
928 int oldCapacity = queue.length;
929 int newCapacity = (oldCapacity < 64)
930 ? (oldCapacity + 1) * 2
931 : IntMath.checkedMultiply(oldCapacity / 2, 3);
932 return capAtMaximumSize(newCapacity, maximumSize);
933 }
934
935
936 private static int capAtMaximumSize(int queueSize, int maximumSize) {
937 return Math.min(queueSize - 1, maximumSize) + 1;
938 }
939 }