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         public CompareFunc compare_func { private set; get; }
  48
  49         private int _size = 0;
  50         private int _stamp = 0;
  51         private Type1Node<G>? _r = null;
  52         private Type2Node<G>? _r_prime = null;
  53         private Type2Node<G>? _lm_head = null;
  54         private Type2Node<G>? _lm_tail = null;
  55         private Type1Node<G>? _p = null;
  56 #if VALA_0_16
  57         private Type1Node<G>?[] _a = new Type1Node<G>?[0];
  58 #else
  59         private Type1Node<G>?[] _a = new Type1Node<G>[0];
  60 #endif
  61         private NodePair<G>? _lp_head = null;
  62         private NodePair<G>? _lp_tail = null;
  63         private bool[] _b = new bool[0];
  64         private Type1Node<G>? _ll_head = null;
  65         private Type1Node<G>? _ll_tail = null;
  66         private unowned Node<G> _iter_head = null;
  67         private unowned Node<G> _iter_tail = null;
  68
  69         /**
  70          * Constructs a new, empty priority queue.
  71          *
  72          * If not provided, the function parameter is requested to the
  73          * {@link Functions} function factory methods.
  74          *
  75          * @param compare_func an optional element comparator function
  76          */
  77         public PriorityQueue (CompareFunc? compare_func = null) {
  78                 if (compare_func == null) {
  79                         compare_func = Functions.get_compare_func_for (typeof (G));
  80                 }
  81                 this.compare_func = compare_func;
  82         }
  83
  84         /**
  85          * {@inheritDoc}
  86          */
  87         public override int capacity {
  88                 get { return UNBOUNDED_CAPACITY; }
  89         }
  90
  91         /**
  92          * {@inheritDoc}
  93          */
  94         public override int remaining_capacity {
  95                 get { return UNBOUNDED_CAPACITY; }
  96         }
  97
  98         /**
  99          * {@inheritDoc}
 100          */
 101         public override bool is_full {
 102                 get { return false; }
 103         }
 104
 105         /**
 106          * {@inheritDoc}
 107          */
 108         public override bool offer (G element) {
 109                 #if DEBUG
 110                         _dump ("Start offer: %s".printf ((string)element));
 111                 #endif
 112                 if (_r == null) {
 113                         _r = new Type1Node<G> (element, ref _iter_head, ref _iter_tail);
 114                         _p = _r;
 115                 } else if (_r_prime == null) {
 116                         _r_prime = new Type2Node<G> (element, ref _iter_head, ref _iter_tail);
 117                         _r_prime.parent = _r;
 118                         _r.type2_child = _r_prime;
 119                         if (_compare (_r_prime, _r) < 0)
 120                                 _swap_data (_r_prime, _r);
 121                 } else {
 122                         // Form a tree with a single node N of type I consisting of element e
 123                         Type1Node<G> node = new Type1Node<G> (element, ref _iter_head, ref _iter_tail);
 124
 125                         //Add(Q, N)
 126                         _add (node);
 127                 }
 128
 129                 _stamp++;
 130                 _size++;
 131                 #if DEBUG
 132                         _dump ("End offer: %s".printf ((string)element));
 133                 #endif
 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                         if (_r.iter_next != null) {
 167                                 _r.iter_next.iter_prev = _r.iter_prev;
 168                         }
 169                         if (_r.iter_prev != null) {
 170                                 _r.iter_prev.iter_next = _r.iter_next;
 171                         }
 172                         if (_iter_head == _r) {
 173                                 _iter_head = _r.iter_next;
 174                         }
 175                         if (_iter_tail == _r) {
 176                                 _iter_tail = _r.iter_prev;
 177                         }
 178                         _r = null;
 179                         _p = null;
 180                         return min;
 181                 }
 182                 _move_data (_r, _r_prime);
 183
 184
 185                 // 1c. R'' <- The child of R' containing the minimum element among the children of R'
 186                 if (_r_prime.type1_children_head == null) {
 187                         _remove_type2_node (_r_prime, true);
 188                         _r_prime = null;
 189                         return min;
 190                 }
 191                 Type1Node<G>? r_second = null;
 192                 Type1Node<G> node = _r_prime.type1_children_head;
 193                 while (node != null) {
 194                         if (r_second == null || _compare (node, r_second) < 0) {
 195                                 r_second = node;
 196                         }
 197                         node = node.brothers_next;
 198                 }
 199
 200                 // 1d. R'.element <- R''.element
 201                 _move_data (_r_prime, r_second);
 202
 203                 // 2a. Delete the subtree rooted at R'' from Q
 204                 _remove_type1_node (r_second, true);
 205
 206                 // 2b. For all children N of type I of R'' do make N a child of R' of Q
 207                 node = r_second.type1_children_head;
 208                 while (node != null) {
 209                         Type1Node<G> next = node.brothers_next;
 210                         _remove_type1_node (node, false);
 211                         _add_in_r_prime (node);
 212                         node = next;
 213                 }
 214
 215                 // For now we can't have type2 node other than R' (left for reference)
 216                 #if false
 217                         // 3a. If R'' has no child of type II then goto Step 4.
 218                         if (r_second.type2_child != null) {
 219                                 // 3b. Let M' be the child of type II of R''. Insert(Q, M'.element)
 220                                 Type2Node<G> m_prime = r_second.type2_child;
 221                                 _remove_type2_node (m_prime);
 222                                 offer (m_prime.data);
 223
 224                                 // 3c. For all children N of M do make N a child of R' of Q
 225                                 node = m_prime.type1_children_head;
 226                                 while (node != null) {
 227                                         Type1Node<G> next = node.brothers_next;
 228                                         _remove_type1_node (node);
 229                                         _add_in_r_prime (node);
 230                                         node = next;
 231                                 }
 232                         }
 233                 #endif
 234
 235                 // 4. Adjust(Q, P, P)
 236                 if (_p == null) {
 237                         _p = _r;
 238                 }
 239                 _adjust (_p, _p);
 240
 241                 // For now we can't have type2 node other than R' (left for reference)
 242                 #if false
 243                         // 5a. if LM is empty then goto Step 6
 244                         if (_lm_head != null) {
 245                                 // 5b. M <- Head(LM); LM <- Tail(LM)
 246                                 Type2Node<G> m = _lm_head;
 247
 248                                 // 5c. Delete M from Q
 249                                 _remove_type2_node (m);
 250
 251                                 // 5d. I nsert(Q, M.element)
 252                                 offer (m.data);
 253
 254                                 // 5e. For all children N of M do make M a child of R' of Q
 255                                 node = m.type1_children_head;
 256                                 while (node != null) {
 257                                         Type1Node<G> next = node.brothers_next;
 258                                         _remove_type1_node (node);
 259                                         _add_in_r_prime (node);
 260                                         node = next;
 261                                 }
 262                         }
 263                 #endif
 264
 265                 // 6. While among the children of R' there exist any two different nodes Ri and Rj
 266                 // such that Ri.degree = Rj.degree do Link(Q, Ri, Rj)
 267                 while (_check_linkable ()) {}
 268
 269                 // 7. Return MinElement
 270                 return min;
 271         }
 272
 273         /**
 274          * {@inheritDoc}
 275          */
 276         public override int drain (Collection<G> recipient, int amount = -1) {
 277                 if (amount == -1) {
 278                         amount = this._size;
 279                 }
 280                 for (int i = 0; i < amount; i++) {
 281                         if (this._size == 0) {
 282                                 return i;
 283                         }
 284                         recipient.add (poll ());
 285                 }
 286                 return amount;
 287         }
 288
 289         /**
 290          * {@inheritDoc}
 291          */
 292         public override int size {
 293                 get { return _size; }
 294         }
 295
 296         /**
 297          * {@inheritDoc}
 298          */
 299         public override bool contains (G item) {
 300                 foreach (G an_item in this) {
 301                         if (compare_func (item, an_item) == 0) {
 302                                 return true;
 303                         }
 304                 }
 305                 return false;
 306         }
 307
 308         /**
 309          * {@inheritDoc}
 310          */
 311         public override bool add (G item) {
 312                 return offer (item);
 313         }
 314
 315         /**
 316          * {@inheritDoc}
 317          */
 318         public override bool remove (G item) {
 319                 #if DEBUG
 320                         _dump ("Start remove: %s".printf ((string) item));
 321                 #endif
 322
 323                 Iterator<G> iterator = new Iterator<G> (this);
 324                 while (iterator.next ()) {
 325                         G an_item = iterator.get ();
 326                         if (compare_func (item, an_item) == 0) {
 327                                 iterator.remove ();
 328                                 return true;
 329                         }
 330                 }
 331                 return false;
 332         }
 333
 334         /**
 335          * {@inheritDoc}
 336          */
 337         public override void clear () {
 338                 _size = 0;
 339                 _r = null;
 340                 _r_prime = null;
 341                 _lm_head = null;
 342                 _lm_tail = null;
 343                 _p = null;
 344 #if VALA_0_16
 345                 _a = new Type1Node<G>?[0];
 346 #else
 347                 _a = new Type1Node<G>[0];
 348 #endif
 349                 _lp_head = null;
 350                 _lp_tail = null;
 351                 _b = new bool[0];
 352                 _ll_head = null;
 353                 _ll_tail = null;
 354                 _iter_head = null;
 355                 _iter_tail = null;
 356         }
 357
 358         /**
 359          * {@inheritDoc}
 360          */
 361         public override Gee.Iterator<G> iterator () {
 362                 return new Iterator<G> (this);
 363         }
 364
 365         private inline int _compare (Node<G> node1, Node<G> node2) {
 366                 // Assume there can't be two nodes pending drop
 367                 if (node1.pending_drop) {
 368                         return -1;
 369                 } else if (node2.pending_drop) {
 370                         return 1;
 371                 } else {
 372                         return compare_func (node1.data, node2.data);
 373                 }
 374         }
 375
 376         private inline void _swap_data (Node<G> node1, Node<G> node2) {
 377                 #if DEBUG
 378                         _dump ("Before swap: %p(%s) %p(%s)".printf(node1, (string)node1.data, node2, (string)node2.data));
 379                 #endif
 380                 G temp_data = (owned) node1.data;
 381                 bool temp_pending_drop = node1.pending_drop;
 382                 node1.data = (owned) node2.data;
 383                 node1.pending_drop = node2.pending_drop;
 384                 node2.data = (owned) temp_data;
 385                 node2.pending_drop = temp_pending_drop;
 386
 387                 if (node1.iter_next == node2) { // Before swap: N1 N2
 388                         unowned Node<G> temp_iter_prev = node1.iter_prev;
 389                         unowned Node<G> temp_iter_next = node2.iter_next;
 390
 391                         node1.iter_prev = node2;
 392                         node1.iter_next = temp_iter_next;
 393                         node2.iter_prev = temp_iter_prev;
 394                         node2.iter_next = node1;
 395                 } else if (node1.iter_prev == node2) { // Before swap: N2 N1
 396                         unowned Node<G> temp_iter_prev = node2.iter_prev;
 397                         unowned Node<G> temp_iter_next = node1.iter_next;
 398
 399                         node1.iter_prev = temp_iter_prev;
 400                         node1.iter_next = node2;
 401                         node2.iter_prev = node1;
 402                         node2.iter_next = temp_iter_next;
 403                 } else {
 404                         unowned Node<G> temp_iter_prev = node1.iter_prev;
 405                         unowned Node<G> temp_iter_next = node1.iter_next;
 406
 407                         node1.iter_prev = node2.iter_prev;
 408                         node1.iter_next = node2.iter_next;
 409                         node2.iter_prev = temp_iter_prev;
 410                         node2.iter_next = temp_iter_next;
 411                 }
 412
 413                 if (node2 == _iter_head) {
 414                         _iter_head = node1;
 415                 } else if (node1 == _iter_head) {
 416                         _iter_head = node2;
 417                 }
 418                 if (node2 == _iter_tail) {
 419                         _iter_tail = node1;
 420                 } else if (node1 == _iter_tail) {
 421                         _iter_tail = node2;
 422                 }
 423
 424                 if (node1.iter_prev != null) {
 425                         node1.iter_prev.iter_next = node1;
 426                 }
 427                 if (node1.iter_next != null) {
 428                         node1.iter_next.iter_prev = node1;
 429                 }
 430                 if (node2.iter_prev != null) {
 431                         node2.iter_prev.iter_next = node2;
 432                 }
 433                 if (node2.iter_next != null) {
 434                         node2.iter_next.iter_prev = node2;
 435                 }
 436
 437                 #if DEBUG
 438                         _dump ("After swap: %p(%s) %p(%s)".printf(node1, (string)node1.data, node2, (string)node2.data));
 439                 #endif
 440         }
 441
 442         private inline void _move_data (Node<G> target, Node<G> source) {
 443                 #if DEBUG
 444                         _dump ("Before move: %p(%s) <- %p(%s)".printf(target, (string)target.data, source, (string)source.data));
 445                 #endif
 446
 447                 if (target.iter_next != null) {
 448                         target.iter_next.iter_prev = target.iter_prev;
 449                 } else if (_iter_tail == target) {
 450                         _iter_tail = target.iter_prev;
 451                 }
 452                 if (target.iter_prev != null) {
 453                         target.iter_prev.iter_next = target.iter_next;
 454                 } else if (_iter_head == target) {
 455                         _iter_head = target.iter_next;
 456                 }
 457
 458                 target.data = source.data;
 459                 target.pending_drop = source.pending_drop;
 460                 target.iter_next = source.iter_next;
 461                 target.iter_prev = source.iter_prev;
 462                 source.iter_next = null;
 463                 source.iter_prev = null;
 464
 465                 if (target.iter_next != null) {
 466                         target.iter_next.iter_prev = target;
 467                 } else if (_iter_tail == source) {
 468                         _iter_tail = target;
 469                 }
 470                 if (target.iter_prev != null) {
 471                         target.iter_prev.iter_next = target;
 472                 } else if (_iter_head == source) {
 473                         _iter_head = target;
 474                 }
 475                 #if DEBUG
 476                         _dump ("After move:");
 477                 #endif
 478         }
 479
 480         private void _link (owned Type1Node<G> ri, owned Type1Node<G> rj) {
 481                 assert (ri.degree () == rj.degree ());
 482
 483                 // Delete the subtrees rooted at Ri and Rj from Q
 484                 _remove_type1_node (ri, false);
 485                 _remove_type1_node (rj, false);
 486
 487                 // If Ri.element > Rj.element then Swap(Ri,Rj)
 488                 if (_compare (ri, rj) > 0) {
 489                         Type1Node<G> temp = ri;
 490                         ri = rj;
 491                         rj = temp;
 492                 }
 493
 494                 // Make Rj the last child of Ri
 495                 _add_to (rj, ri);
 496
 497                 // Make Ri (whose degree now = d+1) a child of R' of Q
 498                 _add_in_r_prime (ri);
 499         }
 500
 501         private void _add (Type1Node<G> n) {
 502                 // Make N a child of R' of Q
 503                 _add_in_r_prime (n);
 504
 505                 // If N.element < R'.element then Swap(N.element, R'.element)
 506                 if (_compare (n, _r_prime) < 0) {
 507                         _swap_data (n, _r_prime);
 508                 }
 509
 510                 // If R'.element < R.element then Swap(R'.element, R.element)
 511                 if (_compare (_r_prime, _r) < 0) {
 512                         _swap_data (_r_prime, _r);
 513                 }
 514
 515                 // If among the children of R' there exist any two different nodes Ri and Rj
 516                 // such that Ri.degree = Rj.degree then Link(Q, Ri, Rj)
 517                 _check_linkable ();
 518
 519                 #if DEBUG
 520                         _dump ("End _add: %p(%s)".printf (n, (string) n.data));
 521                 #endif
 522         }
 523
 524         private bool _check_linkable () {
 525                 #if DEBUG
 526                         _dump ("Start _check_linkable:");
 527                 #endif
 528
 529                 if (_lp_head != null) {
 530                         NodePair<G> pair = _lp_head;
 531                         _link (pair.node1, pair.node2);
 532                         return true;
 533                 }
 534                 return false;
 535         }
 536
 537         private Node<G> _re_insert (owned Type1Node<G> n) {
 538                 assert (n != _r);
 539
 540                 #if DEBUG
 541                         _dump ("Start _re_insert: %p(%s)".printf (n, (string) n.data));
 542                 #endif
 543
 544                 //Parent <- N.parent
 545                 Node<G> parent = n.parent;
 546
 547                 // Delete the subtree rooted at N from Q
 548                 _remove_type1_node (n, false);
 549
 550                 // Add(Q, N)
 551                 _add (n);
 552
 553                 // Return Parent
 554                 return parent;
 555         }
 556
 557         private void _adjust (Type1Node<G> p1, Type1Node<G> p2) {
 558                 // If M.lost <= 1 for all nodes M in Q then return
 559                 if (_ll_head == null) {
 560                         return;
 561                 }
 562
 563                 #if DEBUG
 564                         _dump ("Start _adjust: %p(%s), %p(%s)".printf (p1, (string) p1.data, p2, (string) p2.data));
 565                 #endif
 566
 567                 // If P1.lost > P2.lost then M <- P1 else M <- P2
 568                 Type1Node<G> m;
 569                 if (p1.lost > p2.lost) {
 570                         m = p1;
 571                 } else {
 572                         m = p2;
 573                 }
 574
 575                 // If M.lost <= 1 then M <- M' for some node M' in Q such that M'.lost > 1
 576                 if (m.lost <= 1) {
 577                         m = _ll_head;
 578                         if (_ll_head.ll_next != null) {
 579                                 _ll_head.ll_next.ll_prev = null;
 580                         }
 581                         _ll_head = _ll_head.ll_next;
 582                 }
 583
 584                 // P <- ReInsert(Q, M)
 585                 _p = (Type1Node<G>) _re_insert (m);
 586
 587                 #if DEBUG
 588                         _dump ("End _adjust: %p(%s), %p(%s)".printf (p1, (string) p1.data, p2, (string) p2.data));
 589                 #endif
 590         }
 591
 592         private void _delete (Node<G> n, out unowned Node<G> prev = null) {
 593                 // DecreaseKey(Q, N, infinite)
 594                 _decrease_key (n);
 595
 596                 // DeleteMin(Q)
 597                 poll ();
 598         }
 599
 600         private void _decrease_key (Node<G> n) {
 601                 #if DEBUG
 602                         _dump ("Start _decrease_key: %p(%s)".printf (n, (string) n.data));
 603                 #endif
 604
 605                 if (n == _r || _r_prime == null) {
 606                         return;
 607                 }
 608
 609                 n.pending_drop = true;
 610
 611                 // If (N = R or R') and (R'.element < R.element) then
 612                 // Swap(R'.element, R.element); return
 613                 if (n == _r_prime && _compare (_r_prime, _r) < 0) {
 614                         _swap_data (_r_prime, _r);
 615                         return;
 616                 }
 617
 618                 // For now we can't have type2 node other than R' (left for reference)
 619                 #if false
 620                         // If (N is of type II) and (N.element < N.parent.element) then
 621                         // Swap(N.element, N.parent.element); N <- N.parent
 622                         if (n is Type2Node && _compare (n, n.parent) < 0) {
 623                                 _swap_data (n, n.parent);
 624                                 n = n.parent;
 625                         }
 626                 #endif
 627
 628                 // Can't occur as we made n be the most little (left for reference)
 629                 #if false
 630                         // If N.element >= N.parent.element then return
 631                         if (n.parent != null && _compare (n, n.parent) >= 0) {
 632                                 return;
 633                         }
 634                 #endif
 635
 636                 // P' <- ReInsert(Q, N)
 637                 Node<G> p_prime = _re_insert ((Type1Node<G>) n);
 638
 639                 if (p_prime is Type2Node) {
 640                         // Adjust(Q, P, P);
 641                         _adjust (_p, _p);
 642                 } else {
 643                         // Adjust(Q, P, P');
 644                         _adjust (_p, (Type1Node<G>) p_prime);
 645                 }
 646         }
 647
 648         private void _add_to (Type1Node<G> node, Type1Node<G> parent) {
 649                 parent.add (node);
 650                 parent.lost = 0;
 651         }
 652
 653         private void _add_in_r_prime (Type1Node<G> node) {
 654                 #if DEBUG
 655                         _dump ("Start _add_in_r_prime: %p(%s)".printf (node, (string) node.data));
 656                 #endif
 657
 658                 int degree = node.degree ();
 659
 660                 Type1Node<G>? insertion_point = null;
 661                 if (degree < _a.length) {
 662                         insertion_point = _a[degree];
 663                 }
 664
 665                 if (insertion_point == null) {
 666                         if (_r_prime.type1_children_tail != null) {
 667                                 node.brothers_prev = _r_prime.type1_children_tail;
 668                                 _r_prime.type1_children_tail.brothers_next = node;
 669                         } else {
 670                                 _r_prime.type1_children_head = node;
 671                         }
 672                         _r_prime.type1_children_tail = node;
 673                 } else {
 674                         if (insertion_point.brothers_prev != null) {
 675                                 insertion_point.brothers_prev.brothers_next = node;
 676                                 node.brothers_prev = insertion_point.brothers_prev;
 677                         } else {
 678                                 _r_prime.type1_children_head = node;
 679                         }
 680                         node.brothers_next = insertion_point;
 681                         insertion_point.brothers_prev = node;
 682                 }
 683                 node.parent = _r_prime;
 684
 685                 // Maintain A, B and LP
 686                 if (degree >= _a.length) {
 687                         _a.resize (degree + 1);
 688                         _b.resize (degree + 1);
 689                 }
 690
 691                 // If there is already a child of such degree
 692                 if (_a[degree] == null) {
 693                         _b[degree] = true;
 694                 } else {
 695                         // Else if there is an odd number of child of such degree
 696                         if (_b[degree]) {
 697                                 // Make a pair
 698                                 NodePair<G> pair = new NodePair<G> (node, node.brothers_next);
 699                                 node.brothers_next.pair = pair;
 700                                 node.pair = pair;
 701                                 if (_lp_head == null) {
 702                                         _lp_head = pair;
 703                                         _lp_tail = pair;
 704                                 } else {
 705                                         pair.lp_prev = _lp_tail;
 706                                         _lp_tail.lp_next = pair;
 707                                         _lp_tail = pair;
 708                                 }
 709                                 // There is now an even number of child of such degree
 710                                 _b[degree] = false;
 711                         } else {
 712                                 _b[degree] = true;
 713                         }
 714                 }
 715                 _a[degree] = node;
 716
 717                 #if DEBUG
 718                         _dump ("End _add_in_r_prime: %p(%s)".printf (node, (string) node.data));
 719                 #endif
 720         }
 721
 722         private void _remove_type1_node (Type1Node<G> node, bool with_iteration) {
 723                 #if DEBUG
 724                         _dump ("Start _remove_type1_node: %p(%s)".printf (node, (string) node.data));
 725                 #endif
 726
 727                 if (node.parent == _r_prime) {
 728                         _updated_degree (node, false);
 729                 } else {
 730                         // Maintain LL
 731                         if (node.ll_prev != null) {
 732                                 node.ll_prev.ll_next = node.ll_next;
 733                         } else if (_ll_head == node) {
 734                                 _ll_head = node.ll_next;
 735                         }
 736                         if (node.ll_next != null) {
 737                                 node.ll_next.ll_prev = node.ll_prev;
 738                         } else if (_ll_tail == node) {
 739                                 _ll_tail = node.ll_prev;
 740                         }
 741
 742                         if (node.parent != null) {
 743                                 if (node.parent.parent == _r_prime) {
 744                                         _updated_degree ((Type1Node<G>) node.parent, true);
 745                                 } else if (node.parent.parent != null) {
 746                                         Type1Node<G> parent = (Type1Node<G>) node.parent;
 747
 748                                         // Increment parent's lost count
 749                                         parent.lost++;
 750
 751                                         // And add it to LL if needed
 752                                         if (parent.lost > 1) {
 753                                                 if (_ll_tail != null) {
 754                                                         parent.ll_prev = _ll_tail;
 755                                                         _ll_tail.ll_next = parent;
 756                                                 } else {
 757                                                         _ll_head = parent;
 758                                                 }
 759                                                 _ll_tail = parent;
 760                                         }
 761                                 }
 762                         }
 763                 }
 764
 765                 // Check whether removed node is P
 766                 if (node == _p) {
 767                         _p = null;
 768                 }
 769
 770                 // Maintain brothers list
 771                 node.remove ();
 772
 773                 // Maintain iteration
 774                 if (with_iteration) {
 775                         if (node.iter_prev != null) {
 776                                 node.iter_prev.iter_next = node.iter_next;
 777                         } else if (_iter_head == node) {
 778                                 _iter_head = node.iter_next;
 779                         }
 780                         if (node.iter_next != null) {
 781                                 node.iter_next.iter_prev = node.iter_prev;
 782                         } else if (_iter_tail == node) {
 783                                 _iter_tail = node.iter_prev;
 784                         }
 785                 }
 786                 #if DEBUG
 787                         _dump ("End _remove_type1_node: %p(%s)".printf (node, (string) node.data));
 788                 #endif
 789         }
 790
 791         private void _updated_degree (Type1Node<G> node, bool child_removed) {
 792                 int degree = node.degree ();
 793
 794                 // Maintain A and B
 795                 if (child_removed && _a[degree - 1] == null) {
 796                         _a[degree - 1] = node;
 797                         _b[degree - 1] = ! _b[degree - 1];
 798                 }
 799
 800                 _b[degree] = ! _b[degree];
 801                 if (_a[degree] == node) {
 802                         Type1Node<G> next = node.brothers_next;
 803                         if (next != null && next.degree () == degree) {
 804                                 _a[degree] = next;
 805                         } else {
 806                                 _a[degree] = null;
 807
 808                                 int i = _a.length - 1;
 809                                 while (i >= 0 && _a[i] == null) {
 810                                         i--;
 811                                 }
 812                                 _a.resize (i + 1);
 813                                 _b.resize (i + 1);
 814                         }
 815                 }
 816
 817                 // Maintain LP
 818                 if (node.pair != null) {
 819                         NodePair<G> pair = node.pair;
 820                         Type1Node<G> other = (pair.node1 == node ? pair.node2 : pair.node1);
 821                         node.pair = null;
 822                         other.pair = null;
 823                         if (pair.lp_prev != null) {
 824                                 pair.lp_prev.lp_next = pair.lp_next;
 825                         } else {
 826                                 _lp_head = pair.lp_next;
 827                         }
 828                         if (pair.lp_next != null) {
 829                                 pair.lp_next.lp_prev = pair.lp_prev;
 830                         } else {
 831                                 _lp_tail = pair.lp_prev;
 832                         }
 833                 }
 834         }
 835
 836         private void _remove_type2_node (Type2Node<G> node, bool with_iteration) {
 837                 #if DEBUG
 838                         _dump ("Start _remove_type2_node: %p(%s)".printf (node, (string) node.data));
 839                 #endif
 840                 ((Type1Node<G>) node.parent).type2_child = null;
 841                 node.parent = null;
 842
 843                 // For now we can't have type2 node other than R' (left for reference)
 844                 #if false
 845                         // Maintain LM
 846                         if (node != _r_prime) {
 847                                 if (node.lm_prev != null) {
 848                                         node.lm_prev.lm_next = node.lm_next;
 849                                 } else if (_lm_head == node) {
 850                                         _lm_head = node.lm_next;
 851                                 }
 852                                 if (node.lm_next != null) {
 853                                         node.lm_next.lm_prev = node.lm_prev;
 854                                 } else if (_lm_tail == node)  {
 855                                         _lm_tail = node.lm_prev;
 856                                 }
 857                                 node.lm_next = null;
 858                                 node.lm_prev = null;
 859                         }
 860                 #endif
 861
 862                 // Maintain iteration
 863                 if (with_iteration) {
 864                         if (node.iter_prev != null) {
 865                                 node.iter_prev.iter_next = node.iter_next;
 866                         } else if (_iter_head == node) {
 867                                 _iter_head = node.iter_next;
 868                         }
 869                         if (node.iter_next != null) {
 870                                 node.iter_next.iter_prev = node.iter_prev;
 871                         } else if (_iter_tail == node) {
 872                                 _iter_tail = node.iter_prev;
 873                         }
 874                 }
 875                 #if DEBUG
 876                         _dump ("End _remove_type2_node: %p(%s)".printf (node, (string) node.data));
 877                 #endif
 878         }
 879
 880         #if DEBUG
 881         public void _dump (string message) {
 882                 stdout.printf (">>>> %s\n", message);
 883
 884                 stdout.printf ("A.length = %d:", _a.length);
 885                 foreach (Node<G>? node in _a) {
 886                         stdout.printf (" %p(%s);", node, node != null ? (string) node.data : null);
 887                 }
 888                 stdout.printf ("\n");
 889
 890                 stdout.printf ("B.length = %d:", _b.length);
 891                 foreach (bool even in _b) {
 892                         stdout.printf (" %s;", even.to_string ());
 893                 }
 894                 stdout.printf ("\n");
 895
 896                 stdout.printf ("LP:");
 897                 unowned NodePair<G>? pair = _lp_head;
 898                 while (pair != null) {
 899                         stdout.printf (" (%p(%s),%p(%s));", pair.node1, (string) pair.node1.data, pair.node2, (string) pair.node2.data);
 900                         pair = pair.lp_next;
 901                 }
 902                 stdout.printf ("\n");
 903
 904                 stdout.printf ("LL:");
 905                 unowned Type1Node<G>? node = _ll_head;
 906                 while (node != null) {
 907                         stdout.printf (" %p(%s);", node, (string) node.data);
 908                         node = node.ll_next;
 909                 }
 910                 stdout.printf ("\n");
 911
 912                 stdout.printf ("ITER:");
 913                 unowned Node<G>? inode_prev = null;
 914                 unowned Node<G>? inode = _iter_head;
 915                 while (inode != null) {
 916                         stdout.printf (" %p(%s);", inode, (string) inode.data);
 917                         assert (inode.iter_prev == inode_prev);
 918                         inode_prev = inode;
 919                         inode = inode.iter_next;
 920                 }
 921                 stdout.printf ("\n");
 922
 923                 stdout.printf ("%s\n", _r != null ? _r.to_string () : null);
 924
 925                 stdout.printf ("\n");
 926         }
 927         #endif
 928
 929         private abstract class Node<G> {
 930                 public G data;
 931                 public weak Node<G>? parent = null;
 932
 933                 public int type1_children_count;
 934                 public Type1Node<G>? type1_children_head = null;
 935                 public Type1Node<G>? type1_children_tail = null;
 936
 937                 public unowned Node<G>? iter_prev;
 938                 public unowned Node<G>? iter_next = null;
 939
 940                 public bool pending_drop;
 941
 942                 protected Node (G data, ref unowned Node<G>? head, ref unowned Node<G>? tail) {
 943                         this.data = data;
 944                         iter_prev = tail;
 945                         tail = this;
 946                         if (iter_prev != null) {
 947                                 iter_prev.iter_next = this;
 948                         }
 949                         if (head == null) {
 950                                 head = this;
 951                         }
 952                 }
 953
 954                 public inline int degree () {
 955                         return type1_children_count;
 956                 }
 957
 958         #if DEBUG
 959                 public string children_to_string (int level = 0) {
 960                         StringBuilder builder = new StringBuilder ();
 961                         bool first = true;
 962                         Type1Node<G> child = type1_children_head;
 963                         while (child != null) {
 964                                 if (!first) {
 965                                         builder.append (",\n");
 966                                 }
 967                                 first = false;
 968                                 builder.append (child.to_string (level));
 969                                 child = child.brothers_next;
 970                         }
 971                         return builder.str;
 972                 }
 973
 974                 public abstract string to_string (int level = 0);
 975         #endif
 976         }
 977
 978         private class Type1Node<G> : Node<G> {
 979                 public uint lost;
 980                 public weak Type1Node<G>? brothers_prev = null;
 981                 public Type1Node<G>? brothers_next = null;
 982                 public Type2Node<G>? type2_child = null;
 983                 public weak Type1Node<G>? ll_prev = null;
 984                 public Type1Node<G>? ll_next = null;
 985                 public weak NodePair<G>? pair = null;
 986
 987                 public Type1Node (G data, ref unowned Node<G>? head, ref unowned Node<G>? tail) {
 988                         base (data, ref head, ref tail);
 989                 }
 990
 991                 public inline void add (Type1Node<G> node) {
 992                         node.parent = this;
 993                         if (type1_children_head == null) {
 994                                 type1_children_head = node;
 995                         } else {
 996                                 node.brothers_prev = type1_children_tail;
 997                         }
 998                         if (type1_children_tail != null) {
 999                                 type1_children_tail.brothers_next = node;
1000                         }
1001                         type1_children_tail = node;
1002                         type1_children_count++;
1003                 }
1004
1005                 public inline void remove () {
1006                         if (brothers_prev == null) {
1007                                 parent.type1_children_head = brothers_next;
1008                         } else {
1009                                 brothers_prev.brothers_next = brothers_next;
1010                         }
1011                         if (brothers_next == null) {
1012                                 parent.type1_children_tail = brothers_prev;
1013                         } else {
1014                                 brothers_next.brothers_prev = brothers_prev;
1015                         }
1016                         parent.type1_children_count--;
1017                         parent = null;
1018                         brothers_prev = null;
1019                         brothers_next = null;
1020                 }
1021
1022                 #if DEBUG
1023                 public override string to_string (int level = 0) {
1024                         StringBuilder builder = new StringBuilder ();
1025                         builder.append (string.nfill (level, '\t'));
1026                         builder.append ("(");
1027                         builder.append_printf("%p(%s)/%u", this, (string)data, lost);
1028                         if (type1_children_head != null || type2_child != null) {
1029                                 builder.append (":\n");
1030                         }
1031                         if (type1_children_head != null) {
1032                                 builder.append (children_to_string (level + 1));
1033                         }
1034                         if (type1_children_head != null && type2_child != null) {
1035                                 builder.append (",\n");
1036                         }
1037                         if (type2_child != null) {
1038                                 builder.append (type2_child.to_string (level + 1));
1039                         }
1040                         if (type1_children_head != null || type2_child != null) {
1041                                 builder.append ("\n");
1042                                 builder.append (string.nfill (level, '\t'));
1043                         }
1044                         builder.append (")");
1045                         return builder.str;
1046                 }
1047                 #endif
1048         }
1049
1050         private class Type2Node<G> : Node<G> {
1051                 // For now we can't have type2 node other than R' (left for reference)
1052                 #if false
1053                         public weak Type2Node<G>? lm_prev = null;
1054                         public Type2Node<G>? lm_next = null;
1055                 #endif
1056
1057                 public Type2Node (G data, ref unowned Node<G>? head, ref unowned Node<G>? tail) {
1058                         base (data, ref head, ref tail);
1059                 }
1060
1061                 #if DEBUG
1062                 public override string to_string (int level = 0) {
1063                         StringBuilder builder = new StringBuilder ();
1064                         builder.append (string.nfill (level, '\t'));
1065                         builder.append_printf ("[%p(%s)", this, (string)data);
1066                         if (type1_children_head != null) {
1067                                 builder.append (":\n");
1068                                 builder.append (children_to_string (level + 1));
1069                                 builder.append ("\n");
1070                                 builder.append (string.nfill (level, '\t'));
1071                         }
1072                         builder.append ("]");
1073                         return builder.str;
1074                 }
1075                 #endif
1076         }
1077
1078         private class DummyNode<G> : Node<G> {
1079                 public DummyNode (ref unowned Node<G>? prev_next, ref unowned Node<G>? next_prev, Node<G>? iter_prev, Node<G>? iter_next) {
1080                         #if DEBUG
1081                         base ("<<dummy>>", ref prev_next, ref next_prev);
1082                         #else
1083                         base (null, ref prev_next, ref next_prev);
1084                         #endif
1085                         this.iter_prev = iter_prev;
1086                         this.iter_next = iter_next;
1087                         prev_next = next_prev = this;
1088                 }
1089
1090                 #if DEBUG
1091                 public override string to_string (int level = 0) {
1092                         StringBuilder builder = new StringBuilder ();
1093                         builder.append (string.nfill (level, '\t'));
1094                         builder.append ("%p<<dummy>>".printf(this));
1095                         return builder.str;
1096                 }
1097                 #endif
1098         }
1099
1100         private class NodePair<G> {
1101                 public weak NodePair<G>? lp_prev = null;
1102                 public NodePair<G>? lp_next = null;
1103                 public Type1Node<G> node1 = null;
1104                 public Type1Node<G> node2 = null;
1105
1106                 public NodePair (Type1Node<G> node1, Type1Node<G> node2) {
1107                         this.node1 = node1;
1108                         this.node2 = node2;
1109                 }
1110         }
1111
1112         private class Iterator<G> : Object, Gee.Iterator<G> {
1113                 private PriorityQueue<G> queue;
1114                 private unowned Node<G>? position;
1115                 private unowned Node<G>? previous;
1116                 private int stamp;
1117
1118                 public Iterator (PriorityQueue<G> queue) {
1119                         this.queue = queue;
1120                         this.position = null;
1121                         this.previous = null;
1122                         this.stamp = queue._stamp;
1123                 }
1124
1125                 public bool next () {
1126                         unowned Node<G>? next = _get_next_node ();
1127                         if (next != null) {
1128                                 previous = position;
1129                                 position = next;
1130                         }
1131                         return next != null;
1132                 }
1133
1134                 public bool has_next () {
1135                         return _get_next_node () != null;
1136                 }
1137
1138                 private inline unowned Node<G>? _get_next_node () {
1139                         if (position != null) {
1140                                 return position.iter_next;
1141                         } else {
1142                                 return (previous != null) ? previous.iter_next : queue._iter_head;
1143                         }
1144                 }
1145
1146                 public bool first () {
1147                         assert (stamp == queue._stamp);
1148                         position = queue._iter_head;
1149                         previous = null;
1150                         return position != null;
1151                 }
1152
1153                 public new G get () {
1154                         assert (stamp == queue._stamp);
1155                         assert (position != null);
1156                         return position.data;
1157                 }
1158
1159                 public void remove () {
1160                         assert (stamp == queue._stamp);
1161                         assert (position != null);
1162                         DummyNode<G> dn;
1163                         if (previous != null) {
1164                                 dn = new DummyNode<G> (ref previous.iter_next, ref position.iter_prev, previous, position);
1165                         } else {
1166                                 dn = new DummyNode<G> (ref queue._iter_head, ref position.iter_prev, null, position);
1167                         }
1168                         queue._delete (position);
1169                         position = null;
1170                         if (previous != null) {
1171                                 previous.iter_next = dn.iter_next;
1172                         }
1173                         if (dn == queue._iter_head) {
1174                                 queue._iter_head = dn.iter_next;
1175                         }
1176                         if (dn.iter_next != null) {
1177                                 dn.iter_next.iter_prev = previous;
1178                         }
1179                         if (dn == queue._iter_tail) {
1180                                 queue._iter_tail = previous;
1181                         }
1182                         stamp++;
1183                         assert (stamp == queue._stamp);
1184                 }
1185         }
1186 }