[libgee] Introduce the Map.Entry<K, V> class and the Map.entries property
- From: Didier Villevalois <dvillevalois src gnome org>
- To: svn-commits-list gnome org
- Cc:
- Subject: [libgee] Introduce the Map.Entry<K, V> class and the Map.entries property
- Date: Sun, 20 Sep 2009 15:42:59 +0000 (UTC)
commit 93ab6ba6e32056ef9f15ff8ce844143c207c99b6
Author: Didier 'Ptitjes <ptitjes free fr>
Date: Sun Sep 20 16:25:17 2009 +0200
Introduce the Map.Entry<K,V> class and the Map.entries property
We also use Map.entries to optimize the implementations of
set_all, has_all and HashMultiMap by avoiding the common pattern:
iterate on keys and for each key get the associated value.
gee/abstractmap.vala | 13 +++-
gee/hashmap.vala | 96 ++++++++++++++++++++++++++++++
gee/hashmultimap.vala | 10 ++--
gee/map.vala | 20 ++++++
gee/readonlymap.vala | 9 +++
gee/treemap.vala | 155 +++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 294 insertions(+), 9 deletions(-)
---
diff --git a/gee/abstractmap.vala b/gee/abstractmap.vala
index e753795..275ceea 100644
--- a/gee/abstractmap.vala
+++ b/gee/abstractmap.vala
@@ -57,6 +57,11 @@ public abstract class Gee.AbstractMap<K,V> : Object, Map<K,V> {
/**
* @inheritDoc
*/
+ public abstract Set<Map.Entry<K,V>> entries { owned get; }
+
+ /**
+ * @inheritDoc
+ */
public abstract bool has_key (K key);
/**
@@ -107,8 +112,8 @@ public abstract class Gee.AbstractMap<K,V> : Object, Map<K,V> {
* @inheritDoc
*/
public virtual void set_all (Map<K,V> map) {
- foreach (K key in map.keys) {
- set (key, map.get (key));
+ foreach (Map.Entry<K,V> entry in map.entries) {
+ set (entry.key, entry.value);
}
}
@@ -134,8 +139,8 @@ public abstract class Gee.AbstractMap<K,V> : Object, Map<K,V> {
* @inheritDoc
*/
public virtual bool has_all (Map<K,V> map) {
- foreach (K key in map.keys) {
- if (!has (key, map.get (key))) {
+ foreach (Map.Entry<K,V> entry in map.entries) {
+ if (!has (entry.key, entry.value)) {
return false;
}
}
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index 31e359e..300dead 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -60,6 +60,15 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
}
/**
+ * @inheritDoc
+ */
+ public override Set<Map.Entry<K,V>> entries {
+ owned get {
+ return new EntrySet<K,V> (this);
+ }
+ }
+
+ /**
* The keys' hash function.
*/
public HashFunc key_hash_func { private set; get; }
@@ -242,11 +251,38 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
public V value;
public Node<K,V> next;
public uint key_hash;
+ public unowned Map.Entry<K,V>? entry;
public Node (owned K k, owned V v, uint hash) {
key = (owned) k;
value = (owned) v;
key_hash = hash;
+ entry = 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) {
+ result = new Entry<K,V> (node);
+ node.entry = result;
+ result.add_weak_pointer (&node.entry);
+ }
+ return result;
+ }
+
+ public Entry (Node<K,V> node) {
+ _node = node;
+ }
+
+ public override K key { get { return _node.key; } }
+
+ public override V value {
+ get { return _node.value; }
+ set { _node.value = value; }
}
}
@@ -345,6 +381,50 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
}
}
+ private class EntrySet<K,V> : AbstractSet<Map.Entry<K, V>> {
+ private HashMap<K,V> _map;
+
+ public EntrySet (HashMap<K,V> map) {
+ _map = map;
+ }
+
+ public override Iterator<Map.Entry<K, V>> iterator () {
+ return new EntryIterator<K,V> (_map);
+ }
+
+ public override int size {
+ get { return _map.size; }
+ }
+
+ public override bool add (Map.Entry<K, V> entry) {
+ assert_not_reached ();
+ }
+
+ public override void clear () {
+ assert_not_reached ();
+ }
+
+ public override bool remove (Map.Entry<K, V> entry) {
+ assert_not_reached ();
+ }
+
+ public override bool contains (Map.Entry<K, V> entry) {
+ return _map.has (entry.key, entry.value);
+ }
+
+ public override bool add_all (Collection<Map.Entry<K, V>> entries) {
+ assert_not_reached ();
+ }
+
+ public override bool remove_all (Collection<Map.Entry<K, V>> entries) {
+ assert_not_reached ();
+ }
+
+ public override bool retain_all (Collection<Map.Entry<K, V>> entries) {
+ assert_not_reached ();
+ }
+ }
+
private abstract class NodeIterator<K,V> : Object {
protected HashMap<K,V> _map;
private int _index = -1;
@@ -460,5 +540,21 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
assert_not_reached ();
}
}
+
+ private class EntryIterator<K,V> : NodeIterator<K,V>, Iterator<Map.Entry<K,V>> {
+ public EntryIterator (HashMap map) {
+ base (map);
+ }
+
+ public new Map.Entry<K,V> get () {
+ assert (_stamp == _map._stamp);
+ assert (_node != null);
+ return Entry<K,V>.entry_for<K,V> (_node);
+ }
+
+ public void remove () {
+ assert_not_reached ();
+ }
+ }
}
diff --git a/gee/hashmultimap.vala b/gee/hashmultimap.vala
index 0c46a10..25fa8ac 100644
--- a/gee/hashmultimap.vala
+++ b/gee/hashmultimap.vala
@@ -67,9 +67,9 @@ public class Gee.HashMultiMap<K,V> : GLib.Object, MultiMap<K,V> {
public MultiSet<K> get_all_keys () {
MultiSet<K> result = new HashMultiSet<K> (_key_hash_func, _key_equal_func);
- foreach (var key in _items.keys) {
- for (int i = 0; i < _items.get (key).size; i++) {
- result.add (key);
+ foreach (var entry in _items.entries) {
+ for (int i = 0; i < entry.value.size; i++) {
+ result.add (entry.key);
}
}
return result;
@@ -77,8 +77,8 @@ public class Gee.HashMultiMap<K,V> : GLib.Object, MultiMap<K,V> {
public Collection<V> get_values () {
var result = new ArrayList<V> (_value_equal_func);
- foreach (var key in _items.keys) {
- foreach (var value in _items.get (key)) {
+ foreach (var entry in _items.entries) {
+ foreach (var value in entry.value) {
result.add (value);
}
}
diff --git a/gee/map.vala b/gee/map.vala
index e98e995..733c2c1 100644
--- a/gee/map.vala
+++ b/gee/map.vala
@@ -45,6 +45,26 @@ public interface Gee.Map<K,V> : GLib.Object {
public abstract Collection<V> values { owned get; }
/**
+ * The read-only view of the entries of this map.
+ */
+ public abstract Set<Entry<K,V>> entries { owned get; }
+
+ /**
+ * An entry of a map.
+ */
+ public abstract class Entry<K,V> : Object {
+ /**
+ * The key of this entry.
+ */
+ public abstract K key { get; }
+
+ /**
+ * The value of this entry.
+ */
+ public abstract V value { get; set; }
+ }
+
+ /**
* Determines whether this map has the specified key.
*
* @param key the key to locate in the map
diff --git a/gee/readonlymap.vala b/gee/readonlymap.vala
index ddcc47e..0163c9a 100644
--- a/gee/readonlymap.vala
+++ b/gee/readonlymap.vala
@@ -65,6 +65,15 @@ internal class Gee.ReadOnlyMap<K,V> : Object, Map<K,V> {
}
}
+ /**
+ * @inheritDoc
+ */
+ public Set<Map.Entry<K,V>> entries {
+ owned get {
+ return _map.entries;
+ }
+ }
+
private Map<K,V> _map;
/**
diff --git a/gee/treemap.vala b/gee/treemap.vala
index d4f807b..32c6a70 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -58,6 +58,15 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
}
/**
+ * @inheritDoc
+ */
+ public override Set<Map.Entry<K,V>> entries {
+ owned get {
+ return new EntrySet<K,V> (this);
+ }
+ }
+
+ /**
* The keys' comparator function.
*/
public CompareFunc key_compare_func { private set; get; }
@@ -367,6 +376,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
public Node<K, V>? right;
public weak Node<K, V>? prev;
public weak Node<K, V>? next;
+ public unowned Map.Entry<K,V>? entry;
}
private Node<K, V>? root = null;
@@ -374,6 +384,31 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
private weak Node<K, V>? last = null;
private int stamp = 0;
+ 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) {
+ result = new Entry<K,V> (node);
+ node.entry = result;
+ result.add_weak_pointer (&node.entry);
+ }
+ return result;
+ }
+
+ public Entry (Node<K,V> node) {
+ _node = node;
+ }
+
+ public override K key { get { return _node.key; } }
+
+ public override V value {
+ get { return _node.value; }
+ set { _node.value = value; }
+ }
+ }
+
private class KeySet<K,V> : AbstractSet<K> {
private TreeMap<K,V> _map;
@@ -468,6 +503,50 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
}
}
+ private class EntrySet<K,V> : AbstractSet<Map.Entry<K, V>> {
+ private TreeMap<K,V> _map;
+
+ public EntrySet (TreeMap<K,V> map) {
+ _map = map;
+ }
+
+ public override Iterator<Map.Entry<K, V>> iterator () {
+ return new EntryIterator<K,V> (_map);
+ }
+
+ public override int size {
+ get { return _map.size; }
+ }
+
+ public override bool add (Map.Entry<K, V> entry) {
+ assert_not_reached ();
+ }
+
+ public override void clear () {
+ assert_not_reached ();
+ }
+
+ public override bool remove (Map.Entry<K, V> entry) {
+ assert_not_reached ();
+ }
+
+ public override bool contains (Map.Entry<K, V> entry) {
+ return _map.has (entry.key, entry.value);
+ }
+
+ public override bool add_all (Collection<Map.Entry<K, V>> entries) {
+ assert_not_reached ();
+ }
+
+ public override bool remove_all (Collection<Map.Entry<K, V>> entries) {
+ assert_not_reached ();
+ }
+
+ public override bool retain_all (Collection<Map.Entry<K, V>> entries) {
+ assert_not_reached ();
+ }
+ }
+
private class KeyIterator<K,V> : Object, Gee.Iterator<K>, BidirIterator<K> {
private TreeMap<K,V> _map;
@@ -619,4 +698,80 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
private ValueIterator.State state = ValueIterator.State.BEFORE_THE_BEGIN;
private bool run = false;
}
+
+ private class EntryIterator<K,V> : Object, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
+ private TreeMap<K,V> _map;
+
+ // concurrent modification protection
+ private int stamp;
+
+ public EntryIterator (TreeMap<K,V> map) {
+ _map = map;
+ stamp = _map.stamp;
+ }
+
+ public bool next () {
+ assert (stamp == _map.stamp);
+ if (current != null) {
+ current = current.next;
+ } else if (state == EntryIterator.State.BEFORE_THE_BEGIN) {
+ run = true;
+ current = _map.first;
+ }
+ return current != null;
+ }
+
+ public bool has_next () {
+ assert (stamp == _map.stamp);
+ return (current == null && state == EntryIterator.State.BEFORE_THE_BEGIN) ||
+ (current != null && current.next != null);
+ }
+
+ public bool first () {
+ assert (stamp == _map.stamp);
+ current = _map.first;
+ return current != null; // on false it is null anyway
+ }
+
+ public bool previous () {
+ assert (stamp == _map.stamp);
+ if (current != null) {
+ current = current.prev;
+ } else if (state == EntryIterator.State.PAST_THE_END) {
+ current = _map.last;
+ }
+ state = EntryIterator.State.BEFORE_THE_BEGIN;
+ return current != null;
+ }
+
+ public bool has_previous () {
+ assert (stamp == _map.stamp);
+ return (current == null && state == EntryIterator.State.PAST_THE_END) ||
+ (current != null && current.prev != null);
+ }
+
+ public bool last () {
+ assert (stamp == _map.stamp);
+ current = _map.last;
+ return current != null; // on false it is null anyway
+ }
+
+ public new Map.Entry<K,V> get () {
+ assert (stamp == _map.stamp);
+ assert (current != null);
+ return Entry<K,V>.entry_for<K,V> (current);
+ }
+
+ public void remove () {
+ assert_not_reached ();
+ }
+
+ private weak Node<K, V>? current;
+ private enum State {
+ BEFORE_THE_BEGIN,
+ PAST_THE_END
+ }
+ private EntryIterator.State state = EntryIterator.State.BEFORE_THE_BEGIN;
+ private bool run = false;
+ }
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]