gee/treemap.vala

   1 /* treemap.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 Map} 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.
  31  *
  32  * @see HashMap
  33  */
  34 public class Gee.TreeMap<K,V> : Gee.AbstractBidirSortedMap<K,V> {
  35         /**
  36          * {@inheritDoc}
  37          */
  38         public override int size {
  39                 get { return _size; }
  40         }
  41
  42         public override bool read_only {
  43                 get { return false; }
  44         }
  45
  46         /**
  47          * {@inheritDoc}
  48          */
  49         public override Set<K> keys {
  50                 owned get {
  51                         var keys = _keys;
  52                         if (_keys == null) {
  53                                 keys = new KeySet<K,V> (this);
  54                                 _keys = keys;
  55                                 keys.add_weak_pointer ((void**) (&_keys));
  56                         }
  57                         return keys;
  58                 }
  59         }
  60
  61         /**
  62          * {@inheritDoc}
  63          */
  64         public override Collection<V> values {
  65                 owned get {
  66                         var values = _values;
  67                         if (_values == null) {
  68                                 values = new ValueCollection<K,V> (this);
  69                                 _values = values;
  70                                 values.add_weak_pointer ((void**) (&_values));
  71                         }
  72                         return values;
  73                 }
  74         }
  75
  76         /**
  77          * {@inheritDoc}
  78          */
  79         public override Set<Map.Entry<K,V>> entries {
  80                 owned get {
  81                         var entries = _entries;
  82                         if (_entries == null) {
  83                                 entries = new EntrySet<K,V> (this);
  84                                 _entries = entries;
  85                                 entries.add_weak_pointer ((void**) (&_entries));
  86                         }
  87                         return entries;
  88                 }
  89         }
  90
  91         /**
  92          * The keys' comparator function.
  93          */
  94         [CCode (notify = false)]
  95         public CompareDataFunc<K> key_compare_func { private set; get; }
  96
  97         /**
  98          * The values' equality testing function.
  99          */
 100         [CCode (notify = false)]
 101         public EqualDataFunc<V> value_equal_func { private set; get; }
 102
 103         private int _size = 0;
 104
 105         private weak SortedSet<K> _keys;
 106         private weak Collection<V> _values;
 107         private weak SortedSet<Map.Entry<K,V>> _entries;
 108
 109         /**
 110          * Constructs a new, empty tree map sorted according to the specified
 111          * comparator function.
 112          *
 113          * If not provided, the functions parameters are requested to the
 114          * {@link Functions} function factory methods.
 115          *
 116          * @param key_compare_func an optional key comparator function
 117          * @param value_equal_func an optional values equality testing function
 118          */
 119         public TreeMap (owned CompareDataFunc<K>? key_compare_func = null, owned EqualDataFunc<V>? value_equal_func = null) {
 120                 if (key_compare_func == null) {
 121                         key_compare_func = Functions.get_compare_func_for (typeof (K));
 122                 }
 123                 if (value_equal_func == null) {
 124                         value_equal_func = Functions.get_equal_func_for (typeof (V));
 125                 }
 126                 this.key_compare_func = key_compare_func;
 127                 this.value_equal_func = value_equal_func;
 128         }
 129
 130         private void rotate_right (ref Node<K, V> root) {
 131                 Node<K,V> pivot = (owned) root.left;
 132                 pivot.color = root.color;
 133                 root.color = Node.Color.RED;
 134                 root.left = (owned) pivot.right;
 135                 pivot.right = (owned) root;
 136                 root = (owned) pivot;
 137         }
 138
 139         private void rotate_left (ref Node<K, V> root) {
 140                 Node<K,V> pivot = (owned) root.right;
 141                 pivot.color = root.color;
 142                 root.color = Node.Color.RED;
 143                 root.right = (owned) pivot.left;
 144                 pivot.left = (owned) root;
 145                 root = (owned) pivot;
 146         }
 147
 148         private bool is_red (Node<K, V>? n) {
 149                 return n != null && n.color == Node.Color.RED;
 150         }
 151
 152         private bool is_black (Node<K, V>? n) {
 153                 return n == null || n.color == Node.Color.BLACK;
 154         }
 155
 156         /**
 157          * {@inheritDoc}
 158          */
 159         public override bool has_key (K key) {
 160                 weak Node<K, V>? cur = root;
 161                 while (cur != null) {
 162                         int res = key_compare_func (key, cur.key);
 163                         if (res == 0) {
 164                                 return true;
 165                         } else if (res < 0) {
 166                                 cur = cur.left;
 167                         } else {
 168                                 cur = cur.right;
 169                         }
 170                 }
 171                 return false;
 172         }
 173
 174         /**
 175          * {@inheritDoc}
 176          */
 177         public override bool has (K key, V value) {
 178                 V? own_value = get (key);
 179                 return (own_value != null && value_equal_func (own_value, value));
 180         }
 181
 182         /**
 183          * {@inheritDoc}
 184          */
 185         public override V? get (K key) {
 186                 weak Node<K, V>? cur = root;
 187                 while (cur != null) {
 188                         int res = key_compare_func (key, cur.key);
 189                         if (res == 0) {
 190                                 return cur.value;
 191                         } else if (res < 0) {
 192                                 cur = cur.left;
 193                         } else {
 194                                 cur = cur.right;
 195                         }
 196                 }
 197                 return null;
 198         }
 199
 200         private bool set_to_node (ref Node<K, V>? node, K key, V value, out V? old_value, Node<K, V>? prev, Node<K, V>? next) {
 201                 if (node == null) {
 202                         old_value = null;
 203                         node = new Node<K,V> (key, value, prev, next);
 204                         if (prev == null) {
 205                                 first = node;
 206                         }
 207                         if (next == null) {
 208                                 last = node;
 209                         }
 210                         _size++;
 211                         return true;
 212                 }
 213
 214                 int cmp = key_compare_func (key, node.key);
 215                 bool changed;
 216                 if (cmp == 0) {
 217                         if (value_equal_func (value, node.value)) {
 218                                 old_value = null;
 219                                 changed = false;
 220                         } else {
 221                                 old_value = (owned) node.value;
 222                                 node.value = value;
 223                                 changed = true;
 224                         }
 225                 } else if (cmp < 0) {
 226                         changed = set_to_node (ref node.left, key, value, out old_value, node.prev, node);
 227                 } else {
 228                         changed = set_to_node (ref node.right, key, value, out old_value, node, node.next);
 229                 }
 230
 231                 fix_up (ref node);
 232                 return changed;
 233         }
 234
 235         /**
 236          * {@inheritDoc}
 237          */
 238         public override void set (K key, V value) {
 239                 V old_value;
 240                 set_to_node (ref root, key, value, out old_value, null, null);
 241                 root.color = Node.Color.BLACK;
 242                 stamp++;
 243         }
 244
 245         private void move_red_left (ref Node<K, V> root) {
 246                 root.flip ();
 247                 if (is_red (root.right.left)) {
 248                         rotate_right (ref root.right);
 249                         rotate_left (ref root);
 250                         root.flip ();
 251                 }
 252         }
 253
 254         private void move_red_right (ref Node<K, V> root) {
 255                 root.flip ();
 256                 if (is_red (root.left.left)) {
 257                         rotate_right (ref root);
 258                         root.flip ();
 259                 }
 260         }
 261
 262         private void fix_removal (ref Node<K,V> node, out K? key = null, out V? value) {
 263                 Node<K,V> n = (owned) node;
 264                 key = (owned) n.key;
 265                 value = (owned) n.value;
 266                 if (n.prev != null) {
 267                         n.prev.next = n.next;
 268                 } else {
 269                         first = n.next;
 270                 }
 271                 if (n.next != null) {
 272                         n.next.prev = n.prev;
 273                 } else {
 274                         last = n.next;
 275                 }
 276                 n.value = null;
 277                 node = null;
 278                 _size--;
 279         }
 280
 281         private void remove_minimal (ref Node<K,V> node, out K key, out V value) {
 282                 if (node.left == null) {
 283                         fix_removal (ref node, out key, out value);
 284                         return;
 285                 }
 286
 287                 if (is_black (node.left) && is_black (node.left.left)) {
 288                         move_red_left (ref node);
 289                 }
 290
 291                 remove_minimal (ref node.left, out key, out value);
 292
 293                 fix_up (ref node);
 294         }
 295
 296         private bool remove_from_node (ref Node<K, V>? node, K key, out V? value, out unowned Node<K, V>? prev = null, out unowned Node<K, V>? next = null) {
 297                 if (node == null) {
 298                         value = null;
 299                         next = null;
 300                         prev = null;
 301                         return false;
 302                 } else if (key_compare_func (key, node.key) < 0) {
 303                         weak Node<K,V> left = node.left;
 304                         if (left == null) {
 305                                 value = null;
 306                                 next = null;
 307                                 prev = null;
 308                                 return false;
 309                         }
 310                         if (node.left != null && is_black (left) && is_black (left.left)) {
 311                                 move_red_left (ref node);
 312                         }
 313                         bool r = remove_from_node (ref node.left, key, out value, out prev, out next);
 314                         fix_up (ref node);
 315                         return r;
 316                 } else {
 317                         if (is_red (node.left)) {
 318                                 rotate_right (ref node);
 319                         }
 320
 321                         weak Node<K,V>? r = node.right;
 322                         if (key_compare_func (key, node.key) == 0 && r == null) {
 323                                 prev = node.prev;
 324                                 next = node.next;
 325                                 fix_removal (ref node, null, out value);
 326                                 return true;
 327                         }
 328                         if (is_black (r) && r != null && is_black (r.left)) {
 329                                 move_red_right (ref node);
 330                         }
 331                         if (key_compare_func (key, node.key) == 0) {
 332                                 value = (owned) node.value;
 333                                 prev = node.prev;
 334                                 next = node;
 335                                 remove_minimal (ref node.right, out node.key, out node.value);
 336                                 fix_up (ref node);
 337                                 return true;
 338                         } else {
 339                                 bool re = remove_from_node (ref node.right, key, out value, out prev, out next);
 340                                 fix_up (ref node);
 341                                 return re;
 342                         }
 343                 }
 344         }
 345
 346         private void fix_up (ref Node<K,V> node) {
 347                 if (is_black (node.left) && is_red (node.right)) {
 348                         rotate_left (ref node);
 349                 }
 350                 if (is_red (node.left) && is_red (node.left.left)) {
 351                         rotate_right (ref node);
 352                 }
 353                 if (is_red (node.left) && is_red (node.right)) {
 354                         node.flip ();
 355                 }
 356         }
 357
 358         /**
 359          * {@inheritDoc}
 360          */
 361         public override bool unset (K key, out V? value = null) {
 362                 bool b = remove_from_node (ref root, key, out value);
 363
 364                 if (root != null) {
 365                         root.color = Node.Color.BLACK;
 366                 }
 367                 stamp++;
 368                 return b;
 369         }
 370
 371         private inline void clear_subtree (owned Node<K,V> node) {
 372                 node.key = null;
 373                 node.value = null;
 374                 if (node.left != null)
 375                         clear_subtree ((owned) node.left);
 376                 if (node.right != null)
 377                         clear_subtree ((owned) node.right);
 378         }
 379
 380         /**
 381          * {@inheritDoc}
 382          */
 383         public override void clear () {
 384                 if (root != null) {
 385                         clear_subtree ((owned) root);
 386                         first = last = null;
 387                 }
 388                 _size = 0;
 389                 stamp++;
 390         }
 391
 392         /**
 393          * {@inheritDoc}
 394          */
 395         public override SortedMap<K,V> head_map (K before) {
 396                 return new SubMap<K,V> (this, new Range<K,V>.head (this, before));
 397         }
 398
 399         /**
 400          * {@inheritDoc}
 401          */
 402         public override SortedMap<K,V> tail_map (K after) {
 403                 return new SubMap<K,V> (this, new Range<K,V>.tail (this, after));
 404         }
 405
 406         /**
 407          * {@inheritDoc}
 408          */
 409         public override SortedMap<K,V> sub_map (K after, K before) {
 410                 return new SubMap<K,V> (this, new Range<K,V> (this, after, before));
 411         }
 412
 413         /**
 414          * {@inheritDoc}
 415          */
 416         public override SortedSet<K> ascending_keys {
 417                 owned get {
 418                         var keys = _keys;
 419                         if (_keys == null) {
 420                                 keys = new KeySet<K,V> (this);
 421                                 _keys = keys;
 422                                 keys.add_weak_pointer (&_keys);
 423                         }
 424                         return keys;
 425                 }
 426         }
 427         /**
 428          * {@inheritDoc}
 429          */
 430         public override SortedSet<Map.Entry<K,V>> ascending_entries {
 431                 owned get {
 432                         var entries = _entries;
 433                         if (_entries == null) {
 434                                 entries = new EntrySet<K,V> (this);
 435                                 _entries = entries;
 436                                 entries.add_weak_pointer (&_entries);
 437                         }
 438                         return entries;
 439                 }
 440         }
 441
 442         /**
 443          * {@inheritDoc}
 444          */
 445         public override Gee.MapIterator<K,V> map_iterator () {
 446                 return new MapIterator<K,V> (this);
 447         }
 448
 449         /**
 450          * {@inheritDoc}
 451          */
 452         public override Gee.BidirMapIterator<K,V> bidir_map_iterator () {
 453                 return new MapIterator<K,V> (this);
 454         }
 455
 456         [Compact]
 457         private class Node<K, V> {
 458                 public enum Color {
 459                         RED,
 460                         BLACK;
 461
 462                         public Color flip () {
 463                                 if (this == RED) {
 464                                         return BLACK;
 465                                 } else {
 466                                         return RED;
 467                                 }
 468                         }
 469                 }
 470
 471                 public Node (owned K key, owned V value, Node<K,V>? prev, Node<K,V>? next) {
 472                         this.key = (owned) key;
 473                         this.value = (owned) value;
 474                         this.color = Color.RED;
 475                         this.prev = prev;
 476                         this.next = next;
 477                         if (prev != null) {
 478                                 prev.next = this;
 479                         }
 480                         if (next != null) {
 481                                 next.prev = this;
 482                         }
 483                 }
 484
 485                 public void flip () {
 486                         color = color.flip ();
 487                         if (left != null) {
 488                                 left.color = left.color.flip ();
 489                         }
 490                         if (right != null) {
 491                                 right.color = right.color.flip ();
 492                         }
 493                 }
 494
 495                 public K key;
 496                 public V value;
 497                 public Color color;
 498                 public Node<K, V>? left;
 499                 public Node<K, V>? right;
 500                 public weak Node<K, V>? prev;
 501                 public weak Node<K, V>? next;
 502                 public unowned Map.Entry<K,V>? entry;
 503         }
 504
 505         private Node<K, V>? root = null;
 506         private weak Node<K, V>? first = null;
 507         private weak Node<K, V>? last = null;
 508         private int stamp = 0;
 509
 510         private inline K min (K a, K b) {
 511                 return key_compare_func (a, b) <= 0 ? a : b;
 512         }
 513
 514         private inline K max (K a, K b) {
 515                 return key_compare_func (a, b) > 0 ? a : b;
 516         }
 517
 518         private inline unowned Node<K,V>? find_node (K key) {
 519                 unowned Node<K,V>? cur = root;
 520                 while (cur != null) {
 521                         int res = key_compare_func (key, cur.key);
 522                         if (res == 0) {
 523                                 return cur;
 524                         } else if (res < 0) {
 525                                 cur = cur.left;
 526                         } else {
 527                                 cur = cur.right;
 528                         }
 529                 }
 530                 return null;
 531         }
 532
 533         private inline unowned Node<K,V>? find_nearest (K key) {
 534                 unowned Node<K,V>? cur = root;
 535                 while (cur != null) {
 536                         int res = key_compare_func (key, cur.key);
 537                         if (res == 0) {
 538                                 return cur;
 539                         } else if (res < 0) {
 540                                 if (cur.left == null)
 541                                         return cur;
 542                                 cur = cur.left;
 543                         } else {
 544                                 if (cur.right == null)
 545                                         return cur;
 546                                 cur = cur.right;
 547                         }
 548                 }
 549                 return null;
 550         }
 551
 552         private class Entry<K,V> : Map.Entry<K,V> {
 553                 private unowned Node<K,V> _node;
 554
 555                 public static Map.Entry<K,V> entry_for<K,V> (Node<K,V> node) {
 556                         Map.Entry<K,V> result = node.entry;
 557                         if (result == null) {
 558                                 result = new Entry<K,V> (node);
 559                                 node.entry = result;
 560                                 result.add_weak_pointer ((void**) (&node.entry));
 561                         }
 562                         return result;
 563                 }
 564
 565                 public Entry (Node<K,V> node) {
 566                         _node = node;
 567                 }
 568
 569                 public override K key { get { return _node.key; } }
 570
 571                 public override V value {
 572                         get { return _node.value; }
 573                         set { _node.value = value; }
 574                 }
 575
 576                 public override bool read_only { get { return false; } }
 577         }
 578
 579         private inline unowned Node<K,V>? find_lower (K key) {
 580                 unowned Node<K,V>? node = find_nearest (key);
 581                 if (node == null)
 582                         return null;
 583                 return key_compare_func (key, node.key) <= 0 ? node.prev : node;
 584         }
 585
 586         private inline unowned Node<K,V>? find_higher (K key) {
 587                 unowned Node<K,V>? node = find_nearest (key);
 588                 if (node == null)
 589                         return null;
 590                 return key_compare_func (key, node.key) >= 0 ? node.next : node;
 591         }
 592
 593         private inline unowned Node<K,V>? find_floor (K key) {
 594                 unowned Node<K,V>? node = find_nearest (key);
 595                 if (node == null)
 596                         return null;
 597                 return key_compare_func (key, node.key) < 0 ? node.prev : node;
 598         }
 599
 600         private inline unowned Node<K,V>? find_ceil (K key) {
 601                 unowned Node<K,V>? node = find_nearest (key);
 602                 if (node == null)
 603                         return null;
 604                 return key_compare_func (key, node.key) > 0 ? node.next : node;
 605         }
 606
 607         private inline K? lift_null_key (Node<K,V>? node) {
 608                 return node != null ? node.key : null;
 609         }
 610
 611         private class Range<K,V> {
 612                 public Range (TreeMap<K,V> map, K after, K before) {
 613                         this.map = map;
 614                         if (map.key_compare_func (after, before) < 0) {
 615                                 this.after = after;
 616                                 this.before = before;
 617                                 type = RangeType.BOUNDED;
 618                         } else {
 619                                 type = RangeType.EMPTY;
 620                         }
 621                 }
 622
 623                 public Range.head (TreeMap<K,V> map, K before) {
 624                         this.map = map;
 625                         this.before = before;
 626                         type = RangeType.HEAD;
 627                 }
 628
 629                 public Range.tail (TreeMap<K,V> map, K after) {
 630                         this.map = map;
 631                         this.after = after;
 632                         type = RangeType.TAIL;
 633                 }
 634
 635                 public Range.empty (TreeMap<K,V> map) {
 636                         this.map = map;
 637                         type = RangeType.EMPTY;
 638                 }
 639
 640                 public Range<K,V> cut_head (K after) {
 641                         switch (type) {
 642                         case RangeType.HEAD:
 643                                 return new Range<K,V> (map, after, before);
 644                         case RangeType.TAIL:
 645                                 return new Range<K,V>.tail (map, map.max (after, this.after));
 646                         case RangeType.EMPTY:
 647                                 return this;
 648                         case RangeType.BOUNDED:
 649                                 var _after = map.max (after, this.after);
 650                                 return new Range<K,V> (map, _after, before);
 651                         default:
 652                                 assert_not_reached ();
 653                         }
 654                 }
 655
 656                 public Range<K,V> cut_tail (K before) {
 657                         switch (type) {
 658                         case RangeType.HEAD:
 659                                 return new Range<K,V>.head (map, map.min (before, this.before));
 660                         case RangeType.TAIL:
 661                                 return new Range<K,V> (map, after, before);
 662                         case RangeType.EMPTY:
 663                                 return this;
 664                         case RangeType.BOUNDED:
 665                                 var _before = map.min (before, this.before);
 666                                 return new Range<K,V> (map, after, _before);
 667                         default:
 668                                 assert_not_reached ();
 669                         }
 670                 }
 671
 672                 public Range<K,V> cut (K after, K before) {
 673                         if (type == RangeType.EMPTY)
 674                                 return this;
 675                         var _before = (type == RangeType.HEAD || type == RangeType.BOUNDED) ?
 676                                 map.min (before, this.before) : before;
 677                         var _after = (type == RangeType.TAIL || type == RangeType.BOUNDED) ?
 678                                 map.max (after, this.after) : after;
 679                         return new Range<K,V> (map, _after, _before);
 680                 }
 681
 682                 public bool in_range (K key) {
 683                         return type == RangeType.EMPTY ? false : compare_range(key) == 0;
 684                 }
 685
 686                 public int compare_range (K key) {
 687                         switch (type) {
 688                         case RangeType.HEAD:
 689                                 return map.key_compare_func (key, before) < 0 ? 0 : 1;
 690                         case RangeType.TAIL:
 691                                 return map.key_compare_func (key, after) >= 0 ? 0 : -1;
 692                         case RangeType.EMPTY:
 693                                 return 0; // For simplicity - please make sure it does not break anything
 694                         case RangeType.BOUNDED:
 695                                 return map.key_compare_func (key, after) >= 0 ?
 696                                         (map.key_compare_func (key, before) < 0 ? 0 : 1) : -1;
 697                         default:
 698                                 assert_not_reached ();
 699                         }
 700                 }
 701
 702                 public bool empty_submap () {
 703                         switch (type) {
 704                         case RangeType.HEAD:
 705                                 return map.first == null || !in_range (map.first.key);
 706                         case RangeType.TAIL:
 707                                 return map.last == null || !in_range (map.last.key);
 708                         case RangeType.EMPTY:
 709                                 return true;
 710                         case RangeType.BOUNDED:
 711                                 return first () == null;
 712                         default:
 713                                 assert_not_reached ();
 714                         }
 715                 }
 716
 717                 public unowned Node<K,V>? first () {
 718                         switch (type) {
 719                         case RangeType.EMPTY:
 720                                 return null;
 721                         case RangeType.HEAD:
 722                                 return map.first;
 723                         default:
 724                                 return map.find_floor (after);
 725                         }
 726                 }
 727
 728                 public unowned Node<K,V>? last () {
 729                         switch (type) {
 730                         case RangeType.EMPTY:
 731                                 return null;
 732                         case RangeType.TAIL:
 733                                 return map.last;
 734                         default:
 735                                 return map.find_lower (before);
 736                         }
 737                 }
 738
 739                 private new TreeMap<K,V> map;
 740                 private K after;
 741                 private K before;
 742                 private RangeType type;
 743         }
 744
 745         private enum RangeType {
 746                 HEAD,
 747                 TAIL,
 748                 EMPTY,
 749                 BOUNDED
 750         }
 751
 752         private class SubMap<K,V> : AbstractBidirSortedMap<K,V> {
 753                 public override int size { get { return keys.size; } }
 754                 public bool is_empty { get { return keys.is_empty; } }
 755
 756                 public SubMap (TreeMap<K,V> map, Range<K,V> range) {
 757                         this.map = map;
 758                         this.range = range;
 759                 }
 760
 761                 private weak SortedSet<K>? _keys;
 762                 public override Set<K> keys {
 763                         owned get {
 764                                 var keys = _keys;
 765                                 if (_keys == null) {
 766                                         keys = new SubKeySet<K,V> (map, range);
 767                                         _keys = keys;
 768                                         keys.add_weak_pointer(&_keys);
 769                                 }
 770                                 return keys;
 771                         }
 772                 }
 773
 774                 private weak Collection<K>? _values;
 775                 public override Collection<V> values {
 776                         owned get {
 777                                 var values = _values;
 778                                 if (_values == null) {
 779                                         values = new SubValueCollection<K,V> (map, range);
 780                                         _values = values;
 781                                         values.add_weak_pointer(&_values);
 782                                 }
 783                                 return values;
 784                         }
 785                 }
 786
 787                 private weak SortedSet<Entry<K,V>>? _entries;
 788                 public override Set<Entry<K,V>> entries {
 789                         owned get {
 790                                 var entries = _entries;
 791                                 if (_entries == null) {
 792                                         entries = new SubEntrySet<K,V> (map, range);
 793                                         _entries = entries;
 794                                         entries.add_weak_pointer(&_entries);
 795                                 }
 796                                 return entries;
 797                         }
 798                 }
 799
 800                 public override bool read_only {
 801                         get {
 802                                 return true;
 803                         }
 804                 }
 805
 806                 public override bool has_key (K key) {
 807                         return range.in_range (key) && map.has_key (key);
 808                 }
 809
 810                 public override bool has (K key, V value) {
 811                         return range.in_range (key) && map.has (key, value);
 812                 }
 813
 814                 public override new V? get (K key) {
 815                         return range.in_range (key) ? map.get (key) : null;
 816                 }
 817
 818                 public override void set (K key, V value) {
 819                         if (range.in_range (key))
 820                                 map.set (key, value);
 821                 }
 822
 823                 public override bool unset (K key, out V? value = null) {
 824                         value = null;
 825                         return range.in_range (key) && map.unset (key, out value);
 826                 }
 827
 828                 public override void clear () {
 829                         for (var iterator = map_iterator (); iterator.next ();)
 830                                 iterator.unset ();
 831                 }
 832
 833                 public override Gee.MapIterator<K,V> map_iterator () {
 834                         return new SubMapIterator<K,V> (map, range);
 835                 }
 836
 837                 public override BidirMapIterator<K,V> bidir_map_iterator () {
 838                         return new SubMapIterator<K,V> (map, range);
 839                 }
 840
 841                 public override SortedMap<K,V> head_map (K before) {
 842                         return new SubMap<K,V> (map, range.cut_tail (before));
 843                 }
 844
 845                 public override SortedMap<K,V> tail_map (K after) {
 846                         return new SubMap<K,V> (map, range.cut_head (after));
 847                 }
 848
 849                 public override SortedMap<K,V> sub_map (K after, K before) {
 850                         return new SubMap<K,V> (map, range.cut (after, before));
 851                 }
 852
 853                 public override SortedSet<K> ascending_keys {
 854                         owned get {
 855                                 var keys = _keys;
 856                                 if (_keys == null) {
 857                                         keys = new SubKeySet<K,V> (map, range);
 858                                         _keys = keys;
 859                                         keys.add_weak_pointer(&_keys);
 860                                 }
 861                                 return keys;
 862                         }
 863                 }
 864
 865                 public override SortedSet<K> ascending_entries {
 866                         owned get {
 867                                 var entries = _entries;
 868                                 if (_entries == null) {
 869                                         entries = new SubEntrySet<K,V> (map, range);
 870                                         _entries = entries;
 871                                         entries.add_weak_pointer(&_entries);
 872                                 }
 873                                 return _entries;
 874                         }
 875                 }
 876
 877                 private TreeMap<K,V> map;
 878                 private Range<K,V> range;
 879         }
 880
 881         private class KeySet<K,V> : AbstractBidirSortedSet<K> {
 882                 private TreeMap<K,V> _map;
 883
 884                 public KeySet (TreeMap<K,V> map) {
 885                         _map = map;
 886                 }
 887
 888                 public override Iterator<K> iterator () {
 889                         return new KeyIterator<K,V> (_map);
 890                 }
 891
 892                 public override int size {
 893                         get { return _map.size; }
 894                 }
 895
 896                 public override bool read_only {
 897                         get { return true; }
 898                 }
 899
 900                 public override bool add (K key) {
 901                         assert_not_reached ();
 902                 }
 903
 904                 public override void clear () {
 905                         assert_not_reached ();
 906                 }
 907
 908                 public override bool remove (K key) {
 909                         assert_not_reached ();
 910                 }
 911
 912                 public override bool contains (K key) {
 913                         return _map.has_key (key);
 914                 }
 915
 916                 public override K first () {
 917                         assert (_map.first != null);
 918                         return _map.first.key;
 919                 }
 920
 921                 public override K last () {
 922                         assert (_map.last != null);
 923                         return _map.last.key;
 924                 }
 925
 926                 public override BidirIterator<K> bidir_iterator () {
 927                         return new KeyIterator<K,V> (_map);
 928                 }
 929
 930                 public override SortedSet<K> head_set (K before) {
 931                         return new SubKeySet<K,V> (_map, new Range<K,V>.head (_map, before));
 932                 }
 933
 934                 public override SortedSet<K> tail_set (K after) {
 935                         return new SubKeySet<K,V> (_map, new Range<K,V>.tail (_map, after));
 936                 }
 937
 938                 public override SortedSet<K> sub_set (K after, K before) {
 939                         return new SubKeySet<K,V> (_map, new Range<K,V> (_map, after, before));
 940                 }
 941
 942                 public override Iterator<K>? iterator_at (K item) {
 943                         weak Node<K,V>? node = _map.find_node (item);
 944                         if (node == null)
 945                                 return null;
 946                         return new KeyIterator<K,V>.pointing (_map, node);
 947                 }
 948
 949                 public override K? lower (K item) {
 950                         return _map.lift_null_key (_map.find_lower (item));
 951                 }
 952
 953                 public override K? higher (K item) {
 954                         return _map.lift_null_key (_map.find_higher (item));
 955                 }
 956
 957                 public override K? floor (K item) {
 958                         return _map.lift_null_key (_map.find_floor (item));
 959                 }
 960
 961                 public override K? ceil (K item) {
 962                         return _map.lift_null_key (_map.find_ceil (item));
 963                 }
 964         }
 965
 966         private class SubKeySet<K,V> : AbstractBidirSortedSet<K> {
 967                 [CCode (notify = false)]
 968                 public TreeMap<K,V> map { private set; get; }
 969                 [CCode (notify = false)]
 970                 public Range<K,V> range { private set; get; }
 971
 972                 public SubKeySet (TreeMap<K,V> map, Range<K,V> range) {
 973                         this.map = map;
 974                         this.range = range;
 975                 }
 976
 977                 public override Iterator<K> iterator () {
 978                         return new SubKeyIterator<K,V> (map, range);
 979                 }
 980
 981                 public override int size {
 982                         get {
 983                                 var i = 0;
 984                                 Gee.Iterator<K> iterator = iterator ();
 985                                 while (iterator.next ())
 986                                         i++;
 987                                 return i;
 988                         }
 989                 }
 990
 991                 public override bool read_only {
 992                         get {
 993                                 return true;
 994                         }
 995                 }
 996
 997                 public bool is_empty { get { return range.empty_submap (); } }
 998
 999                 public override bool add (K key) {
1000                         assert_not_reached ();
1001                 }
1002
1003                 public override void clear () {
1004                         assert_not_reached ();
1005                 }
1006
1007                 public override bool remove (K key) {
1008                         assert_not_reached ();
1009                 }
1010
1011                 public override bool contains (K key) {
1012                         return range.in_range(key) && map.has_key (key);
1013                 }
1014
1015                 public override BidirIterator<K> bidir_iterator () {
1016                         return new SubKeyIterator<K,V> (map, range);
1017                 }
1018
1019                 public override K first () {
1020                         weak Node<K,V>? _first = range.first ();
1021                         assert (_first != null);
1022                         return _first.key;
1023                 }
1024
1025                 public override K last () {
1026                         weak Node<K,V>? _last = range.last ();
1027                         assert (_last != null);
1028                         return _last.key;
1029                 }
1030
1031                 public override SortedSet<K> head_set (K before) {
1032                         return new SubKeySet<K,V> (map, range.cut_tail (before));
1033                 }
1034
1035                 public override SortedSet<K> tail_set (K after) {
1036                         return new SubKeySet<K,V> (map, range.cut_head (after));
1037                 }
1038
1039                 public override SortedSet<K> sub_set (K after, K before) {
1040                         return new SubKeySet<K,V> (map, range.cut (after, before));
1041                 }
1042
1043                 public override Iterator<K>? iterator_at (K key) {
1044                         if (!range.in_range (key))
1045                                 return null;
1046                         weak Node<K,V>? n = map.find_node (key);
1047                         if (n == null)
1048                                 return null;
1049                         return new SubKeyIterator<K,V>.pointing (map, range, n);
1050                 }
1051
1052                 public override K? lower (K key) {
1053                         var res = range.compare_range (key);
1054                         if (res > 0)
1055                                 return last ();
1056                         var l = map.lift_null_key (map.find_lower (key));
1057                         return l != null && range.in_range (l) ? l : null;
1058                 }
1059
1060                 public override K? higher (K key) {
1061                         var res = range.compare_range (key);
1062                         if (res < 0)
1063                                 return first ();
1064                         var h = map.lift_null_key (map.find_higher (key));
1065                         return h != null && range.in_range (h) ? h : null;
1066                 }
1067
1068                 public override K? floor (K key) {
1069                         var res = range.compare_range (key);
1070                         if (res > 0)
1071                                 return last ();
1072                         var l = map.lift_null_key (map.find_floor (key));
1073                         return l != null && range.in_range (l) ? l : null;
1074                 }
1075
1076                 public override K? ceil (K key) {
1077                         var res = range.compare_range (key);
1078                         if (res < 0)
1079                                 return first ();
1080                         var h = map.lift_null_key (map.find_ceil (key));
1081                         return h != null && range.in_range (h) ? h : null;
1082                 }
1083         }
1084
1085         private class ValueCollection<K,V> : AbstractCollection<V> {
1086                 private TreeMap<K,V> _map;
1087
1088                 public ValueCollection (TreeMap<K,V> map) {
1089                         _map = map;
1090                 }
1091
1092                 public override Iterator<V> iterator () {
1093                         return new ValueIterator<K,V> (_map);
1094                 }
1095
1096                 public override int size {
1097                         get { return _map.size; }
1098                 }
1099
1100                 public override bool read_only {
1101                         get { return true; }
1102                 }
1103
1104                 public override bool add (V key) {
1105                         assert_not_reached ();
1106                 }
1107
1108                 public override void clear () {
1109                         assert_not_reached ();
1110                 }
1111
1112                 public override bool remove (V key) {
1113                         assert_not_reached ();
1114                 }
1115
1116                 public override bool contains (V key) {
1117                         Iterator<V> it = iterator ();
1118                         while (it.next ()) {
1119                                 if (_map.value_equal_func (key, it.get ())) {
1120                                         return true;
1121                                 }
1122                         }
1123                         return false;
1124                 }
1125         }
1126
1127         private class SubValueCollection<K,V> : AbstractCollection<V> {
1128                 [CCode (notify = false)]
1129                 public TreeMap<K,V> map { private set; get; }
1130                 [CCode (notify = false)]
1131                 public Range<K,V> range { private set; get; }
1132
1133                 public SubValueCollection (TreeMap<K,V> map, Range<K,V> range) {
1134                         this.map = map;
1135                         this.range = range;
1136                 }
1137
1138                 public override Iterator<V> iterator () {
1139                         return new SubValueIterator<K,V> (map, range);
1140                 }
1141
1142                 public override bool read_only {
1143                         get {
1144                                 return true;
1145                         }
1146                 }
1147
1148                 public override int size {
1149                         get {
1150                                 var i = 0;
1151                                 Gee.Iterator<V> iterator = iterator ();
1152                                 while (iterator.next ())
1153                                         i++;
1154                                 return i;
1155                         }
1156                 }
1157
1158                 public bool is_empty { get { return range.empty_submap (); } }
1159
1160                 public override bool add (V key) {
1161                         assert_not_reached ();
1162                 }
1163
1164                 public override void clear () {
1165                         assert_not_reached ();
1166                 }
1167
1168                 public override bool remove (V key) {
1169                         assert_not_reached ();
1170                 }
1171
1172                 public override bool contains (V key) {
1173                         Iterator<V> it = iterator ();
1174                         while (it.next ()) {
1175                                 if (map.value_equal_func (key, it.get ())) {
1176                                         return true;
1177                                 }
1178                         }
1179                         return false;
1180                 }
1181         }
1182
1183         private class EntrySet<K,V> : AbstractBidirSortedSet<Map.Entry<K, V>> {
1184                 private TreeMap<K,V> _map;
1185
1186                 public EntrySet (TreeMap<K,V> map) {
1187                         _map = map;
1188                 }
1189
1190                 public override Iterator<Map.Entry<K, V>> iterator () {
1191                         return new EntryIterator<K,V> (_map);
1192                 }
1193
1194                 public override int size {
1195                         get { return _map.size; }
1196                 }
1197
1198                 public override bool read_only {
1199                         get { return true; }
1200                 }
1201
1202                 public override bool add (Map.Entry<K, V> entry) {
1203                         assert_not_reached ();
1204                 }
1205
1206                 public override void clear () {
1207                         assert_not_reached ();
1208                 }
1209
1210                 public override bool remove (Map.Entry<K, V> entry) {
1211                         assert_not_reached ();
1212                 }
1213
1214                 public override bool contains (Map.Entry<K, V> entry) {
1215                         return _map.has (entry.key, entry.value);
1216                 }
1217
1218                 public override Map.Entry<K, V>/*?*/ first () {
1219                         assert (_map.first != null);
1220                         return Entry.entry_for<K,V> (_map.first);
1221                 }
1222
1223                 public override Map.Entry<K, V>/*?*/ last () {
1224                         assert (_map.last != null);
1225                         return Entry.entry_for<K,V> (_map.last);
1226                 }
1227
1228                 public override BidirIterator<Map.Entry<K, V>> bidir_iterator () {
1229                         return new EntryIterator<K,V> (_map);
1230                 }
1231
1232                 public override SortedSet<Map.Entry<K, V>> head_set (Map.Entry<K, V> before) {
1233                         return new SubEntrySet<K,V> (_map, new Range<K,V>.head (_map, before.key));
1234                 }
1235
1236                 public override SortedSet<Map.Entry<K, V>> tail_set (Map.Entry<K, V> after) {
1237                         return new SubEntrySet<K,V> (_map, new Range<K,V>.tail (_map, after.key));
1238                 }
1239
1240                 public override SortedSet<K> sub_set (Map.Entry<K, V> after, Map.Entry<K, V> before) {
1241                         return new SubEntrySet<K,V> (_map, new Range<K,V> (_map, after.key, before.key));
1242                 }
1243
1244                 public override Iterator<Map.Entry<K, V>>? iterator_at (Map.Entry<K, V> item) {
1245                         weak Node<K,V>? node = _map.find_node (item.key);
1246                         if (node == null || !_map.value_equal_func (node.value, item.value))
1247                                 return null;
1248                         return new EntryIterator<K,V>.pointing (_map, node);
1249                 }
1250
1251                 public override Map.Entry<K, V>/*?*/ lower (Map.Entry<K, V> item) {
1252                         weak Node<K,V>? l = _map.find_lower (item.key);
1253                         return l != null ? Entry.entry_for<K,V> (l) : null;
1254                 }
1255
1256                 public override Map.Entry<K, V>/*?*/ higher (Map.Entry<K, V> item) {
1257                         weak Node<K,V>? l = _map.find_higher (item.key);
1258                         return l != null ? Entry.entry_for<K,V> (l) : null;
1259                 }
1260
1261                 public override Map.Entry<K, V>/*?*/ floor (Map.Entry<K, V> item) {
1262                         weak Node<K,V>? l = _map.find_floor (item.key);
1263                         return l != null ? Entry.entry_for<K,V> (l) : null;
1264                 }
1265
1266                 public override Map.Entry<K, V>/*?*/ ceil (Map.Entry<K, V> item) {
1267                         weak Node<K,V>? l = _map.find_ceil (item.key);
1268                         return l != null ? Entry.entry_for<K,V> (l) : null;
1269                 }
1270         }
1271
1272         private class SubEntrySet<K,V> : AbstractBidirSortedSet<Map.Entry<K,V>> {
1273                 [CCode (notify = false)]
1274                 public TreeMap<K,V> map { private set; get; }
1275                 [CCode (notify = false)]
1276                 public Range<K,V> range { private set; get; }
1277
1278                 public SubEntrySet (TreeMap<K,V> map, Range<K,V> range) {
1279                         this.map = map;
1280                         this.range = range;
1281                 }
1282
1283                 public override Iterator<Map.Entry<K,V>> iterator () {
1284                         return new SubEntryIterator<K,V> (map, range);
1285                 }
1286
1287                 public override int size {
1288                         get {
1289                                 var i = 0;
1290                                 Gee.Iterator<Map.Entry<K,V>> iterator = iterator ();
1291                                 while (iterator.next ())
1292                                         i++;
1293                                 return i;
1294                         }
1295                 }
1296
1297                 public override bool read_only {
1298                         get {
1299                                 return true;
1300                         }
1301                 }
1302
1303                 public bool is_empty { get { return range.empty_submap (); } }
1304
1305                 public override bool add (Map.Entry<K,V> entry) {
1306                         assert_not_reached ();
1307                 }
1308
1309                 public override void clear () {
1310                         assert_not_reached ();
1311                 }
1312
1313                 public override bool remove (Map.Entry<K,V> entry) {
1314                         assert_not_reached ();
1315                 }
1316
1317                 public override bool contains (Map.Entry<K,V> entry) {
1318                         return range.in_range(entry.key) && map.has (entry.key, entry.value);
1319                 }
1320
1321                 public override BidirIterator<K> bidir_iterator () {
1322                         return new SubEntryIterator<K,V> (map, range);
1323                 }
1324
1325                 public override Map.Entry<K,V> first () {
1326                         weak Node<K,V>? _first = range.first ();
1327                         assert (_first != null);
1328                         return Entry.entry_for<K,V> (_first);
1329                 }
1330
1331                 public override Map.Entry<K,V> last () {
1332                         weak Node<K,V>? _last = range.last ();
1333                         assert (_last != null);
1334                         return Entry.entry_for<K,V> (_last);
1335                 }
1336
1337                 public override SortedSet<K> head_set (Map.Entry<K,V> before) {
1338                         return new SubEntrySet<K,V> (map, range.cut_tail (before.key));
1339                 }
1340
1341                 public override SortedSet<K> tail_set (Map.Entry<K,V> after) {
1342                         return new SubEntrySet<K,V> (map, range.cut_head (after.key));
1343                 }
1344
1345                 public override SortedSet<K> sub_set (Map.Entry<K,V> after, Map.Entry<K,V> before) {
1346                         return new SubEntrySet<K,V> (map, range.cut (after.key, before.key));
1347                 }
1348
1349                 public override Iterator<Map.Entry<K,V>>? iterator_at (Map.Entry<K,V> entry) {
1350                         if (!range.in_range (entry.key))
1351                                 return null;
1352                         weak Node<K,V>? n = map.find_node (entry.key);
1353                         if (n == null || !map.value_equal_func (n.value, entry.value))
1354                                 return null;
1355                         return new SubEntryIterator<K,V>.pointing (map, range, n);
1356                 }
1357
1358                 public override Map.Entry<K,V>/*?*/ lower (Map.Entry<K,V> entry) {
1359                         var res = range.compare_range (entry.key);
1360                         if (res > 0)
1361                                 return last ();
1362                         weak Node<K,V>? l = map.find_lower (entry.key);
1363                         return l != null && range.in_range (l.key) ? Entry.entry_for<K,V> (l) : null;
1364                 }
1365
1366                 public override Map.Entry<K,V>/*?*/ higher (Map.Entry<K,V> entry) {
1367                         var res = range.compare_range (entry.key);
1368                         if (res < 0)
1369                                 return first ();
1370                         weak Node<K,V>? h = map.find_higher (entry.key);
1371                         return h != null && range.in_range (h.key) ? Entry.entry_for<K,V> (h) : null;
1372                 }
1373
1374                 public override Map.Entry<K,V>/*?*/ floor (Map.Entry<K,V> entry) {
1375                         var res = range.compare_range (entry.key);
1376                         if (res > 0)
1377                                 return last ();
1378                         weak Node<K,V>? l = map.find_floor (entry.key);
1379                         return l != null && range.in_range (l.key) ? Entry.entry_for<K,V> (l) : null;
1380                 }
1381
1382                 public override Map.Entry<K,V>/*?*/ ceil (Map.Entry<K,V> entry) {
1383                         var res = range.compare_range (entry.key);
1384                         if (res < 0)
1385                                 return first ();
1386                         weak Node<K,V>? h = map.find_ceil (entry.key);
1387                         return h != null && range.in_range (h.key) ? Entry.entry_for<K,V> (h) : null;
1388                 }
1389         }
1390
1391         private class NodeIterator<K, V> : Object {
1392                 protected TreeMap<K,V> _map;
1393
1394                 // concurrent modification protection
1395                 protected int stamp;
1396
1397                 protected bool started = false;
1398
1399                 internal weak Node<K, V>? current;
1400                 protected weak Node<K, V>? _next;
1401                 protected weak Node<K, V>? _prev;
1402
1403                 public NodeIterator (TreeMap<K,V> map) {
1404                         _map = map;
1405                         this.stamp = _map.stamp;
1406                 }
1407
1408                 public NodeIterator.pointing (TreeMap<K,V> map, Node<K,V> current) {
1409                         _map = map;
1410                         stamp = _map.stamp;
1411                         this.current = current;
1412                 }
1413
1414                 public bool next () {
1415                         assert (stamp == _map.stamp);
1416                         if (current != null) {
1417                                 if (current.next != null) {
1418                                         current = current.next;
1419                                         return true;
1420                                 } else {
1421                                         return false;
1422                                 }
1423                         } else if (_next == null && _prev == null) {
1424                                 current = _map.first;
1425                                 started = true;
1426                                 return current != null;
1427                         } else {
1428                                 current = _next;
1429                                 if (current != null) {
1430                                         _next = null;
1431                                         _prev = null;
1432                                 }
1433                                 return current != null;
1434                         }
1435                 }
1436
1437                 public bool has_next () {
1438                         assert (stamp == _map.stamp);
1439                         return (current == null && _next == null && _prev == null && _map.first != null) ||
1440                                (current == null && _next != null) ||
1441                                (current != null && current.next != null);
1442                 }
1443
1444                 public bool first () {
1445                         assert (stamp == _map.stamp);
1446                         current = _map.first;
1447                         _next = null;
1448                         _prev = null;
1449                         return current != null; // on false it is null anyway
1450                 }
1451
1452                 public bool previous () {
1453                         assert (stamp == _map.stamp);
1454                         if (current != null) {
1455                                 if (current.prev != null) {
1456                                         current = current.prev;
1457                                         return true;
1458                                 } else {
1459                                         return false;
1460                                 }
1461                         } else {
1462                                 if (_prev != null) {
1463                                         current = _prev;
1464                                         _next = null;
1465                                         _prev = null;
1466                                         return true;
1467                                 } else {
1468                                         return false;
1469                                 }
1470                         }
1471                 }
1472
1473                 public bool has_previous () {
1474                         assert (stamp == _map.stamp);
1475                         return (current == null && _prev != null) ||
1476                                (current != null && current.prev != null);
1477                 }
1478
1479                 public bool last () {
1480                         assert (stamp == _map.stamp);
1481                         current = _map.last;
1482                         _next = null;
1483                         _prev = null;
1484                         return current != null; // on false it is null anyway
1485                 }
1486
1487                 public void remove () {
1488                         assert_not_reached ();
1489                 }
1490
1491                 public void unset () {
1492                         assert (stamp == _map.stamp);
1493                         assert (current != null);
1494                         V value;
1495                         bool success = _map.remove_from_node (ref _map.root, current.key, out value, out _prev, out _next);
1496                         assert (success);
1497                         if (_map.root != null)
1498                                 _map.root.color = Node.Color.BLACK;
1499                         current = null;
1500                         stamp++;
1501                         _map.stamp++;
1502                         assert (stamp == _map.stamp);
1503                 }
1504
1505                 public virtual bool read_only {
1506                         get {
1507                                 return true;
1508                         }
1509                 }
1510
1511                 public bool valid {
1512                         get {
1513                                 return current != null;
1514                         }
1515                 }
1516
1517                 internal unowned Node<K,V>? safe_next_get () {
1518                         return (current != null) ? current.next : _next;
1519                 }
1520
1521                 internal unowned Node<K,V>? safe_previous_get () {
1522                         return (current != null) ? current.prev : _prev;
1523                 }
1524         }
1525
1526         private class SubNodeIterator<K,V> : Object {
1527                 public SubNodeIterator (TreeMap<K,V> map, Range<K,V> range) {
1528                         _map = map;
1529                         this.range = range;
1530                 }
1531
1532                 public SubNodeIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
1533                         _map = map;
1534                         this.range = range;
1535                         this.iterator = new NodeIterator<K,V>.pointing (_map, node);
1536                 }
1537
1538                 public bool next () {
1539                         if (iterator != null) {
1540                                 weak Node<K,V>? node= iterator.safe_next_get ();
1541                                 if (node != null && range.in_range (node.key)) {
1542                                         assert (iterator.next ());
1543                                         return true;
1544                                 } else {
1545                                         return false;
1546                                 }
1547                         } else {
1548                                 return first ();
1549                         }
1550                 }
1551
1552                 public bool has_next () {
1553                         if (iterator != null) {
1554                                 weak Node<K,V>? node = iterator.safe_next_get ();
1555                                 return node != null && range.in_range (node.key);
1556                         } else {
1557                                 return range.first () != null;
1558                         }
1559                 }
1560
1561                 public virtual bool first () {
1562                         weak Node<K,V>? node = range.first ();
1563                         if (node == null)
1564                                 return false;
1565                         iterator = iterator_pointing_at (node);
1566                         return true;
1567                 }
1568
1569                 public bool previous () {
1570                         if (iterator == null)
1571                                 return false;
1572                         weak Node<K,V>? node;
1573                         if ((node = iterator.safe_previous_get ()) != null && range.in_range (node.key)) {
1574                                 assert (iterator.previous ());
1575                                 return true;
1576                         } else {
1577                                 return false;
1578                         }
1579                 }
1580
1581                 public bool has_previous () {
1582                         if (iterator == null)
1583                                 return false;
1584                         weak Node<K,V>? node;
1585                         return (node = iterator.safe_previous_get ()) != null && range.in_range (node.key);
1586                 }
1587
1588                 public virtual bool last () {
1589                         weak Node<K,V>? node = range.last ();
1590                         if (node == null)
1591                                 return false;
1592                         iterator = iterator_pointing_at (node);
1593                         return true;
1594                 }
1595
1596                 public void remove () {
1597                         assert (valid);
1598                         iterator.remove ();
1599                 }
1600
1601                 public void unset () {
1602                         assert (valid);
1603                         iterator.unset ();
1604                 }
1605
1606                 public virtual bool read_only {
1607                         get {
1608                                 return true;
1609                         }
1610                 }
1611
1612                 public bool valid {
1613                         get {
1614                                 return iterator != null && iterator.valid;
1615                         }
1616                 }
1617
1618                 protected virtual NodeIterator<K,V> iterator_pointing_at (Node<K,V> node) {
1619                         return new NodeIterator<K,V>.pointing (_map, node);
1620                 }
1621
1622                 protected new TreeMap<K,V> _map;
1623                 protected Range<K,V> range;
1624                 protected NodeIterator<K,V>? iterator = null;
1625         }
1626
1627         private class KeyIterator<K,V> : NodeIterator<K, V>, Traversable<K>, Gee.Iterator<K>, BidirIterator<K> {
1628                 public KeyIterator (TreeMap<K,V> map) {
1629                         base (map);
1630                 }
1631
1632                 public KeyIterator.pointing (TreeMap<K,V> map, Node<K,V> current) {
1633                         base.pointing (map, current);
1634                 }
1635
1636                 public new K get () {
1637                         assert (stamp == _map.stamp);
1638                         assert (current != null);
1639                         return current.key;
1640                 }
1641
1642                 public bool foreach (ForallFunc<K> f) {
1643                         if (current != null) {
1644                                 if (!f (current.key)) {
1645                                         return false;
1646                                 }
1647                                 current = current.next;
1648                         } else if (_next == null) {
1649                                 current = _map.first;
1650                                 started = true;
1651                         } else {
1652                                 current = _next;
1653                                 if (current != null) {
1654                                         _next = null;
1655                                         _prev = null;
1656                                 }
1657                         }
1658                         for (; current != null; current = current.next) {
1659                                 if (!f (current.key)) {
1660                                         return false;
1661                                 }
1662                         }
1663                         return true;
1664                 }
1665         }
1666
1667         private class SubKeyIterator<K,V> : SubNodeIterator<K,V>, Traversable<K>, Gee.Iterator<K>, BidirIterator<K> {
1668                 public SubKeyIterator (TreeMap<K,V> map, Range<K,V> range) {
1669                         base (map, range);
1670                 }
1671
1672                 public SubKeyIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
1673                         base.pointing (map, range, node);
1674                 }
1675
1676                 public new K get () {
1677                         assert (valid);
1678                         return iterator.current.key;
1679                 }
1680
1681                 public bool foreach (ForallFunc<K> f) {
1682                         if (valid) {
1683                                 if (!f (iterator.current.key)) {
1684                                         return false;
1685                                 }
1686                         }
1687                         while (iterator.next ()) {
1688                                 if (!f (iterator.current.key)) {
1689                                         return false;
1690                                 }
1691                         }
1692                         return true;
1693                 }
1694         }
1695
1696         private class ValueIterator<K,V> : NodeIterator<K,V>, Traversable<V>, Gee.Iterator<V>, Gee.BidirIterator<V> {
1697                 public ValueIterator (TreeMap<K,V> map) {
1698                         base (map);
1699                 }
1700
1701                 public ValueIterator.pointing (TreeMap<K,V> map, Node<K,V> current) {
1702                         base.pointing (map, current);
1703                 }
1704
1705                 public new V get () {
1706                         assert (stamp == _map.stamp);
1707                         assert (valid);
1708                         return current.value;
1709                 }
1710
1711                 public bool foreach (ForallFunc<V> f) {
1712                         if (current != null) {
1713                                 if (!f (current.key)) {
1714                                         return false;
1715                                 }
1716                                 current = current.next;
1717                         } else if (_next == null) {
1718                                 current = _map.first;
1719                                 started = true;
1720                         } else {
1721                                 current = _next;
1722                                 if (current != null) {
1723                                         _next = null;
1724                                         _prev = null;
1725                                 }
1726                         }
1727                         for (; current != null; current = current.next) {
1728                                 if (!f (current.key)) {
1729                                         return false;
1730                                 }
1731                         }
1732                         return true;
1733                 }
1734         }
1735
1736         private class SubValueIterator<K,V> : SubNodeIterator<K,V>, Traversable<V>, Gee.Iterator<V>, BidirIterator<V> {
1737                 public SubValueIterator (TreeMap<K,V> map, Range<K,V> range) {
1738                         base (map, range);
1739                 }
1740
1741                 public SubValueIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
1742                         base.pointing (map, range, node);
1743                 }
1744
1745                 public new V get () {
1746                         assert (valid);
1747                         return iterator.current.value;
1748                 }
1749
1750                 public bool foreach (ForallFunc<V> f) {
1751                         if (valid) {
1752                                 if (!f (iterator.current.key)) {
1753                                         return false;
1754                                 }
1755                         }
1756                         while (iterator.next ()) {
1757                                 if (!f (iterator.current.key)) {
1758                                         return false;
1759                                 }
1760                         }
1761                         return true;
1762                 }
1763         }
1764
1765         private class EntryIterator<K,V> : NodeIterator<K,V>, Traversable<Map.Entry<K, V>>, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
1766                 public EntryIterator (TreeMap<K,V> map) {
1767                         base (map);
1768                 }
1769
1770                 public EntryIterator.pointing (TreeMap<K,V> map, Node<K,V> node) {
1771                         base.pointing (map, node);
1772                 }
1773
1774                 public new Map.Entry<K,V> get () {
1775                         assert (stamp == _map.stamp);
1776                         assert (valid);
1777                         return Entry.entry_for<K,V> (current);
1778                 }
1779
1780                 public new void remove () {
1781                         unset ();
1782                 }
1783
1784                 public bool foreach (ForallFunc<Map.Entry<K, V>> f) {
1785                         if (current != null) {
1786                                 if (!f (Entry.entry_for<K,V> (current))) {
1787                                         return false;
1788                                 }
1789                                 current = current.next;
1790                         } else if (_next == null) {
1791                                 current = _map.first;
1792                                 started = true;
1793                         } else {
1794                                 current = _next;
1795                                 if (current != null) {
1796                                         _next = null;
1797                                         _prev = null;
1798                                 }
1799                         }
1800                         for (; current != null; current = current.next) {
1801                                 if (!f (Entry.entry_for<K,V> (current))) {
1802                                         return false;
1803                                 }
1804                         }
1805                         return true;
1806                 }
1807         }
1808
1809         private class SubEntryIterator<K,V> : SubNodeIterator<K,V>, Traversable<Map.Entry<K, V>>, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
1810                 public SubEntryIterator (TreeMap<K,V> map, Range<K,V> range) {
1811                         base (map, range);
1812                 }
1813
1814                 public SubEntryIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
1815                         base.pointing (map, range, node);
1816                 }
1817
1818                 public new Map.Entry<K,V> get () {
1819                         assert (iterator != null);
1820                         return Entry.entry_for<K,V> (iterator.current);
1821                 }
1822
1823                 public new void remove () {
1824                         unset ();
1825                 }
1826
1827                 public bool foreach (ForallFunc<Map.Entry<K, V>> f) {
1828                         if (valid) {
1829                                 if (!f (Entry.entry_for<K,V> (iterator.current))) {
1830                                         return false;
1831                                 }
1832                         }
1833                         while (iterator.next ()) {
1834                                 if (!f (Entry.entry_for<K,V> (iterator.current))) {
1835                                         return false;
1836                                 }
1837                         }
1838                         return true;
1839                 }
1840         }
1841
1842         private class MapIterator<K,V> : NodeIterator<K,V>, Gee.MapIterator<K,V>, BidirMapIterator<K,V> {
1843                 public MapIterator (TreeMap<K,V> map) {
1844                         base (map);
1845                 }
1846
1847                 public K get_key () {
1848                         assert (stamp == _map.stamp);
1849                         assert (valid);
1850                         return current.key;
1851                 }
1852
1853                 public V get_value () {
1854                         assert (stamp == _map.stamp);
1855                         assert (valid);
1856                         return current.value;
1857                 }
1858
1859                 public void set_value (V value) {
1860                         assert (stamp == _map.stamp);
1861                         assert (valid);
1862                         current.value = value;
1863                 }
1864
1865                 public override bool read_only {
1866                         get {
1867                                 return false;
1868                         }
1869                 }
1870
1871                 public bool mutable {
1872                         get {
1873                                 return true;
1874                         }
1875                 }
1876         }
1877
1878         private class SubMapIterator<K,V> : SubNodeIterator<K,V>, Gee.MapIterator<K,V>, BidirMapIterator<K,V> {
1879                 public SubMapIterator (TreeMap<K,V> map, Range<K,V> range) {
1880                         base (map, range);
1881                 }
1882
1883                 public K get_key () {
1884                         assert (valid);
1885                         return iterator.current.key;
1886                 }
1887
1888                 public V get_value () {
1889                         assert (valid);
1890                         return iterator.current.value;
1891                 }
1892
1893                 public void set_value (V value) {
1894                         assert (valid);
1895                         iterator.current.value = value;
1896                 }
1897
1898                 public override bool read_only {
1899                         get {
1900                                 return false;
1901                         }
1902                 }
1903
1904                 public bool mutable {
1905                         get {
1906                                 return true;
1907                         }
1908                 }
1909         }
1910 }