GNOME.org
 

[libgee] Introduce the ListIterator interface and make lists implement it

commit 14e877f7f99a521db59174d77d4876f92c03e78d
Author: Didier 'Ptitjes <ptitjes free fr>
Date:   Tue Sep 15 13:33:29 2009 +0200

    Introduce the ListIterator interface and make lists implement it

 gee/Makefile.am       |    1 +
 gee/abstractlist.vala |    5 ++
 gee/arraylist.vala    |   76 +++++++++++++++++++++++++++--
 gee/linkedlist.vala   |  127 +++++++++++++++++++++++++++++++++++++++++++++----
 gee/list.vala         |    7 +++
 gee/listiterator.vala |   50 +++++++++++++++++++
 gee/readonlylist.vala |   42 ++++++++++++++++
 tests/testlist.vala   |   79 +++++++++++++++++++++++++++++-
 8 files changed, 370 insertions(+), 17 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 4a899b0..f9d7266 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -32,6 +32,7 @@ libgee_la_VALASOURCES = \
 	iterator.vala \
 	linkedlist.vala \
 	list.vala \
+	listiterator.vala \
 	map.vala \
 	multimap.vala \
 	multiset.vala \
diff --git a/gee/abstractlist.vala b/gee/abstractlist.vala
index ec1bb39..23d491e 100644
--- a/gee/abstractlist.vala
+++ b/gee/abstractlist.vala
@@ -34,6 +34,11 @@ public abstract class Gee.AbstractList<G> : Gee.AbstractCollection<G>, List<G> {
 	/**
 	 * @inheritDoc
 	 */
+	public abstract ListIterator<G> list_iterator ();
+
+	/**
+	 * @inheritDoc
+	 */
 	public abstract new G? get (int index);
 
 	/**
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
index e4810e0..0e0e29e 100644
--- a/gee/arraylist.vala
+++ b/gee/arraylist.vala
@@ -3,6 +3,7 @@
  * Copyright (C) 2004-2005  Novell, Inc
  * Copyright (C) 2005  David Waite
  * Copyright (C) 2007-2008  Jürg Billeter
+ * Copyright (C) 2009  Didier Villevalois
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -20,6 +21,7 @@
  *
  * Author:
  * 	Jürg Billeter <j bitron ch>
+ * 	Didier 'Ptitjes Villevalois <ptitjes free fr>
  */
 
 using GLib;
@@ -76,6 +78,13 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 	/**
 	 * @inheritDoc
 	 */
+	public override ListIterator<G> list_iterator () {
+		return new Iterator<G> (this);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
 	public override bool contains (G item) {
 		return (index_of (item) != -1);
 	}
@@ -237,7 +246,7 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 		_items.resize (value);
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G> {
+	private class Iterator<G> : Object, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G> {
 		public ArrayList<G> list {
 			construct {
 				_list = value;
@@ -258,11 +267,12 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 
 		public bool next () {
 			assert (_stamp == _list._stamp);
-			if (_index < _list._size) {
+			if (_index + 1 < _list._size) {
 				_index++;
+				_removed = false;
+				return true;
 			}
-			_removed = false;
-			return (_index < _list._size);
+			return false;
 		}
 
 		public bool has_next () {
@@ -285,7 +295,7 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 			assert (_index >= 0);
 			assert (_index < _list._size);
 			assert (! _removed);
-			return _list.get (_index);
+			return _list._items[_index];
 		}
 
 		public void remove () {
@@ -298,6 +308,62 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 			_removed = true;
 			_stamp = _list._stamp;
 		}
+
+		public bool previous () {
+			assert (_stamp == _list._stamp);
+			if (_index > 0) {
+				_index--;
+				return true;
+			}
+			return false;
+		}
+
+		public bool has_previous () {
+			assert (_stamp == _list._stamp);
+			return (_index - 1 >= 0);
+		}
+
+		public bool last () {
+			assert (_stamp == _list._stamp);
+			if (_list.size == 0) {
+				return false;
+			}
+			_index = _list._size - 1;
+			return true;
+		}
+
+		public new void set (G item) {
+			assert (_stamp == _list._stamp);
+			assert (_index >= 0);
+			assert (_index < _list._size);
+			_list._items[_index] = item;
+			_stamp = ++_list._stamp;
+		}
+
+		public void insert (G item) {
+			assert (_stamp == _list._stamp);
+			assert (_index >= 0);
+			assert (_index < _list._size);
+			_list.insert (_index, item);
+			_index++;
+			_stamp = _list._stamp;
+		}
+
+		public void add (G item) {
+			assert (_stamp == _list._stamp);
+			assert (_index >= 0);
+			assert (_index < _list._size);
+			_list.insert (_index + 1, item);
+			_index++;
+			_stamp = _list._stamp;
+		}
+
+		public int index () {
+			assert (_stamp == _list._stamp);
+			assert (_index >= 0);
+			assert (_index < _list._size);
+			return _index;
+		}
 	}
 }
 
diff --git a/gee/linkedlist.vala b/gee/linkedlist.vala
index 1918033..e021ee8 100644
--- a/gee/linkedlist.vala
+++ b/gee/linkedlist.vala
@@ -3,8 +3,7 @@
  * Copyright (C) 2004-2005  Novell, Inc
  * Copyright (C) 2005  David Waite
  * Copyright (C) 2007-2008  Jürg Billeter
- * Copyright (C) 2009  Mark Lee
- * Copyright (C) 2009  Julien Fontanet
+ * Copyright (C) 2009  Mark Lee, Didier Villevalois
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -22,6 +21,7 @@
  *
  * Author:
  * 	Mark Lee <marklee src gnome org>
+ * 	Didier 'Ptitjes Villevalois <ptitjes free fr>
  */
 
 /**
@@ -65,6 +65,13 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 	/**
 	 * @inheritDoc
 	 */
+	public override ListIterator<G> list_iterator () {
+		return new Iterator<G> (this);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
 	public override int size {
 		get { return this._size; }
 	}
@@ -385,31 +392,38 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 		}
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G> {
+	private class Iterator<G> : Object, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G> {
 		private bool started = false;
 		private bool removed = false;
 		private unowned Node<G>? position;
 		private int _stamp;
 		private LinkedList<G> _list;
+		private int _index;
 
 		public Iterator (LinkedList<G> list) {
 			this._list = list;
 			this.position = null;
+			this._index = -1;
 			this._stamp = list._stamp;
 		}
 
 		public bool next () {
 			assert (this._stamp == this._list._stamp);
 
-			if (this.removed) {
+			if (this.removed && this.position != null) {
 				this.removed = false;
-			} else if (!this.started) {
+				return true;
+			} else if (!this.started && this._list._head != null) {
 				this.started = true;
 				this.position = this._list._head;
-			} else if (this.position != null) {
+				this._index++;
+				return true;
+			} else if (this.position != null && this.position.next != null) {
 				this.position = this.position.next;
+				this._index++;
+				return true;
 			}
-			return this.position != null;
+			return false;
 		}
 
 		public bool has_next () {
@@ -427,9 +441,14 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 
 		public bool first () {
 			assert (this._stamp == this._list._stamp);
-			this.position = null;
-			this.started = false;
-			return next ();
+			if (this._list.size == 0) {
+				return false;
+			}
+			this.position = this._list._head;
+			this.started = true;
+			this._index = 0;
+			this.removed = false;
+			return this.position != null;
 		}
 
 		public new G get () {
@@ -452,6 +471,94 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 			this.removed = true;
 			this._stamp = this._list._stamp;
 		}
+
+		public bool previous () {
+			assert (this._stamp == this._list._stamp);
+
+			if (!this.started) {
+				this.position = null;
+				return false;
+			} else if (this.position != null && this.position.prev != null) {
+				this.position = this.position.prev;
+				this._index--;
+				return true;
+			}
+			return false;
+		}
+
+		public bool has_previous () {
+			assert (this._stamp == this._list._stamp);
+
+			if (!this.started) {
+				return false;
+			} else if (this.position != null) {
+				return this.position.prev != null;
+			}
+			return false;
+		}
+
+		public bool last () {
+			assert (this._stamp == this._list._stamp);
+
+			if (this._list.size == 0) {
+				return false;
+			}
+			this.position = this._list._tail;
+			this.started = true;
+			this._index = this._list._size - 1;
+			return this.position != null;
+		}
+
+		public new void set (G item) {
+			assert (this._stamp == this._list._stamp);
+			assert (this.position != null);
+
+			this.position.data = item;
+		}
+
+		public void insert (G item) {
+			assert (this._stamp == this._list._stamp);
+			assert (this.position != null);
+
+			Node<G> n = new Node<G> (item);
+			if (this.position.prev != null) {
+				this.position.prev.next = n;
+				n.prev = this.position.prev;
+			} else {
+				this._list._head = n;
+			}
+			this.position.prev = n;
+			n.next = this.position;
+			this._list._size++;
+			this._index++;
+			_stamp = _list._stamp;
+		}
+
+		public void add (G item) {
+			assert (this._stamp == this._list._stamp);
+			assert (this.position != null);
+
+			Node<G> n = new Node<G> (item);
+			if (this.position.next != null) {
+				this.position.next.prev = n;
+				n.next = this.position.next;
+			} else {
+				this._list._tail = n;
+			}
+			this.position.next = n;
+			n.prev = this.position;
+			this.position = n;
+			this._list._size++;
+			this._index++;
+			_stamp = _list._stamp;
+		}
+
+		public int index () {
+			assert (this._stamp == this._list._stamp);
+			assert (this.position != null);
+
+			return this._index;
+		}
 	}
 
 	private unowned Node<G>? _get_node_at (int index) {
diff --git a/gee/list.vala b/gee/list.vala
index d3221bb..eae18b1 100644
--- a/gee/list.vala
+++ b/gee/list.vala
@@ -25,6 +25,13 @@
  */
 public interface Gee.List<G> : Collection<G> {
 	/**
+	 * Returns a ListIterator that can be used for iteration over this list.
+	 *
+	 * @return a ListIterator that can be used for iteration over this list
+	 */
+	public abstract new ListIterator<G> list_iterator ();
+
+	/**
 	 * Returns the item at the specified index in this list.
 	 *
 	 * @param index zero-based index of the item to be returned
diff --git a/gee/listiterator.vala b/gee/listiterator.vala
new file mode 100644
index 0000000..34eb3e0
--- /dev/null
+++ b/gee/listiterator.vala
@@ -0,0 +1,50 @@
+/* listiterator.vala
+ *
+ * Copyright (C) 2009  Didier Villevalois
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
+ *
+ * Author:
+ * 	Didier 'Ptitjes Villevalois <ptitjes free fr>
+ */
+
+/**
+ * A list iterator. This supports bi-directionnal and index-based iteration.
+ */
+public interface Gee.ListIterator<G> : Gee.BidirIterator<G> {
+	/**
+	 * Sets the current item in the iteration to the specified new item.
+	 */
+	public abstract void set (G item);
+
+	/**
+	 * Inserts the specified item before the current item in the iteration. The
+	 * cursor is let to point to the current item.
+	 */
+	public abstract void insert (G item);
+
+	/**
+	 * Adds the specified item after the current item in the iteration. The
+	 * cursor is moved to point to the new added item.
+	 */
+	public abstract void add (G item);
+
+	/**
+	 * Returns the current index in the iteration.
+	 *
+	 * @return the current index
+	 */
+	public abstract int index ();
+}
diff --git a/gee/readonlylist.vala b/gee/readonlylist.vala
index f29a790..ad85f59 100644
--- a/gee/readonlylist.vala
+++ b/gee/readonlylist.vala
@@ -46,6 +46,13 @@ internal class Gee.ReadOnlyList<G> : Gee.ReadOnlyCollection<G>, List<G> {
 	/**
 	 * @inheritDoc
 	 */
+	public ListIterator<G> list_iterator () {
+		return new Iterator<G> (((Gee.List<G>) _collection).list_iterator ());
+	}
+
+	/**
+	 * @inheritDoc
+	 */
 	public int index_of (G item) {
 		return ((Gee.List<G>) _collection).index_of (item);
 	}
@@ -119,5 +126,40 @@ internal class Gee.ReadOnlyList<G> : Gee.ReadOnlyCollection<G>, List<G> {
 	public virtual new List<G> read_only_view {
 		owned get { return this; }
 	}
+
+	
+	private class Iterator<G> : ReadOnlyCollection.Iterator<G>, BidirIterator<G>, ListIterator<G> {
+		public Iterator (ListIterator<G> iterator) {
+			base (iterator);
+		}
+
+		public bool previous () {
+			return ((ListIterator<G>) _iter).previous ();
+		}
+
+		public bool has_previous () {
+			return ((ListIterator<G>) _iter).has_previous ();
+		}
+
+		public bool last () {
+			return ((ListIterator<G>) _iter).last ();
+		}
+
+		public new void set (G item) {
+			assert_not_reached ();
+		}
+
+		public void insert (G item) {
+			assert_not_reached ();
+		}
+
+		public void add (G item) {
+			assert_not_reached ();
+		}
+
+		public int index () {
+			return ((ListIterator<G>) _iter).index ();
+		}
+	}
 }
 
diff --git a/tests/testlist.vala b/tests/testlist.vala
index cd4b0ad..2d8d7a9 100644
--- a/tests/testlist.vala
+++ b/tests/testlist.vala
@@ -31,6 +31,7 @@ public abstract class ListTests : CollectionTests {
 	public ListTests (string name) {
 		base (name);
 		add_test ("[List] iterator is ordered", test_iterator_is_ordered);
+		add_test ("[List] list iterator", test_list_iterator);
 		add_test ("[List] duplicates are retained",
 		          test_duplicates_are_retained);
 		add_test ("[List] get", test_get);
@@ -52,7 +53,7 @@ public abstract class ListTests : CollectionTests {
 
 		// Check iterate empty list
 		var iterator = test_list.iterator ();
-		assert (! iterator.next());
+		assert (! iterator.next ());
 
 		// Check iterate list
 		assert (test_list.add ("one"));
@@ -69,7 +70,81 @@ public abstract class ListTests : CollectionTests {
 		assert (iterator.get () == "three");
 		assert (iterator.next());
 		assert (iterator.get () == "one");
-		assert (! iterator.next());
+		assert (! iterator.next ());
+	}
+
+	public void test_list_iterator () {
+		var test_list = test_collection as Gee.List<string>;
+
+		// Check the test list is not null
+		assert (test_list != null);
+
+		// Check iterate empty list
+		var iterator = test_list.list_iterator ();
+		assert (! iterator.has_next ());
+		assert (! iterator.next ());
+		assert (! iterator.has_previous ());
+		assert (! iterator.previous ());
+		assert (! iterator.first ());
+		assert (! iterator.last ());
+
+		// Check iterate list
+		assert (test_list.add ("one"));
+		assert (test_list.add ("two"));
+		assert (test_list.add ("three"));
+
+		iterator = test_list.list_iterator ();
+		assert (iterator.next());
+		assert (iterator.get () == "one");
+		assert (iterator.index () == 0);
+		iterator.set ("new one");
+		assert (iterator.next());
+		assert (iterator.get () == "two");
+		assert (iterator.index () == 1);
+		iterator.set ("new two");
+		assert (test_list.size == 3);
+		assert (iterator.index () == 1);
+		iterator.insert ("before two");
+		assert (test_list.size == 4);
+		assert (iterator.index () == 2);
+		iterator.add ("after two");
+		assert (test_list.size == 5);
+		assert (iterator.index () == 3);
+		assert (iterator.next());
+		assert (iterator.get () == "three");
+		assert (iterator.index () == 4);
+		iterator.set ("new three");
+		assert (! iterator.has_next ());
+		assert (! iterator.next ());
+
+		assert (iterator.first ());
+		assert (iterator.get () == "new one");
+		assert (iterator.index () == 0);
+		assert (! iterator.has_previous ());
+		assert (! iterator.previous ());
+
+		assert (iterator.last ());
+		assert (iterator.get () == "new three");
+		assert (iterator.index () == 4);
+		assert (! iterator.has_next ());
+		assert (! iterator.next ());
+
+		assert (iterator.has_previous ());
+		assert (iterator.previous ());
+		assert (iterator.get () == "after two");
+		assert (iterator.index () == 3);
+		assert (iterator.has_previous ());
+		assert (iterator.previous ());
+		assert (iterator.get () == "new two");
+		assert (iterator.index () == 2);
+		assert (iterator.has_previous ());
+		assert (iterator.previous ());
+		assert (iterator.get () == "before two");
+		assert (iterator.index () == 1);
+		assert (iterator.has_previous ());
+		assert (iterator.previous ());
+		assert (iterator.get () == "new one");
+		assert (iterator.index () == 0);
 	}
 
 	public virtual void test_duplicates_are_retained () {
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]