3 * Copyright (C) 2009 Didier Villevalois
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 * Didier 'Ptitjes Villevalois <ptitjes@free.fr>
24 * Relaxed fibonacci heap priority queue implementation of the {@link Queue}.
26 * The elements of the priority queue are ordered according to their natural
27 * ordering, or by a compare_func provided at queue construction time. A
28 * priority queue does not permit null elements and does not have bounded
31 * This implementation provides O(1) time for offer and peek methods, and
32 * O(log n) for poll method. It is based on the algorithms described by
33 * Boyapati Chandra Sekhar in:
35 * "Worst Case Efficient Data Structures
36 * for Priority Queues and Deques with Heap Order"
37 * Boyapati Chandra Sekhar (under the guidance of Prof. C. Pandu Rangan)
38 * Department of Computer Science and Engineering
39 * Indian Institute of Technology, Madras
42 public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
45 * The elements' comparator function.
47 [CCode (notify = false)]
48 public CompareDataFunc<G> compare_func { private set; get; }
50 private int _size = 0;
51 private int _stamp = 0;
52 private Type1Node<G>? _r = null;
53 private Type2Node<G>? _r_prime = null;
54 private Type2Node<G>? _lm_head = null;
55 private Type2Node<G>? _lm_tail = null;
56 private Type1Node<G>? _p = null;
58 private Type1Node<G>?[] _a = new Type1Node<G>?[0];
60 private Type1Node<G>?[] _a = new Type1Node<G>[0];
62 private NodePair<G>? _lp_head = null;
63 private NodePair<G>? _lp_tail = null;
64 private bool[] _b = new bool[0];
65 private Type1Node<G>? _ll_head = null;
66 private Type1Node<G>? _ll_tail = null;
69 * Constructs a new, empty priority queue.
71 * If not provided, the function parameter is requested to the
72 * {@link Functions} function factory methods.
74 * @param compare_func an optional element comparator function
76 public PriorityQueue (owned CompareDataFunc<G>? compare_func = null) {
77 if (compare_func == null) {
78 compare_func = Functions.get_compare_func_for (typeof (G));
80 this.compare_func = compare_func;
86 public override int capacity {
87 get { return UNBOUNDED_CAPACITY; }
93 public override int remaining_capacity {
94 get { return UNBOUNDED_CAPACITY; }
100 public override bool is_full {
101 get { return false; }
107 public override bool read_only {
108 get { return false; }
114 public bool offer (G element) {
116 _r = new Type1Node<G> (element);
118 } else if (_r_prime == null) {
119 _r_prime = new Type2Node<G> (element);
120 _r_prime.parent = _r;
121 _r.type2_child = _r_prime;
122 if (_compare (_r_prime, _r) < 0)
123 _swap_data (_r_prime, _r);
125 // Form a tree with a single node N of type I consisting of element e
126 Type1Node<G> node = new Type1Node<G> (element);
140 public override G? peek () {
150 public override G? poll () {
152 _dump ("Start poll:");
155 // 1a. M inElement <- R.element
160 _r.pending_drop = false;
164 // 1b. R.element = R'.element
165 if (_r_prime == null) {
170 _r.data = _r_prime.data;
172 // 1c. R'' <- The child of R' containing the minimum element among the children of R'
173 if (_r_prime.type1_children_head == null) {
174 _remove_type2_node (_r_prime);
178 Type1Node<G>? r_second = null;
179 Type1Node<G> node = _r_prime.type1_children_head;
180 while (node != null) {
181 if (r_second == null || _compare (node, r_second) < 0) {
184 node = node.brothers_next;
187 // 1d. R'.element <- R''.element
188 _r_prime.data = r_second.data;
190 // 2a. Delete the subtree rooted at R'' from Q
191 _remove_type1_node (r_second);
193 // 2b. For all children N of type I of R'' do make N a child of R' of Q
194 node = r_second.type1_children_head;
195 while (node != null) {
196 Type1Node<G> next = node.brothers_next;
197 _remove_type1_node (node);
198 _add_in_r_prime (node);
202 // For now we can't have type2 node other than R' (left for reference)
204 // 3a. If R'' has no child of type II then goto Step 4.
205 if (r_second.type2_child != null) {
206 // 3b. Let M' be the child of type II of R''. Insert(Q, M'.element)
207 Type2Node<G> m_prime = r_second.type2_child;
208 _remove_type2_node (m_prime);
209 offer (m_prime.data);
211 // 3c. For all children N of M do make N a child of R' of Q
212 node = m_prime.type1_children_head;
213 while (node != null) {
214 Type1Node<G> next = node.brothers_next;
215 _remove_type1_node (node);
216 _add_in_r_prime (node);
222 // 4. Adjust(Q, P, P)
228 // For now we can't have type2 node other than R' (left for reference)
230 // 5a. if LM is empty then goto Step 6
231 if (_lm_head != null) {
232 // 5b. M <- Head(LM); LM <- Tail(LM)
233 Type2Node<G> m = _lm_head;
235 // 5c. Delete M from Q
236 _remove_type2_node (m);
238 // 5d. I nsert(Q, M.element)
241 // 5e. For all children N of M do make M a child of R' of Q
242 node = m.type1_children_head;
243 while (node != null) {
244 Type1Node<G> next = node.brothers_next;
245 _remove_type1_node (node);
246 _add_in_r_prime (node);
252 // 6. While among the children of R' there exist any two different nodes Ri and Rj
253 // such that Ri.degree = Rj.degree do Link(Q, Ri, Rj)
254 while (_check_linkable ()) {}
256 // 7. Return MinElement
263 public int drain (Collection<G> recipient, int amount = -1) {
267 for (int i = 0; i < amount; i++) {
268 if (this._size == 0) {
271 recipient.add (poll ());
279 public override int size {
280 get { return _size; }
286 public override bool contains (G item) {
287 foreach (G an_item in this) {
288 if (compare_func (item, an_item) == 0) {
298 public override bool add (G item) {
305 public override bool remove (G item) {
307 _dump ("Start remove: %s".printf ((string) item));
310 Iterator<G> iterator = new Iterator<G> (this);
311 while (iterator.next ()) {
312 G an_item = iterator.get ();
313 if (compare_func (item, an_item) == 0) {
314 _delete (iterator.get_node ());
324 public override void clear () {
332 _a = new Type1Node<G>?[0];
334 _a = new Type1Node<G>[0];
346 public override Gee.Iterator<G> iterator () {
347 return new Iterator<G> (this);
350 private inline int _compare (Node<G> node1, Node<G> node2) {
351 // Assume there can't be two nodes pending drop
352 if (node1.pending_drop) {
354 } else if (node2.pending_drop) {
357 return compare_func (node1.data, node2.data);
361 private inline void _swap_data (Node<G> node1, Node<G> node2) {
362 G temp_data = (owned) node1.data;
363 bool temp_pending_drop = node1.pending_drop;
364 node1.data = (owned) node2.data;
365 node1.pending_drop = node2.pending_drop;
366 node2.data = (owned) temp_data;
367 node2.pending_drop = temp_pending_drop;
370 private void _link (Type1Node<G> ri, Type1Node<G> rj) {
371 assert (ri.degree () == rj.degree ());
373 // Delete the subtrees rooted at Ri and Rj from Q
374 _remove_type1_node (ri);
375 _remove_type1_node (rj);
377 // If Ri.element > Rj.element then Swap(Ri,Rj)
378 if (_compare (ri, rj) > 0) {
379 Type1Node<G> temp = ri;
384 // Make Rj the last child of Ri
387 // Make Ri (whose degree now = d+1) a child of R' of Q
388 _add_in_r_prime (ri);
391 private void _add (Type1Node<G> n) {
392 // Make N a child of R' of Q
395 // If N.element < R'.element then Swap(N.element, R'.element)
396 if (_compare (n, _r_prime) < 0) {
397 _swap_data (n, _r_prime);
400 // If R'.element < R.element then Swap(R'.element, R.element)
401 if (_compare (_r_prime, _r) < 0) {
402 _swap_data (_r_prime, _r);
405 // If among the children of R' there exist any two different nodes Ri and Rj
406 // such that Ri.degree = Rj.degree then Link(Q, Ri, Rj)
410 _dump ("End _add: %s".printf ((string) n.data));
414 private bool _check_linkable () {
416 _dump ("Start _check_linkable:");
419 if (_lp_head != null) {
420 NodePair<G> pair = _lp_head;
421 _link (pair.node1, pair.node2);
427 private Node<G> _re_insert (Type1Node<G> n) {
431 _dump ("Start _re_insert: %s".printf ((string) n.data));
435 Node<G> parent = n.parent;
437 // Delete the subtree rooted at N from Q
438 _remove_type1_node (n);
447 private void _adjust (Type1Node<G> p1, Type1Node<G> p2) {
448 // If M.lost <= 1 for all nodes M in Q then return
449 if (_ll_head == null) {
454 _dump ("Start _adjust: %s, %s".printf ((string) p1.data, (string) p2.data));
457 // If P1.lost > P2.lost then M <- P1 else M <- P2
459 if (p1.lost > p2.lost) {
465 // If M.lost <= 1 then M <- M' for some node M' in Q such that M'.lost > 1
468 if (_ll_head.ll_next != null) {
469 _ll_head.ll_next.ll_prev = null;
471 _ll_head = _ll_head.ll_next;
474 // P <- ReInsert(Q, M)
475 _p = (Type1Node<G>) _re_insert (m);
478 _dump ("End _adjust: %s, %s".printf ((string) p1.data, (string) p2.data));
482 private void _delete (Node<G> n) {
483 // DecreaseKey(Q, N, infinite)
490 private void _decrease_key (Node<G> n) {
492 _dump ("Start _decrease_key: %s".printf ((string) n.data));
495 if (n == _r || _r_prime == null) {
499 n.pending_drop = true;
501 // If (N = R or R') and (R'.element < R.element) then
502 // Swap(R'.element, R.element); return
503 if (n == _r_prime && _compare (_r_prime, _r) < 0) {
504 _swap_data (_r_prime, _r);
508 // For now we can't have type2 node other than R' (left for reference)
510 // If (N is of type II) and (N.element < N.parent.element) then
511 // Swap(N.element, N.parent.element); N <- N.parent
512 if (n is Type2Node && _compare (n, n.parent) < 0) {
513 _swap_data (n, n.parent);
518 // Can't occur as we made n be the most little (left for reference)
520 // If N.element >= N.parent.element then return
521 if (n.parent != null && _compare (n, n.parent) >= 0) {
526 // P' <- ReInsert(Q, N)
527 Node<G> p_prime = _re_insert ((Type1Node<G>) n);
529 if (p_prime is Type2Node) {
534 _adjust (_p, (Type1Node<G>) p_prime);
538 private void _add_to (Type1Node<G> node, Type1Node<G> parent) {
543 private void _add_in_r_prime (Type1Node<G> node) {
545 _dump ("Start _add_in_r_prime: %s".printf ((string) node.data));
548 int degree = node.degree ();
550 Type1Node<G>? insertion_point = null;
551 if (degree < _a.length) {
552 insertion_point = _a[degree];
555 if (insertion_point == null) {
556 if (_r_prime.type1_children_tail != null) {
557 node.brothers_prev = _r_prime.type1_children_tail;
558 _r_prime.type1_children_tail.brothers_next = node;
560 _r_prime.type1_children_head = node;
562 _r_prime.type1_children_tail = node;
564 if (insertion_point.brothers_prev != null) {
565 insertion_point.brothers_prev.brothers_next = node;
566 node.brothers_prev = insertion_point.brothers_prev;
568 _r_prime.type1_children_head = node;
570 node.brothers_next = insertion_point;
571 insertion_point.brothers_prev = node;
573 node.parent = _r_prime;
575 // Maintain A, B and LP
576 if (degree >= _a.length) {
577 _a.resize (degree + 1);
578 _b.resize (degree + 1);
581 // If there is already a child of such degree
582 if (_a[degree] == null) {
585 // Else if there is an odd number of child of such degree
588 NodePair<G> pair = new NodePair<G> (node, node.brothers_next);
589 node.brothers_next.pair = pair;
591 if (_lp_head == null) {
595 pair.lp_prev = _lp_tail;
596 _lp_tail.lp_next = pair;
599 // There is now an even number of child of such degree
608 _dump ("End _add_in_r_prime: %s".printf ((string) node.data));
612 private void _remove_type1_node (Type1Node<G> node) {
614 _dump ("Start _remove_type1_node: %s".printf ((string) node.data));
617 if (node.parent == _r_prime) {
618 _updated_degree (node, false);
621 if (node.ll_prev != null) {
622 node.ll_prev.ll_next = node.ll_next;
623 } else if (_ll_head == node) {
624 _ll_head = node.ll_next;
626 if (node.ll_next != null) {
627 node.ll_next.ll_prev = node.ll_prev;
628 } else if (_ll_tail == node) {
629 _ll_tail = node.ll_prev;
632 if (node.parent != null) {
633 if (node.parent.parent == _r_prime) {
634 _updated_degree ((Type1Node<G>) node.parent, true);
635 } else if (node.parent.parent != null) {
636 Type1Node<G> parent = (Type1Node<G>) node.parent;
638 // Increment parent's lost count
641 // And add it to LL if needed
642 if (parent.lost > 1) {
643 if (_ll_tail != null) {
644 parent.ll_prev = _ll_tail;
645 _ll_tail.ll_next = parent;
655 // Check whether removed node is P
660 // Maintain brothers list
664 private void _updated_degree (Type1Node<G> node, bool child_removed) {
665 int degree = node.degree ();
668 if (child_removed && _a[degree - 1] == null) {
669 _a[degree - 1] = node;
670 _b[degree - 1] = ! _b[degree - 1];
673 _b[degree] = ! _b[degree];
674 if (_a[degree] == node) {
675 Type1Node<G> next = node.brothers_next;
676 if (next != null && next.degree () == degree) {
681 int i = _a.length - 1;
682 while (i >= 0 && _a[i] == null) {
691 if (node.pair != null) {
692 NodePair<G> pair = node.pair;
693 Type1Node<G> other = (pair.node1 == node ? pair.node2 : pair.node1);
696 if (pair.lp_prev != null) {
697 pair.lp_prev.lp_next = pair.lp_next;
699 _lp_head = pair.lp_next;
701 if (pair.lp_next != null) {
702 pair.lp_next.lp_prev = pair.lp_prev;
704 _lp_tail = pair.lp_prev;
709 private void _remove_type2_node (Type2Node<G> node) {
710 ((Type1Node<G>) node.parent).type2_child = null;
713 // For now we can't have type2 node other than R' (left for reference)
716 if (node != _r_prime) {
717 if (node.lm_prev != null) {
718 node.lm_prev.lm_next = node.lm_next;
719 } else if (_lm_head == node) {
720 _lm_head = node.lm_next;
722 if (node.lm_next != null) {
723 node.lm_next.lm_prev = node.lm_prev;
724 } else if (_lm_tail == node) {
725 _lm_tail = node.lm_prev;
734 public void _dump (string message) {
735 stdout.printf (">>>> %s\n", message);
737 stdout.printf ("A.length = %d:", _a.length);
738 foreach (Node<G>? node in _a) {
739 stdout.printf (" %s;", node != null ? (string) node.data : null);
741 stdout.printf ("\n");
743 stdout.printf ("B.length = %d:", _b.length);
744 foreach (bool even in _b) {
745 stdout.printf (" %s;", even.to_string ());
747 stdout.printf ("\n");
749 stdout.printf ("LP:");
750 unowned NodePair<G>? pair = _lp_head;
751 while (pair != null) {
752 stdout.printf (" (%s,%s);", (string) pair.node1.data, (string) pair.node2.data);
755 stdout.printf ("\n");
757 stdout.printf ("LL:");
758 unowned Type1Node<G>? node = _ll_head;
759 while (node != null) {
760 stdout.printf (" %s;", (string) node.data);
763 stdout.printf ("\n");
765 stdout.printf ("%s\n", _r != null ? _r.to_string () : null);
767 stdout.printf ("\n");
771 private abstract class Node<G> {
773 public weak Node<G>? parent = null;
775 public int type1_children_count;
776 public Type1Node<G>? type1_children_head = null;
777 public Type1Node<G>? type1_children_tail = null;
779 public bool pending_drop;
781 protected Node (G data) {
785 public inline int degree () {
786 return type1_children_count;
790 public string children_to_string (int level = 0) {
791 StringBuilder builder = new StringBuilder ();
793 Type1Node<G> child = type1_children_head;
794 while (child != null) {
796 builder.append (",\n");
799 builder.append (child.to_string (level));
800 child = child.brothers_next;
805 public abstract string to_string (int level = 0);
809 private class Type1Node<G> : Node<G> {
811 public weak Type1Node<G>? brothers_prev = null;
812 public Type1Node<G>? brothers_next = null;
813 public Type2Node<G>? type2_child = null;
814 public weak Type1Node<G>? ll_prev = null;
815 public Type1Node<G>? ll_next = null;
816 public weak NodePair<G>? pair = null;
818 public Type1Node (G data) {
822 public inline void add (Type1Node<G> node) {
824 if (type1_children_head == null) {
825 type1_children_head = node;
827 node.brothers_prev = type1_children_tail;
829 if (type1_children_tail != null) {
830 type1_children_tail.brothers_next = node;
832 type1_children_tail = node;
833 type1_children_count++;
836 public inline void remove () {
837 if (brothers_prev == null) {
838 parent.type1_children_head = brothers_next;
840 brothers_prev.brothers_next = brothers_next;
842 if (brothers_next == null) {
843 parent.type1_children_tail = brothers_prev;
845 brothers_next.brothers_prev = brothers_prev;
847 parent.type1_children_count--;
849 brothers_prev = null;
850 brothers_next = null;
854 public override string to_string (int level = 0) {
855 StringBuilder builder = new StringBuilder ();
856 builder.append (string.nfill (level, '\t'));
857 builder.append ("(");
858 builder.append ((string) data);
859 builder.append ("/");
860 builder.append (lost.to_string ());
861 if (type1_children_head != null || type2_child != null) {
862 builder.append (":\n");
864 if (type1_children_head != null) {
865 builder.append (children_to_string (level + 1));
867 if (type1_children_head != null && type2_child != null) {
868 builder.append (",\n");
870 if (type2_child != null) {
871 builder.append (type2_child.to_string (level + 1));
873 if (type1_children_head != null || type2_child != null) {
874 builder.append ("\n");
875 builder.append (string.nfill (level, '\t'));
877 builder.append (")");
883 private class Type2Node<G> : Node<G> {
884 // For now we can't have type2 node other than R' (left for reference)
886 public weak Type2Node<G>? lm_prev = null;
887 public Type2Node<G>? lm_next = null;
890 public Type2Node (G data) {
895 public override string to_string (int level = 0) {
896 StringBuilder builder = new StringBuilder ();
897 builder.append (string.nfill (level, '\t'));
898 builder.append ("[");
899 builder.append ((string) data);
900 if (type1_children_head != null) {
901 builder.append (":\n");
902 builder.append (children_to_string (level + 1));
903 builder.append ("\n");
904 builder.append (string.nfill (level, '\t'));
906 builder.append ("]");
912 private class NodePair<G> {
913 public weak NodePair<G>? lp_prev = null;
914 public NodePair<G>? lp_next = null;
915 public Type1Node<G> node1 = null;
916 public Type1Node<G> node2 = null;
918 public NodePair (Type1Node<G> node1, Type1Node<G> node2) {
924 private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
925 private PriorityQueue<G> queue;
926 private bool started = false;
927 private bool from_type1_children = false;
928 private bool from_type2_child = false;
929 private unowned Node<G>? position;
930 private unowned Node<G>? _next;
932 private bool removed = false;
934 public Iterator (PriorityQueue<G> queue) {
936 this.position = queue._r;
937 this.stamp = queue._stamp;
940 public bool next () {
941 assert (stamp == queue._stamp);
949 return (position != null);
952 public bool has_next () {
953 assert (stamp == queue._stamp);
960 return (_next != null);
963 private bool _has_next() {
965 return _next != null;
966 } else if (_next is Type1Node) {
967 var node = _next as Type1Node<G>;
968 if (!from_type1_children && node.type1_children_head != null) {
969 _next = node.type1_children_head;
970 from_type1_children = false;
971 from_type2_child = false;
973 } else if (!from_type2_child && node.type2_child != null) {
974 _next = node.type2_child;
975 from_type1_children = false;
976 from_type2_child = false;
978 } else if (node.brothers_next != null) {
979 _next = node.brothers_next;
980 from_type1_children = false;
981 from_type2_child = false;
984 from_type1_children = true;
985 } else if (_next is Type2Node) {
986 var node = _next as Type2Node<G>;
987 if (!from_type1_children && node.type1_children_head != null) {
988 _next = node.type1_children_head;
989 from_type1_children = false;
990 from_type2_child = false;
993 from_type2_child = true;
995 if (_next != null && _next != queue._r) {
996 _next = _next.parent;
1002 public new G get () {
1003 assert (stamp == queue._stamp);
1004 assert (position != null);
1006 return position.data;
1009 public void remove () {
1010 assert (stamp == queue._stamp);
1011 assert (position != null);
1014 Node<G> node = position;
1016 queue._delete (node);
1017 stamp = queue._stamp;
1021 internal Node<G> get_node () {
1022 assert (stamp == queue._stamp);
1023 assert (position != null);
1027 public bool read_only {
1035 return started && ! removed && position != null;
1039 public void foreach (ForallFunc<G> f) {