gee/priorityqueue.vala

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