gee/treeset.vala

   1 /* treeset.vala
   2  *
   3  * Copyright (C) 2009-2011  Maciej Piechotka
   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  *      Maciej Piechotka <uzytkownik2@gmail.com>
  21  */
  22
  23 using GLib;
  24
  25 /**
  26  * Left-leaning red-black tree implementation of the {@link Set} interface.
  27  *
  28  * This implementation is especially well designed for large quantity of
  29  * data. The (balanced) tree implementation insure that the set and get
  30  * methods are in logarithmic complexity. For a linear implementation see
  31  * {@link HashSet}.
  32  *
  33  * @see HashSet
  34  */
  35 public class Gee.TreeSet<G> : AbstractBidirSortedSet<G> {
  36         /**
  37          * {@inheritDoc}
  38          */
  39         public override int size {
  40                 get {return _size;}
  41         }
  42
  43         /**
  44          * {@inheritDoc}
  45          */
  46         public override bool read_only {
  47                 get { return false; }
  48         }
  49
  50         /**
  51          * The elements' comparator function.
  52          */
  53         [CCode (notify = false)]
  54         public CompareDataFunc<G> compare_func { private set; get; }
  55
  56         private int _size = 0;
  57
  58         /**
  59          * Constructs a new, empty tree set sorted according to the specified
  60          * comparator function.
  61          *
  62          * If not provided, the function parameter is requested to the
  63          * {@link Functions} function factory methods.
  64          *
  65          * @param compare_func an optional element comparator function
  66          */
  67         public TreeSet (owned CompareDataFunc<G>? compare_func = null) {
  68                 if (compare_func == null) {
  69                         compare_func = Functions.get_compare_func_for (typeof (G));
  70                 }
  71                 this.compare_func = compare_func;
  72         }
  73
  74         /**
  75          * {@inheritDoc}
  76          */
  77         public override bool contains (G item) {
  78                 weak Node<G>? cur = root;
  79                 while (cur != null) {
  80                         int res = compare_func (item, cur.key);
  81                         if (res == 0) {
  82                                 return true;
  83                         } else if (res < 0) {
  84                                 cur = cur.left;
  85                         } else {
  86                                 cur = cur.right;
  87                         }
  88                 }
  89                 return false;
  90         }
  91
  92         private inline void rotate_right (ref Node<G> root) {
  93                 Node<G> pivot = (owned) root.left;
  94                 pivot.color = root.color;
  95                 root.color = Node.Color.RED;
  96                 root.left = (owned) pivot.right;
  97                 pivot.right = (owned) root;
  98                 root = (owned) pivot;
  99 #if DEBUG
 100                 stdout.printf (dump ("after rotate right on %s".printf ((string)root.right.key)));
 101 #endif
 102         }
 103
 104         private inline void rotate_left (ref Node<G> root) {
 105                 Node<G> pivot = (owned) root.right;
 106                 pivot.color = root.color;
 107                 root.color = Node.Color.RED;
 108                 root.right = (owned) pivot.left;
 109                 pivot.left = (owned) root;
 110                 root = (owned) pivot;
 111 #if DEBUG
 112                 stdout.printf (dump ("after rotate left on %s".printf ((string)root.left.key)));
 113 #endif
 114         }
 115
 116         private inline bool is_red (Node<G>? n) {
 117                 return n != null && n.color == Node.Color.RED;
 118         }
 119
 120         private inline bool is_black (Node<G>? n) {
 121                 return n == null || n.color == Node.Color.BLACK;
 122         }
 123
 124         private inline void fix_up (ref Node<G> node) {
 125 #if DEBUG
 126                 var n = (string)node.key;
 127 #endif
 128                 if (is_black (node.left) && is_red (node.right)) {
 129                         rotate_left (ref node);
 130                 }
 131                 if (is_red (node.left) && is_red (node.left.left)) {
 132                         rotate_right (ref node);
 133                 }
 134                 if (is_red (node.left) && is_red (node.right)) {
 135                         node.flip ();
 136                 }
 137 #if DEBUG
 138                 stdout.printf (dump ("after fix up on %s".printf (n)));
 139 #endif
 140         }
 141
 142         private bool add_to_node (ref Node<G>? node, owned G item, Node<G>? prev, Node<G>? next) {
 143 #if DEBUG
 144                 if (node != null)
 145                         stdout.printf ("Adding %s to %s\n".printf ((string) item, (string) node.key));
 146 #endif
 147                 if (node == null) {
 148                         node = new Node<G> ((owned) item, prev, next);
 149                         if (prev == null) {
 150                                 _first = node;
 151                         }
 152                         if (next == null) {
 153                                 _last = node;
 154                         }
 155                         _size++;
 156                         return true;
 157                 }
 158
 159                 int cmp = compare_func (item, node.key);
 160                 if (cmp == 0) {
 161                         fix_up (ref node);
 162                         return false;
 163                 } else if (cmp < 0) {
 164                         bool r = add_to_node (ref node.left, item, node.prev, node);
 165                         fix_up (ref node);
 166                         return r;
 167                 } else {
 168                         bool r = add_to_node (ref node.right, item, node, node.next);
 169                         fix_up (ref node);
 170                         return r;
 171                 }
 172         }
 173
 174         /**
 175          * {@inheritDoc}
 176          *
 177          * If the element already exists in the set it will not be added twice.
 178          */
 179         public override bool add (G item) {
 180 #if CONSISTENCY_CHECKS
 181                 check ();
 182 #endif
 183                 bool r = add_to_node (ref root, item, null, null);
 184                 root.color = Node.Color.BLACK;
 185 #if CONSISTENCY_CHECKS
 186                 check ();
 187 #endif
 188                 stamp++;
 189                 return r;
 190         }
 191
 192         private inline void move_red_left (ref Node<G> root) {
 193 #if DEBUG
 194                 var n = (string)root.key;
 195 #endif
 196                 root.flip ();
 197                 if (is_red (root.right.left)) {
 198                         rotate_right (ref root.right);
 199                         rotate_left (ref root);
 200                         root.flip ();
 201                 }
 202 #if DEBUG
 203                 stdout.printf (dump ("after red left on %s".printf (n)));
 204 #endif
 205         }
 206
 207         private inline void move_red_right (ref Node<G> root) {
 208 #if DEBUG
 209                 var n = (string)root.key;
 210 #endif
 211                 root.flip ();
 212                 if (is_red (root.left.left)) {
 213                         rotate_right (ref root);
 214                         root.flip ();
 215                 }
 216 #if DEBUG
 217                 stdout.printf (dump ("after red right on %s".printf (n)));
 218 #endif
 219         }
 220
 221         private inline void fix_removal (ref Node<G> node, out G? key = null) {
 222                 Node<G> n = (owned)node;
 223                 key = (owned) n.key;
 224                 if (n.prev != null) {
 225                         n.prev.next = n.next;
 226                 } else {
 227                         _first = n.next;
 228                 }
 229                 if (n.next != null) {
 230                         n.next.prev = n.prev;
 231                 } else {
 232                         _last = n.prev;
 233                 }
 234                 node = null;
 235                 _size--;
 236         }
 237
 238         private void remove_minimal (ref Node<G> node, out G key) {
 239                 if (node.left == null) {
 240                         fix_removal (ref node, out key);
 241                         return;
 242                 }
 243
 244                 if (is_black (node.left) && is_black (node.left.left)) {
 245                         move_red_left (ref node);
 246                 }
 247
 248                 remove_minimal (ref node.left, out key);
 249
 250                 fix_up (ref node);
 251         }
 252
 253         private bool remove_from_node (ref Node<G>? node, G item, out unowned Node<G>? prev = null, out unowned Node<G>? next = null) {
 254 #if DEBUG
 255                 stdout.printf ("Removing %s from %s\n", (string)item, node != null ? (string)node.key : null);
 256 #endif
 257                 if (node == null) {
 258                         prev = null;
 259                         next = null;
 260                         return false;
 261                 } else if (compare_func (item, node.key) < 0) {
 262                         weak Node<G> left = node.left;
 263                         if (left == null) {
 264                                 prev = null;
 265                                 next = null;
 266                                 return false;
 267                         }
 268                         if (is_black (left) && is_black (left.left)) {
 269                                 move_red_left (ref node);
 270                         }
 271                         bool r = remove_from_node (ref node.left, item, out prev, out next);
 272                         fix_up (ref node);
 273                         return r;
 274                 } else {
 275                         if (is_red (node.left)) {
 276                                 rotate_right (ref node);
 277                         }
 278
 279                         weak Node<G>? r = node.right;
 280                         if (compare_func (item, node.key) == 0 && r == null) {
 281                                 prev = node.prev;
 282                                 next = node.next;
 283                                 fix_removal (ref node, null);
 284                                 return true;
 285                         }
 286                         if (is_black (r) && r != null && is_black (r.left)) {
 287                                 move_red_right (ref node);
 288                         }
 289                         if (compare_func (item, node.key) == 0) {
 290                                 prev = node.prev;
 291                                 next = node;
 292                                 remove_minimal (ref node.right, out node.key);
 293                                 fix_up (ref node);
 294                                 return true;
 295                         } else {
 296                                 bool re = remove_from_node (ref node.right, item, out prev, out next);
 297                                 fix_up (ref node);
 298                                 return re;
 299                         }
 300                 }
 301         }
 302
 303         /**
 304          * {@inheritDoc}
 305          */
 306         public override bool remove (G item) {
 307 #if CONSISTENCY_CHECKS
 308                 check ();
 309 #endif
 310                 bool b = remove_from_node (ref root, item);
 311                 if (root != null) {
 312                         root.color = Node.Color.BLACK;
 313                 }
 314 #if CONSISTENCY_CHECKS
 315                 check ();
 316 #endif
 317                 stamp++;
 318                 return b;
 319         }
 320
 321         private inline void clear_subtree (owned Node<G> node) {
 322                 node.key = null;
 323                 if (node.left != null)
 324                         clear_subtree ((owned) node.left);
 325                 if (node.right != null)
 326                         clear_subtree ((owned) node.right);
 327         }
 328
 329         /**
 330          * {@inheritDoc}
 331          */
 332         public override void clear () {
 333                 if (root != null) {
 334                         clear_subtree ((owned) root);
 335                         _first = _last = null;
 336                 }
 337                 _size = 0;
 338                 stamp++;
 339         }
 340
 341         /**
 342          * {@inheritDoc}
 343          */
 344         public override Gee.Iterator<G> iterator () {
 345                 return new Iterator<G> (this);
 346         }
 347
 348         /**
 349          * {@inheritDoc}
 350          */
 351         public override BidirIterator<G> bidir_iterator () {
 352                 return new Iterator<G> (this);
 353         }
 354
 355         private inline G? lift_null_get (Node<G>? node) {
 356                 return node != null ? node.key : null;
 357         }
 358
 359         /**
 360          * {@inheritDoc}
 361          */
 362         public override G first () {
 363                 assert (_first != null);
 364                 return _first.key;
 365         }
 366
 367         /**
 368          * {@inheritDoc}
 369          */
 370         public override G last () {
 371                 assert (_last != null);
 372                 return _last.key;
 373         }
 374
 375         /**
 376          * {@inheritDoc}
 377          */
 378         public override SortedSet<G> head_set (G before) {
 379                 return new SubSet<G>.head (this, before);
 380         }
 381
 382         /**
 383          * {@inheritDoc}
 384          */
 385         public override SortedSet<G> tail_set (G after) {
 386                 return new SubSet<G>.tail (this, after);
 387         }
 388
 389         /**
 390          * {@inheritDoc}
 391          */
 392         public override SortedSet<G> sub_set (G after, G before) {
 393                 return new SubSet<G> (this, after, before);
 394         }
 395
 396         private inline unowned Node<G>? find_node (G item) {
 397                 weak Node<G>? cur = root;
 398                 while (cur != null) {
 399                         int res = compare_func (item, cur.key);
 400                         if (res == 0) {
 401                                 return cur;
 402                         } else if (res < 0) {
 403                                 cur = cur.left;
 404                         } else {
 405                                 cur = cur.right;
 406                         }
 407                 }
 408                 return null;
 409         }
 410
 411         /**
 412          * {@inheritDoc}
 413          */
 414         public override Gee.Iterator<G>? iterator_at (G item) {
 415                 weak Node<G>? node = find_node (item);
 416                 return node != null ? new Iterator<G>.pointing (this, node) : null;
 417         }
 418
 419         private inline unowned Node<G>? find_nearest (G item) {
 420                 weak Node<G>? cur = root;
 421                 while (cur != null) {
 422                         int res = compare_func (item, cur.key);
 423                         if (res == 0) {
 424                                 return cur;
 425                         } else if (res < 0) {
 426                                 if (cur.left == null)
 427                                         return cur;
 428                                 cur = cur.left;
 429                         } else {
 430                                 if (cur.right == null)
 431                                         return cur;
 432                                 cur = cur.right;
 433                         }
 434                 }
 435                 return null;
 436         }
 437
 438         private inline unowned Node<G>? find_lower (G item) {
 439                 weak Node<G>? node = find_nearest (item);
 440                 if (node == null)
 441                         return null;
 442                 return compare_func (item, node.key) <= 0 ? node.prev : node;
 443         }
 444
 445         private inline unowned Node<G>? find_higher (G item) {
 446                 weak Node<G>? node = find_nearest (item);
 447                 if (node == null)
 448                         return null;
 449                 return compare_func (item, node.key) >= 0 ? node.next : node;
 450         }
 451
 452         private inline unowned Node<G>? find_floor (G item) {
 453                 weak Node<G>? node = find_nearest (item);
 454                 if (node == null)
 455                         return null;
 456                 return compare_func (item, node.key) < 0 ? node.prev : node;
 457         }
 458
 459         private inline unowned Node<G>? find_ceil (G item) {
 460                 weak Node<G>? node = find_nearest (item);
 461                 if (node == null)
 462                         return null;
 463                 return compare_func (item, node.key) > 0 ? node.next : node;
 464         }
 465
 466         /**
 467          * {@inheritDoc}
 468          */
 469         public override G? lower (G item) {
 470                 return lift_null_get (find_lower (item));
 471         }
 472
 473         /**
 474          * {@inheritDoc}
 475          */
 476         public override G? higher (G item) {
 477                 return lift_null_get (find_higher (item));
 478         }
 479
 480         /**
 481          * {@inheritDoc}
 482          */
 483         public override G? floor (G item) {
 484                 return lift_null_get (find_floor (item));
 485         }
 486
 487         /**
 488          * {@inheritDoc}
 489          */
 490         public override G? ceil (G item) {
 491                 return lift_null_get (find_ceil (item));
 492         }
 493
 494 #if CONSISTENCY_CHECKS
 495         public inline void check () {
 496                 check_subtree (root);
 497                 assert (root == null || root.color == Node.Color.BLACK);
 498 #if DEBUG
 499                 stdout.printf ("%s\n", dump ());
 500 #endif
 501         }
 502
 503         private inline uint check_subtree (Node<G>? node) {
 504                 if (node == null)
 505                         return 0;
 506                 assert (! (is_black (node.left) && is_red (node.right))); // Check left-leaning
 507                 assert (! (is_red (node) && is_red (node.left))); // Check red property
 508                 uint l = check_subtree (node.left);
 509                 uint r = check_subtree (node.right);
 510                 assert (l == r);
 511                 return l + (node.color == Node.Color.BLACK ? 1 : 0);
 512         }
 513 #endif
 514 #if DEBUG
 515         public string dump (string? when = null) {
 516                 return "TreeSet dump%s:\n%s".printf (when == null ? "" : (" " + when), dump_node (root));
 517         }
 518
 519         private inline string dump_node (Node<G>? node, uint depth = 0) {
 520                 if (node != null)
 521                         return dump_node (node.left, depth + 1) +
 522                                "%s%s%p(%s)\033[0m\n".printf (string.nfill (depth, ' '),
 523                                                            node.color == Node.Color.RED ? "\033[0;31m" : "",
 524                                                            node, (string)node.key) +
 525                                dump_node (node.right, depth + 1);
 526                 return "";
 527         }
 528 #endif
 529
 530         [Compact]
 531         private class Node<G> {
 532                 public enum Color {
 533                         RED,
 534                         BLACK;
 535
 536                         public Color flip () {
 537                                 if (this == RED) {
 538                                         return BLACK;
 539                                 } else {
 540                                         return RED;
 541                                 }
 542                         }
 543                 }
 544
 545                 public Node (owned G node, Node<G>? prev, Node<G>? next) {
 546                         this.key = (owned) node;
 547                         this.color = Color.RED;
 548                         this.prev = prev;
 549                         this.next = next;
 550                         if (prev != null) {
 551                                 prev.next = this;
 552                         }
 553                         if (next != null) {
 554                                 next.prev = this;
 555                         }
 556                 }
 557
 558                 public void flip () {
 559                         color = color.flip ();
 560                         if (left != null) {
 561                                 left.color = left.color.flip ();
 562                         }
 563                         if (right != null) {
 564                                 right.color = right.color.flip ();
 565                         }
 566                 }
 567
 568                 public G key;
 569                 public Color color;
 570                 public Node<G>? left;
 571                 public Node<G>? right;
 572                 public weak Node<G>? prev;
 573                 public weak Node<G>? next;
 574         }
 575
 576         private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G> {
 577                 private TreeSet<G> _set;
 578
 579                 // concurrent modification protection
 580                 private int stamp;
 581
 582                 public Iterator (TreeSet<G> set) {
 583                         _set = set;
 584                         stamp = _set.stamp;
 585                 }
 586
 587                 public Iterator.pointing (TreeSet<G> set, Node<G> current) {
 588                         this._set = set;
 589                         this.current = current;
 590                         this.stamp = set.stamp;
 591                         this.started = true;
 592                 }
 593
 594                 public bool next () {
 595                         assert (stamp == _set.stamp);
 596                         if (current != null) {
 597                                 if (current.next != null) {
 598                                         current = current.next;
 599                                         return true;
 600                                 } else {
 601                                         return false;
 602                                 }
 603                         } else if (!started) {
 604                                 current = _set._first;
 605                                 started = true;
 606                                 return current != null;
 607                         } else {
 608                                 current = _next;
 609                                 if (current != null) {
 610                                         _next = null;
 611                                         _prev = null;
 612                                 }
 613                                 return current != null;
 614                         }
 615                 }
 616
 617                 public bool has_next () {
 618                         assert (stamp == _set.stamp);
 619                         return (!started && _set._first != null) ||
 620                                (current == null && _next != null) ||
 621                                (current != null && current.next != null);
 622                 }
 623
 624                 public bool first () {
 625                         assert (stamp == _set.stamp);
 626                         current = _set._first;
 627                         _next = null;
 628                         _prev = null;
 629                         started = true;
 630                         return current != null; // on false it is null anyway
 631                 }
 632
 633                 public bool previous () {
 634                         assert (stamp == _set.stamp);
 635                         if (current != null) {
 636                                 if (current.prev != null) {
 637                                         current = current.prev;
 638                                         return true;
 639                                 } else {
 640                                         return false;
 641                                 }
 642                         } else {
 643                                 if (_prev != null) {
 644                                         current = _prev;
 645                                         _next = null;
 646                                         _prev = null;
 647                                         return true;
 648                                 } else {
 649                                         return false;
 650                                 }
 651                         }
 652                 }
 653
 654                 public bool has_previous () {
 655                         assert (stamp == _set.stamp);
 656                         return (current == null && _prev != null) ||
 657                                (current != null && current.prev != null);
 658                 }
 659
 660                 public bool last () {
 661                         assert (stamp == _set.stamp);
 662                         current = _set._last;
 663                         _next = null;
 664                         _prev = null;
 665                         started = true;
 666                         return current != null; // on false it is null anyway
 667                 }
 668
 669                 public new G get () {
 670                         assert (stamp == _set.stamp);
 671                         assert (current != null);
 672                         return current.key;
 673                 }
 674
 675                 public void remove () {
 676                         assert (stamp == _set.stamp);
 677                         assert (current != null);
 678                         bool success = _set.remove_from_node (ref _set.root, current.key, out _prev, out _next);
 679                         assert (success);
 680                         if (_set.root != null)
 681                                 _set.root.color = Node.Color.BLACK;
 682                         current = null;
 683                         assert (stamp++ == _set.stamp++);
 684                 }
 685
 686                 internal bool safe_next_get (out G val) {
 687                         if (current != null) {
 688                                 val = _set.lift_null_get (current.next);
 689                                 return current.next != null;
 690                         } else {
 691                                 val = _set.lift_null_get (_next);
 692                                 return _next != null;
 693                         }
 694                 }
 695
 696                 internal bool safe_previous_get (out G val) {
 697                         if (current != null) {
 698                                 val = _set.lift_null_get (current.prev);
 699                                 return current.prev != null;
 700                         } else {
 701                                 val = _set.lift_null_get (_prev);
 702                                 return _next != null;
 703                         }
 704                 }
 705
 706                 public bool valid {
 707                         get {
 708                                 assert (stamp == _set.stamp);
 709                                 return current != null;
 710                         }
 711                 }
 712
 713                 public bool read_only {
 714                         get {
 715                                 return false;
 716                         }
 717                 }
 718
 719                 public bool foreach (ForallFunc<G> f) {
 720                         assert (stamp == _set.stamp);
 721                         if (current != null) {
 722                                 if (!f (current.key)) {
 723                                         return false;
 724                                 }
 725                                 _next = current.next;
 726                         } else if (!started) {
 727                                 _next = _set._first;
 728                         }
 729                         while (_next != null) {
 730                                 current = _next;
 731                                 if (!f (current.key)) {
 732                                         return false;
 733                                 }
 734                                 _next = current.next;
 735                         }
 736                         return true;
 737                 }
 738
 739                 private weak Node<G>? current = null;
 740                 private weak Node<G>? _next = null;
 741                 private weak Node<G>? _prev = null;
 742                 private bool started = false;
 743         }
 744
 745         private inline G min (G a, G b) {
 746                 return compare_func (a, b) <= 0 ? a : b;
 747         }
 748
 749         private inline G max (G a, G b) {
 750                 return compare_func (a, b) > 0 ? a : b;
 751         }
 752
 753         private class Range<G> {
 754                 public Range (TreeSet<G> set, G after, G before) {
 755                         this.set = set;
 756                         if (set.compare_func (after, before) < 0) {
 757                                 this.after = after;
 758                                 this.before = before;
 759                                 type = RangeType.BOUNDED;
 760                         } else {
 761                                 type = RangeType.EMPTY;
 762                         }
 763                 }
 764
 765                 public Range.head (TreeSet<G> set, G before) {
 766                         this.set = set;
 767                         this.before = before;
 768                         type = RangeType.HEAD;
 769                 }
 770
 771                 public Range.tail (TreeSet<G> set, G after) {
 772                         this.set = set;
 773                         this.after = after;
 774                         type = RangeType.TAIL;
 775                 }
 776
 777 #if false
 778                 public Range.empty (TreeSet<G> set) {
 779                         this.set = set;
 780                         type = RangeType.EMPTY;
 781                 }
 782 #endif
 783
 784                 public Range<G> cut_head (G after) {
 785                         switch (type) {
 786                         case RangeType.HEAD:
 787                                 return new Range<G> (set, after, before);
 788                         case RangeType.TAIL:
 789                                 return new Range<G>.tail (set, set.max (after, this.after));
 790                         case RangeType.EMPTY:
 791                                 return this;
 792                         case RangeType.BOUNDED:
 793                                 var _after = set.max (after, this.after);
 794                                 return new Range<G> (set, _after, before);
 795                         default:
 796                                 assert_not_reached ();
 797                         }
 798                 }
 799
 800                 public Range<G> cut_tail (G before) {
 801                         switch (type) {
 802                         case RangeType.HEAD:
 803                                 return new Range<G>.head (set, set.min (before, this.before));
 804                         case RangeType.TAIL:
 805                                 return new Range<G> (set, after, before);
 806                         case RangeType.EMPTY:
 807                                 return this;
 808                         case RangeType.BOUNDED:
 809                                 var _before = set.min (before, this.before);
 810                                 return new Range<G> (set, after, _before);
 811                         default:
 812                                 assert_not_reached ();
 813                         }
 814                 }
 815
 816                 public Range<G> cut (G after, G before) {
 817                         if (type == RangeType.EMPTY)
 818                                 return this;
 819                         var _before = type != RangeType.TAIL ? set.min (before, this.before) : before;
 820                         var _after = type != RangeType.HEAD ? set.max (after, this.after) : after;
 821                         return new Range<G> (set, _after, _before);
 822                 }
 823
 824                 public bool in_range (G item) {
 825                         return type == RangeType.EMPTY ? false : compare_range (item) == 0;
 826                 }
 827
 828                 public int compare_range (G item) {
 829                         switch (type) {
 830                         case RangeType.HEAD:
 831                                 return set.compare_func (item, before) < 0 ? 0 : 1;
 832                         case RangeType.TAIL:
 833                                 return set.compare_func (item, after) >= 0 ? 0 : -1;
 834                         case RangeType.EMPTY:
 835                                 return 0; // For simplicity - please make sure it does not break anything
 836                         case RangeType.BOUNDED:
 837                                 return set.compare_func (item, after) >= 0 ?
 838                                         (set.compare_func (item, before) < 0 ? 0 : 1) : -1;
 839                         default:
 840                                 assert_not_reached ();
 841                         }
 842                 }
 843
 844                 public bool empty_subset () {
 845                         switch (type) {
 846                         case RangeType.HEAD:
 847                                 return set._first == null || !in_range (set._first.key);
 848                         case RangeType.TAIL:
 849                                 return set._last == null || !in_range (set._last.key);
 850                         case RangeType.EMPTY:
 851                                 return true;
 852                         case RangeType.BOUNDED:
 853                                 return first () == null;
 854                         default:
 855                                 assert_not_reached ();
 856                         }
 857                 }
 858
 859                 public unowned Node<G>? first () {
 860                         switch (type) {
 861                         case RangeType.EMPTY:
 862                                 return null;
 863                         case RangeType.HEAD:
 864                                 return set._first;
 865                         default:
 866                                 return set.find_floor (after);
 867                         }
 868                 }
 869
 870                 public unowned Node<G>? last () {
 871                         switch (type) {
 872                         case RangeType.EMPTY:
 873                                 return null;
 874                         case RangeType.TAIL:
 875                                 return set._last;
 876                         default:
 877                                 return set.find_lower (before);
 878                         }
 879                 }
 880
 881                 private new TreeSet<G> set;
 882                 private G after;
 883                 private G before;
 884                 private RangeType type;
 885         }
 886
 887         private enum RangeType {
 888                 HEAD,
 889                 TAIL,
 890                 EMPTY,
 891                 BOUNDED
 892         }
 893
 894         private class SubSet<G> : AbstractBidirSortedSet<G> {
 895                 public SubSet (TreeSet<G> set, G after, G before) {
 896                         this.set = set;
 897                         this.range = new Range<G> (set, after, before);
 898                 }
 899
 900                 public SubSet.head (TreeSet<G> set, G before) {
 901                         this.set = set;
 902                         this.range = new Range<G>.head (set, before);
 903                 }
 904
 905                 public SubSet.tail (TreeSet<G> set, G after) {
 906                         this.set = set;
 907                         this.range = new Range<G>.tail (set, after);
 908                 }
 909
 910                 public SubSet.from_range (TreeSet<G> set, Range<G> range) {
 911                         this.set = set;
 912                         this.range = range;
 913                 }
 914
 915                 public override int size {
 916                         get {
 917                                 var i = 0;
 918                                 Gee.Iterator<G> iterator = iterator ();
 919                                 while (iterator.next ())
 920                                         i++;
 921                                 return i;
 922                         }
 923                 }
 924
 925                 public override bool read_only {
 926                         get { return true; }
 927                 }
 928
 929                 public bool is_empty {
 930                         get {
 931                                 return range.empty_subset ();
 932                         }
 933                 }
 934
 935                 public override bool contains (G item) {
 936                         return range.in_range (item) && set.contains (item);
 937                 }
 938
 939                 public override bool add (G item) {
 940                         return range.in_range (item) && set.add (item);
 941                 }
 942
 943                 public override bool remove (G item) {
 944                         return range.in_range (item) && set.remove (item);
 945                 }
 946
 947                 public override void clear () {
 948                         var iter = iterator ();
 949                         while (iter.next ()) {
 950                                 iter.remove ();
 951                         }
 952                 }
 953
 954                 public override Gee.Iterator<G> iterator () {
 955                         return new SubIterator<G> (set, range);
 956                 }
 957
 958                 public override BidirIterator<G> bidir_iterator () {
 959                         return new SubIterator<G> (set, range);
 960                 }
 961
 962                 public override G first () {
 963                         weak Node<G>? _first = range.first ();
 964                         assert (_first != null);
 965                         return _first.key;
 966                 }
 967
 968                 public override G last () {
 969                         weak Node<G>? _last = range.last ();
 970                         assert (_last != null);
 971                         return _last.key;
 972                 }
 973
 974                 public override SortedSet<G> head_set (G before) {
 975                         return new SubSet<G>.from_range (set, range.cut_tail (before));
 976                 }
 977
 978                 public override SortedSet<G> tail_set (G after) {
 979                         return new SubSet<G>.from_range (set, range.cut_head (after));
 980                 }
 981
 982                 public override SortedSet<G> sub_set (G after, G before) {
 983                         return new SubSet<G>.from_range (set, range.cut (after, before));
 984                 }
 985
 986                 public override Gee.Iterator<G>? iterator_at (G item) {
 987                         if (!range.in_range (item))
 988                                 return null;
 989                         weak Node<G>? n = set.find_node (item);
 990                         if (n == null)
 991                                 return null;
 992                         return new SubIterator<G>.pointing (set, range, n);
 993                 }
 994
 995                 public override G? lower (G item) {
 996                         var res = range.compare_range (item);
 997                         if (res > 0)
 998                                 return last ();
 999                         var l = set.lower (item);
1000                         return l != null && range.in_range (l) ? l : null;
1001                 }
1002
1003                 public override G? higher (G item) {
1004                         var res = range.compare_range (item);
1005                         if (res < 0)
1006                                 return first ();
1007                         var h = set.higher (item);
1008                         return h != null && range.in_range (h) ? h : null;
1009                 }
1010
1011                 public override G? floor (G item) {
1012                         var res = range.compare_range (item);
1013                         if (res > 0)
1014                                 return last ();
1015                         var l = set.floor (item);
1016                         return l != null && range.in_range (l) ? l : null;
1017                 }
1018
1019                 public override G? ceil (G item) {
1020                         var res = range.compare_range (item);
1021                         if (res < 0)
1022                                 return first ();
1023                         var h = set.ceil (item);
1024                         return h != null && range.in_range (h) ? h : null;
1025                 }
1026
1027                 private new TreeSet<G> set;
1028                 private Range<G> range;
1029         }
1030
1031         private class SubIterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G> {
1032                 public SubIterator (TreeSet<G> set, Range<G> range) {
1033                         this.set = set;
1034                         this.range = range;
1035                 }
1036
1037                 public SubIterator.pointing (TreeSet<G> set, Range<G> range, Node<G> node) {
1038                         this.set = set;
1039                         this.range = range;
1040                         this.iterator = new Iterator<G>.pointing (set, node);
1041                 }
1042
1043                 public bool next () {
1044                         if (iterator != null) {
1045                                 G next;
1046                                 if (iterator.safe_next_get (out next) && range.in_range (next)) {
1047                                         assert (iterator.next ());
1048                                         return true;
1049                                 } else {
1050                                         return false;
1051                                 }
1052                         } else {
1053                                 return first ();
1054                         }
1055                 }
1056
1057                 public bool has_next () {
1058                         if (iterator != null) {
1059                                 G next;
1060                                 return (iterator.safe_next_get (out next) && range.in_range (next));
1061                         } else {
1062                                 return range.first () != null;
1063                         }
1064                 }
1065
1066                 public bool first () {
1067                         weak Node<G>? node = range.first ();
1068                         if (node == null)
1069                                 return false;
1070                         iterator = new Iterator<G>.pointing (set, node);
1071                         return true;
1072                 }
1073
1074                 public bool previous () {
1075                         if (iterator == null)
1076                                 return false;
1077                         G prev;
1078                         if (iterator.safe_previous_get (out prev) && range.in_range (prev)) {
1079                                 assert (iterator.previous ());
1080                                 return true;
1081                         } else {
1082                                 return false;
1083                         }
1084                 }
1085
1086                 public bool has_previous () {
1087                         if (iterator == null)
1088                                 return false;
1089                         G prev;
1090                         return iterator.safe_previous_get (out prev) && range.in_range (prev);
1091                 }
1092
1093                 public bool last () {
1094                         weak Node<G>? node = range.last ();
1095                         if (node == null)
1096                                 return false;
1097                         iterator = new Iterator<G>.pointing (set, node);
1098                         return true;
1099                 }
1100
1101                 public new G get () {
1102                         assert (iterator != null);
1103                         return iterator.get ();
1104                 }
1105
1106                 public void remove () {
1107                         assert (iterator != null);
1108                         iterator.remove ();
1109                 }
1110
1111                 public bool read_only {
1112                         get {
1113                                 return false;
1114                         }
1115                 }
1116
1117                 public bool valid {
1118                         get {
1119                                 return iterator.valid;
1120                         }
1121                 }
1122
1123                 public bool foreach(ForallFunc<G> f) {
1124                         if(valid) {
1125                                 if (!f(get())) {
1126                                         return false;
1127                                 }
1128                         }
1129                         while(next()) {
1130                                 if (!f(get())) {
1131                                         return false;
1132                                 }
1133                         }
1134                         return true;
1135                 }
1136
1137                 private new TreeSet<G> set;
1138                 private Range<G> range;
1139                 private Iterator<G>? iterator = null;
1140         }
1141
1142         private Node<G>? root = null;
1143         private weak Node<G>? _first = null;
1144         private weak Node<G>? _last = null;
1145         private int stamp = 0;
1146 }