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