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