summaryrefslogtreecommitdiff
path: root/gee/treemap.vala
diff options
context:
space:
mode:
Diffstat (limited to 'gee/treemap.vala')
-rw-r--r--gee/treemap.vala1268
1 files changed, 1206 insertions, 62 deletions
diff --git a/gee/treemap.vala b/gee/treemap.vala
index 8b3917e..2d2708a 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -1,6 +1,6 @@
/* treemap.vala
*
- * Copyright (C) 2009 Maciej Piechotka
+ * Copyright (C) 2009-2011 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -31,20 +31,24 @@ using GLib;
*
* @see HashMap
*/
-public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
+public class Gee.TreeMap<K,V> : Gee.AbstractBidirSortedMap<K,V> {
/**
* {@inheritDoc}
*/
public override int size {
get { return _size; }
}
+
+ public override bool read_only {
+ get { return false; }
+ }
/**
* {@inheritDoc}
*/
public override Set<K> keys {
owned get {
- Set<K> keys = _keys;
+ var keys = _keys;
if (_keys == null) {
keys = new KeySet<K,V> (this);
_keys = keys;
@@ -59,7 +63,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
*/
public override Collection<V> values {
owned get {
- Collection<K> values = _values;
+ var values = _values;
if (_values == null) {
values = new ValueCollection<K,V> (this);
_values = values;
@@ -74,7 +78,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
*/
public override Set<Map.Entry<K,V>> entries {
owned get {
- Set<Map.Entry<K,V>> entries = _entries;
+ var entries = _entries;
if (_entries == null) {
entries = new EntrySet<K,V> (this);
_entries = entries;
@@ -87,18 +91,20 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
/**
* The keys' comparator function.
*/
- public CompareFunc key_compare_func { private set; get; }
+ [CCode (notify = false)]
+ public CompareDataFunc<K> key_compare_func { private set; get; }
/**
* The values' equality testing function.
*/
- public EqualFunc value_equal_func { private set; get; }
+ [CCode (notify = false)]
+ public EqualDataFunc<V> value_equal_func { private set; get; }
private int _size = 0;
- private weak Set<K> _keys;
+ private weak SortedSet<K> _keys;
private weak Collection<V> _values;
- private weak Set<Map.Entry<K,V>> _entries;
+ private weak SortedSet<Map.Entry<K,V>> _entries;
/**
* Constructs a new, empty tree map sorted according to the specified
@@ -110,7 +116,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
* @param key_compare_func an optional key comparator function
* @param value_equal_func an optional values equality testing function
*/
- public TreeMap (CompareFunc? key_compare_func = null, EqualFunc? value_equal_func = null) {
+ public TreeMap (owned CompareDataFunc<K>? key_compare_func = null, owned EqualDataFunc<V>? value_equal_func = null) {
if (key_compare_func == null) {
key_compare_func = Functions.get_compare_func_for (typeof (K));
}
@@ -121,6 +127,10 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
this.value_equal_func = value_equal_func;
}
+ ~TreeMap () {
+ clear ();
+ }
+
private void rotate_right (ref Node<K, V> root) {
Node<K,V> pivot = (owned) root.left;
pivot.color = root.color;
@@ -191,8 +201,9 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
return null;
}
- private void set_to_node (ref Node<K, V>? node, K key, V value, Node<K, V>? prev, Node<K, V>? next) {
+ 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) {
if (node == null) {
+ old_value = null;
node = new Node<K,V> (key, value, prev, next);
if (prev == null) {
first = node;
@@ -201,25 +212,36 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
last = node;
}
_size++;
+ return true;
}
int cmp = key_compare_func (key, node.key);
+ bool changed;
if (cmp == 0) {
- node.value = value;
+ if (value_equal_func (value, node.value)) {
+ old_value = null;
+ changed = false;
+ } else {
+ old_value = (owned) node.value;
+ node.value = value;
+ changed = true;
+ }
} else if (cmp < 0) {
- set_to_node (ref node.left, key, value, node.prev, node);
+ changed = set_to_node (ref node.left, key, value, out old_value, node.prev, node);
} else {
- set_to_node (ref node.right, key, value, node, node.next);
+ changed = set_to_node (ref node.right, key, value, out old_value, node, node.next);
}
fix_up (ref node);
+ return changed;
}
/**
* {@inheritDoc}
*/
public override void set (K key, V value) {
- set_to_node (ref root, key, value, null, null);
+ V old_value;
+ set_to_node (ref root, key, value, out old_value, null, null);
root.color = Node.Color.BLACK;
stamp++;
}
@@ -243,12 +265,8 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
private void fix_removal (ref Node<K,V> node, out K? key = null, out V? value) {
Node<K,V> n = (owned) node;
- if (&key != null)
- key = (owned) n.key;
- else
- n.key = null;
- if (&value != null)
- value = (owned) n.value;
+ key = (owned) n.key;
+ value = (owned) n.value;
if (n.prev != null) {
n.prev.next = n.next;
} else {
@@ -279,12 +297,18 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
fix_up (ref node);
}
- 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) {
+ 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) {
if (node == null) {
+ value = null;
+ next = null;
+ prev = null;
return false;
} else if (key_compare_func (key, node.key) < 0) {
weak Node<K,V> left = node.left;
if (left == null) {
+ value = null;
+ next = null;
+ prev = null;
return false;
}
if (node.left != null && is_black (left) && is_black (left.left)) {
@@ -300,10 +324,8 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
weak Node<K,V>? r = node.right;
if (key_compare_func (key, node.key) == 0 && r == null) {
- if (&prev != null)
- prev = node.prev;
- if (&next != null)
- next = node.next;
+ prev = node.prev;
+ next = node.next;
fix_removal (ref node, null, out value);
return true;
}
@@ -312,10 +334,8 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
}
if (key_compare_func (key, node.key) == 0) {
value = (owned) node.value;
- if (&prev != null)
- prev = node.prev;
- if (&next != null)
- next = node;
+ prev = node.prev;
+ next = node;
remove_minimal (ref node.right, out node.key, out node.value);
fix_up (ref node);
return true;
@@ -343,12 +363,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
* {@inheritDoc}
*/
public override bool unset (K key, out V? value = null) {
- V node_value;
- bool b = remove_from_node (ref root, key, out node_value);
-
- if (&value != null) {
- value = (owned) node_value;
- }
+ bool b = remove_from_node (ref root, key, out value);
if (root != null) {
root.color = Node.Color.BLACK;
@@ -381,9 +396,66 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
/**
* {@inheritDoc}
*/
+ public override SortedMap<K,V> head_map (K before) {
+ return new SubMap<K,V> (this, new Range<K,V>.head (this, before));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public override SortedMap<K,V> tail_map (K after) {
+ return new SubMap<K,V> (this, new Range<K,V>.tail (this, after));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public override SortedMap<K,V> sub_map (K after, K before) {
+ return new SubMap<K,V> (this, new Range<K,V> (this, after, before));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public override SortedSet<K> ascending_keys {
+ owned get {
+ var keys = _keys;
+ if (_keys == null) {
+ keys = new KeySet<K,V> (this);
+ _keys = keys;
+ keys.add_weak_pointer (&_keys);
+ }
+ return keys;
+ }
+ }
+ /**
+ * {@inheritDoc}
+ */
+ public override SortedSet<Map.Entry<K,V>> ascending_entries {
+ owned get {
+ var entries = _entries;
+ if (_entries == null) {
+ entries = new EntrySet<K,V> (this);
+ _entries = entries;
+ entries.add_weak_pointer (&_entries);
+ }
+ return entries;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
public override Gee.MapIterator<K,V> map_iterator () {
return new MapIterator<K,V> (this);
}
+
+ /**
+ * {@inheritDoc}
+ */
+ public override Gee.BidirMapIterator<K,V> bidir_map_iterator () {
+ return new MapIterator<K,V> (this);
+ }
[Compact]
private class Node<K, V> {
@@ -439,12 +511,54 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
private weak Node<K, V>? last = null;
private int stamp = 0;
+ private inline K min (K a, K b) {
+ return key_compare_func (a, b) <= 0 ? a : b;
+ }
+
+ private inline K max (K a, K b) {
+ return key_compare_func (a, b) > 0 ? a : b;
+ }
+
+ private inline unowned Node<K,V>? find_node (K key) {
+ unowned Node<K,V>? cur = root;
+ while (cur != null) {
+ int res = key_compare_func (key, cur.key);
+ if (res == 0) {
+ return cur;
+ } else if (res < 0) {
+ cur = cur.left;
+ } else {
+ cur = cur.right;
+ }
+ }
+ return null;
+ }
+
+ private inline unowned Node<K,V>? find_nearest (K key) {
+ unowned Node<K,V>? cur = root;
+ while (cur != null) {
+ int res = key_compare_func (key, cur.key);
+ if (res == 0) {
+ return cur;
+ } else if (res < 0) {
+ if (cur.left == null)
+ return cur;
+ cur = cur.left;
+ } else {
+ if (cur.right == null)
+ return cur;
+ cur = cur.right;
+ }
+ }
+ return null;
+ }
+
private class Entry<K,V> : Map.Entry<K,V> {
private unowned Node<K,V> _node;
public static Map.Entry<K,V> entry_for<K,V> (Node<K,V> node) {
Map.Entry<K,V> result = node.entry;
- if (node.entry == null) {
+ if (result == null) {
result = new Entry<K,V> (node);
node.entry = result;
result.add_weak_pointer ((void**) (&node.entry));
@@ -462,9 +576,313 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
get { return _node.value; }
set { _node.value = value; }
}
+
+ public override bool read_only { get { return false; } }
}
- private class KeySet<K,V> : AbstractSet<K> {
+ private inline unowned Node<K,V>? find_lower (K key) {
+ unowned Node<K,V>? node = find_nearest (key);
+ if (node == null)
+ return null;
+ return key_compare_func (key, node.key) <= 0 ? node.prev : node;
+ }
+
+ private inline unowned Node<K,V>? find_higher (K key) {
+ unowned Node<K,V>? node = find_nearest (key);
+ if (node == null)
+ return null;
+ return key_compare_func (key, node.key) >= 0 ? node.next : node;
+ }
+
+ private inline unowned Node<K,V>? find_floor (K key) {
+ unowned Node<K,V>? node = find_nearest (key);
+ if (node == null)
+ return null;
+ return key_compare_func (key, node.key) < 0 ? node.prev : node;
+ }
+
+ private inline unowned Node<K,V>? find_ceil (K key) {
+ unowned Node<K,V>? node = find_nearest (key);
+ if (node == null)
+ return null;
+ return key_compare_func (key, node.key) > 0 ? node.next : node;
+ }
+
+ private inline K? lift_null_key (Node<K,V>? node) {
+ return node != null ? node.key : null;
+ }
+
+ private class Range<K,V> {
+ public Range (TreeMap<K,V> map, K after, K before) {
+ this.map = map;
+ if (map.key_compare_func (after, before) < 0) {
+ this.after = after;
+ this.before = before;
+ type = RangeType.BOUNDED;
+ } else {
+ type = RangeType.EMPTY;
+ }
+ }
+
+ public Range.head (TreeMap<K,V> map, K before) {
+ this.map = map;
+ this.before = before;
+ type = RangeType.HEAD;
+ }
+
+ public Range.tail (TreeMap<K,V> map, K after) {
+ this.map = map;
+ this.after = after;
+ type = RangeType.TAIL;
+ }
+
+ public Range.empty (TreeMap<K,V> map) {
+ this.map = map;
+ type = RangeType.EMPTY;
+ }
+
+ public Range<K,V> cut_head (K after) {
+ switch (type) {
+ case RangeType.HEAD:
+ return new Range<K,V> (map, after, before);
+ case RangeType.TAIL:
+ return new Range<K,V>.tail (map, map.max (after, this.after));
+ case RangeType.EMPTY:
+ return this;
+ case RangeType.BOUNDED:
+ var _after = map.max (after, this.after);
+ return new Range<K,V> (map, _after, before);
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public Range<K,V> cut_tail (K before) {
+ switch (type) {
+ case RangeType.HEAD:
+ return new Range<K,V>.head (map, map.min (before, this.before));
+ case RangeType.TAIL:
+ return new Range<K,V> (map, after, before);
+ case RangeType.EMPTY:
+ return this;
+ case RangeType.BOUNDED:
+ var _before = map.min (before, this.before);
+ return new Range<K,V> (map, after, _before);
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public Range<K,V> cut (K after, K before) {
+ if (type == RangeType.EMPTY)
+ return this;
+ var _before = (type == RangeType.HEAD || type == RangeType.BOUNDED) ?
+ map.min (before, this.before) : before;
+ var _after = (type == RangeType.TAIL || type == RangeType.BOUNDED) ?
+ map.max (after, this.after) : after;
+ return new Range<K,V> (map, _after, _before);
+ }
+
+ public bool in_range (K key) {
+ return type == RangeType.EMPTY ? false : compare_range(key) == 0;
+ }
+
+ public int compare_range (K key) {
+ switch (type) {
+ case RangeType.HEAD:
+ return map.key_compare_func (key, before) < 0 ? 0 : 1;
+ case RangeType.TAIL:
+ return map.key_compare_func (key, after) >= 0 ? 0 : -1;
+ case RangeType.EMPTY:
+ return 0; // For simplicity - please make sure it does not break anything
+ case RangeType.BOUNDED:
+ return map.key_compare_func (key, after) >= 0 ?
+ (map.key_compare_func (key, before) < 0 ? 0 : 1) : -1;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public bool empty_submap () {
+ switch (type) {
+ case RangeType.HEAD:
+ return map.first == null || !in_range (map.first.key);
+ case RangeType.TAIL:
+ return map.last == null || !in_range (map.last.key);
+ case RangeType.EMPTY:
+ return true;
+ case RangeType.BOUNDED:
+ return first () == null;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public unowned Node<K,V>? first () {
+ switch (type) {
+ case RangeType.EMPTY:
+ return null;
+ case RangeType.HEAD:
+ return map.first;
+ default:
+ return map.find_floor (after);
+ }
+ }
+
+ public unowned Node<K,V>? last () {
+ switch (type) {
+ case RangeType.EMPTY:
+ return null;
+ case RangeType.TAIL:
+ return map.last;
+ default:
+ return map.find_lower (before);
+ }
+ }
+
+ private new TreeMap<K,V> map;
+ private K after;
+ private K before;
+ private RangeType type;
+ }
+
+ private enum RangeType {
+ HEAD,
+ TAIL,
+ EMPTY,
+ BOUNDED
+ }
+
+ private class SubMap<K,V> : AbstractBidirSortedMap<K,V> {
+ public override int size { get { return keys.size; } }
+ public bool is_empty { get { return keys.is_empty; } }
+
+ public SubMap (TreeMap<K,V> map, Range<K,V> range) {
+ this.map = map;
+ this.range = range;
+ }
+
+ private weak SortedSet<K>? _keys;
+ public override Set<K> keys {
+ owned get {
+ var keys = _keys;
+ if (_keys == null) {
+ keys = new SubKeySet<K,V> (map, range);
+ _keys = keys;
+ keys.add_weak_pointer(&_keys);
+ }
+ return keys;
+ }
+ }
+
+ private weak Collection<K>? _values;
+ public override Collection<V> values {
+ owned get {
+ var values = _values;
+ if (_values == null) {
+ values = new SubValueCollection<K,V> (map, range);
+ _values = values;
+ values.add_weak_pointer(&_values);
+ }
+ return values;
+ }
+ }
+
+ private weak SortedSet<Entry<K,V>>? _entries;
+ public override Set<Entry<K,V>> entries {
+ owned get {
+ var entries = _entries;
+ if (_entries == null) {
+ entries = new SubEntrySet<K,V> (map, range);
+ _entries = entries;
+ entries.add_weak_pointer(&_entries);
+ }
+ return entries;
+ }
+ }
+
+ public override bool read_only {
+ get {
+ return true;
+ }
+ }
+
+ public override bool has_key (K key) {
+ return range.in_range (key) && map.has_key (key);
+ }
+
+ public override bool has (K key, V value) {
+ return range.in_range (key) && map.has (key, value);
+ }
+
+ public override new V? get (K key) {
+ return range.in_range (key) ? map.get (key) : null;
+ }
+
+ public override void set (K key, V value) {
+ if (range.in_range (key))
+ map.set (key, value);
+ }
+
+ public override bool unset (K key, out V? value = null) {
+ value = null;
+ return range.in_range (key) && map.unset (key, out value);
+ }
+
+ public override void clear () {
+ for (var iterator = map_iterator (); iterator.next ();)
+ iterator.unset ();
+ }
+
+ public override Gee.MapIterator<K,V> map_iterator () {
+ return new SubMapIterator<K,V> (map, range);
+ }
+
+ public override BidirMapIterator<K,V> bidir_map_iterator () {
+ return new SubMapIterator<K,V> (map, range);
+ }
+
+ public override SortedMap<K,V> head_map (K before) {
+ return new SubMap<K,V> (map, range.cut_tail (before));
+ }
+
+ public override SortedMap<K,V> tail_map (K after) {
+ return new SubMap<K,V> (map, range.cut_head (after));
+ }
+
+ public override SortedMap<K,V> sub_map (K after, K before) {
+ return new SubMap<K,V> (map, range.cut (after, before));
+ }
+
+ public override SortedSet<K> ascending_keys {
+ owned get {
+ var keys = _keys;
+ if (_keys == null) {
+ keys = new SubKeySet<K,V> (map, range);
+ _keys = keys;
+ keys.add_weak_pointer(&_keys);
+ }
+ return keys;
+ }
+ }
+
+ public override SortedSet<K> ascending_entries {
+ owned get {
+ var entries = _entries;
+ if (_entries == null) {
+ entries = new SubEntrySet<K,V> (map, range);
+ _entries = entries;
+ entries.add_weak_pointer(&_entries);
+ }
+ return _entries;
+ }
+ }
+
+ private TreeMap<K,V> map;
+ private Range<K,V> range;
+ }
+
+ private class KeySet<K,V> : AbstractBidirSortedSet<K> {
private TreeMap<K,V> _map;
public KeySet (TreeMap<K,V> map) {
@@ -479,6 +897,10 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
get { return _map.size; }
}
+ public override bool read_only {
+ get { return true; }
+ }
+
public override bool add (K key) {
assert_not_reached ();
}
@@ -495,17 +917,173 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
return _map.has_key (key);
}
- public override bool add_all (Collection<K> collection) {
+ public override K first () {
+ assert (_map.first != null);
+ return _map.first.key;
+ }
+
+ public override K last () {
+ assert (_map.last != null);
+ return _map.last.key;
+ }
+
+ public override BidirIterator<K> bidir_iterator () {
+ return new KeyIterator<K,V> (_map);
+ }
+
+ public override SortedSet<K> head_set (K before) {
+ return new SubKeySet<K,V> (_map, new Range<K,V>.head (_map, before));
+ }
+
+ public override SortedSet<K> tail_set (K after) {
+ return new SubKeySet<K,V> (_map, new Range<K,V>.tail (_map, after));
+ }
+
+ public override SortedSet<K> sub_set (K after, K before) {
+ return new SubKeySet<K,V> (_map, new Range<K,V> (_map, after, before));
+ }
+
+ public override Iterator<K>? iterator_at (K item) {
+ weak Node<K,V>? node = _map.find_node (item);
+ if (node == null)
+ return null;
+ return new KeyIterator<K,V>.pointing (_map, node);
+ }
+
+ public override K? lower (K item) {
+ return _map.lift_null_key (_map.find_lower (item));
+ }
+
+ public override K? higher (K item) {
+ return _map.lift_null_key (_map.find_higher (item));
+ }
+
+ public override K? floor (K item) {
+ return _map.lift_null_key (_map.find_floor (item));
+ }
+
+ public override K? ceil (K item) {
+ return _map.lift_null_key (_map.find_ceil (item));
+ }
+ }
+
+ private class SubKeySet<K,V> : AbstractBidirSortedSet<K> {
+ [CCode (notify = false)]
+ public TreeMap<K,V> map { private set; get; }
+ [CCode (notify = false)]
+ public Range<K,V> range { private set; get; }
+
+ public SubKeySet (TreeMap<K,V> map, Range<K,V> range) {
+ this.map = map;
+ this.range = range;
+ }
+
+ public override Iterator<K> iterator () {
+ return new SubKeyIterator<K,V> (map, range);
+ }
+
+ public override int size {
+ get {
+ var i = 0;
+ Gee.Iterator<K> iterator = iterator ();
+ while (iterator.next ())
+ i++;
+ return i;
+ }
+ }
+
+ public override bool read_only {
+ get {
+ return true;
+ }
+ }
+
+ public bool is_empty { get { return range.empty_submap (); } }
+
+ public override bool add (K key) {
assert_not_reached ();
}
- public override bool remove_all (Collection<K> collection) {
+ public override void clear () {
assert_not_reached ();
}
- public override bool retain_all (Collection<K> collection) {
+ public override bool remove (K key) {
assert_not_reached ();
}
+
+ public override bool contains (K key) {
+ return range.in_range(key) && map.has_key (key);
+ }
+
+ public override BidirIterator<K> bidir_iterator () {
+ return new SubKeyIterator<K,V> (map, range);
+ }
+
+ public override K first () {
+ weak Node<K,V>? _first = range.first ();
+ assert (_first != null);
+ return _first.key;
+ }
+
+ public override K last () {
+ weak Node<K,V>? _last = range.last ();
+ assert (_last != null);
+ return _last.key;
+ }
+
+ public override SortedSet<K> head_set (K before) {
+ return new SubKeySet<K,V> (map, range.cut_tail (before));
+ }
+
+ public override SortedSet<K> tail_set (K after) {
+ return new SubKeySet<K,V> (map, range.cut_head (after));
+ }
+
+ public override SortedSet<K> sub_set (K after, K before) {
+ return new SubKeySet<K,V> (map, range.cut (after, before));
+ }
+
+ public override Iterator<K>? iterator_at (K key) {
+ if (!range.in_range (key))
+ return null;
+ weak Node<K,V>? n = map.find_node (key);
+ if (n == null)
+ return null;
+ return new SubKeyIterator<K,V>.pointing (map, range, n);
+ }
+
+ public override K? lower (K key) {
+ var res = range.compare_range (key);
+ if (res > 0)
+ return last ();
+ var l = map.lift_null_key (map.find_lower (key));
+ return l != null && range.in_range (l) ? l : null;
+ }
+
+ public override K? higher (K key) {
+ var res = range.compare_range (key);
+ if (res < 0)
+ return first ();
+ var h = map.lift_null_key (map.find_higher (key));
+ return h != null && range.in_range (h) ? h : null;
+ }
+
+ public override K? floor (K key) {
+ var res = range.compare_range (key);
+ if (res > 0)
+ return last ();
+ var l = map.lift_null_key (map.find_floor (key));
+ return l != null && range.in_range (l) ? l : null;
+ }
+
+ public override K? ceil (K key) {
+ var res = range.compare_range (key);
+ if (res < 0)
+ return first ();
+ var h = map.lift_null_key (map.find_ceil (key));
+ return h != null && range.in_range (h) ? h : null;
+ }
}
private class ValueCollection<K,V> : AbstractCollection<V> {
@@ -523,6 +1101,10 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
get { return _map.size; }
}
+ public override bool read_only {
+ get { return true; }
+ }
+
public override bool add (V key) {
assert_not_reached ();
}
@@ -544,21 +1126,65 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
}
return false;
}
+ }
+
+ private class SubValueCollection<K,V> : AbstractCollection<V> {
+ [CCode (notify = false)]
+ public TreeMap<K,V> map { private set; get; }
+ [CCode (notify = false)]
+ public Range<K,V> range { private set; get; }
+
+ public SubValueCollection (TreeMap<K,V> map, Range<K,V> range) {
+ this.map = map;
+ this.range = range;
+ }
+
+ public override Iterator<V> iterator () {
+ return new SubValueIterator<K,V> (map, range);
+ }
+
+ public override bool read_only {
+ get {
+ return true;
+ }
+ }
+
+ public override int size {
+ get {
+ var i = 0;
+ Gee.Iterator<V> iterator = iterator ();
+ while (iterator.next ())
+ i++;
+ return i;
+ }
+ }
+
+ public bool is_empty { get { return range.empty_submap (); } }
- public override bool add_all (Collection<V> collection) {
+ public override bool add (V key) {
assert_not_reached ();
}
- public override bool remove_all (Collection<V> collection) {
+ public override void clear () {
assert_not_reached ();
}
- public override bool retain_all (Collection<V> collection) {
+ public override bool remove (V key) {
assert_not_reached ();
}
+
+ public override bool contains (V key) {
+ Iterator<V> it = iterator ();
+ while (it.next ()) {
+ if (map.value_equal_func (key, it.get ())) {
+ return true;
+ }
+ }
+ return false;
+ }
}
- private class EntrySet<K,V> : AbstractSet<Map.Entry<K, V>> {
+ private class EntrySet<K,V> : AbstractBidirSortedSet<Map.Entry<K, V>> {
private TreeMap<K,V> _map;
public EntrySet (TreeMap<K,V> map) {
@@ -573,6 +1199,10 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
get { return _map.size; }
}
+ public override bool read_only {
+ get { return true; }
+ }
+
public override bool add (Map.Entry<K, V> entry) {
assert_not_reached ();
}
@@ -589,32 +1219,200 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
return _map.has (entry.key, entry.value);
}
- public override bool add_all (Collection<Map.Entry<K, V>> entries) {
+ public override Map.Entry<K, V>/*?*/ first () {
+ assert (_map.first != null);
+ return Entry.entry_for<K,V> (_map.first);
+ }
+
+ public override Map.Entry<K, V>/*?*/ last () {
+ assert (_map.last != null);
+ return Entry.entry_for<K,V> (_map.last);
+ }
+
+ public override BidirIterator<Map.Entry<K, V>> bidir_iterator () {
+ return new EntryIterator<K,V> (_map);
+ }
+
+ public override SortedSet<Map.Entry<K, V>> head_set (Map.Entry<K, V> before) {
+ return new SubEntrySet<K,V> (_map, new Range<K,V>.head (_map, before.key));
+ }
+
+ public override SortedSet<Map.Entry<K, V>> tail_set (Map.Entry<K, V> after) {
+ return new SubEntrySet<K,V> (_map, new Range<K,V>.tail (_map, after.key));
+ }
+
+ public override SortedSet<K> sub_set (Map.Entry<K, V> after, Map.Entry<K, V> before) {
+ return new SubEntrySet<K,V> (_map, new Range<K,V> (_map, after.key, before.key));
+ }
+
+ public override Iterator<Map.Entry<K, V>>? iterator_at (Map.Entry<K, V> item) {
+ weak Node<K,V>? node = _map.find_node (item.key);
+ if (node == null || !_map.value_equal_func (node.value, item.value))
+ return null;
+ return new EntryIterator<K,V>.pointing (_map, node);
+ }
+
+ public override Map.Entry<K, V>/*?*/ lower (Map.Entry<K, V> item) {
+ weak Node<K,V>? l = _map.find_lower (item.key);
+ return l != null ? Entry.entry_for<K,V> (l) : null;
+ }
+
+ public override Map.Entry<K, V>/*?*/ higher (Map.Entry<K, V> item) {
+ weak Node<K,V>? l = _map.find_higher (item.key);
+ return l != null ? Entry.entry_for<K,V> (l) : null;
+ }
+
+ public override Map.Entry<K, V>/*?*/ floor (Map.Entry<K, V> item) {
+ weak Node<K,V>? l = _map.find_floor (item.key);
+ return l != null ? Entry.entry_for<K,V> (l) : null;
+ }
+
+ public override Map.Entry<K, V>/*?*/ ceil (Map.Entry<K, V> item) {
+ weak Node<K,V>? l = _map.find_ceil (item.key);
+ return l != null ? Entry.entry_for<K,V> (l) : null;
+ }
+ }
+
+ private class SubEntrySet<K,V> : AbstractBidirSortedSet<Map.Entry<K,V>> {
+ [CCode (notify = false)]
+ public TreeMap<K,V> map { private set; get; }
+ [CCode (notify = false)]
+ public Range<K,V> range { private set; get; }
+
+ public SubEntrySet (TreeMap<K,V> map, Range<K,V> range) {
+ this.map = map;
+ this.range = range;
+ }
+
+ public override Iterator<Map.Entry<K,V>> iterator () {
+ return new SubEntryIterator<K,V> (map, range);
+ }
+
+ public override int size {
+ get {
+ var i = 0;
+ Gee.Iterator<Map.Entry<K,V>> iterator = iterator ();
+ while (iterator.next ())
+ i++;
+ return i;
+ }
+ }
+
+ public override bool read_only {
+ get {
+ return true;
+ }
+ }
+
+ public bool is_empty { get { return range.empty_submap (); } }
+
+ public override bool add (Map.Entry<K,V> entry) {
assert_not_reached ();
}
- public override bool remove_all (Collection<Map.Entry<K, V>> entries) {
+ public override void clear () {
assert_not_reached ();
}
- public override bool retain_all (Collection<Map.Entry<K, V>> entries) {
+ public override bool remove (Map.Entry<K,V> entry) {
assert_not_reached ();
}
+
+ public override bool contains (Map.Entry<K,V> entry) {
+ return range.in_range(entry.key) && map.has (entry.key, entry.value);
+ }
+
+ public override BidirIterator<K> bidir_iterator () {
+ return new SubEntryIterator<K,V> (map, range);
+ }
+
+ public override Map.Entry<K,V> first () {
+ weak Node<K,V>? _first = range.first ();
+ assert (_first != null);
+ return Entry.entry_for<K,V> (_first);
+ }
+
+ public override Map.Entry<K,V> last () {
+ weak Node<K,V>? _last = range.last ();
+ assert (_last != null);
+ return Entry.entry_for<K,V> (_last);
+ }
+
+ public override SortedSet<K> head_set (Map.Entry<K,V> before) {
+ return new SubEntrySet<K,V> (map, range.cut_tail (before.key));
+ }
+
+ public override SortedSet<K> tail_set (Map.Entry<K,V> after) {
+ return new SubEntrySet<K,V> (map, range.cut_head (after.key));
+ }
+
+ public override SortedSet<K> sub_set (Map.Entry<K,V> after, Map.Entry<K,V> before) {
+ return new SubEntrySet<K,V> (map, range.cut (after.key, before.key));
+ }
+
+ public override Iterator<Map.Entry<K,V>>? iterator_at (Map.Entry<K,V> entry) {
+ if (!range.in_range (entry.key))
+ return null;
+ weak Node<K,V>? n = map.find_node (entry.key);
+ if (n == null || !map.value_equal_func (n.value, entry.value))
+ return null;
+ return new SubEntryIterator<K,V>.pointing (map, range, n);
+ }
+
+ public override Map.Entry<K,V>/*?*/ lower (Map.Entry<K,V> entry) {
+ var res = range.compare_range (entry.key);
+ if (res > 0)
+ return last ();
+ weak Node<K,V>? l = map.find_lower (entry.key);
+ return l != null && range.in_range (l.key) ? Entry.entry_for<K,V> (l) : null;
+ }
+
+ public override Map.Entry<K,V>/*?*/ higher (Map.Entry<K,V> entry) {
+ var res = range.compare_range (entry.key);
+ if (res < 0)
+ return first ();
+ weak Node<K,V>? h = map.find_higher (entry.key);
+ return h != null && range.in_range (h.key) ? Entry.entry_for<K,V> (h) : null;
+ }
+
+ public override Map.Entry<K,V>/*?*/ floor (Map.Entry<K,V> entry) {
+ var res = range.compare_range (entry.key);
+ if (res > 0)
+ return last ();
+ weak Node<K,V>? l = map.find_floor (entry.key);
+ return l != null && range.in_range (l.key) ? Entry.entry_for<K,V> (l) : null;
+ }
+
+ public override Map.Entry<K,V>/*?*/ ceil (Map.Entry<K,V> entry) {
+ var res = range.compare_range (entry.key);
+ if (res < 0)
+ return first ();
+ weak Node<K,V>? h = map.find_ceil (entry.key);
+ return h != null && range.in_range (h.key) ? Entry.entry_for<K,V> (h) : null;
+ }
}
- private class NodeIterator<K,V> : Object {
+ private class NodeIterator<K, V> : Object {
protected TreeMap<K,V> _map;
// concurrent modification protection
protected int stamp;
- protected weak Node<K, V>? current;
+ protected bool started = false;
+
+ internal weak Node<K, V>? current;
protected weak Node<K, V>? _next;
protected weak Node<K, V>? _prev;
public NodeIterator (TreeMap<K,V> map) {
_map = map;
+ this.stamp = _map.stamp;
+ }
+
+ public NodeIterator.pointing (TreeMap<K,V> map, Node<K,V> current) {
+ _map = map;
stamp = _map.stamp;
+ this.current = current;
}
public bool next () {
@@ -628,6 +1426,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
}
} else if (_next == null && _prev == null) {
current = _map.first;
+ started = true;
return current != null;
} else {
current = _next;
@@ -644,7 +1443,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
return (current == null && _next == null && _prev == null && _map.first != null) ||
(current == null && _next != null) ||
(current != null && current.next != null);
- }
+ }
public bool first () {
assert (stamp == _map.stamp);
@@ -692,7 +1491,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
public void remove () {
assert_not_reached ();
}
-
+
public void unset () {
assert (stamp == _map.stamp);
assert (current != null);
@@ -706,65 +1505,410 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
_map.stamp++;
assert (stamp == _map.stamp);
}
+
+ public virtual bool read_only {
+ get {
+ return true;
+ }
+ }
+
+ public bool valid {
+ get {
+ return current != null;
+ }
+ }
+
+ internal unowned Node<K,V>? safe_next_get () {
+ return (current != null) ? current.next : _next;
+ }
+
+ internal unowned Node<K,V>? safe_previous_get () {
+ return (current != null) ? current.prev : _prev;
+ }
}
- private class KeyIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<K>, BidirIterator<K> {
+ private class SubNodeIterator<K,V> : Object {
+ public SubNodeIterator (TreeMap<K,V> map, Range<K,V> range) {
+ _map = map;
+ this.range = range;
+ }
+
+ public SubNodeIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
+ _map = map;
+ this.range = range;
+ this.iterator = new NodeIterator<K,V>.pointing (_map, node);
+ }
+
+ public bool next () {
+ if (iterator != null) {
+ weak Node<K,V>? node= iterator.safe_next_get ();
+ if (node != null && range.in_range (node.key)) {
+ assert (iterator.next ());
+ return true;
+ } else {
+ return false;
+ }
+ } else {
+ return first ();
+ }
+ }
+
+ public bool has_next () {
+ if (iterator != null) {
+ weak Node<K,V>? node = iterator.safe_next_get ();
+ return node != null && range.in_range (node.key);
+ } else {
+ return range.first () != null;
+ }
+ }
+
+ public virtual bool first () {
+ weak Node<K,V>? node = range.first ();
+ if (node == null)
+ return false;
+ iterator = iterator_pointing_at (node);
+ return true;
+ }
+
+ public bool previous () {
+ if (iterator == null)
+ return false;
+ weak Node<K,V>? node;
+ if ((node = iterator.safe_previous_get ()) != null && range.in_range (node.key)) {
+ assert (iterator.previous ());
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ public bool has_previous () {
+ if (iterator == null)
+ return false;
+ weak Node<K,V>? node;
+ return (node = iterator.safe_previous_get ()) != null && range.in_range (node.key);
+ }
+
+ public virtual bool last () {
+ weak Node<K,V>? node = range.last ();
+ if (node == null)
+ return false;
+ iterator = iterator_pointing_at (node);
+ return true;
+ }
+
+ public void remove () {
+ assert (valid);
+ iterator.remove ();
+ }
+
+ public void unset () {
+ assert (valid);
+ iterator.unset ();
+ }
+
+ public virtual bool read_only {
+ get {
+ return true;
+ }
+ }
+
+ public bool valid {
+ get {
+ return iterator != null && iterator.valid;
+ }
+ }
+
+ protected virtual NodeIterator<K,V> iterator_pointing_at (Node<K,V> node) {
+ return new NodeIterator<K,V>.pointing (_map, node);
+ }
+
+ protected new TreeMap<K,V> _map;
+ protected Range<K,V> range;
+ protected NodeIterator<K,V>? iterator = null;
+ }
+
+ private class KeyIterator<K,V> : NodeIterator<K, V>, Traversable<K>, Gee.Iterator<K>, BidirIterator<K> {
public KeyIterator (TreeMap<K,V> map) {
base (map);
}
+ public KeyIterator.pointing (TreeMap<K,V> map, Node<K,V> current) {
+ base.pointing (map, current);
+ }
+
public new K get () {
assert (stamp == _map.stamp);
assert (current != null);
return current.key;
}
+
+ public bool foreach (ForallFunc<K> f) {
+ if (current != null) {
+ if (!f (current.key)) {
+ return false;
+ }
+ current = current.next;
+ } else if (_next == null) {
+ current = _map.first;
+ started = true;
+ } else {
+ current = _next;
+ if (current != null) {
+ _next = null;
+ _prev = null;
+ }
+ }
+ for (; current != null; current = current.next) {
+ if (!f (current.key)) {
+ return false;
+ }
+ }
+ return true;
+ }
}
- private class ValueIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<V>, Gee.BidirIterator<V> {
+ private class SubKeyIterator<K,V> : SubNodeIterator<K,V>, Traversable<K>, Gee.Iterator<K>, BidirIterator<K> {
+ public SubKeyIterator (TreeMap<K,V> map, Range<K,V> range) {
+ base (map, range);
+ }
+
+ public SubKeyIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
+ base.pointing (map, range, node);
+ }
+
+ public new K get () {
+ assert (valid);
+ return iterator.current.key;
+ }
+
+ public bool foreach (ForallFunc<K> f) {
+ if (valid) {
+ if (!f (iterator.current.key)) {
+ return false;
+ }
+ }
+ while (iterator.next ()) {
+ if (!f (iterator.current.key)) {
+ return false;
+ }
+ }
+ return true;
+ }
+ }
+
+ private class ValueIterator<K,V> : NodeIterator<K,V>, Traversable<V>, Gee.Iterator<V>, Gee.BidirIterator<V> {
public ValueIterator (TreeMap<K,V> map) {
base (map);
}
+ public ValueIterator.pointing (TreeMap<K,V> map, Node<K,V> current) {
+ base.pointing (map, current);
+ }
+
public new V get () {
assert (stamp == _map.stamp);
- assert (current != null);
+ assert (valid);
return current.value;
}
+
+ public bool foreach (ForallFunc<V> f) {
+ if (current != null) {
+ if (!f (current.key)) {
+ return false;
+ }
+ current = current.next;
+ } else if (_next == null) {
+ current = _map.first;
+ started = true;
+ } else {
+ current = _next;
+ if (current != null) {
+ _next = null;
+ _prev = null;
+ }
+ }
+ for (; current != null; current = current.next) {
+ if (!f (current.key)) {
+ return false;
+ }
+ }
+ return true;
+ }
+ }
+
+ private class SubValueIterator<K,V> : SubNodeIterator<K,V>, Traversable<V>, Gee.Iterator<V>, BidirIterator<V> {
+ public SubValueIterator (TreeMap<K,V> map, Range<K,V> range) {
+ base (map, range);
+ }
+
+ public SubValueIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
+ base.pointing (map, range, node);
+ }
+
+ public new V get () {
+ assert (valid);
+ return iterator.current.value;
+ }
+
+ public bool foreach (ForallFunc<V> f) {
+ if (valid) {
+ if (!f (iterator.current.key)) {
+ return false;
+ }
+ }
+ while (iterator.next ()) {
+ if (!f (iterator.current.key)) {
+ return false;
+ }
+ }
+ return true;
+ }
}
- private class EntryIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
+ 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>> {
public EntryIterator (TreeMap<K,V> map) {
base (map);
}
+ public EntryIterator.pointing (TreeMap<K,V> map, Node<K,V> node) {
+ base.pointing (map, node);
+ }
+
public new Map.Entry<K,V> get () {
assert (stamp == _map.stamp);
- assert (current != null);
- return Entry<K,V>.entry_for<K,V> (current);
+ assert (valid);
+ return Entry.entry_for<K,V> (current);
+ }
+
+ public new void remove () {
+ unset ();
+ }
+
+ public bool foreach (ForallFunc<Map.Entry<K, V>> f) {
+ if (current != null) {
+ if (!f (Entry.entry_for<K,V> (current))) {
+ return false;
+ }
+ current = current.next;
+ } else if (_next == null) {
+ current = _map.first;
+ started = true;
+ } else {
+ current = _next;
+ if (current != null) {
+ _next = null;
+ _prev = null;
+ }
+ }
+ for (; current != null; current = current.next) {
+ if (!f (Entry.entry_for<K,V> (current))) {
+ return false;
+ }
+ }
+ return true;
+ }
+ }
+
+ 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>> {
+ public SubEntryIterator (TreeMap<K,V> map, Range<K,V> range) {
+ base (map, range);
+ }
+
+ public SubEntryIterator.pointing (TreeMap<K,V> map, Range<K,V> range, Node<K,V> node) {
+ base.pointing (map, range, node);
+ }
+
+ public new Map.Entry<K,V> get () {
+ assert (iterator != null);
+ return Entry.entry_for<K,V> (iterator.current);
+ }
+
+ public new void remove () {
+ unset ();
+ }
+
+ public bool foreach (ForallFunc<Map.Entry<K, V>> f) {
+ if (valid) {
+ if (!f (Entry.entry_for<K,V> (iterator.current))) {
+ return false;
+ }
+ }
+ while (iterator.next ()) {
+ if (!f (Entry.entry_for<K,V> (iterator.current))) {
+ return false;
+ }
+ }
+ return true;
}
}
- private class MapIterator<K,V> : NodeIterator<K,V>, Gee.MapIterator<K,V> {
+ private class MapIterator<K,V> : NodeIterator<K,V>, Gee.MapIterator<K,V>, BidirMapIterator<K,V> {
public MapIterator (TreeMap<K,V> map) {
base (map);
}
public K get_key () {
assert (stamp == _map.stamp);
- assert (current != null);
+ assert (valid);
return current.key;
}
public V get_value () {
assert (stamp == _map.stamp);
- assert (current != null);
+ assert (valid);
return current.value;
}
public void set_value (V value) {
assert (stamp == _map.stamp);
- assert (current != null);
+ assert (valid);
current.value = value;
}
+
+ public override bool read_only {
+ get {
+ return false;
+ }
+ }
+
+ public bool mutable {
+ get {
+ return true;
+ }
+ }
+ }
+
+ private class SubMapIterator<K,V> : SubNodeIterator<K,V>, Gee.MapIterator<K,V>, BidirMapIterator<K,V> {
+ public SubMapIterator (TreeMap<K,V> map, Range<K,V> range) {
+ base (map, range);
+ }
+
+ public K get_key () {
+ assert (valid);
+ return iterator.current.key;
+ }
+
+ public V get_value () {
+ assert (valid);
+ return iterator.current.value;
+ }
+
+ public void set_value (V value) {
+ assert (valid);
+ iterator.current.value = value;
+ }
+
+ public override bool read_only {
+ get {
+ return false;
+ }
+ }
+
+ public bool mutable {
+ get {
+ return true;
+ }
+ }
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-13 07:00:34 +0000