3 * Copyright (C) 2009-2011 Maciej Piechotka
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.
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.
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
20 * Maciej Piechotka <uzytkownik2@gmail.com>
26 * Left-leaning red-black tree implementation of the {@link Map} interface.
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.
34 public class Gee.TreeMap<K,V> : Gee.AbstractBidirSortedMap<K,V> {
38 public override int size {
42 public override bool read_only {
49 public override Set<K> keys {
53 keys = new KeySet<K,V> (this);
55 keys.add_weak_pointer ((void**) (&_keys));
64 public override Collection<V> values {
67 if (_values == null) {
68 values = new ValueCollection<K,V> (this);
70 values.add_weak_pointer ((void**) (&_values));
79 public override Set<Map.Entry<K,V>> entries {
81 var entries = _entries;
82 if (_entries == null) {
83 entries = new EntrySet<K,V> (this);
85 entries.add_weak_pointer ((void**) (&_entries));
92 * The keys' comparator function.
94 [CCode (notify = false)]
95 public CompareDataFunc<K> key_compare_func { private set; get; }
98 * The values' equality testing function.
100 [CCode (notify = false)]
101 public EqualDataFunc<V> value_equal_func { private set; get; }
103 private int _size = 0;
105 private weak SortedSet<K> _keys;
106 private weak Collection<V> _values;
107 private weak SortedSet<Map.Entry<K,V>> _entries;
110 * Constructs a new, empty tree map sorted according to the specified
111 * comparator function.
113 * If not provided, the functions parameters are requested to the
114 * {@link Functions} function factory methods.
116 * @param key_compare_func an optional key comparator function
117 * @param value_equal_func an optional values equality testing function
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));
123 if (value_equal_func == null) {
124 value_equal_func = Functions.get_equal_func_for (typeof (V));
126 this.key_compare_func = key_compare_func;
127 this.value_equal_func = value_equal_func;
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;
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;
152 private bool is_red (Node<K, V>? n) {
153 return n != null && n.color == Node.Color.RED;
156 private bool is_black (Node<K, V>? n) {
157 return n == null || n.color == Node.Color.BLACK;
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);
169 } else if (res < 0) {
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));
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);
195 } else if (res < 0) {
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) {
207 node = new Node<K,V> (key, value, prev, next);
218 int cmp = key_compare_func (key, node.key);
221 if (value_equal_func (value, node.value)) {
225 old_value = (owned) node.value;
229 } else if (cmp < 0) {
230 changed = set_to_node (ref node.left, key, value, out old_value, node.prev, node);
232 changed = set_to_node (ref node.right, key, value, out old_value, node, node.next);
242 public override void set (K key, V value) {
244 set_to_node (ref root, key, value, out old_value, null, null);
245 root.color = Node.Color.BLACK;
249 private void move_red_left (ref Node<K, V> root) {
251 if (is_red (root.right.left)) {
252 rotate_right (ref root.right);
253 rotate_left (ref root);
258 private void move_red_right (ref Node<K, V> root) {
260 if (is_red (root.left.left)) {
261 rotate_right (ref root);
266 private void fix_removal (ref Node<K,V> node, out K? key = null, out V? value) {
267 Node<K,V> n = (owned) node;
269 value = (owned) n.value;
270 if (n.prev != null) {
271 n.prev.next = n.next;
275 if (n.next != null) {
276 n.next.prev = n.prev;
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);
291 if (is_black (node.left) && is_black (node.left.left)) {
292 move_red_left (ref node);
295 remove_minimal (ref node.left, out key, out value);
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) {
306 } else if (key_compare_func (key, node.key) < 0) {
307 weak Node<K,V> left = node.left;
314 if (node.left != null && is_black (left) && is_black (left.left)) {
315 move_red_left (ref node);
317 bool r = remove_from_node (ref node.left, key, out value, out prev, out next);
321 if (is_red (node.left)) {
322 rotate_right (ref node);
325 weak Node<K,V>? r = node.right;
326 if (key_compare_func (key, node.key) == 0 && r == null) {
329 fix_removal (ref node, null, out value);
332 if (is_black (r) && r != null && is_black (r.left)) {
333 move_red_right (ref node);
335 if (key_compare_func (key, node.key) == 0) {
336 value = (owned) node.value;
339 remove_minimal (ref node.right, out node.key, out node.value);
343 bool re = remove_from_node (ref node.right, key, out value, out prev, out next);
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);
354 if (is_red (node.left) && is_red (node.left.left)) {
355 rotate_right (ref node);
357 if (is_red (node.left) && is_red (node.right)) {
365 public override bool unset (K key, out V? value = null) {
366 bool b = remove_from_node (ref root, key, out value);
369 root.color = Node.Color.BLACK;
375 private inline void clear_subtree (owned Node<K,V> node) {
378 if (node.left != null)
379 clear_subtree ((owned) node.left);
380 if (node.right != null)
381 clear_subtree ((owned) node.right);
387 public override void clear () {
389 clear_subtree ((owned) root);
399 public override SortedMap<K,V> head_map (K before) {
400 return new SubMap<K,V> (this, new Range<K,V>.head (this, before));
406 public override SortedMap<K,V> tail_map (K after) {
407 return new SubMap<K,V> (this, new Range<K,V>.tail (this, after));
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));
420 public override SortedSet<K> ascending_keys {
424 keys = new KeySet<K,V> (this);
426 keys.add_weak_pointer (&_keys);
434 public override SortedSet<Map.Entry<K,V>> ascending_entries {
436 var entries = _entries;
437 if (_entries == null) {
438 entries = new EntrySet<K,V> (this);
440 entries.add_weak_pointer (&_entries);
449 public override Gee.MapIterator<K,V> map_iterator () {
450 return new MapIterator<K,V> (this);
456 public override Gee.BidirMapIterator<K,V> bidir_map_iterator () {
457 return new MapIterator<K,V> (this);
461 private class Node<K, V> {
466 public Color flip () {
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;
489 public void flip () {
490 color = color.flip ();
492 left.color = left.color.flip ();
495 right.color = right.color.flip ();
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;
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;
514 private inline K min (K a, K b) {
515 return key_compare_func (a, b) <= 0 ? a : b;
518 private inline K max (K a, K b) {
519 return key_compare_func (a, b) > 0 ? a : b;
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);
528 } else if (res < 0) {
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);
543 } else if (res < 0) {
544 if (cur.left == null)
548 if (cur.right == null)
556 private class Entry<K,V> : Map.Entry<K,V> {
557 private unowned Node<K,V> _node;
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);
564 result.add_weak_pointer ((void**) (&node.entry));
569 public Entry (Node<K,V> node) {
573 public override K key { get { return _node.key; } }
575 public override V value {
576 get { return _node.value; }
577 set { _node.value = value; }
580 public override bool read_only { get { return false; } }
583 private inline unowned Node<K,V>? find_lower (K key) {
584 unowned Node<K,V>? node = find_nearest (key);
587 return key_compare_func (key, node.key) <= 0 ? node.prev : node;
590 private inline unowned Node<K,V>? find_higher (K key) {
591 unowned Node<K,V>? node = find_nearest (key);
594 return key_compare_func (key, node.key) >= 0 ? node.next : node;
597 private inline unowned Node<K,V>? find_floor (K key) {
598 unowned Node<K,V>? node = find_nearest (key);
601 return key_compare_func (key, node.key) < 0 ? node.prev : node;
604 private inline unowned Node<K,V>? find_ceil (K key) {
605 unowned Node<K,V>? node = find_nearest (key);
608 return key_compare_func (key, node.key) > 0 ? node.next : node;
611 private inline K? lift_null_key (Node<K,V>? node) {
612 return node != null ? node.key : null;
615 private class Range<K,V> {
616 public Range (TreeMap<K,V> map, K after, K before) {
618 if (map.key_compare_func (after, before) < 0) {
620 this.before = before;
621 type = RangeType.BOUNDED;
623 type = RangeType.EMPTY;
627 public Range.head (TreeMap<K,V> map, K before) {
629 this.before = before;
630 type = RangeType.HEAD;
633 public Range.tail (TreeMap<K,V> map, K after) {
636 type = RangeType.TAIL;
639 public Range.empty (TreeMap<K,V> map) {
641 type = RangeType.EMPTY;
644 public Range<K,V> cut_head (K after) {
647 return new Range<K,V> (map, after, before);
649 return new Range<K,V>.tail (map, map.max (after, this.after));
650 case RangeType.EMPTY:
652 case RangeType.BOUNDED:
653 var _after = map.max (after, this.after);
654 return new Range<K,V> (map, _after, before);
656 assert_not_reached ();
660 public Range<K,V> cut_tail (K before) {
663 return new Range<K,V>.head (map, map.min (before, this.before));
665 return new Range<K,V> (map, after, before);
666 case RangeType.EMPTY:
668 case RangeType.BOUNDED:
669 var _before = map.min (before, this.before);
670 return new Range<K,V> (map, after, _before);
672 assert_not_reached ();
676 public Range<K,V> cut (K after, K before) {
677 if (type == RangeType.EMPTY)
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);
686 public bool in_range (K key) {
687 return type == RangeType.EMPTY ? false : compare_range(key) == 0;
690 public int compare_range (K key) {
693 return map.key_compare_func (key, before) < 0 ? 0 : 1;
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;
702 assert_not_reached ();
706 public bool empty_submap () {
709 return map.first == null || !in_range (map.first.key);
711 return map.last == null || !in_range (map.last.key);
712 case RangeType.EMPTY:
714 case RangeType.BOUNDED:
715 return first () == null;
717 assert_not_reached ();
721 public unowned Node<K,V>? first () {
723 case RangeType.EMPTY:
728 return map.find_floor (after);
732 public unowned Node<K,V>? last () {
734 case RangeType.EMPTY:
739 return map.find_lower (before);
743 private new TreeMap<K,V> map;
746 private RangeType type;
749 private enum RangeType {
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; } }
760 public SubMap (TreeMap<K,V> map, Range<K,V> range) {
765 private weak SortedSet<K>? _keys;
766 public override Set<K> keys {
770 keys = new SubKeySet<K,V> (map, range);
772 keys.add_weak_pointer(&_keys);
778 private weak Collection<K>? _values;
779 public override Collection<V> values {
781 var values = _values;
782 if (_values == null) {
783 values = new SubValueCollection<K,V> (map, range);
785 values.add_weak_pointer(&_values);
791 private weak SortedSet<Entry<K,V>>? _entries;
792 public override Set<Entry<K,V>> entries {
794 var entries = _entries;
795 if (_entries == null) {
796 entries = new SubEntrySet<K,V> (map, range);
798 entries.add_weak_pointer(&_entries);
804 public override bool read_only {
810 public override bool has_key (K key) {
811 return range.in_range (key) && map.has_key (key);
814 public override bool has (K key, V value) {
815 return range.in_range (key) && map.has (key, value);
818 public override new V? get (K key) {
819 return range.in_range (key) ? map.get (key) : null;
822 public override void set (K key, V value) {
823 if (range.in_range (key))
824 map.set (key, value);
827 public override bool unset (K key, out V? value = null) {
829 return range.in_range (key) && map.unset (key, out value);
832 public override void clear () {
833 for (var iterator = map_iterator (); iterator.next ();)
837 public override Gee.MapIterator<K,V> map_iterator () {
838 return new SubMapIterator<K,V> (map, range);
841 public override BidirMapIterator<K,V> bidir_map_iterator () {
842 return new SubMapIterator<K,V> (map, range);
845 public override SortedMap<K,V> head_map (K before) {
846 return new SubMap<K,V> (map, range.cut_tail (before));
849 public override SortedMap<K,V> tail_map (K after) {
850 return new SubMap<K,V> (map, range.cut_head (after));
853 public override SortedMap<K,V> sub_map (K after, K before) {
854 return new SubMap<K,V> (map, range.cut (after, before));
857 public override SortedSet<K> ascending_keys {
861 keys = new SubKeySet<K,V> (map, range);
863 keys.add_weak_pointer(&_keys);
869 public override SortedSet<K> ascending_entries {
871 var entries = _entries;
872 if (_entries == null) {
873 entries = new SubEntrySet<K,V> (map, range);
875 entries.add_weak_pointer(&_entries);
881 private TreeMap<K,V> map;
882 private Range<K,V> range;
885 private class KeySet<K,V> : AbstractBidirSortedSet<K> {
886 private TreeMap<K,V> _map;
888 public KeySet (TreeMap<K,V> map) {
892 public override Iterator<K> iterator () {
893 return new KeyIterator<K,V> (_map);
896 public override int size {
897 get { return _map.size; }
900 public override bool read_only {
904 public override bool add (K key) {
905 assert_not_reached ();
908 public override void clear () {
909 assert_not_reached ();
912 public override bool remove (K key) {
913 assert_not_reached ();
916 public override bool contains (K key) {
917 return _map.has_key (key);
920 public override K first () {
921 assert (_map.first != null);
922 return _map.first.key;
925 public override K last () {
926 assert (_map.last != null);
927 return _map.last.key;
930 public override BidirIterator<K> bidir_iterator () {
931 return new KeyIterator<K,V> (_map);
934 public override SortedSet<K> head_set (K before) {
935 return new SubKeySet<K,V> (_map, new Range<K,V>.head (_map, before));
938 public override SortedSet<K> tail_set (K after) {
939 return new SubKeySet<K,V> (_map, new Range<K,V>.tail (_map, after));
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));
946 public override Iterator<K>? iterator_at (K item) {
947 weak Node<K,V>? node = _map.find_node (item);
950 return new KeyIterator<K,V>.pointing (_map, node);
953 public override K? lower (K item) {
954 return _map.lift_null_key (_map.find_lower (item));
957 public override K? higher (K item) {
958 return _map.lift_null_key (_map.find_higher (item));
961 public override K? floor (K item) {
962 return _map.lift_null_key (_map.find_floor (item));
965 public override K? ceil (K item) {
966 return _map.lift_null_key (_map.find_ceil (item));
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; }
976 public SubKeySet (TreeMap<K,V> map, Range<K,V> range) {
981 public override Iterator<K> iterator () {
982 return new SubKeyIterator<K,V> (map, range);
985 public override int size {
988 Gee.Iterator<K> iterator = iterator ();
989 while (iterator.next ())
995 public override bool read_only {
1001 public bool is_empty { get { return range.empty_submap (); } }
1003 public override bool add (K key) {
1004 assert_not_reached ();
1007 public override void clear () {
1008 assert_not_reached ();
1011 public override bool remove (K key) {
1012 assert_not_reached ();
1015 public override bool contains (K key) {
1016 return range.in_range(key) && map.has_key (key);
1019 public override BidirIterator<K> bidir_iterator () {
1020 return new SubKeyIterator<K,V> (map, range);
1023 public override K first () {
1024 weak Node<K,V>? _first = range.first ();
1025 assert (_first != null);
1029 public override K last () {
1030 weak Node<K,V>? _last = range.last ();
1031 assert (_last != null);
1035 public override SortedSet<K> head_set (K before) {
1036 return new SubKeySet<K,V> (map, range.cut_tail (before));
1039 public override SortedSet<K> tail_set (K after) {
1040 return new SubKeySet<K,V> (map, range.cut_head (after));
1043 public override SortedSet<K> sub_set (K after, K before) {
1044 return new SubKeySet<K,V> (map, range.cut (after, before));
1047 public override Iterator<K>? iterator_at (K key) {
1048 if (!range.in_range (key))
1050 weak Node<K,V>? n = map.find_node (key);
1053 return new SubKeyIterator<K,V>.pointing (map, range, n);
1056 public override K? lower (K key) {
1057 var res = range.compare_range (key);
1060 var l = map.lift_null_key (map.find_lower (key));
1061 return l != null && range.in_range (l) ? l : null;
1064 public override K? higher (K key) {
1065 var res = range.compare_range (key);
1068 var h = map.lift_null_key (map.find_higher (key));
1069 return h != null && range.in_range (h) ? h : null;
1072 public override K? floor (K key) {
1073 var res = range.compare_range (key);
1076 var l = map.lift_null_key (map.find_floor (key));
1077 return l != null && range.in_range (l) ? l : null;
1080 public override K? ceil (K key) {
1081 var res = range.compare_range (key);
1084 var h = map.lift_null_key (map.find_ceil (key));
1085 return h != null && range.in_range (h) ? h : null;
1089 private class ValueCollection<K,V> : AbstractCollection<V> {
1090 private TreeMap<K,V> _map;
1092 public ValueCollection (TreeMap<K,V> map) {
1096 public override Iterator<V> iterator () {
1097 return new ValueIterator<K,V> (_map);
1100 public override int size {
1101 get { return _map.size; }
1104 public override bool read_only {
1105 get { return true; }
1108 public override bool add (V key) {
1109 assert_not_reached ();
1112 public override void clear () {
1113 assert_not_reached ();
1116 public override bool remove (V key) {
1117 assert_not_reached ();
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 ())) {
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; }
1137 public SubValueCollection (TreeMap<K,V> map, Range<K,V> range) {
1142 public override Iterator<V> iterator () {
1143 return new SubValueIterator<K,V> (map, range);
1146 public override bool read_only {
1152 public override int size {
1155 Gee.Iterator<V> iterator = iterator ();
1156 while (iterator.next ())
1162 public bool is_empty { get { return range.empty_submap (); } }
1164 public override bool add (V key) {
1165 assert_not_reached ();
1168 public override void clear () {
1169 assert_not_reached ();
1172 public override bool remove (V key) {
1173 assert_not_reached ();
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 ())) {
1187 private class EntrySet<K,V> : AbstractBidirSortedSet<Map.Entry<K, V>> {
1188 private TreeMap<K,V> _map;
1190 public EntrySet (TreeMap<K,V> map) {
1194 public override Iterator<Map.Entry<K, V>> iterator () {
1195 return new EntryIterator<K,V> (_map);
1198 public override int size {
1199 get { return _map.size; }
1202 public override bool read_only {
1203 get { return true; }
1206 public override bool add (Map.Entry<K, V> entry) {
1207 assert_not_reached ();
1210 public override void clear () {
1211 assert_not_reached ();
1214 public override bool remove (Map.Entry<K, V> entry) {
1215 assert_not_reached ();
1218 public override bool contains (Map.Entry<K, V> entry) {
1219 return _map.has (entry.key, entry.value);
1222 public override Map.Entry<K, V>/*?*/ first () {
1223 assert (_map.first != null);
1224 return Entry.entry_for<K,V> (_map.first);
1227 public override Map.Entry<K, V>/*?*/ last () {
1228 assert (_map.last != null);
1229 return Entry.entry_for<K,V> (_map.last);
1232 public override BidirIterator<Map.Entry<K, V>> bidir_iterator () {
1233 return new EntryIterator<K,V> (_map);
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));
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));
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));
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))
1252 return new EntryIterator<K,V>.pointing (_map, node);
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;
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;
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;
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;
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; }
1282 public SubEntrySet (TreeMap<K,V> map, Range<K,V> range) {
1287 public override Iterator<Map.Entry<K,V>> iterator () {
1288 return new SubEntryIterator<K,V> (map, range);
1291 public override int size {
1294 Gee.Iterator<Map.Entry<K,V>> iterator = iterator ();
1295 while (iterator.next ())
1301 public override bool read_only {
1307 public bool is_empty { get { return range.empty_submap (); } }
1309 public override bool add (Map.Entry<K,V> entry) {
1310 assert_not_reached ();
1313 public override void clear () {
1314 assert_not_reached ();
1317 public override bool remove (Map.Entry<K,V> entry) {
1318 assert_not_reached ();
1321 public override bool contains (Map.Entry<K,V> entry) {
1322 return range.in_range(entry.key) && map.has (entry.key, entry.value);
1325 public override BidirIterator<K> bidir_iterator () {
1326 return new SubEntryIterator<K,V> (map, range);
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);
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);
1341 public override SortedSet<K> head_set (Map.Entry<K,V> before) {
1342 return new SubEntrySet<K,V> (map, range.cut_tail (before.key));
1345 public override SortedSet<K> tail_set (Map.Entry<K,V> after) {
1346 return new SubEntrySet<K,V> (map, range.cut_head (after.key));
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));
1353 public override Iterator<Map.Entry<K,V>>? iterator_at (Map.Entry<K,V> entry) {
1354 if (!range.in_range (entry.key))
1356 weak Node<K,V>? n = map.find_node (entry.key);
1357 if (n == null || !map.value_equal_func (n.value, entry.value))
1359 return new SubEntryIterator<K,V>.pointing (map, range, n);
1362 public override Map.Entry<K,V>/*?*/ lower (Map.Entry<K,V> entry) {
1363 var res = range.compare_range (entry.key);
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;
1370 public override Map.Entry<K,V>/*?*/ higher (Map.Entry<K,V> entry) {
1371 var res = range.compare_range (entry.key);
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;
1378 public override Map.Entry<K,V>/*?*/ floor (Map.Entry<K,V> entry) {
1379 var res = range.compare_range (entry.key);
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;
1386 public override Map.Entry<K,V>/*?*/ ceil (Map.Entry<K,V> entry) {
1387 var res = range.compare_range (entry.key);
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;
1395 private class NodeIterator<K, V> : Object {
1396 protected TreeMap<K,V> _map;
1398 // concurrent modification protection
1399 protected int stamp;
1401 protected bool started = false;
1403 internal weak Node<K, V>? current;
1404 protected weak Node<K, V>? _next;
1405 protected weak Node<K, V>? _prev;
1407 public NodeIterator (TreeMap<K,V> map) {
1409 this.stamp = _map.stamp;
1412 public NodeIterator.pointing (TreeMap<K,V> map, Node<K,V> current) {
1415 this.current = current;
1418 public bool next () {
1419 assert (stamp == _map.stamp);
1420 if (current != null) {
1421 if (current.next != null) {
1422 current = current.next;
1427 } else if (_next == null && _prev == null) {
1428 current = _map.first;
1430 return current != null;
1433 if (current != null) {
1437 return current != null;
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);
1448 public bool first () {
1449 assert (stamp == _map.stamp);
1450 current = _map.first;
1453 return current != null; // on false it is null anyway
1456 public bool previous () {
1457 assert (stamp == _map.stamp);
1458 if (current != null) {
1459 if (current.prev != null) {
1460 current = current.prev;
1466 if (_prev != null) {
1477 public bool has_previous () {
1478 assert (stamp == _map.stamp);
1479 return (current == null && _prev != null) ||
1480 (current != null && current.prev != null);
1483 public bool last () {
1484 assert (stamp == _map.stamp);
1485 current = _map.last;
1488 return current != null; // on false it is null anyway
1491 public void remove () {
1492 assert_not_reached ();
1495 public void unset () {
1496 assert (stamp == _map.stamp);
1497 assert (current != null);
1499 bool success = _map.remove_from_node (ref _map.root, current.key, out value, out _prev, out _next);
1501 if (_map.root != null)
1502 _map.root.color = Node.Color.BLACK;
1506 assert (stamp == _map.stamp);
1509 public virtual bool read_only {
1517 return current != null;
1521 internal unowned Node<K,V>? safe_next_get () {
1522 return (current != null) ? current.next : _next;
1525 internal unowned Node<K,V>? safe_previous_get () {
1526 return (current != null) ? current.prev : _prev;
1530 private class SubNodeIterator<K,V> : Object {
1531 public SubNodeIterator (TreeMap<K,V> map, Range<K,V> range) {
1536 public SubNodeIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
1539 this.iterator = new NodeIterator<K,V>.pointing (_map, node);
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 ());
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);
1561 return range.first () != null;
1565 public virtual bool first () {
1566 weak Node<K,V>? node = range.first ();
1569 iterator = iterator_pointing_at (node);
1573 public bool previous () {
1574 if (iterator == null)
1576 weak Node<K,V>? node;
1577 if ((node = iterator.safe_previous_get ()) != null && range.in_range (node.key)) {
1578 assert (iterator.previous ());
1585 public bool has_previous () {
1586 if (iterator == null)
1588 weak Node<K,V>? node;
1589 return (node = iterator.safe_previous_get ()) != null && range.in_range (node.key);
1592 public virtual bool last () {
1593 weak Node<K,V>? node = range.last ();
1596 iterator = iterator_pointing_at (node);
1600 public void remove () {
1605 public void unset () {
1610 public virtual bool read_only {
1618 return iterator != null && iterator.valid;
1622 protected virtual NodeIterator<K,V> iterator_pointing_at (Node<K,V> node) {
1623 return new NodeIterator<K,V>.pointing (_map, node);
1626 protected new TreeMap<K,V> _map;
1627 protected Range<K,V> range;
1628 protected NodeIterator<K,V>? iterator = null;
1631 private class KeyIterator<K,V> : NodeIterator<K, V>, Traversable<K>, Gee.Iterator<K>, BidirIterator<K> {
1632 public KeyIterator (TreeMap<K,V> map) {
1636 public KeyIterator.pointing (TreeMap<K,V> map, Node<K,V> current) {
1637 base.pointing (map, current);
1640 public new K get () {
1641 assert (stamp == _map.stamp);
1642 assert (current != null);
1646 public bool foreach (ForallFunc<K> f) {
1647 if (current != null) {
1648 if (!f (current.key)) {
1651 current = current.next;
1652 } else if (_next == null) {
1653 current = _map.first;
1657 if (current != null) {
1662 for (; current != null; current = current.next) {
1663 if (!f (current.key)) {
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) {
1676 public SubKeyIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
1677 base.pointing (map, range, node);
1680 public new K get () {
1682 return iterator.current.key;
1685 public bool foreach (ForallFunc<K> f) {
1687 if (!f (iterator.current.key)) {
1691 while (iterator.next ()) {
1692 if (!f (iterator.current.key)) {
1700 private class ValueIterator<K,V> : NodeIterator<K,V>, Traversable<V>, Gee.Iterator<V>, Gee.BidirIterator<V> {
1701 public ValueIterator (TreeMap<K,V> map) {
1705 public ValueIterator.pointing (TreeMap<K,V> map, Node<K,V> current) {
1706 base.pointing (map, current);
1709 public new V get () {
1710 assert (stamp == _map.stamp);
1712 return current.value;
1715 public bool foreach (ForallFunc<V> f) {
1716 if (current != null) {
1717 if (!f (current.key)) {
1720 current = current.next;
1721 } else if (_next == null) {
1722 current = _map.first;
1726 if (current != null) {
1731 for (; current != null; current = current.next) {
1732 if (!f (current.key)) {
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) {
1745 public SubValueIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
1746 base.pointing (map, range, node);
1749 public new V get () {
1751 return iterator.current.value;
1754 public bool foreach (ForallFunc<V> f) {
1756 if (!f (iterator.current.key)) {
1760 while (iterator.next ()) {
1761 if (!f (iterator.current.key)) {
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) {
1774 public EntryIterator.pointing (TreeMap<K,V> map, Node<K,V> node) {
1775 base.pointing (map, node);
1778 public new Map.Entry<K,V> get () {
1779 assert (stamp == _map.stamp);
1781 return Entry.entry_for<K,V> (current);
1784 public new void remove () {
1788 public bool foreach (ForallFunc<Map.Entry<K, V>> f) {
1789 if (current != null) {
1790 if (!f (Entry.entry_for<K,V> (current))) {
1793 current = current.next;
1794 } else if (_next == null) {
1795 current = _map.first;
1799 if (current != null) {
1804 for (; current != null; current = current.next) {
1805 if (!f (Entry.entry_for<K,V> (current))) {
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) {
1818 public SubEntryIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
1819 base.pointing (map, range, node);
1822 public new Map.Entry<K,V> get () {
1823 assert (iterator != null);
1824 return Entry.entry_for<K,V> (iterator.current);
1827 public new void remove () {
1831 public bool foreach (ForallFunc<Map.Entry<K, V>> f) {
1833 if (!f (Entry.entry_for<K,V> (iterator.current))) {
1837 while (iterator.next ()) {
1838 if (!f (Entry.entry_for<K,V> (iterator.current))) {
1846 private class MapIterator<K,V> : NodeIterator<K,V>, Gee.MapIterator<K,V>, BidirMapIterator<K,V> {
1847 public MapIterator (TreeMap<K,V> map) {
1851 public K get_key () {
1852 assert (stamp == _map.stamp);
1857 public V get_value () {
1858 assert (stamp == _map.stamp);
1860 return current.value;
1863 public void set_value (V value) {
1864 assert (stamp == _map.stamp);
1866 current.value = value;
1869 public override bool read_only {
1875 public bool mutable {
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) {
1887 public K get_key () {
1889 return iterator.current.key;
1892 public V get_value () {
1894 return iterator.current.value;
1897 public void set_value (V value) {
1899 iterator.current.value = value;
1902 public override bool read_only {
1908 public bool mutable {