1
2
3
4
5
6
7
8
9
10
11
12
13
14 package net.sf.jgabl2.core.data.pq.impl;
15
16 import net.sf.jgabl2.core.data.pq.IMeltablePriorityQueue;
17 import net.sf.jgabl2.core.data.pq.IMutablePriorityQueue;
18 import net.sf.jgabl2.core.util.check.CheckPolicy;
19 import net.sf.jgabl2.core.util.check.CheckPolicyManager;
20 import net.sf.jgabl2.core.util.check.InvariantType;
21 import net.sf.jgabl2.core.util.check.InvariantViolatedException;
22
23 import java.util.AbstractQueue;
24 import java.util.Comparator;
25 import java.util.Iterator;
26 import java.util.logging.Level;
27 import java.util.logging.Logger;
28
29 /**
30 * A fast alternative to <em>Fibonacci heaps</em>. A pairing heap is easier
31 * to implement and much faster in practice than a Fibonacci heap. However, the
32 * asymptotic complexity of some most operations is not known exactly.
33 *
34 * <p> <strong>Note that this implementation is not synchronized.</strong>
35 *
36 * @param <E> them item type of this queue
37 *
38 * @author Alexander Schwartz
39 * @since 0.1.0
40 *
41 * @see "L. Fredman, R. Sedgewick, D. Sleator and R. Tarjan, <em>The Pairing Heap: A New Form of Self-Adjusting Heap</em>, Algorithmica, 1986(1), pages 111-129."
42 * @see <a href="http://en.wikipedia.org/wiki/Pairing_heap"
43 * >Wikipedia article covering pairing heaps</a>
44 */
45 public final class PairingHeap<E>
46 extends AbstractQueue<E>
47 implements IMutablePriorityQueue<E>, IMeltablePriorityQueue<E> {
48
49
50
51
52 /** The logger of this class. */
53 private static final Logger LOG = Logger.getLogger(
54 PairingHeap.class.getName());
55
56 /** The check policy of this class. */
57 private static final CheckPolicy CHECK_POLICY = CheckPolicyManager
58 .getCheckPolicy(PairingHeap.class);
59
60
61
62
63 /**
64 * The comparator, or null if priority queue uses elements' natural
65 * ordering.
66 */
67 private Comparator<?super E> comparator = null;
68
69 /**
70 * The root of the enclosed tree, or <code>null</code>
71 * if this collections is empty.
72 */
73 private TreeItem<E> root = null;
74
75 /** The number of stored elements. */
76 private int size = 0;
77
78
79
80
81 /**
82 * Creates an instance using the default comparator.
83 * @complexity constant-time
84 */
85 public PairingHeap() {
86 super();
87 }
88
89 /**
90 * Creates an empty pairing heap that orders its elements according to the
91 * specified comparator.
92 *
93 * @param comparator
94 * the comparator used to order this priority queue. If
95 * <tt>null</tt> then the order depends on the elements'
96 * natural ordering.
97 * @complexity constant-time
98 */
99 public PairingHeap(final Comparator<?super E> comparator) {
100 super();
101 this.comparator = comparator;
102 }
103
104
105
106
107 /** {@inheritDoc} */
108 public Comparator<?super E> comparator() {
109 return this.comparator;
110 }
111
112 /** {@inheritDoc} */
113 @Override
114 public int size() {
115 return this.size;
116 }
117
118 /**
119 * {@inheritDoc}
120 *
121 * @complexity constant-time (proved)
122 */
123 @Override
124 public boolean isEmpty() {
125 return (this.size == 0);
126 }
127
128 /**
129 * {@inheritDoc}
130 *
131 * @complexity constant-time
132 */
133 public E peek() {
134 if (isEmpty()) {
135 return null;
136 }
137
138 return this.root.getData();
139 }
140
141
142
143 /**
144 * {@inheritDoc}
145 *
146 * Returns <code>true</code>.
147 */
148 public boolean offer(final E value) {
149 insert(value);
150
151 return true;
152 }
153
154 /**
155 * {@inheritDoc}
156 *
157 * @complexity constant-time
158 */
159 public PositionHandle<E> insert(final E obj) {
160 if (LOG.isLoggable(Level.FINER)) {
161 LOG.log(
162 Level.FINER,
163 "Inserting '"
164 + obj + "' (current size is "
165 + size() + ")");
166 }
167
168 final TreeItem<E> item = new TreeItem<E>(obj);
169
170 setRoot(link(this.root,
171 item));
172 ++this.size;
173
174 if (CHECK_POLICY.checkInvariant(InvariantType.EXPENSIVE_INVARIANT)) {
175 checkInvariant();
176 }
177
178 return new OwnPosHandle(item);
179 }
180
181
182 /**
183 * {@inheritDoc}
184 * @complexity amortized logarithmic-time (conjectured)
185 */
186 public E poll() {
187 if (isEmpty()) {
188 return null;
189 }
190
191 --this.size;
192
193 final E data = this.root.getData();
194 final TreeItem<E> child = this.root.getChild();
195
196 if (child == null) {
197 setRoot(null);
198 checkInvariant();
199
200 return data;
201 }
202
203
204 pairChildren(this.root);
205
206
207 setRoot(linkChildren(this.root));
208
209 checkInvariant();
210
211 return data;
212 }
213
214 /**
215 * {@inheritDoc}
216 * @complexity amortized logarithmic-time (conjectured)
217 */
218 public void remove(final PositionHandle<E> handle) {
219 if (handle == null) {
220 throw new IllegalArgumentException();
221 }
222
223 final TreeItem<E> item = ((OwnPosHandle) handle).item;
224 assert (item != null);
225 removeTreeItem(item);
226 }
227
228
229
230
231 /**
232 * {@inheritDoc}
233 * @complexity amortized constant-time (conjectured)
234 */
235 public void decreaseKey(final PositionHandle<E> handle) {
236 final TreeItem<E> item = ((OwnPosHandle) handle).item;
237
238 if (item == this.root) {
239 return;
240 }
241
242 item.cutFromParent();
243 setRoot(link(this.root,
244 item));
245
246 checkInvariant();
247 }
248
249
250
251
252 /**
253 * {@inheritDoc}
254 *
255 * @complexity constant-time
256 */
257 public void melt(final IMeltablePriorityQueue<E> queue) {
258 if (!(queue instanceof IMeltablePriorityQueue)) {
259 throw new IllegalArgumentException();
260 }
261
262 if (this.equals(queue)) {
263 throw new IllegalArgumentException();
264 }
265
266 final PairingHeap<E> priorityQueue = (PairingHeap<E>) queue;
267
268 this.size += priorityQueue.size;
269 setRoot(link(this.root,
270 priorityQueue.root));
271 priorityQueue.root = null;
272 priorityQueue.size = 0;
273
274 this.checkInvariant();
275 priorityQueue.checkInvariant();
276 }
277
278
279 /** Removed the specified tree item from this tree.
280 * @param item a tree item to be removed
281 */
282 private void removeTreeItem(final TreeItem<E> item) {
283 if (item == this.root) {
284 poll();
285
286 return;
287 }
288
289 item.cutFromParent();
290
291 final PairingHeap<E> priorityQueue
292 = new PairingHeap<E>(this.comparator);
293
294 priorityQueue.size = 1;
295 priorityQueue.root = item;
296 priorityQueue.poll();
297 melt(priorityQueue);
298 }
299
300 /**
301 * Restructures the given tree rooted at <code>parent</code>.
302 *
303 * @param parent a tree item
304 * @return a restructured version of the input tree.
305 */
306 private TreeItem<E> linkChildren(final TreeItem<E> parent) {
307 TreeItem<E> child = parent.getChild();
308 TreeItem<E> myroot = child;
309
310 if (child == null) {
311 return myroot;
312 }
313
314 child = child.getSibling();
315 myroot.setSibling(null);
316
317 while (child != null) {
318 final TreeItem<E> next = child.getSibling();
319
320 child.setSibling(null);
321 myroot = link(
322 myroot,
323 child);
324 child = next;
325 }
326
327 return myroot;
328 }
329
330 /**
331 * Restructures the given tree such that its root is eliminated.
332 * Is invoked from the method {@link #poll()} only.
333 *
334 * @param parent a tree item representing the tree whose
335 * items are to be paired
336 */
337 private void pairChildren(final TreeItem<E> parent) {
338 final TreeItem<E> firstChild = parent.getChild();
339
340 if (firstChild == null) {
341 return;
342 }
343
344 parent.setChild(null);
345
346 TreeItem<E> next = firstChild;
347
348 do {
349 final TreeItem<E> child1 = next;
350 final TreeItem<E> child2 = next.getSibling();
351
352 if (child2 == null) {
353 parent.addChild(child1);
354
355 return;
356 }
357
358 next = child2.getSibling();
359
360 child1.setSibling(null);
361 child2.setSibling(null);
362
363 parent.addChild(link(child1,
364 child2));
365 } while (next != null);
366 }
367
368 /**
369 * Pairs two given trees. This is the most important method
370 * of the <i>pairing heap</i> approach.
371 *
372 * Side effect: Both given tree items will be modified.
373 *
374 * @param firstTree a tree item; can be <code>null</code>
375 * @param secondTree another tree item; can be <code>null</code>
376 *
377 * @return a tree item representing the paired trees.
378 * The set of tree items of the returned tree is the union
379 * of the tree items of both input trees
380 */
381 private TreeItem<E> link(final TreeItem<E> firstTree,
382 final TreeItem<E> secondTree) {
383 if (firstTree == null) {
384 return secondTree;
385 }
386
387 if (secondTree == null) {
388 return firstTree;
389 }
390
391 if (compare(
392 firstTree.getData(),
393 secondTree.getData()) < 0) {
394 firstTree.addChild(secondTree);
395
396 return firstTree;
397 }
398
399 secondTree.addChild(firstTree);
400
401 return secondTree;
402 }
403
404 /**
405 * Assigns the root tree item.
406 * @param root a tree item to be used as the root of the tree;
407 * can be <code>null</code> to clear the tree
408 */
409 private void setRoot(final TreeItem<E> root) {
410 this.root = root;
411
412 if (root != null) {
413 root.setSibling(null);
414 root.setParent(null);
415 }
416 }
417
418 /**
419 * Compares two given values. The comparator {@link #comparator}
420 * is used if set. It the comparator is not set than the natural
421 * order of the items is used, if the items are {@link Comparable}.
422 *
423 * @param a the first value
424 * @param b the second value
425 * @return "0" if <code>a</code> and <code>b</code> are equal,
426 * "-1" if <code>a</code> is smaller than <code>b</code>,
427 * and "-1" if <code>a</code> is larger than <code>b</code>
428 * @throws IllegalStateException if and only if no comparator is
429 * set and the item
430 */
431 @SuppressWarnings("unchecked")
432 private int compare(final E a, final E b)
433 throws IllegalStateException {
434
435 if (this.comparator != null) {
436 return this.comparator.compare(a, b);
437 }
438
439 if (!(a instanceof Comparable)) {
440 throw new IllegalStateException(
441 "No comparator given and "
442 + "the element type is not comparable.");
443 }
444
445 final Comparable<E> comp = (Comparable) a;
446
447 return comp.compareTo(b);
448 }
449
450 /**
451 * Checks the representation invariant unless the {@link #CHECK_POLICY}
452 * prevents it.
453 *
454 * Throws an {@link InvariantViolatedException} in case of an
455 * invariant violation.
456 * @throws InvariantViolatedException
457 * only if the representation invariant is violated.
458 */
459 protected void checkInvariant()
460 throws InvariantViolatedException {
461 if (CHECK_POLICY.checkInvariant(InvariantType.CHEAP_INVARIANT)) {
462 checkSizeAndRoot();
463 }
464
465 if (!CHECK_POLICY.checkInvariant(InvariantType.EXPENSIVE_INVARIANT)) {
466 return;
467 }
468
469 final int numberOfChilds = checkNode(
470 this.root,
471 null,
472 "");
473
474 if (numberOfChilds != this.size) {
475 throw new InvariantViolatedException("Size is "
476 + this.size
477 + ", but the actual number of tree nodes is "
478 + numberOfChilds);
479 }
480 }
481
482 /**
483 * Verifies whether the size is non-negative, and whether the
484 * size attribute corresponds to the the state of the root of this tree.
485 *
486 * Throws an {@link InvariantViolatedException} in case of an
487 * invariant violation.
488 *
489 * @throws InvariantViolatedException
490 * only if the representation invariant is violated.
491 */
492 private void checkSizeAndRoot()
493 throws InvariantViolatedException {
494 if (this.size < 0) {
495 throw new InvariantViolatedException(
496 "Size is negative: "
497 + this.size);
498 }
499
500 final boolean flagRootNull = (this.root == null);
501
502 if (flagRootNull != (this.size == 0)) {
503 throw new InvariantViolatedException("Size is "
504 + this.size + " but root if " + this.root);
505 }
506 }
507
508 /**
509 * Analyses recursively the subtree rooted at the given <code>item</code>,
510 * verifies whether the parent references are consistent, and returns the
511 * number of tree items.
512 *
513 * @param item a tree item
514 * @param parent the parent of <code>item</code>
515 * @param indent an indent string (only used for logging)
516 * @return the number of all (dirent and indirect) children
517 * of <code>item</code>
518 * @throws InvariantViolatedException
519 * only if the representation invariant is violated.
520 */
521 private int checkNode(
522 final TreeItem<E> item,
523 final TreeItem<E> parent,
524 final String indent)
525 throws InvariantViolatedException {
526 if (item == null) {
527 return 0;
528 }
529
530 if (LOG.isLoggable(Level.FINEST)) {
531 LOG.log(
532 Level.FINEST,
533 indent + "CheckNode: node "
534 + item + " has parent "
535 + item.getParent());
536 }
537
538 if (item.getParent() != parent) {
539 throw new InvariantViolatedException("node '" + item
540 + "' has wrong parent (" + item.getParent()
541 + " instead of "
542 + parent + ")");
543 }
544
545 if (item == parent) {
546 throw new InvariantViolatedException("node '" + item
547 + "' is its own parent.");
548 }
549
550 final int numberOfChildsA = checkNode(
551 item.getSibling(),
552 parent,
553 indent);
554 final int numberOfChildsB = checkNode(
555 item.getChild(),
556 item,
557 indent + " ");
558
559 return numberOfChildsA + numberOfChildsB + 1;
560 }
561
562 /** {@inheritDoc} */
563 @Override
564 public Iterator<E> iterator() {
565 throw new UnsupportedOperationException();
566 }
567
568 /** Wraps a {@link TreeItem} as a {@link PositionHandle}. */
569 final class OwnPosHandle
570 implements PositionHandle<E> {
571
572
573
574 /** the item represented by this handled. */
575 private final TreeItem<E> item;
576
577
578
579
580 /**
581 * Creates a new instance wrapping the given tree item.
582 * @param item a tree item; may not be <code>null</code>
583 */
584 OwnPosHandle(final TreeItem<E> item) {
585 this.item = item;
586 }
587
588 /**
589 * Returns the value of the tree item
590 * wrapped by this handle.
591 *
592 * @return the value of the tree item
593 * wrapped by this handle.
594 */
595 public E getValue() {
596 return this.item.getData();
597 }
598 }
599 }
600
601
602 /**
603 * A item of (non-binary) tree in child-sibling representation.
604 * @author Alexander Schwartz
605 *
606 * @param <E> the item type
607 */
608 final class TreeItem<E> {
609
610
611
612 /** the parent of this tree item; can be <code>null</code>. */
613 private TreeItem<E> parent = null;
614
615 /** the first child of this tree item; can be <code>null</code>. */
616 private TreeItem<E> child = null;
617
618 /** the first sibling of this tree item; can be <code>null</code>. */
619 private TreeItem<E> sibling = null;
620
621 /** the value stored in this item. */
622 private final E data;
623
624
625
626
627 /**
628 * Creates a new instance storing the given value.
629 * @param data the value to be stored in this item.
630 */
631 TreeItem(final E data) {
632 this.data = data;
633 }
634
635
636
637
638 /**
639 * Add the given item as the first child.
640 * @param item the item be added as first child
641 *
642 * @postcond <code>this.child == item</code>
643 */
644 void addChild(final TreeItem<E> item) {
645 item.sibling = this.child;
646 item.parent = this;
647 this.child = item;
648 }
649
650 /**
651 * Cuts this tree item from its parent.
652 */
653 void cutFromParent() {
654 if (this.parent == null) {
655 return;
656 }
657
658 if (this.parent.child == this) {
659 this.parent.child = this.sibling;
660 } else {
661 TreeItem<E> sister = this.parent.child;
662
663 while (sister.sibling != this) {
664 sister = sister.sibling;
665 }
666
667 sister.sibling = this.sibling;
668 }
669
670 this.sibling = null;
671 this.parent = null;
672 }
673
674 /** {@inheritDoc} */
675 @Override
676 public String toString() {
677 return this.data.toString();
678 }
679
680 /** Returns the first child tree item.
681 * @return the first child tree item;
682 * can be <code>null</code> */
683 public TreeItem<E> getChild() {
684 return this.child;
685 }
686
687 /** Assings the first child tree item.
688 * @param child a tree item to be used set as child;
689 * can be <code>null</code> */
690 public void setChild(final TreeItem<E> child) {
691 this.child = child;
692 }
693
694 /** Returns the parent tree item.
695 * @return the parent tree item; can be <code>null</code> */
696 public TreeItem<E> getParent() {
697 return this.parent;
698 }
699
700 /** Assings the parent tree item.
701 * @param parent a tree item to be used set as parent;
702 * can be <code>null</code> */
703 public void setParent(final TreeItem<E> parent) {
704 this.parent = parent;
705 }
706
707 /** Returns the sibling tree item.
708 * @return the first child tree item; can be <code>null</code> */
709 public TreeItem<E> getSibling() {
710 return this.sibling;
711 }
712
713 /** Assigns the sibling reference.
714 * @param sibling a tree item to be used set as sibling;
715 can be <code>null</code> */
716 public void setSibling(final TreeItem<E> sibling) {
717 this.sibling = sibling;
718 }
719
720 /** Returns the value of this item.
721 * @return the value of this item; can be <code>null</code> */
722 public E getData() {
723 return this.data;
724 }
725 }