Introduce Queue and Deque interfaces, and implement them in LinkedList

5 files changed, 391 insertions, 0 deletions

diff --git a/tests/Makefile.am b/tests/Makefile.am
index 4162ac5..ddac44b 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -18,13 +18,16 @@ tests_VALASOURCES = \
        testarraylist.vala \
        testcase.vala \
        testcollection.vala \
+       testdeque.vala \
        testhashmultimap.vala \
        testhashmultiset.vala \
        testlinkedlist.vala \
+       testlinkedlistasdeque.vala \
        testlist.vala \
        testmain.vala \
        testmultimap.vala \
        testmultiset.vala \
+       testqueue.vala \
        testreadonlycollection.vala \
        testreadonlylist.vala \
        $(NULL)
diff --git a/tests/testdeque.vala b/tests/testdeque.vala
new file mode 100644
index 0000000..d100ce0
--- /dev/null
+++ b/tests/testdeque.vala
@@ -0,0 +1,225 @@
+/* testdeque.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>
+ */
+
+using Gee;
+
+public abstract class DequeTests : QueueTests {
+
+	public DequeTests (string name) {
+		base (name);
+		add_test ("[Deque] queue use", test_queue_use);
+		add_test ("[Deque] stack use", test_stack_use);
+		add_test ("[Deque] reversed stack use", test_reversed_stack_use);
+	}
+
+	public void test_queue_use () {
+		var test_deque = test_collection as Gee.Deque<string>;
+		ArrayList<string> recipient = new ArrayList<string> ();
+
+		// Check the test deque is not null
+		assert (test_deque != null);
+
+		// Check normal FIFO behavior
+		assert (test_deque.offer_tail ("one"));
+		assert (test_deque.size == 1);
+		assert (test_deque.offer_tail ("two"));
+		assert (test_deque.size == 2);
+		assert (test_deque.offer_tail ("three"));
+		assert (test_deque.size == 3);
+		assert (test_deque.offer_tail ("four"));
+		assert (test_deque.size == 4);
+		assert (test_deque.peek_head () == "one");
+		assert (test_deque.poll_head () == "one");
+		assert (test_deque.size == 3);
+		assert (test_deque.peek_head () == "two");
+		assert (test_deque.poll_head () == "two");
+		assert (test_deque.size == 2);
+		assert (test_deque.peek_head () == "three");
+		assert (test_deque.poll_head () == "three");
+		assert (test_deque.size == 1);
+		assert (test_deque.peek_head () == "four");
+		assert (test_deque.poll_head () == "four");
+		assert (test_deque.size == 0);
+
+		// Check normal behavior when no element
+		assert (test_deque.peek_head () == null);
+		assert (test_deque.poll_head () == null);
+
+		// Check drain with FIFO behavior
+		recipient.clear ();
+		assert (test_deque.offer_tail ("one"));
+		assert (test_deque.offer_tail ("two"));
+		assert (test_deque.offer_tail ("three"));
+		assert (test_deque.offer_tail ("four"));
+		assert (test_deque.size == 4);
+		assert (test_deque.drain_head (recipient, 1) == 1);
+		assert (test_deque.size == 3);
+		assert (recipient.size == 1);
+		assert (recipient.get (0) == "one");
+		assert (test_deque.drain_head (recipient) == 3);
+		assert (test_deque.size == 0);
+		assert (recipient.size == 4);
+		assert (recipient.get (1) == "two");
+		assert (recipient.get (2) == "three");
+		assert (recipient.get (3) == "four");
+
+		// Check drain one when no element
+		recipient.clear ();
+		assert (test_deque.drain_head (recipient, 1) == 0);
+		assert (test_deque.size == 0);
+		assert (recipient.size == 0);
+
+		// Check drain all when no element
+		recipient.clear ();
+		assert (test_deque.drain_head (recipient) == 0);
+		assert (test_deque.size == 0);
+		assert (recipient.size == 0);
+	}
+
+	public void test_stack_use () {
+		var test_deque = test_collection as Gee.Deque<string>;
+		ArrayList<string> recipient = new ArrayList<string> ();
+
+		// Check the test deque is not null
+		assert (test_deque != null);
+
+		// Check normal LIFO behavior
+		assert (test_deque.offer_head ("one"));
+		assert (test_deque.size == 1);
+		assert (test_deque.offer_head ("two"));
+		assert (test_deque.size == 2);
+		assert (test_deque.offer_head ("three"));
+		assert (test_deque.size == 3);
+		assert (test_deque.offer_head ("four"));
+		assert (test_deque.size == 4);
+		assert (test_deque.peek_head () == "four");
+		assert (test_deque.poll_head () == "four");
+		assert (test_deque.size == 3);
+		assert (test_deque.peek_head () == "three");
+		assert (test_deque.poll_head () == "three");
+		assert (test_deque.size == 2);
+		assert (test_deque.peek_head () == "two");
+		assert (test_deque.poll_head () == "two");
+		assert (test_deque.size == 1);
+		assert (test_deque.peek_head () == "one");
+		assert (test_deque.poll_head () == "one");
+		assert (test_deque.size == 0);
+
+		// Check normal behavior when no element
+		assert (test_deque.peek_head () == null);
+		assert (test_deque.poll_head () == null);
+
+		// Check drain with LIFO behavior
+		recipient.clear ();
+		assert (test_deque.offer_head ("one"));
+		assert (test_deque.offer_head ("two"));
+		assert (test_deque.offer_head ("three"));
+		assert (test_deque.offer_head ("four"));
+		assert (test_deque.size == 4);
+		assert (test_deque.drain_head (recipient, 1) == 1);
+		assert (test_deque.size == 3);
+		assert (recipient.size == 1);
+		assert (recipient.get (0) == "four");
+		assert (test_deque.drain_head (recipient) == 3);
+		assert (test_deque.size == 0);
+		assert (recipient.size == 4);
+		assert (recipient.get (1) == "three");
+		assert (recipient.get (2) == "two");
+		assert (recipient.get (3) == "one");
+
+		// Check drain one when no element
+		recipient.clear ();
+		assert (test_deque.drain_head (recipient, 1) == 0);
+		assert (test_deque.size == 0);
+		assert (recipient.size == 0);
+
+		// Check drain all when no element
+		recipient.clear ();
+		assert (test_deque.drain_head (recipient) == 0);
+		assert (test_deque.size == 0);
+		assert (recipient.size == 0);
+	}
+
+	public void test_reversed_stack_use () {
+		var test_deque = test_collection as Gee.Deque<string>;
+		ArrayList<string> recipient = new ArrayList<string> ();
+
+		// Check the test deque is not null
+		assert (test_deque != null);
+
+		// Check normal LIFO behavior
+		assert (test_deque.offer_tail ("one"));
+		assert (test_deque.size == 1);
+		assert (test_deque.offer_tail ("two"));
+		assert (test_deque.size == 2);
+		assert (test_deque.offer_tail ("three"));
+		assert (test_deque.size == 3);
+		assert (test_deque.offer_tail ("four"));
+		assert (test_deque.size == 4);
+		assert (test_deque.peek_tail () == "four");
+		assert (test_deque.poll_tail () == "four");
+		assert (test_deque.size == 3);
+		assert (test_deque.peek_tail () == "three");
+		assert (test_deque.poll_tail () == "three");
+		assert (test_deque.size == 2);
+		assert (test_deque.peek_tail () == "two");
+		assert (test_deque.poll_tail () == "two");
+		assert (test_deque.size == 1);
+		assert (test_deque.peek_tail () == "one");
+		assert (test_deque.poll_tail () == "one");
+		assert (test_deque.size == 0);
+
+		// Check normal behavior when no element
+		assert (test_deque.peek_tail () == null);
+		assert (test_deque.poll_tail () == null);
+
+		// Check drain with LIFO behavior
+		recipient.clear ();
+		assert (test_deque.offer_tail ("one"));
+		assert (test_deque.offer_tail ("two"));
+		assert (test_deque.offer_tail ("three"));
+		assert (test_deque.offer_tail ("four"));
+		assert (test_deque.size == 4);
+		assert (test_deque.drain_tail (recipient, 1) == 1);
+		assert (test_deque.size == 3);
+		assert (recipient.size == 1);
+		assert (recipient.get (0) == "four");
+		assert (test_deque.drain_tail (recipient) == 3);
+		assert (test_deque.size == 0);
+		assert (recipient.size == 4);
+		assert (recipient.get (1) == "three");
+		assert (recipient.get (2) == "two");
+		assert (recipient.get (3) == "one");
+
+		// Check drain one when no element
+		recipient.clear ();
+		assert (test_deque.drain_tail (recipient, 1) == 0);
+		assert (test_deque.size == 0);
+		assert (recipient.size == 0);
+
+		// Check drain all when no element
+		recipient.clear ();
+		assert (test_deque.drain_tail (recipient) == 0);
+		assert (test_deque.size == 0);
+		assert (recipient.size == 0);
+	}
+}
diff --git a/tests/testlinkedlistasdeque.vala b/tests/testlinkedlistasdeque.vala
new file mode 100644
index 0000000..81b791f
--- /dev/null
+++ b/tests/testlinkedlistasdeque.vala
@@ -0,0 +1,49 @@
+/* testlinkedlistasdeque.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
+ *
+ * Authors:
+ * 	Didier 'Ptitjes Villevalois <ptitjes@free.fr>
+ */
+
+using Gee;
+
+public class LinkedListAsDequeTests : DequeTests {
+
+	public LinkedListAsDequeTests () {
+		base ("LinkedList as Deque");
+		add_test ("[LinkedList] selected functions", test_selected_functions);
+	}
+
+	public override void set_up () {
+		test_collection = new LinkedList<string> ();
+	}
+
+	public override void tear_down () {
+		test_collection = null;
+	}
+
+	private void test_selected_functions () {
+		var test_list = test_collection as LinkedList<string>;
+
+		// Check the collection exists
+		assert (test_list != null);
+
+		// Check the selected equal function
+		assert (test_list.equal_func == str_equal);
+	}
+}
diff --git a/tests/testmain.vala b/tests/testmain.vala
index 90705b0..204a33d 100644
--- a/tests/testmain.vala
+++ b/tests/testmain.vala
@@ -28,6 +28,7 @@ void main (string[] args) {
 	TestSuite.get_root ().add_suite (new HashMultiMapTests ().get_suite ());
 	TestSuite.get_root ().add_suite (new HashMultiSetTests ().get_suite ());
 	TestSuite.get_root ().add_suite (new LinkedListTests ().get_suite ());
+	TestSuite.get_root ().add_suite (new LinkedListAsDequeTests ().get_suite ());
 	TestSuite.get_root ().add_suite (new ReadOnlyListTests ().get_suite ());
 
 	Test.run ();
diff --git a/tests/testqueue.vala b/tests/testqueue.vala
new file mode 100644
index 0000000..e872084
--- /dev/null
+++ b/tests/testqueue.vala
@@ -0,0 +1,113 @@
+/* testqueue.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>
+ */
+
+using Gee;
+
+public abstract class QueueTests : CollectionTests {
+
+	public QueueTests (string name) {
+		base (name);
+		add_test ("[Queue] capacity bound", test_capacity_bound);
+		add_test ("[Queue] one element operation", test_one_element_operation);
+	}
+
+	public void test_capacity_bound () {
+		var test_queue = test_collection as Gee.Queue<string>;
+
+		// Check the test queue is not null
+		assert (test_queue != null);
+
+		if (test_queue.capacity == null) {
+			// Unbounded capacity
+			assert (test_queue.remaining_capacity == null);
+			assert (! test_queue.is_full);
+		} else {
+			// Bounded capacity
+			assert (test_queue.is_empty);
+
+			// Check that we can fill it completely
+			int capacity = test_queue.capacity;
+			for (int i = 1; i <= capacity; i++) {
+				assert (! test_queue.is_full);
+				assert (test_queue.offer ("one") == true);
+				assert (test_queue.remaining_capacity == capacity - i);
+			}
+			assert (test_queue.is_full);
+
+			// Check that we can empty it completely
+			for (int i = 1; i <= capacity; i++) {
+				assert (test_queue.poll () == "one");
+				assert (! test_queue.is_full);
+				assert (test_queue.remaining_capacity == i);
+			}
+			assert (test_queue.is_empty);
+		}
+	}
+
+	public void test_one_element_operation () {
+		var test_queue = test_collection as Gee.Queue<string>;
+		ArrayList<string> recipient = new ArrayList<string> ();
+
+		// Check the test queue is not null
+		assert (test_queue != null);
+
+		// Check offer one element when there is none yet
+		assert (test_queue.offer ("one") == true);
+		assert (test_queue.peek () == "one");
+		assert (test_queue.size == 1);
+		assert (! test_queue.is_empty);
+
+		// Check poll when there is one element
+		assert (test_queue.poll () == "one");
+		assert (test_queue.size == 0);
+		assert (test_queue.is_empty);
+
+		// Check poll when there is no element
+		assert (test_queue.peek () == null);
+		assert (test_queue.poll () == null);
+
+		// Check drain one element when there is one
+		recipient.clear ();
+		assert (test_queue.offer ("one") == true);
+		assert (test_queue.drain (recipient, 1) == 1);
+		assert (test_queue.size == 0);
+		assert (test_queue.is_empty);
+		assert (recipient.size == 1);
+		assert (recipient.get (0) == "one");
+
+		// Check drain one element when there is none
+		recipient.clear ();
+		assert (test_queue.drain (recipient, 1) == 0);
+		assert (test_queue.size == 0);
+		assert (test_queue.is_empty);
+		assert (recipient.size == 0);
+
+		// Check drain all elements when there is one
+		recipient.clear ();
+		assert (test_queue.offer ("one") == true);
+		assert (test_queue.drain (recipient) == 1);
+		assert (test_queue.size == 0);
+		assert (test_queue.is_empty);
+		assert (recipient.size == 1);
+		assert (recipient.get (0) == "one");
+	}
+}