From 0df670e36816c285e793f6c73fb5038acc3c1050 Mon Sep 17 00:00:00 2001 From: Maciej Piechotka Date: Mon, 27 Aug 2012 23:37:29 -0700 Subject: [PATCH] Allow early termination of iteration --- gee/abstractcollection.vala | 4 +- gee/abstractmap.vala | 4 +- gee/abstractmultimap.vala | 22 ++++++----- gee/abstractmultiset.vala | 35 ++++++++++++----- gee/arraylist.vala | 12 ++++-- gee/arrayqueue.vala | 12 ++++-- gee/concurrentlist.vala | 14 +++++-- gee/hashmap.vala | 60 +++++++++++++++++++---------- gee/hashset.vala | 14 +++++-- gee/hazardpointer.vala | 2 +- gee/linkedlist.vala | 7 +++- gee/mapiterator.vala | 19 ++++++--- gee/priorityqueue.vala | 17 ++++++--- gee/readonlycollection.vala | 8 ++-- gee/readonlymap.vala | 4 +- gee/traversable.vala | 16 +++++--- gee/treemap.vala | 93 ++++++++++++++++++++++++++++++++------------- gee/treeset.vala | 28 ++++++++++---- gee/unfolditerator.vala | 23 +++++++---- tests/testcollection.vala | 4 +- tests/testmap.vala | 4 +- 21 files changed, 270 insertions(+), 132 deletions(-) diff --git a/gee/abstractcollection.vala b/gee/abstractcollection.vala index 5476541..0e72fff 100644 --- a/gee/abstractcollection.vala +++ b/gee/abstractcollection.vala @@ -66,8 +66,8 @@ public abstract class Gee.AbstractCollection : Object, Traversable, Iterab */ public abstract Iterator iterator (); - public virtual void foreach (ForallFunc f) { - iterator ().foreach (f); + public virtual bool foreach (ForallFunc f) { + return iterator ().foreach (f); } public virtual Iterator stream (owned StreamFunc f) { diff --git a/gee/abstractmap.vala b/gee/abstractmap.vala index 849612e..cd761b8 100644 --- a/gee/abstractmap.vala +++ b/gee/abstractmap.vala @@ -118,8 +118,8 @@ public abstract class Gee.AbstractMap : Object, Traversable> /** * {@inheritDoc} */ - public virtual void foreach (ForallFunc> f) { - iterator ().foreach (f); + public virtual bool foreach (ForallFunc> f) { + return iterator ().foreach (f); } /** diff --git a/gee/abstractmultimap.vala b/gee/abstractmultimap.vala index 441dab3..4056633 100644 --- a/gee/abstractmultimap.vala +++ b/gee/abstractmultimap.vala @@ -251,14 +251,16 @@ public abstract class Gee.AbstractMultiMap : Object, MultiMap { return outer.get_key (); } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { if (inner != null && outer.valid) { - K key = outer.get_key (); - inner.foreach ((v) => {f (key);}); + K key = outer.get_key (); + if (!inner.foreach ((v) => {return f (key);})) { + return false; + } outer.next (); } - outer.foreach ((key, col) => { - col.foreach ((v) => {f (key);}); + return outer.foreach ((key, col) => { + return col.foreach ((v) => {return f (key);}); }); } } @@ -273,13 +275,15 @@ public abstract class Gee.AbstractMultiMap : Object, MultiMap { return inner.get (); } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { if (inner != null && outer.valid) { - inner.foreach (f); + if (!inner.foreach (f)) { + return false; + } outer.next (); } - outer.foreach ((key, col) => { - col.foreach (f); + return outer.foreach ((key, col) => { + return col.foreach (f); }); } } diff --git a/gee/abstractmultiset.vala b/gee/abstractmultiset.vala index 39915d8..1be4fd4 100644 --- a/gee/abstractmultiset.vala +++ b/gee/abstractmultiset.vala @@ -161,17 +161,32 @@ public abstract class Gee.AbstractMultiSet : AbstractCollection, MultiSet< } } - public void foreach (ForallFunc f) { - if(!_removed && _iter.valid) - f(_iter.get_key()); - if(_iter.valid) - for(int i = _pending - 1; i > 0; --i) - f(_iter.get_key()); - while(_iter.next()) - for(int i = _iter.get_value(); i > 0; --i) - f(_iter.get_key()); - _pending = 0; + public bool foreach (ForallFunc f) { + if (_iter.valid) { + if (!_removed) { + if (!f(_iter.get_key())) { + return false; + } + } + for(int i = _pending - 1; i >= 0; --i) { + if (!f(_iter.get_key())) { + _pending = i; + return false; + } + } + } + while(_iter.next()) { + for(int i = _iter.get_value() - 1; i >= 0; --i) { + if (!f(_iter.get_key())) { + _removed = false; + _pending = i; + return false; + } + } + } _removed = false; + _pending = 0; + return true; } } } diff --git a/gee/arraylist.vala b/gee/arraylist.vala index 23610f5..d6254e8 100644 --- a/gee/arraylist.vala +++ b/gee/arraylist.vala @@ -389,15 +389,19 @@ public class Gee.ArrayList : AbstractBidirList { } } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { assert (_stamp == _list._stamp); - if (_index < 0 || _removed) + if (_index < 0 || _removed) { _index++; + } while (_index < _list._size) { - f (_list._items[_index]); + if (!f (_list._items[_index])) { + return false; + } _index++; } - _index = _list._size; + _index = _list._size - 1; + return true; } } } diff --git a/gee/arrayqueue.vala b/gee/arrayqueue.vala index 6ab67ce..9775df2 100644 --- a/gee/arrayqueue.vala +++ b/gee/arrayqueue.vala @@ -312,15 +312,19 @@ public class Gee.ArrayQueue : Gee.AbstractQueue, Deque { public bool read_only { get {return false;} } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { assert (_queue._stamp == _stamp); - if(!valid) { + if (!valid) { _offset++; _removed = false; } - for(int i = _offset; i < _queue._length; i++) { - f (_queue._items[(_queue._start + i) % _queue._items.length]); + for (int i = _offset; i < _queue._length; i++) { + if (!f (_queue._items[(_queue._start + i) % _queue._items.length])) { + _offset = i; + return false; + } } + return true; } private ArrayQueue _queue; diff --git a/gee/concurrentlist.vala b/gee/concurrentlist.vala index 14ec37f..f1c9126 100644 --- a/gee/concurrentlist.vala +++ b/gee/concurrentlist.vala @@ -339,10 +339,13 @@ public class Gee.ConcurrentList : AbstractList { _index++; } - public new void foreach (ForallFunc f) { + public new bool foreach (ForallFunc f) { HazardPointer.Context ctx = new HazardPointer.Context (); - if (_started && !_removed) - f (HazardPointer.get_pointer (&_curr._data)); + if (_started && !_removed) { + if (!f (HazardPointer.get_pointer (&_curr._data))) { + return false; + } + } Node? _old_prev = _removed ? _prev : null; while (Node.proceed (ref _prev, ref _curr)) { if (_removed) @@ -350,8 +353,11 @@ public class Gee.ConcurrentList : AbstractList { _removed = false; _started = true; _index++; - f (HazardPointer.get_pointer (&_curr._data)); + if (!f (HazardPointer.get_pointer (&_curr._data))) { + return false; + } } + return true; } private bool _started; diff --git a/gee/hashmap.vala b/gee/hashmap.vala index 79f971a..da06f72 100644 --- a/gee/hashmap.vala +++ b/gee/hashmap.vala @@ -551,22 +551,28 @@ public class Gee.HashMap : Gee.AbstractMap { assert_not_reached (); } - public void foreach(ForallFunc f) { + public bool foreach(ForallFunc f) { if (_node != null) { - f(_node.key); - if(_next == null) + if (!f(_node.key)) { + return false; + } + if(_next == null) { _next = _node.next; + } } do { while(_next != null) { _node = _next; - f(_node.key); + if (!f(_node.key)) { + return false; + } _next = _next.next; } - if (_index + 1 < _map._array_size) + if (_index + 1 < _map._array_size) { _next = _map._nodes[++_index]; - else - break; + } else { + return true; + } } while(true); } } @@ -632,22 +638,28 @@ public class Gee.HashMap : Gee.AbstractMap { assert_not_reached (); } - public void foreach(ForallFunc f) { + public bool foreach(ForallFunc f) { if (_node != null) { - f(_node.value); - if(_next == null) + if (!f(_node.value)) { + return false; + } + if(_next == null) { _next = _node.next; + } } do { while(_next != null) { _node = _next; - f(_node.value); + if (!f(_node.value)) { + return false; + } _next = _next.next; } - if (_index + 1 < _map._array_size) + if (_index + 1 < _map._array_size) { _next = _map._nodes[++_index]; - else - break; + } else { + return true; + } } while(true); } } @@ -667,22 +679,28 @@ public class Gee.HashMap : Gee.AbstractMap { assert_not_reached (); } - public void foreach(ForallFunc> f) { + public bool foreach(ForallFunc> f) { if (_node != null) { - f(Entry.entry_for (_node)); - if(_next == null) + if (!f(Entry.entry_for (_node))) { + return false; + } + if(_next == null) { _next = _node.next; + } } do { while(_next != null) { _node = _next; - f(Entry.entry_for (_node)); + if (!f(Entry.entry_for (_node))) { + return false; + } _next = _next.next; } - if (_index + 1 < _map._array_size) + if (_index + 1 < _map._array_size) { _next = _map._nodes[++_index]; - else - break; + } else { + return true; + } } while(true); } } diff --git a/gee/hashset.vala b/gee/hashset.vala index 21fefdc..07da4f7 100644 --- a/gee/hashset.vala +++ b/gee/hashset.vala @@ -288,20 +288,26 @@ public class Gee.HashSet : AbstractSet { } } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { assert (_stamp == _set._stamp); - if (_node != null) - f (_node.key); + if (_node != null) { + if (!f (_node.key)) { + return false; + } + } while (_index + 1 < _set._array_size || _next != null) { if (_next != null) { _node = _next; - f (_node.key); + if (!f (_node.key)) { + return false; + } _next = _node.next; } else { _index++; _next = _set._nodes[_index]; } } + return false; } } } diff --git a/gee/hazardpointer.vala b/gee/hazardpointer.vala index d6dd7d1..8e548e1 100644 --- a/gee/hazardpointer.vala +++ b/gee/hazardpointer.vala @@ -495,7 +495,7 @@ public class Gee.HazardPointer { // FIXME: Make it a struct Collection> temp = new ArrayList> (); _queue.drain (temp); _queue_mutex.unlock (); - temp.foreach ((x) => {_global_to_free.add_all (x);}); + temp.foreach ((x) => {_global_to_free.add_all (x); return true;}); } try_free (_global_to_free); } diff --git a/gee/linkedlist.vala b/gee/linkedlist.vala index 2877e32..e20f377 100644 --- a/gee/linkedlist.vala +++ b/gee/linkedlist.vala @@ -606,7 +606,7 @@ public class Gee.LinkedList : AbstractBidirList, Queue, Deque { } } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { assert (_stamp == _list._stamp); if (!started) { position = _list._head; @@ -615,10 +615,13 @@ public class Gee.LinkedList : AbstractBidirList, Queue, Deque { } removed = false; while (position != null) { - f (position.data); + if (!f (position.data)) { + return false; + } position = position.next; } position = _list._tail; + return true; } } diff --git a/gee/mapiterator.vala b/gee/mapiterator.vala index a098b1d..ae83fcf 100644 --- a/gee/mapiterator.vala +++ b/gee/mapiterator.vala @@ -23,7 +23,7 @@ namespace Gee { public delegate A FoldMapFunc (K k, V v, owned A a); - public delegate void ForallMapFunc (K k, V v); + public delegate bool ForallMapFunc (K k, V v); } /** @@ -128,11 +128,18 @@ public interface Gee.MapIterator : Object { * Operation moves the iterator to last element in iteration. If iterator * points at some element it will be included in iteration. */ - public new virtual void foreach (ForallMapFunc f) { - if (valid) - f (get_key (), get_value ()); - while (next ()) - f (get_key (), get_value ()); + public new virtual bool foreach (ForallMapFunc f) { + if (valid) { + if (!f (get_key (), get_value ())) { + return false; + } + } + while (next ()) { + if (!f (get_key (), get_value ())) { + return false; + } + } + return true; } } diff --git a/gee/priorityqueue.vala b/gee/priorityqueue.vala index ba8b185..413f8c8 100644 --- a/gee/priorityqueue.vala +++ b/gee/priorityqueue.vala @@ -1036,11 +1036,18 @@ public class Gee.PriorityQueue : Gee.AbstractQueue { } } - public void foreach (ForallFunc f) { - if (valid) - f (position.data); - while (next ()) - f (position.data); + public bool foreach (ForallFunc f) { + if (valid) { + if (!f (position.data)) { + return false; + } + } + while (next ()) { + if (!f (position.data)) { + return false; + } + } + return true; } } } diff --git a/gee/readonlycollection.vala b/gee/readonlycollection.vala index fcf76f4..9f5823f 100644 --- a/gee/readonlycollection.vala +++ b/gee/readonlycollection.vala @@ -69,8 +69,8 @@ internal class Gee.ReadOnlyCollection : Object, Traversable, Iterable, /** * {@inheritDoc} */ - public void foreach (ForallFunc f) { - _collection.foreach (f); + public bool foreach (ForallFunc f) { + return _collection.foreach (f); } /** @@ -210,8 +210,8 @@ internal class Gee.ReadOnlyCollection : Object, Traversable, Iterable, get { return typeof (G); } } - public void foreach (ForallFunc f) { - _iter.foreach (f); + public bool foreach (ForallFunc f) { + return _iter.foreach (f); } public Gee.Iterator stream (owned StreamFunc f) { diff --git a/gee/readonlymap.vala b/gee/readonlymap.vala index 8921244..4f126cc 100644 --- a/gee/readonlymap.vala +++ b/gee/readonlymap.vala @@ -225,8 +225,8 @@ internal class Gee.ReadOnlyMap : Object, Traversable>, Itera /** * {@inheritDoc} */ - public void foreach (ForallFunc> f) { - _map.foreach (f); + public bool foreach (ForallFunc> f) { + return _map.foreach (f); } /** diff --git a/gee/traversable.vala b/gee/traversable.vala index 841ab26..ac757c5 100644 --- a/gee/traversable.vala +++ b/gee/traversable.vala @@ -22,7 +22,7 @@ namespace Gee { public delegate A FoldFunc (owned G g, owned A a); - public delegate void ForallFunc (owned G g); + public delegate bool ForallFunc (owned G g); public delegate Lazy? UnfoldFunc (); public delegate Traversable.Stream StreamFunc (Traversable.Stream state, owned Lazy? g, out Lazy? lazy); public delegate A MapFunc (owned G g); @@ -52,13 +52,17 @@ namespace Gee { [GenericAccessors] public interface Gee.Traversable : Object { /** - * Apply function to each element returned by iterator. + * Apply function to each element returned by iterator untill last element + * or function return ''false''. * * ''{@link Iterator} implementation:'' Operation moves the iterator - * to last element in iteration. If iterator points at some element it - * will be included in iteration. + * to last element in iteration or the first element that returned ''false''. + * If iterator points at some element it will be included in iteration. + * + * @return ''false'' if the argument returned ''false'' at last invocation and + * ''true'' otherwise. */ - public new abstract void foreach (ForallFunc f); + public new abstract bool foreach (ForallFunc f); /** * Stream function is an abstract function allowing writing many @@ -179,7 +183,7 @@ public interface Gee.Traversable : Object { */ public virtual A fold (FoldFunc f, owned A seed) { - this.foreach ((item) => {seed = f ((owned) item, (owned) seed);}); + this.foreach ((item) => {seed = f ((owned) item, (owned) seed); return true; }); return (owned) seed; } diff --git a/gee/treemap.vala b/gee/treemap.vala index c2093d7..9ee094e 100644 --- a/gee/treemap.vala +++ b/gee/treemap.vala @@ -1639,9 +1639,11 @@ public class Gee.TreeMap : Gee.AbstractBidirSortedMap { return current.key; } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { if (current != null) { - f (current.key); + if (!f (current.key)) { + return false; + } current = current.next; } else if (_next == null) { current = _map.first; @@ -1653,8 +1655,12 @@ public class Gee.TreeMap : Gee.AbstractBidirSortedMap { _prev = null; } } - for (; current != null; current = current.next) - f (current.key); + for (; current != null; current = current.next) { + if (!f (current.key)) { + return false; + } + } + return true; } } @@ -1672,11 +1678,18 @@ public class Gee.TreeMap : Gee.AbstractBidirSortedMap { return iterator.current.key; } - public void foreach (ForallFunc f) { - if (valid) - f (iterator.current.key); - while (iterator.next ()) - f (iterator.current.key); + public bool foreach (ForallFunc f) { + if (valid) { + if (!f (iterator.current.key)) { + return false; + } + } + while (iterator.next ()) { + if (!f (iterator.current.key)) { + return false; + } + } + return true; } } @@ -1695,9 +1708,11 @@ public class Gee.TreeMap : Gee.AbstractBidirSortedMap { return current.value; } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { if (current != null) { - f (current.key); + if (!f (current.key)) { + return false; + } current = current.next; } else if (_next == null) { current = _map.first; @@ -1709,8 +1724,12 @@ public class Gee.TreeMap : Gee.AbstractBidirSortedMap { _prev = null; } } - for (; current != null; current = current.next) - f (current.key); + for (; current != null; current = current.next) { + if (!f (current.key)) { + return false; + } + } + return true; } } @@ -1728,11 +1747,18 @@ public class Gee.TreeMap : Gee.AbstractBidirSortedMap { return iterator.current.value; } - public void foreach (ForallFunc f) { - if (valid) - f (iterator.current.key); - while (iterator.next ()) - f (iterator.current.key); + public bool foreach (ForallFunc f) { + if (valid) { + if (!f (iterator.current.key)) { + return false; + } + } + while (iterator.next ()) { + if (!f (iterator.current.key)) { + return false; + } + } + return true; } } @@ -1755,9 +1781,11 @@ public class Gee.TreeMap : Gee.AbstractBidirSortedMap { unset (); } - public void foreach (ForallFunc> f) { + public bool foreach (ForallFunc> f) { if (current != null) { - f (Entry.entry_for (current)); + if (!f (Entry.entry_for (current))) { + return false; + } current = current.next; } else if (_next == null) { current = _map.first; @@ -1769,8 +1797,12 @@ public class Gee.TreeMap : Gee.AbstractBidirSortedMap { _prev = null; } } - for (; current != null; current = current.next) - f (Entry.entry_for (current)); + for (; current != null; current = current.next) { + if (!f (Entry.entry_for (current))) { + return false; + } + } + return true; } } @@ -1792,11 +1824,18 @@ public class Gee.TreeMap : Gee.AbstractBidirSortedMap { unset (); } - public void foreach (ForallFunc> f) { - if (valid) - f (Entry.entry_for (iterator.current)); - while (iterator.next ()) - f (Entry.entry_for (iterator.current)); + public bool foreach (ForallFunc> f) { + if (valid) { + if (!f (Entry.entry_for (iterator.current))) { + return false; + } + } + while (iterator.next ()) { + if (!f (Entry.entry_for (iterator.current))) { + return false; + } + } + return true; } } diff --git a/gee/treeset.vala b/gee/treeset.vala index 8773da1..367c55e 100644 --- a/gee/treeset.vala +++ b/gee/treeset.vala @@ -716,19 +716,24 @@ public class Gee.TreeSet : AbstractBidirSortedSet { } } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { assert (stamp == _set.stamp); if (current != null) { - f (current.key); + if (!f (current.key)) { + return false; + } _next = current.next; } else if (!started) { _next = _set._first; } while (_next != null) { current = _next; - f (current.key); + if (!f (current.key)) { + return false; + } _next = current.next; } + return true; } private weak Node? current = null; @@ -1115,11 +1120,18 @@ public class Gee.TreeSet : AbstractBidirSortedSet { } } - public void foreach(ForallFunc f) { - if(valid) - f(get()); - while(next()) - f(get()); + public bool foreach(ForallFunc f) { + if(valid) { + if (!f(get())) { + return false; + } + } + while(next()) { + if (!f(get())) { + return false; + } + } + return true; } private new TreeSet set; diff --git a/gee/unfolditerator.vala b/gee/unfolditerator.vala index 650b26d..30dcd74 100644 --- a/gee/unfolditerator.vala +++ b/gee/unfolditerator.vala @@ -60,30 +60,39 @@ internal class Gee.UnfoldIterator : Object, Traversable, Iterator { public bool valid { get { return _current != null; } } public bool read_only { get { return true; } } - public void foreach (ForallFunc f) { + public bool foreach (ForallFunc f) { if (_current != null) { - f (_current); + if (!f (_current)) { + return false; + } } if (_next != null) { _current = (owned)_next; - f (_current); + if (!f (_current)) { + return false; + } } else if (_end) { - return; + return true; } if (_current == null) { _current = _func (); if (_current == null) { _end = true; - return; + return true; } else { - f (_current); + if (!f (_current)) { + return false; + } } } while ((_next = _func ()) != null) { _current = (owned)_next; - f (_current); + if (!f (_current)) { + return false; + } } _end = true; + return true; } private UnfoldFunc _func; diff --git a/tests/testcollection.vala b/tests/testcollection.vala index bf90eaf..8b28f85 100644 --- a/tests/testcollection.vala +++ b/tests/testcollection.vala @@ -768,12 +768,12 @@ public abstract class CollectionTests : Gee.TestCase { int count = 0; - test_collection.iterator ().foreach ((x) => {count++;}); + test_collection.iterator ().foreach ((x) => {count++; return true;}); assert (count == 3); Iterator iter = test_collection.iterator (); assert (iter.next ()); - iter.foreach ((x) => {count++;}); + iter.foreach ((x) => {count++; return true;}); assert (count == 6); } diff --git a/tests/testmap.vala b/tests/testmap.vala index 464ec0f..5a63cf8 100644 --- a/tests/testmap.vala +++ b/tests/testmap.vala @@ -548,12 +548,12 @@ public abstract class MapTests : Gee.TestCase { int count = 0; - test_map.map_iterator ().foreach ((x, y) => {count++;}); + test_map.map_iterator ().foreach ((x, y) => {count++; return true;}); assert (count == 3); var iter = test_map.map_iterator (); assert (iter.next ()); - iter.foreach ((x, y) => {count++;}); + iter.foreach ((x, y) => {count++; return true;}); assert (count == 6); } -- 2.7.4