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