gee/priorityqueue.vala

   1 /* priorityqueue.vala
   2  *
   3  * Copyright (C) 2009  Didier Villevalois
   4  *
   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.
   9
  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.
  14
  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
  18  *
  19  * Author:
  20  *      Didier 'Ptitjes Villevalois <ptitjes@free.fr>
  21  */
  22
  23 /**
  24  * Relaxed fibonacci heap priority queue implementation of the {@link Queue}.
  25  *
  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
  29  * capacity.
  30  *
  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:
  34  *
  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
  40  *   May 1996
  41  */
  42 public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
  43
  44         /**
  45          * The elements' comparator function.
  46          */
  47         [CCode (notify = false)]
  48         public CompareDataFunc<G> compare_func { private set; get; }
  49
  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;
  57 #if VALA_0_16
  58         private Type1Node<G>?[] _a = new Type1Node<G>?[0];
  59 #else
  60         private Type1Node<G>?[] _a = new Type1Node<G>[0];
  61 #endif
  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;
  67
  68         /**
  69          * Constructs a new, empty priority queue.
  70          *
  71          * If not provided, the function parameter is requested to the
  72          * {@link Functions} function factory methods.
  73          *
  74          * @param compare_func an optional element comparator function
  75          */
  76         public PriorityQueue (owned CompareDataFunc<G>? compare_func = null) {
  77                 if (compare_func == null) {
  78                         compare_func = Functions.get_compare_func_for (typeof (G));
  79                 }
  80                 this.compare_func = compare_func;
  81         }
  82
  83         /**
  84          * {@inheritDoc}
  85          */
  86         public override int capacity {
  87                 get { return UNBOUNDED_CAPACITY; }
  88         }
  89
  90         /**
  91          * {@inheritDoc}
  92          */
  93         public override int remaining_capacity {
  94                 get { return UNBOUNDED_CAPACITY; }
  95         }
  96
  97         /**
  98          * {@inheritDoc}
  99          */
 100         public override bool is_full {
 101                 get { return false; }
 102         }
 103
 104         /**
 105          * {@inheritDoc}
 106          */
 107         public override bool read_only {
 108                 get { return false; }
 109         }
 110
 111         /**
 112          * {@inheritDoc}
 113          */
 114         public bool offer (G element) {
 115                 if (_r == null) {
 116                         _r = new Type1Node<G> (element);
 117                         _p = _r;
 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);
 124                 } else {
 125                         // Form a tree with a single node N of type I consisting of element e
 126                         Type1Node<G> node = new Type1Node<G> (element);
 127
 128                         //Add(Q, N)
 129                         _add (node);
 130                 }
 131
 132                 _stamp++;
 133                 _size++;
 134                 return true;
 135         }
 136
 137         /**
 138          * {@inheritDoc}
 139          */
 140         public override G? peek () {
 141                 if (_r == null) {
 142                         return null;
 143                 }
 144                 return _r.data;
 145         }
 146
 147         /**
 148          * {@inheritDoc}
 149          */
 150         public override G? poll () {
 151                 #if DEBUG
 152                         _dump ("Start poll:");
 153                 #endif
 154
 155                 // 1a. M inElement <- R.element
 156                 if (_r == null) {
 157                         return null;
 158                 }
 159                 G min = _r.data;
 160                 _r.pending_drop = false;
 161                 _stamp++;
 162                 _size--;
 163
 164                 // 1b. R.element = R'.element
 165                 if (_r_prime == null) {
 166                         _r = null;
 167                         _p = null;
 168                         return min;
 169                 }
 170                 _r.data = _r_prime.data;
 171
 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);
 175                         _r_prime = null;
 176                         return min;
 177                 }
 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) {
 182                                 r_second = node;
 183                         }
 184                         node = node.brothers_next;
 185                 }
 186
 187                 // 1d. R'.element <- R''.element
 188                 _r_prime.data = r_second.data;
 189
 190                 // 2a. Delete the subtree rooted at R'' from Q
 191                 _remove_type1_node (r_second);
 192
 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);
 199                         node = next;
 200                 }
 201
 202                 // For now we can't have type2 node other than R' (left for reference)
 203                 #if false
 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);
 210
 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);
 217                                         node = next;
 218                                 }
 219                         }
 220                 #endif
 221
 222                 // 4. Adjust(Q, P, P)
 223                 if (_p == null) {
 224                         _p = _r;
 225                 }
 226                 _adjust (_p, _p);
 227
 228                 // For now we can't have type2 node other than R' (left for reference)
 229                 #if false
 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;
 234
 235                                 // 5c. Delete M from Q
 236                                 _remove_type2_node (m);
 237
 238                                 // 5d. I nsert(Q, M.element)
 239                                 offer (m.data);
 240
 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);
 247                                         node = next;
 248                                 }
 249                         }
 250                 #endif
 251
 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 ()) {}
 255
 256                 // 7. Return MinElement
 257                 return min;
 258         }
 259
 260         /**
 261          * {@inheritDoc}
 262          */
 263         public int drain (Collection<G> recipient, int amount = -1) {
 264                 if (amount == -1) {
 265                         amount = this._size;
 266                 }
 267                 for (int i = 0; i < amount; i++) {
 268                         if (this._size == 0) {
 269                                 return i;
 270                         }
 271                         recipient.add (poll ());
 272                 }
 273                 return amount;
 274         }
 275
 276         /**
 277          * {@inheritDoc}
 278          */
 279         public override int size {
 280                 get { return _size; }
 281         }
 282
 283         /**
 284          * {@inheritDoc}
 285          */
 286         public override bool contains (G item) {
 287                 foreach (G an_item in this) {
 288                         if (compare_func (item, an_item) == 0) {
 289                                 return true;
 290                         }
 291                 }
 292                 return false;
 293         }
 294
 295         /**
 296          * {@inheritDoc}
 297          */
 298         public override bool add (G item) {
 299                 return offer (item);
 300         }
 301
 302         /**
 303          * {@inheritDoc}
 304          */
 305         public override bool remove (G item) {
 306                 #if DEBUG
 307                         _dump ("Start remove: %s".printf ((string) item));
 308                 #endif
 309
 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 ());
 315                                 return true;
 316                         }
 317                 }
 318                 return false;
 319         }
 320
 321         /**
 322          * {@inheritDoc}
 323          */
 324         public override void clear () {
 325                 _size = 0;
 326                 _r = null;
 327                 _r_prime = null;
 328                 _lm_head = null;
 329                 _lm_tail = null;
 330                 _p = null;
 331 #if VALA_0_16
 332                 _a = new Type1Node<G>?[0];
 333 #else
 334                 _a = new Type1Node<G>[0];
 335 #endif
 336                 _lp_head = null;
 337                 _lp_tail = null;
 338                 _b = new bool[0];
 339                 _ll_head = null;
 340                 _ll_tail = null;
 341         }
 342
 343         /**
 344          * {@inheritDoc}
 345          */
 346         public override Gee.Iterator<G> iterator () {
 347                 return new Iterator<G> (this);
 348         }
 349
 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) {
 353                         return -1;
 354                 } else if (node2.pending_drop) {
 355                         return 1;
 356                 } else {
 357                         return compare_func (node1.data, node2.data);
 358                 }
 359         }
 360
 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;
 368         }
 369
 370         private void _link (Type1Node<G> ri, Type1Node<G> rj) {
 371                 assert (ri.degree () == rj.degree ());
 372
 373                 // Delete the subtrees rooted at Ri and Rj from Q
 374                 _remove_type1_node (ri);
 375                 _remove_type1_node (rj);
 376
 377                 // If Ri.element > Rj.element then Swap(Ri,Rj)
 378                 if (_compare (ri, rj) > 0) {
 379                         Type1Node<G> temp = ri;
 380                         ri = rj;
 381                         rj = temp;
 382                 }
 383
 384                 // Make Rj the last child of Ri
 385                 _add_to (rj, ri);
 386
 387                 // Make Ri (whose degree now = d+1) a child of R' of Q
 388                 _add_in_r_prime (ri);
 389         }
 390
 391         private void _add (Type1Node<G> n) {
 392                 // Make N a child of R' of Q
 393                 _add_in_r_prime (n);
 394
 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);
 398                 }
 399
 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);
 403                 }
 404
 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)
 407                 _check_linkable ();
 408
 409                 #if DEBUG
 410                         _dump ("End _add: %s".printf ((string) n.data));
 411                 #endif
 412         }
 413
 414         private bool _check_linkable () {
 415                 #if DEBUG
 416                         _dump ("Start _check_linkable:");
 417                 #endif
 418
 419                 if (_lp_head != null) {
 420                         NodePair<G> pair = _lp_head;
 421                         _link (pair.node1, pair.node2);
 422                         return true;
 423                 }
 424                 return false;
 425         }
 426
 427         private Node<G> _re_insert (Type1Node<G> n) {
 428                 assert (n != _r);
 429
 430                 #if DEBUG
 431                         _dump ("Start _re_insert: %s".printf ((string) n.data));
 432                 #endif
 433
 434                 //Parent <- N.parent
 435                 Node<G> parent = n.parent;
 436
 437                 // Delete the subtree rooted at N from Q
 438                 _remove_type1_node (n);
 439
 440                 // Add(Q, N)
 441                 _add (n);
 442
 443                 // Return Parent
 444                 return parent;
 445         }
 446
 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) {
 450                         return;
 451                 }
 452
 453                 #if DEBUG
 454                         _dump ("Start _adjust: %s, %s".printf ((string) p1.data, (string) p2.data));
 455                 #endif
 456
 457                 // If P1.lost > P2.lost then M <- P1 else M <- P2
 458                 Type1Node<G> m;
 459                 if (p1.lost > p2.lost) {
 460                         m = p1;
 461                 } else {
 462                         m = p2;
 463                 }
 464
 465                 // If M.lost <= 1 then M <- M' for some node M' in Q such that M'.lost > 1
 466                 if (m.lost <= 1) {
 467                         m = _ll_head;
 468                         if (_ll_head.ll_next != null) {
 469                                 _ll_head.ll_next.ll_prev = null;
 470                         }
 471                         _ll_head = _ll_head.ll_next;
 472                 }
 473
 474                 // P <- ReInsert(Q, M)
 475                 _p = (Type1Node<G>) _re_insert (m);
 476
 477                 #if DEBUG
 478                         _dump ("End _adjust: %s, %s".printf ((string) p1.data, (string) p2.data));
 479                 #endif
 480         }
 481
 482         private void _delete (Node<G> n) {
 483                 // DecreaseKey(Q, N, infinite)
 484                 _decrease_key (n);
 485
 486                 // DeleteMin(Q)
 487                 poll ();
 488         }
 489
 490         private void _decrease_key (Node<G> n) {
 491                 #if DEBUG
 492                         _dump ("Start _decrease_key: %s".printf ((string) n.data));
 493                 #endif
 494
 495                 if (n == _r || _r_prime == null) {
 496                         return;
 497                 }
 498
 499                 n.pending_drop = true;
 500
 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);
 505                         return;
 506                 }
 507
 508                 // For now we can't have type2 node other than R' (left for reference)
 509                 #if false
 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);
 514                                 n = n.parent;
 515                         }
 516                 #endif
 517
 518                 // Can't occur as we made n be the most little (left for reference)
 519                 #if false
 520                         // If N.element >= N.parent.element then return
 521                         if (n.parent != null && _compare (n, n.parent) >= 0) {
 522                                 return;
 523                         }
 524                 #endif
 525
 526                 // P' <- ReInsert(Q, N)
 527                 Node<G> p_prime = _re_insert ((Type1Node<G>) n);
 528
 529                 if (p_prime is Type2Node) {
 530                         // Adjust(Q, P, P);
 531                         _adjust (_p, _p);
 532                 } else {
 533                         // Adjust(Q, P, P');
 534                         _adjust (_p, (Type1Node<G>) p_prime);
 535                 }
 536         }
 537
 538         private void _add_to (Type1Node<G> node, Type1Node<G> parent) {
 539                 parent.add (node);
 540                 parent.lost = 0;
 541         }
 542
 543         private void _add_in_r_prime (Type1Node<G> node) {
 544                 #if DEBUG
 545                         _dump ("Start _add_in_r_prime: %s".printf ((string) node.data));
 546                 #endif
 547
 548                 int degree = node.degree ();
 549
 550                 Type1Node<G>? insertion_point = null;
 551                 if (degree < _a.length) {
 552                         insertion_point = _a[degree];
 553                 }
 554
 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;
 559                         } else {
 560                                 _r_prime.type1_children_head = node;
 561                         }
 562                         _r_prime.type1_children_tail = node;
 563                 } else {
 564                         if (insertion_point.brothers_prev != null) {
 565                                 insertion_point.brothers_prev.brothers_next = node;
 566                                 node.brothers_prev = insertion_point.brothers_prev;
 567                         } else {
 568                                 _r_prime.type1_children_head = node;
 569                         }
 570                         node.brothers_next = insertion_point;
 571                         insertion_point.brothers_prev = node;
 572                 }
 573                 node.parent = _r_prime;
 574
 575                 // Maintain A, B and LP
 576                 if (degree >= _a.length) {
 577                         _a.resize (degree + 1);
 578                         _b.resize (degree + 1);
 579                 }
 580
 581                 // If there is already a child of such degree
 582                 if (_a[degree] == null) {
 583                         _b[degree] = true;
 584                 } else {
 585                         // Else if there is an odd number of child of such degree
 586                         if (_b[degree]) {
 587                                 // Make a pair
 588                                 NodePair<G> pair = new NodePair<G> (node, node.brothers_next);
 589                                 node.brothers_next.pair = pair;
 590                                 node.pair = pair;
 591                                 if (_lp_head == null) {
 592                                         _lp_head = pair;
 593                                         _lp_tail = pair;
 594                                 } else {
 595                                         pair.lp_prev = _lp_tail;
 596                                         _lp_tail.lp_next = pair;
 597                                         _lp_tail = pair;
 598                                 }
 599                                 // There is now an even number of child of such degree
 600                                 _b[degree] = false;
 601                         } else {
 602                                 _b[degree] = true;
 603                         }
 604                 }
 605                 _a[degree] = node;
 606
 607                 #if DEBUG
 608                         _dump ("End _add_in_r_prime: %s".printf ((string) node.data));
 609                 #endif
 610         }
 611
 612         private void _remove_type1_node (Type1Node<G> node) {
 613                 #if DEBUG
 614                         _dump ("Start _remove_type1_node: %s".printf ((string) node.data));
 615                 #endif
 616
 617                 if (node.parent == _r_prime) {
 618                         _updated_degree (node, false);
 619                 } else {
 620                         // Maintain LL
 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;
 625                         }
 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;
 630                         }
 631
 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;
 637
 638                                         // Increment parent's lost count
 639                                         parent.lost++;
 640
 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;
 646                                                 } else {
 647                                                 _ll_head = parent;
 648                                                 }
 649                                                 _ll_tail = parent;
 650                                         }
 651                                 }
 652                         }
 653                 }
 654
 655                 // Check whether removed node is P
 656                 if (node == _p) {
 657                         _p = null;
 658                 }
 659
 660                 // Maintain brothers list
 661                 node.remove ();
 662         }
 663
 664         private void _updated_degree (Type1Node<G> node, bool child_removed) {
 665                 int degree = node.degree ();
 666
 667                 // Maintain A and B
 668                 if (child_removed && _a[degree - 1] == null) {
 669                         _a[degree - 1] = node;
 670                         _b[degree - 1] = ! _b[degree - 1];
 671                 }
 672
 673                 _b[degree] = ! _b[degree];
 674                 if (_a[degree] == node) {
 675                         Type1Node<G> next = node.brothers_next;
 676                         if (next != null && next.degree () == degree) {
 677                                 _a[degree] = next;
 678                         } else {
 679                                 _a[degree] = null;
 680
 681                                 int i = _a.length - 1;
 682                                 while (i >= 0 && _a[i] == null) {
 683                                         i--;
 684                                 }
 685                                 _a.resize (i + 1);
 686                                 _b.resize (i + 1);
 687                         }
 688                 }
 689
 690                 // Maintain LP
 691                 if (node.pair != null) {
 692                         NodePair<G> pair = node.pair;
 693                         Type1Node<G> other = (pair.node1 == node ? pair.node2 : pair.node1);
 694                         node.pair = null;
 695                         other.pair = null;
 696                         if (pair.lp_prev != null) {
 697                                 pair.lp_prev.lp_next = pair.lp_next;
 698                         } else {
 699                                 _lp_head = pair.lp_next;
 700                         }
 701                         if (pair.lp_next != null) {
 702                                 pair.lp_next.lp_prev = pair.lp_prev;
 703                         } else {
 704                                 _lp_tail = pair.lp_prev;
 705                         }
 706                 }
 707         }
 708
 709         private void _remove_type2_node (Type2Node<G> node) {
 710                 ((Type1Node<G>) node.parent).type2_child = null;
 711                 node.parent = null;
 712
 713                 // For now we can't have type2 node other than R' (left for reference)
 714                 #if false
 715                         // Maintain LM
 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;
 721                                 }
 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;
 726                                 }
 727                                 node.lm_next = null;
 728                                 node.lm_prev = null;
 729                         }
 730                 #endif
 731         }
 732
 733         #if DEBUG
 734         public void _dump (string message) {
 735                 stdout.printf (">>>> %s\n", message);
 736
 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);
 740                 }
 741                 stdout.printf ("\n");
 742
 743                 stdout.printf ("B.length = %d:", _b.length);
 744                 foreach (bool even in _b) {
 745                         stdout.printf (" %s;", even.to_string ());
 746                 }
 747                 stdout.printf ("\n");
 748
 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);
 753                         pair = pair.lp_next;
 754                 }
 755                 stdout.printf ("\n");
 756
 757                 stdout.printf ("LL:");
 758                 unowned Type1Node<G>? node = _ll_head;
 759                 while (node != null) {
 760                         stdout.printf (" %s;", (string) node.data);
 761                         node = node.ll_next;
 762                 }
 763                 stdout.printf ("\n");
 764
 765                 stdout.printf ("%s\n", _r != null ? _r.to_string () : null);
 766
 767                 stdout.printf ("\n");
 768         }
 769         #endif
 770
 771         private abstract class Node<G> {
 772                 public G data;
 773                 public weak Node<G>? parent = null;
 774
 775                 public int type1_children_count;
 776                 public Type1Node<G>? type1_children_head = null;
 777                 public Type1Node<G>? type1_children_tail = null;
 778
 779                 public bool pending_drop;
 780
 781                 protected Node (G data) {
 782                         this.data = data;
 783                 }
 784
 785                 public inline int degree () {
 786                         return type1_children_count;
 787                 }
 788
 789         #if DEBUG
 790                 public string children_to_string (int level = 0) {
 791                         StringBuilder builder = new StringBuilder ();
 792                         bool first = true;
 793                         Type1Node<G> child = type1_children_head;
 794                         while (child != null) {
 795                                 if (!first) {
 796                                         builder.append (",\n");
 797                                 }
 798                                 first = false;
 799                                 builder.append (child.to_string (level));
 800                                 child = child.brothers_next;
 801                         }
 802                         return builder.str;
 803                 }
 804
 805                 public abstract string to_string (int level = 0);
 806         #endif
 807         }
 808
 809         private class Type1Node<G> : Node<G> {
 810                 public uint lost;
 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;
 817
 818                 public Type1Node (G data) {
 819                         base (data);
 820                 }
 821
 822                 public inline void add (Type1Node<G> node) {
 823                         node.parent = this;
 824                         if (type1_children_head == null) {
 825                                 type1_children_head = node;
 826                         } else {
 827                                 node.brothers_prev = type1_children_tail;
 828                         }
 829                         if (type1_children_tail != null) {
 830                                 type1_children_tail.brothers_next = node;
 831                         }
 832                         type1_children_tail = node;
 833                         type1_children_count++;
 834                 }
 835
 836                 public inline void remove () {
 837                         if (brothers_prev == null) {
 838                                 parent.type1_children_head = brothers_next;
 839                         } else {
 840                                 brothers_prev.brothers_next = brothers_next;
 841                         }
 842                         if (brothers_next == null) {
 843                                 parent.type1_children_tail = brothers_prev;
 844                         } else {
 845                                 brothers_next.brothers_prev = brothers_prev;
 846                         }
 847                         parent.type1_children_count--;
 848                         parent = null;
 849                         brothers_prev = null;
 850                         brothers_next = null;
 851                 }
 852
 853                 #if DEBUG
 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");
 863                         }
 864                         if (type1_children_head != null) {
 865                                 builder.append (children_to_string (level + 1));
 866                         }
 867                         if (type1_children_head != null && type2_child != null) {
 868                                 builder.append (",\n");
 869                         }
 870                         if (type2_child != null) {
 871                                 builder.append (type2_child.to_string (level + 1));
 872                         }
 873                         if (type1_children_head != null || type2_child != null) {
 874                                 builder.append ("\n");
 875                                 builder.append (string.nfill (level, '\t'));
 876                         }
 877                         builder.append (")");
 878                         return builder.str;
 879                 }
 880                 #endif
 881         }
 882
 883         private class Type2Node<G> : Node<G> {
 884                 // For now we can't have type2 node other than R' (left for reference)
 885                 #if false
 886                         public weak Type2Node<G>? lm_prev = null;
 887                         public Type2Node<G>? lm_next = null;
 888                 #endif
 889
 890                 public Type2Node (G data) {
 891                         base (data);
 892                 }
 893
 894                 #if DEBUG
 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'));
 905                         }
 906                         builder.append ("]");
 907                         return builder.str;
 908                 }
 909                 #endif
 910         }
 911
 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;
 917
 918                 public NodePair (Type1Node<G> node1, Type1Node<G> node2) {
 919                         this.node1 = node1;
 920                         this.node2 = node2;
 921                 }
 922         }
 923
 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;
 931                 private int stamp;
 932                 private bool removed = false;
 933
 934                 public Iterator (PriorityQueue<G> queue) {
 935                         this.queue = queue;
 936                         this.position = queue._r;
 937                         this.stamp = queue._stamp;
 938                 }
 939
 940                 public bool next () {
 941                         assert (stamp == queue._stamp);
 942                         if (!has_next ()) {
 943                                 return false;
 944                         }
 945                         removed = false;
 946                         started = true;
 947                         position = _next;
 948                         _next = null;
 949                         return (position != null);
 950                 }
 951
 952                 public bool has_next () {
 953                         assert (stamp == queue._stamp);
 954                         if (_next == null) {
 955                                 _next = position;
 956                                 if (!_has_next ()) {
 957                                         _next = null;
 958                                 }
 959                         }
 960                         return (_next != null);
 961                 }
 962
 963                 private bool _has_next() {
 964                         if (!started) {
 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;
 972                                         return true;
 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;
 977                                         return true;
 978                                 } else if (node.brothers_next != null) {
 979                                         _next = node.brothers_next;
 980                                         from_type1_children = false;
 981                                         from_type2_child = false;
 982                                         return true;
 983                                 }
 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;
 991                                         return true;
 992                                 }
 993                                 from_type2_child = true;
 994                         }
 995                         if (_next != null && _next != queue._r) {
 996                                 _next = _next.parent;
 997                                 return _has_next ();
 998                         }
 999                         return false;
1000                 }
1001
1002                 public new G get () {
1003                         assert (stamp == queue._stamp);
1004                         assert (position != null);
1005                         assert (! removed);
1006                         return position.data;
1007                 }
1008
1009                 public void remove () {
1010                         assert (stamp == queue._stamp);
1011                         assert (position != null);
1012                         assert (! removed);
1013                         has_next ();
1014                         Node<G> node = position;
1015                         position = null;
1016                         queue._delete (node);
1017                         stamp = queue._stamp;
1018                         removed = true;
1019                 }
1020
1021                 internal Node<G> get_node () {
1022                         assert (stamp == queue._stamp);
1023                         assert (position != null);
1024                         return position;
1025                 }
1026
1027                 public bool read_only {
1028                         get {
1029                                 return false;
1030                         }
1031                 }
1032
1033                 public bool valid {
1034                         get {
1035                                 return started &&  ! removed && position != null;
1036                         }
1037                 }
1038
1039                 public bool foreach (ForallFunc<G> f) {
1040                         if (valid) {
1041                                 if (!f (position.data)) {
1042                                         return false;
1043                                 }
1044                         }
1045                         while (next ()) {
1046                                 if (!f (position.data)) {
1047                                         return false;
1048                                 }
1049                         }
1050                         return true;
1051                 }
1052         }
1053 }