[libgee] Fix the iterators of the TreeMap and TreeSet implementations
- From: Didier Villevalois <dvillevalois src gnome org>
- To: svn-commits-list gnome org
- Cc:
- Subject: [libgee] Fix the iterators of the TreeMap and TreeSet implementations
- Date: Wed, 23 Sep 2009 18:33:16 +0000 (UTC)
commit 5aed214a1e6fd348b680c0eeef84cc37eaad1bf3
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date: Wed Sep 16 20:42:58 2009 +0200
Fix the iterators of the TreeMap and TreeSet implementations
gee/treemap.vala | 181 ++++++++++--------------------------------------------
gee/treeset.vala | 62 +++++--------------
2 files changed, 49 insertions(+), 194 deletions(-)
---
diff --git a/gee/treemap.vala b/gee/treemap.vala
index 7ce274a..6a9b574 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -569,13 +569,15 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
}
}
- private class KeyIterator<K,V> : Object, Gee.Iterator<K>, BidirIterator<K> {
- private TreeMap<K,V> _map;
+ private class NodeIterator<K,V> : Object {
+ protected TreeMap<K,V> _map;
// concurrent modification protection
- private int stamp;
+ protected int stamp;
- public KeyIterator (TreeMap<K,V> map) {
+ protected weak Node<K, V>? current;
+
+ public NodeIterator (TreeMap<K,V> map) {
_map = map;
stamp = _map.stamp;
}
@@ -583,17 +585,21 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
public bool next () {
assert (stamp == _map.stamp);
if (current != null) {
- current = current.next;
- } else if (state == KeyIterator.State.BEFORE_THE_BEGIN) {
- run = true;
+ if (current.next != null) {
+ current = current.next;
+ return true;
+ } else {
+ return false;
+ }
+ } else {
current = _map.first;
+ return current != null;
}
- return current != null;
}
public bool has_next () {
assert (stamp == _map.stamp);
- return (current == null && state == KeyIterator.State.BEFORE_THE_BEGIN) ||
+ return (current == null && _map.first != null) ||
(current != null && current.next != null);
}
@@ -606,18 +612,19 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
public bool previous () {
assert (stamp == _map.stamp);
if (current != null) {
- current = current.prev;
- } else if (state == KeyIterator.State.PAST_THE_END) {
- current = _map.last;
+ if (current.prev != null) {
+ current = current.prev;
+ return true;
+ } else {
+ return false;
+ }
}
- state = KeyIterator.State.BEFORE_THE_BEGIN;
- return current != null;
+ return false;
}
public bool has_previous () {
assert (stamp == _map.stamp);
- return (current == null && state == KeyIterator.State.PAST_THE_END) ||
- (current != null && current.prev != null);
+ return (current != null && current.prev != null);
}
public bool last () {
@@ -625,6 +632,12 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
current = _map.last;
return current != null; // on false it is null anyway
}
+ }
+
+ private class KeyIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<K>, BidirIterator<K> {
+ public KeyIterator (TreeMap<K,V> map) {
+ base (map);
+ }
public new K get () {
assert (stamp == _map.stamp);
@@ -635,71 +648,11 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
public void remove () {
assert_not_reached ();
}
-
- 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;
}
- private class ValueIterator<K,V> : Object, Gee.Iterator<V>, Gee.BidirIterator<V> {
- private TreeMap<K,V> _map;
-
- // concurrent modification protection
- private int stamp;
-
+ private class ValueIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<V>, Gee.BidirIterator<V> {
public ValueIterator (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 == 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 bool previous () {
- assert (stamp == _map.stamp);
- if (current != null) {
- current = current.prev;
- } else if (state == ValueIterator.State.PAST_THE_END) {
- current = _map.last;
- }
- state = ValueIterator.State.BEFORE_THE_BEGIN;
- return current != null;
- }
-
- public bool has_previous () {
- assert (stamp == _map.stamp);
- return (current == null && state == ValueIterator.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
+ base (map);
}
public new V get () {
@@ -711,71 +664,11 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
public void remove () {
assert_not_reached ();
}
-
- 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;
}
- 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;
-
+ private class EntryIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
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
+ base (map);
}
public new Map.Entry<K,V> get () {
@@ -787,13 +680,5 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
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;
}
}
diff --git a/gee/treeset.vala b/gee/treeset.vala
index c3aa9b9..f8836af 100644
--- a/gee/treeset.vala
+++ b/gee/treeset.vala
@@ -342,33 +342,21 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
assert (stamp == _set.stamp);
if (current != null) {
current = current.next;
+ } else if (!started) {
+ current = _set.first;
+ started = true;
} 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 ();
- }
+ current = _next;
+ _next = null;
+ _prev = null;
}
- state = current != null ? Iterator.State.NORMAL : Iterator.State.PAST_THE_END;
return current != null;
}
public bool has_next () {
assert (stamp == _set.stamp);
- if (_set.size == 0) {
- return false;
- }
- return (current == null && state == Iterator.State.BEFORE_THE_BEGIN) ||
- (current == null && state == Iterator.State.NORMAL && _next != null) ||
+ return (!started && _set.first != null) ||
+ (current == null && _next != null) ||
(current != null && current.next != null);
}
@@ -385,29 +373,16 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
if (current != null) {
current = current.prev;
} else {
- switch (state) {
- case Iterator.State.BEFORE_THE_BEGIN:
- break;
- case Iterator.State.NORMAL: // After remove
- current = _prev;
- _next = null;
- _prev = null;
- break;
- case Iterator.State.PAST_THE_END:
- current = _set.last;
- break;
- default:
- assert_not_reached ();
- }
+ current = _prev;
+ _next = null;
+ _prev = null;
}
- state = current != null ? Iterator.State.NORMAL : Iterator.State.BEFORE_THE_BEGIN;
return current != null;
}
public bool has_previous () {
assert (stamp == _set.stamp);
- return (current == null && state == Iterator.State.PAST_THE_END) ||
- (current == null && state == Iterator.State.NORMAL && _prev != null) ||
+ return (current == null && _prev != null) ||
(current != null && current.prev != null);
}
@@ -436,15 +411,10 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
assert (stamp == _set.stamp);
}
- private weak Node<G>? current;
- 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 weak Node<G>? current = null;
+ private weak Node<G>? _next = null;
+ private weak Node<G>? _prev = null;
+ private bool started = false;
}
private Node<G>? root = null;
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]