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