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 void foreach (ForallFunc<G> f) {
 720                         assert (stamp == _set.stamp);
 721                         if (current != null) {
 722                                 f (current.key);
 723                                 _next = current.next;
 724                         } else if (!started) {
 725                                 _next = _set._first;
 726                         }
 727                         while (_next != null) {
 728                                 current = _next;
 729                                 f (current.key);
 730                                 _next = current.next;
 731                         }
 732                 }
 733
 734                 private weak Node<G>? current = null;
 735                 private weak Node<G>? _next = null;
 736                 private weak Node<G>? _prev = null;
 737                 private bool started = false;
 738         }
 739
 740         private inline G min (G a, G b) {
 741                 return compare_func (a, b) <= 0 ? a : b;
 742         }
 743
 744         private inline G max (G a, G b) {
 745                 return compare_func (a, b) > 0 ? a : b;
 746         }
 747
 748         private class Range<G> {
 749                 public Range (TreeSet<G> set, G after, G before) {
 750                         this.set = set;
 751                         if (set.compare_func (after, before) < 0) {
 752                                 this.after = after;
 753                                 this.before = before;
 754                                 type = RangeType.BOUNDED;
 755                         } else {
 756                                 type = RangeType.EMPTY;
 757                         }
 758                 }
 759
 760                 public Range.head (TreeSet<G> set, G before) {
 761                         this.set = set;
 762                         this.before = before;
 763                         type = RangeType.HEAD;
 764                 }
 765
 766                 public Range.tail (TreeSet<G> set, G after) {
 767                         this.set = set;
 768                         this.after = after;
 769                         type = RangeType.TAIL;
 770                 }
 771
 772 #if false
 773                 public Range.empty (TreeSet<G> set) {
 774                         this.set = set;
 775                         type = RangeType.EMPTY;
 776                 }
 777 #endif
 778
 779                 public Range<G> cut_head (G after) {
 780                         switch (type) {
 781                         case RangeType.HEAD:
 782                                 return new Range<G> (set, after, before);
 783                         case RangeType.TAIL:
 784                                 return new Range<G>.tail (set, set.max (after, this.after));
 785                         case RangeType.EMPTY:
 786                                 return this;
 787                         case RangeType.BOUNDED:
 788                                 var _after = set.max (after, this.after);
 789                                 return new Range<G> (set, _after, before);
 790                         default:
 791                                 assert_not_reached ();
 792                         }
 793                 }
 794
 795                 public Range<G> cut_tail (G before) {
 796                         switch (type) {
 797                         case RangeType.HEAD:
 798                                 return new Range<G>.head (set, set.min (before, this.before));
 799                         case RangeType.TAIL:
 800                                 return new Range<G> (set, after, before);
 801                         case RangeType.EMPTY:
 802                                 return this;
 803                         case RangeType.BOUNDED:
 804                                 var _before = set.min (before, this.before);
 805                                 return new Range<G> (set, after, _before);
 806                         default:
 807                                 assert_not_reached ();
 808                         }
 809                 }
 810
 811                 public Range<G> cut (G after, G before) {
 812                         if (type == RangeType.EMPTY)
 813                                 return this;
 814                         var _before = type != RangeType.TAIL ? set.min (before, this.before) : before;
 815                         var _after = type != RangeType.HEAD ? set.max (after, this.after) : after;
 816                         return new Range<G> (set, _after, _before);
 817                 }
 818
 819                 public bool in_range (G item) {
 820                         return type == RangeType.EMPTY ? false : compare_range (item) == 0;
 821                 }
 822
 823                 public int compare_range (G item) {
 824                         switch (type) {
 825                         case RangeType.HEAD:
 826                                 return set.compare_func (item, before) < 0 ? 0 : 1;
 827                         case RangeType.TAIL:
 828                                 return set.compare_func (item, after) >= 0 ? 0 : -1;
 829                         case RangeType.EMPTY:
 830                                 return 0; // For simplicity - please make sure it does not break anything
 831                         case RangeType.BOUNDED:
 832                                 return set.compare_func (item, after) >= 0 ?
 833                                         (set.compare_func (item, before) < 0 ? 0 : 1) : -1;
 834                         default:
 835                                 assert_not_reached ();
 836                         }
 837                 }
 838
 839                 public bool empty_subset () {
 840                         switch (type) {
 841                         case RangeType.HEAD:
 842                                 return set._first == null || !in_range (set._first.key);
 843                         case RangeType.TAIL:
 844                                 return set._last == null || !in_range (set._last.key);
 845                         case RangeType.EMPTY:
 846                                 return true;
 847                         case RangeType.BOUNDED:
 848                                 return first () == null;
 849                         default:
 850                                 assert_not_reached ();
 851                         }
 852                 }
 853
 854                 public unowned Node<G>? first () {
 855                         switch (type) {
 856                         case RangeType.EMPTY:
 857                                 return null;
 858                         case RangeType.HEAD:
 859                                 return set._first;
 860                         default:
 861                                 return set.find_floor (after);
 862                         }
 863                 }
 864
 865                 public unowned Node<G>? last () {
 866                         switch (type) {
 867                         case RangeType.EMPTY:
 868                                 return null;
 869                         case RangeType.TAIL:
 870                                 return set._last;
 871                         default:
 872                                 return set.find_lower (before);
 873                         }
 874                 }
 875
 876                 private new TreeSet<G> set;
 877                 private G after;
 878                 private G before;
 879                 private RangeType type;
 880         }
 881
 882         private enum RangeType {
 883                 HEAD,
 884                 TAIL,
 885                 EMPTY,
 886                 BOUNDED
 887         }
 888
 889         private class SubSet<G> : AbstractBidirSortedSet<G> {
 890                 public SubSet (TreeSet<G> set, G after, G before) {
 891                         this.set = set;
 892                         this.range = new Range<G> (set, after, before);
 893                 }
 894
 895                 public SubSet.head (TreeSet<G> set, G before) {
 896                         this.set = set;
 897                         this.range = new Range<G>.head (set, before);
 898                 }
 899
 900                 public SubSet.tail (TreeSet<G> set, G after) {
 901                         this.set = set;
 902                         this.range = new Range<G>.tail (set, after);
 903                 }
 904
 905                 public SubSet.from_range (TreeSet<G> set, Range<G> range) {
 906                         this.set = set;
 907                         this.range = range;
 908                 }
 909
 910                 public override int size {
 911                         get {
 912                                 var i = 0;
 913                                 Gee.Iterator<G> iterator = iterator ();
 914                                 while (iterator.next ())
 915                                         i++;
 916                                 return i;
 917                         }
 918                 }
 919
 920                 public override bool read_only {
 921                         get { return true; }
 922                 }
 923
 924                 public bool is_empty {
 925                         get {
 926                                 return range.empty_subset ();
 927                         }
 928                 }
 929
 930                 public override bool contains (G item) {
 931                         return range.in_range (item) && set.contains (item);
 932                 }
 933
 934                 public override bool add (G item) {
 935                         return range.in_range (item) && set.add (item);
 936                 }
 937
 938                 public override bool remove (G item) {
 939                         return range.in_range (item) && set.remove (item);
 940                 }
 941
 942                 public override void clear () {
 943                         var iter = iterator ();
 944                         while (iter.next ()) {
 945                                 iter.remove ();
 946                         }
 947                 }
 948
 949                 public override Gee.Iterator<G> iterator () {
 950                         return new SubIterator<G> (set, range);
 951                 }
 952
 953                 public override BidirIterator<G> bidir_iterator () {
 954                         return new SubIterator<G> (set, range);
 955                 }
 956
 957                 public override G first () {
 958                         weak Node<G>? _first = range.first ();
 959                         assert (_first != null);
 960                         return _first.key;
 961                 }
 962
 963                 public override G last () {
 964                         weak Node<G>? _last = range.last ();
 965                         assert (_last != null);
 966                         return _last.key;
 967                 }
 968
 969                 public override SortedSet<G> head_set (G before) {
 970                         return new SubSet<G>.from_range (set, range.cut_tail (before));
 971                 }
 972
 973                 public override SortedSet<G> tail_set (G after) {
 974                         return new SubSet<G>.from_range (set, range.cut_head (after));
 975                 }
 976
 977                 public override SortedSet<G> sub_set (G after, G before) {
 978                         return new SubSet<G>.from_range (set, range.cut (after, before));
 979                 }
 980
 981                 public override Gee.Iterator<G>? iterator_at (G item) {
 982                         if (!range.in_range (item))
 983                                 return null;
 984                         weak Node<G>? n = set.find_node (item);
 985                         if (n == null)
 986                                 return null;
 987                         return new SubIterator<G>.pointing (set, range, n);
 988                 }
 989
 990                 public override G? lower (G item) {
 991                         var res = range.compare_range (item);
 992                         if (res > 0)
 993                                 return last ();
 994                         var l = set.lower (item);
 995                         return l != null && range.in_range (l) ? l : null;
 996                 }
 997
 998                 public override G? higher (G item) {
 999                         var res = range.compare_range (item);
1000                         if (res < 0)
1001                                 return first ();
1002                         var h = set.higher (item);
1003                         return h != null && range.in_range (h) ? h : null;
1004                 }
1005
1006                 public override G? floor (G item) {
1007                         var res = range.compare_range (item);
1008                         if (res > 0)
1009                                 return last ();
1010                         var l = set.floor (item);
1011                         return l != null && range.in_range (l) ? l : null;
1012                 }
1013
1014                 public override G? ceil (G item) {
1015                         var res = range.compare_range (item);
1016                         if (res < 0)
1017                                 return first ();
1018                         var h = set.ceil (item);
1019                         return h != null && range.in_range (h) ? h : null;
1020                 }
1021
1022                 private new TreeSet<G> set;
1023                 private Range<G> range;
1024         }
1025
1026         private class SubIterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G> {
1027                 public SubIterator (TreeSet<G> set, Range<G> range) {
1028                         this.set = set;
1029                         this.range = range;
1030                 }
1031
1032                 public SubIterator.pointing (TreeSet<G> set, Range<G> range, Node<G> node) {
1033                         this.set = set;
1034                         this.range = range;
1035                         this.iterator = new Iterator<G>.pointing (set, node);
1036                 }
1037
1038                 public bool next () {
1039                         if (iterator != null) {
1040                                 G next;
1041                                 if (iterator.safe_next_get (out next) && range.in_range (next)) {
1042                                         assert (iterator.next ());
1043                                         return true;
1044                                 } else {
1045                                         return false;
1046                                 }
1047                         } else {
1048                                 return first ();
1049                         }
1050                 }
1051
1052                 public bool has_next () {
1053                         if (iterator != null) {
1054                                 G next;
1055                                 return (iterator.safe_next_get (out next) && range.in_range (next));
1056                         } else {
1057                                 return range.first () != null;
1058                         }
1059                 }
1060
1061                 public bool first () {
1062                         weak Node<G>? node = range.first ();
1063                         if (node == null)
1064                                 return false;
1065                         iterator = new Iterator<G>.pointing (set, node);
1066                         return true;
1067                 }
1068
1069                 public bool previous () {
1070                         if (iterator == null)
1071                                 return false;
1072                         G prev;
1073                         if (iterator.safe_previous_get (out prev) && range.in_range (prev)) {
1074                                 assert (iterator.previous ());
1075                                 return true;
1076                         } else {
1077                                 return false;
1078                         }
1079                 }
1080
1081                 public bool has_previous () {
1082                         if (iterator == null)
1083                                 return false;
1084                         G prev;
1085                         return iterator.safe_previous_get (out prev) && range.in_range (prev);
1086                 }
1087
1088                 public bool last () {
1089                         weak Node<G>? node = range.last ();
1090                         if (node == null)
1091                                 return false;
1092                         iterator = new Iterator<G>.pointing (set, node);
1093                         return true;
1094                 }
1095
1096                 public new G get () {
1097                         assert (iterator != null);
1098                         return iterator.get ();
1099                 }
1100
1101                 public void remove () {
1102                         assert (iterator != null);
1103                         iterator.remove ();
1104                 }
1105
1106                 public bool read_only {
1107                         get {
1108                                 return false;
1109                         }
1110                 }
1111
1112                 public bool valid {
1113                         get {
1114                                 return iterator.valid;
1115                         }
1116                 }
1117
1118                 public void foreach(ForallFunc<G> f) {
1119                         if(valid)
1120                                 f(get());
1121                         while(next())
1122                                 f(get());
1123                 }
1124
1125                 private new TreeSet<G> set;
1126                 private Range<G> range;
1127                 private Iterator<G>? iterator = null;
1128         }
1129
1130         private Node<G>? root = null;
1131         private weak Node<G>? _first = null;
1132         private weak Node<G>? _last = null;
1133         private int stamp = 0;
1134 }