[libgee] Add has_next and first methods to the Iterator interface
- From: Didier 'Ptitjes' Villevalois <dvillevalois src gnome org>
- To: svn-commits-list gnome org
- Cc:
- Subject: [libgee] Add has_next and first methods to the Iterator interface
- Date: Tue, 15 Sep 2009 18:25:21 +0000 (UTC)
commit 5b2e267494ee7e20a02ab9e04ea1d984f20660c9
Author: Didier 'Ptitjes <ptitjes free fr>
Date: Mon Sep 14 20:51:06 2009 +0200
Add has_next and first methods to the Iterator interface
gee/arraylist.vala | 14 ++++++
gee/hashmap.vala | 102 +++++++++++++++++++++++--------------------
gee/hashmultiset.vala | 16 +++++++
gee/hashset.vala | 37 +++++++++++++---
gee/iterator.vala | 16 +++++++
gee/linkedlist.vala | 28 +++++++++---
gee/priorityqueue.vala | 53 +++++++++++++++++-----
gee/readonlycollection.vala | 8 +++
gee/treemap.vala | 38 +++++++++++++++-
gee/treeset.vala | 45 +++++++++++++++++--
tests/testcollection.vala | 65 +++++++++++++++++++++++++++-
11 files changed, 342 insertions(+), 80 deletions(-)
---
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
index 1bbe2d2..b07ea2b 100644
--- a/gee/arraylist.vala
+++ b/gee/arraylist.vala
@@ -263,6 +263,20 @@ public class Gee.ArrayList<G> : AbstractList<G> {
return (_index < _list._size);
}
+ public bool has_next () {
+ assert (_stamp == _list._stamp);
+ return (_index + 1 < _list._size);
+ }
+
+ public bool first () {
+ assert (_stamp == _list._stamp);
+ if (_list.size == 0) {
+ return false;
+ }
+ _index = 0;
+ return true;
+ }
+
public new G get () {
assert (_stamp == _list._stamp);
assert (_index >= 0);
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index f34f923..d98011e 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -281,43 +281,6 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
}
- private class KeyIterator<K,V> : Object, Iterator<K> {
- public HashMap<K,V> map {
- private set {
- _map = value;
- _stamp = _map._stamp;
- }
- }
-
- private HashMap<K,V> _map;
- private int _index = -1;
- private weak Node<K,V> _node;
-
- // concurrent modification protection
- private int _stamp;
-
- public KeyIterator (HashMap map) {
- this.map = map;
- }
-
- public bool next () {
- if (_node != null) {
- _node = _node.next;
- }
- while (_node == null && _index + 1 < _map._array_size) {
- _index++;
- _node = _map._nodes[_index];
- }
- return (_node != null);
- }
-
- public new K get () {
- assert (_stamp == _map._stamp);
- assert (_node != null);
- return _node.key;
- }
- }
-
private class ValueCollection<K,V> : AbstractCollection<V> {
public HashMap<K,V> map { private set; get; }
@@ -368,7 +331,7 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
}
}
- private class ValueIterator<K,V> : Object, Iterator<V> {
+ private abstract class NodeIterator<K,V> : Object {
public HashMap<K,V> map {
private set {
_map = value;
@@ -376,28 +339,71 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
}
}
- private HashMap<V,K> _map;
+ protected HashMap<K,V> _map;
private int _index = -1;
- private weak Node<K,V> _node;
+ protected weak Node<K,V> _node;
+ protected weak Node<K,V> _next;
// concurrent modification protection
- private int _stamp;
+ protected int _stamp;
- public ValueIterator (HashMap map) {
+ public NodeIterator (HashMap map) {
this.map = map;
}
public bool next () {
- if (_node != null) {
- _node = _node.next;
- }
- while (_node == null && _index + 1 < _map._array_size) {
- _index++;
- _node = _map._nodes[_index];
+ assert (_stamp == _map._stamp);
+ if (!has_next ()) {
+ return false;
}
+ _node = _next;
+ _next = null;
return (_node != null);
}
+ public bool has_next () {
+ assert (_stamp == _map._stamp);
+ if (_next == null) {
+ _next = _node;
+ if (_next != null) {
+ _next = _next.next;
+ }
+ while (_next == null && _index + 1 < _map._array_size) {
+ _index++;
+ _next = _map._nodes[_index];
+ }
+ }
+ return (_next != null);
+ }
+
+ public bool first () {
+ assert (_stamp == _map._stamp);
+ if (_map.size == 0) {
+ return false;
+ }
+ _index = -1;
+ _next = null;
+ return next ();
+ }
+ }
+
+ private class KeyIterator<K,V> : NodeIterator<K,V>, Iterator<K> {
+ public KeyIterator (HashMap map) {
+ base (map);
+ }
+
+ public new K get () {
+ assert (_stamp == _map._stamp);
+ assert (_node != null);
+ return _node.key;
+ }
+ }
+
+ private class ValueIterator<K,V> : NodeIterator<K,V>, Iterator<K> {
+ public ValueIterator (HashMap map) {
+ base (map);
+ }
+
public new V get () {
assert (_stamp == _map._stamp);
assert (_node != null);
diff --git a/gee/hashmultiset.vala b/gee/hashmultiset.vala
index c977426..33dc76e 100644
--- a/gee/hashmultiset.vala
+++ b/gee/hashmultiset.vala
@@ -120,6 +120,22 @@ public class Gee.HashMultiSet<G> : AbstractCollection<G>, MultiSet<G> {
return false;
}
+ public bool has_next () {
+ return _pending > 0 || _iter.has_next ();
+ }
+
+ public bool first () {
+ if (set._nitems == 0) {
+ return false;
+ }
+ _pending = 0;
+ if (_iter.first ()) {
+ var key = _iter.get ();
+ _pending = set._items.get (key) - 1;
+ }
+ return true;
+ }
+
public new G get () {
return _iter.get ();
}
diff --git a/gee/hashset.vala b/gee/hashset.vala
index 0763350..34103d8 100644
--- a/gee/hashset.vala
+++ b/gee/hashset.vala
@@ -211,6 +211,7 @@ public class Gee.HashSet<G> : AbstractSet<G> {
private HashSet<G> _set;
private int _index = -1;
private weak Node<G> _node;
+ private weak Node<G> _next;
// concurrent modification protection
private int _stamp = 0;
@@ -220,16 +221,40 @@ public class Gee.HashSet<G> : AbstractSet<G> {
}
public bool next () {
- if (_node != null) {
- _node = _node.next;
- }
- while (_node == null && _index + 1 < _set._array_size) {
- _index++;
- _node = _set._nodes[_index];
+ assert (_stamp == _set._stamp);
+ if (!has_next ()) {
+ return false;
}
+ _node = _next;
+ _next = null;
return (_node != null);
}
+ public bool has_next () {
+ assert (_stamp == _set._stamp);
+ if (_next == null) {
+ _next = _node;
+ if (_next != null) {
+ _next = _next.next;
+ }
+ while (_next == null && _index + 1 < _set._array_size) {
+ _index++;
+ _next = _set._nodes[_index];
+ }
+ }
+ return (_next != null);
+ }
+
+ public bool first () {
+ assert (_stamp == _set._stamp);
+ if (_set.size == 0) {
+ return false;
+ }
+ _index = -1;
+ _next = null;
+ return next ();
+ }
+
public new G get () {
assert (_stamp == _set._stamp);
assert (_node != null);
diff --git a/gee/iterator.vala b/gee/iterator.vala
index 41de156..2acaca3 100644
--- a/gee/iterator.vala
+++ b/gee/iterator.vala
@@ -1,6 +1,7 @@
/* iterator.vala
*
* Copyright (C) 2007-2008 Jürg Billeter
+ * Copyright (C) 2009 Didier Villevalois, Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -18,6 +19,7 @@
*
* Author:
* Jürg Billeter <j bitron ch>
+ * Maciej Piechotka <uzytkownik2 gmail com>
*/
/**
@@ -32,6 +34,20 @@ public interface Gee.Iterator<G> : GLib.Object {
public abstract bool next ();
/**
+ * Checks whether there is a next element in the iteration.
+ *
+ * @return true if the iterator has a next element
+ */
+ public abstract bool has_next ();
+
+ /**
+ * Rewinds to the first element in the iteration.
+ *
+ * @return true if the iterator has a first element
+ */
+ public abstract bool first ();
+
+ /**
* Returns the current element in the iteration.
*
* @return the current element in the iteration
diff --git a/gee/linkedlist.vala b/gee/linkedlist.vala
index 2572fc5..c01c8d7 100644
--- a/gee/linkedlist.vala
+++ b/gee/linkedlist.vala
@@ -393,7 +393,7 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
public Iterator (LinkedList<G> list) {
this._list = list;
- this.position = list._head;
+ this.position = null;
this._stamp = list._stamp;
}
@@ -402,13 +402,29 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
if (!this.started) {
this.started = true;
- return this.position != null;
- } else if (this.position.next == null) {
- return false;
- } else {
+ this.position = this._list._head;
+ } else if (this.position != null) {
this.position = this.position.next;
- return true;
}
+ return this.position != null;
+ }
+
+ public bool has_next () {
+ assert (this._stamp == this._list._stamp);
+
+ if (!this.started) {
+ return this._list._head != null;
+ } else if (this.position != null) {
+ return this.position.next != null;
+ }
+ return false;
+ }
+
+ public bool first () {
+ assert (this._stamp == this._list._stamp);
+ this.position = null;
+ this.started = false;
+ return next ();
}
public new G get () {
diff --git a/gee/priorityqueue.vala b/gee/priorityqueue.vala
index 7bcf503..3779934 100644
--- a/gee/priorityqueue.vala
+++ b/gee/priorityqueue.vala
@@ -760,6 +760,7 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
private bool from_type1_children = false;
private bool from_type2_child = false;
private unowned Node<G>? position;
+ private unowned Node<G>? _next;
private int stamp;
public Iterator (PriorityQueue<G> queue) {
@@ -770,44 +771,72 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
public bool next () {
assert (stamp == queue._stamp);
+ if (!has_next ()) {
+ return false;
+ }
+ position = _next;
+ _next = null;
+ return (position != null);
+ }
+
+ public bool has_next () {
+ assert (stamp == queue._stamp);
+ if (_next == null) {
+ _next = position;
+ if (!_has_next ()) {
+ _next = null;
+ }
+ }
+ return (_next != null);
+ }
+ private bool _has_next() {
if (!started) {
started = true;
- return position != null;
- } else if (position is Type1Node) {
- var node = position as Type1Node<G>;
+ return _next != null;
+ } else if (_next is Type1Node) {
+ var node = _next as Type1Node<G>;
if (!from_type1_children && node.type1_children_head != null) {
- position = node.type1_children_head;
+ _next = node.type1_children_head;
from_type1_children = false;
from_type2_child = false;
return true;
} else if (!from_type2_child && node.type2_child != null) {
- position = node.type2_child;
+ _next = node.type2_child;
from_type1_children = false;
from_type2_child = false;
return true;
} else if (node.brothers_next != null) {
- position = node.brothers_next;
+ _next = node.brothers_next;
return true;
}
from_type1_children = true;
- } else if (position is Type2Node) {
- var node = position as Type2Node<G>;
+ } else if (_next is Type2Node) {
+ var node = _next as Type2Node<G>;
if (!from_type1_children && node.type1_children_head != null) {
- position = node.type1_children_head;
+ _next = node.type1_children_head;
from_type1_children = false;
from_type2_child = false;
return true;
}
from_type2_child = true;
}
- if (position != queue._r) {
- position = position.parent;
- return next ();
+ if (_next != queue._r) {
+ _next = _next.parent;
+ return _has_next ();
}
return false;
}
+ public bool first () {
+ assert (stamp == queue._stamp);
+ position = queue._r;
+ started = false;
+ from_type1_children = false;
+ from_type2_child = false;
+ return next ();
+ }
+
public new G get () {
assert (stamp == queue._stamp);
assert (position != null);
diff --git a/gee/readonlycollection.vala b/gee/readonlycollection.vala
index b29f914..abaec4e 100644
--- a/gee/readonlycollection.vala
+++ b/gee/readonlycollection.vala
@@ -141,6 +141,14 @@ internal class Gee.ReadOnlyCollection<G> : Object, Iterable<G>, Collection<G> {
return false;
}
+ public bool has_next () {
+ return false;
+ }
+
+ public bool first () {
+ return false;
+ }
+
public new G? get () {
return null;
}
diff --git a/gee/treemap.vala b/gee/treemap.vala
index 56940be..fe7d4ff 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -471,13 +471,25 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
assert (stamp == _map.stamp);
if (current != null) {
current = current.next;
- } else if (!run){
+ } else if (state == KeyIterator.State.BEFORE_THE_BEGIN) {
run = true;
current = _map.first;
}
return current != null;
}
+ public bool has_next () {
+ assert (stamp == _map.stamp);
+ return (current == null && state == KeyIterator.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 new K get () {
assert (stamp == _map.stamp);
assert (current != null);
@@ -485,6 +497,11 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
}
private weak Node<K, V>? current;
+ private enum State {
+ BEFORE_THE_BEGIN,
+ PAST_THE_END
+ }
+ private KeyIterator.State state = KeyIterator.State.BEFORE_THE_BEGIN;
private bool run = false;
}
@@ -509,13 +526,25 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
assert (stamp == _map.stamp);
if (current != null) {
current = current.next;
- } else if (!run){
+ } else if (state == ValueIterator.State.BEFORE_THE_BEGIN) {
run = true;
current = _map.first;
}
return current != null;
}
+ public bool has_next () {
+ assert (stamp == _map.stamp);
+ return (current == null && state == ValueIterator.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 new V get () {
assert (stamp == _map.stamp);
assert (current != null);
@@ -523,6 +552,11 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
}
private weak Node<K, V>? current;
+ private enum State {
+ BEFORE_THE_BEGIN,
+ PAST_THE_END
+ }
+ private ValueIterator.State state = ValueIterator.State.BEFORE_THE_BEGIN;
private bool run = false;
}
}
diff --git a/gee/treeset.vala b/gee/treeset.vala
index e6a53e8..ba047b3 100644
--- a/gee/treeset.vala
+++ b/gee/treeset.vala
@@ -266,7 +266,7 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
* @inheritDoc
*/
public override Gee.Iterator<G> iterator () {
- return new Iterator<G> (this);
+ return new Iterator<G> (this);
}
[Compact]
@@ -336,13 +336,41 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
assert (stamp == _set.stamp);
if (current != null) {
current = current.next;
- } else if (!run){
- run = true;
- current = _set.first;
+ } else {
+ switch (state) {
+ case Iterator.State.BEFORE_THE_BEGIN:
+ current = _set.first;
+ break;
+ case Iterator.State.NORMAL: // After remove
+ current = _next;
+ _next = null;
+ _prev = null;
+ break;
+ case Iterator.State.PAST_THE_END:
+ break;
+ default:
+ assert_not_reached ();
+ }
}
+ state = current != null ? Iterator.State.NORMAL : Iterator.State.PAST_THE_END;
return current != null;
}
+ public bool has_next () {
+ assert (stamp == _set.stamp);
+ return (current == null && state == Iterator.State.BEFORE_THE_BEGIN) ||
+ (current == null && state == Iterator.State.NORMAL && _next != null) ||
+ (current != null && current.next != null);
+ }
+
+ public bool first () {
+ assert (stamp == _set.stamp);
+ current = _set.first;
+ _next = null;
+ _prev = null;
+ return current != null; // on false it is null anyway
+ }
+
public new G get () {
assert (stamp == _set.stamp);
assert (current != null);
@@ -350,7 +378,14 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
}
private weak Node<G>? current;
- private bool run = false;
+ private weak Node<G>? _next;
+ private weak Node<G>? _prev;
+ private enum State {
+ BEFORE_THE_BEGIN,
+ NORMAL,
+ PAST_THE_END
+ }
+ private Iterator.State state = Iterator.State.BEFORE_THE_BEGIN;
}
private Node<G>? root = null;
diff --git a/tests/testcollection.vala b/tests/testcollection.vala
index f37cd6d..295bb2c 100644
--- a/tests/testcollection.vala
+++ b/tests/testcollection.vala
@@ -55,7 +55,15 @@ public abstract class CollectionTests : Gee.TestCase {
public void test_iterator_returns_all_elements_once () {
// Check the collection exists
assert (test_collection != null);
+ bool has_next;
+ // Check with an empty collection
+ Iterator<string> iterator = test_collection.iterator ();
+ assert (! iterator.has_next ());
+ assert (! iterator.next ());
+ assert (! iterator.first ());
+
+ // Check for some elements in the collection
assert (test_collection.add ("one"));
assert (test_collection.add ("two"));
assert (test_collection.add ("three"));
@@ -66,7 +74,53 @@ public abstract class CollectionTests : Gee.TestCase {
bool one_found_once = true;
bool two_found_once = true;
bool three_found_once = true;
- foreach (string element in test_collection) {
+ iterator = test_collection.iterator ();
+ while (true) {
+ has_next = iterator.has_next ();
+ assert (has_next == iterator.next ());
+ if (! has_next) {
+ break;
+ }
+
+ string element = iterator.get ();
+ if (element == "one") {
+ if (one_found) {
+ one_found_once = false;
+ }
+ one_found = true;
+ } else if (element == "two") {
+ if (two_found) {
+ two_found_once = false;
+ }
+ two_found = true;
+ } else if (element == "three") {
+ if (three_found) {
+ three_found_once = false;
+ }
+ three_found = true;
+ }
+ }
+ has_next = iterator.has_next ();
+ assert (! has_next);
+ assert (has_next == iterator.next ());
+ assert (one_found);
+ assert (one_found_once);
+ assert (two_found);
+ assert (two_found_once);
+ assert (three_found);
+ assert (three_found_once);
+
+ // Do it twice to check first ()
+ assert (iterator.first ());
+
+ one_found = false;
+ two_found = false;
+ three_found = false;
+ one_found_once = true;
+ two_found_once = true;
+ three_found_once = true;
+ while (true) {
+ string element = iterator.get ();
if (element == "one") {
if (one_found) {
one_found_once = false;
@@ -83,7 +137,16 @@ public abstract class CollectionTests : Gee.TestCase {
}
three_found = true;
}
+
+ has_next = iterator.has_next ();
+ assert (has_next == iterator.next ());
+ if (! has_next) {
+ break;
+ }
}
+ has_next = iterator.has_next ();
+ assert (! has_next);
+ assert (has_next == iterator.next ());
assert (one_found);
assert (one_found_once);
assert (two_found);
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
