[libgee] Introduce Queue and Deque interfaces, and implement them in LinkedList

[Didier 'Ptitjes' Villevalois <dvillevalois src gnome org>]

commit 18ea5508a5d6f1a00bb41af9750660e96a3f5b67
Author: Didier 'Ptitjes <ptitjes free fr>
Date:   Fri Sep 11 10:05:00 2009 +0200

    Introduce Queue and Deque interfaces, and implement them in LinkedList

 gee/Makefile.am                  |    2 +
 gee/deque.vala                   |  117 ++++++++++++++++++++
 gee/linkedlist.vala              |  138 +++++++++++++++++++++++-
 gee/queue.vala                   |   95 ++++++++++++++++
 tests/Makefile.am                |    3 +
 tests/testdeque.vala             |  225 ++++++++++++++++++++++++++++++++++++++
 tests/testlinkedlistasdeque.vala |   49 ++++++++
 tests/testmain.vala              |    1 +
 tests/testqueue.vala             |  113 +++++++++++++++++++
 9 files changed, 742 insertions(+), 1 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 6fa4869..592625e 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -20,6 +20,7 @@ libgee_la_VALASOURCES = \
 	abstractset.vala \
 	arraylist.vala \
 	collection.vala \
+	deque.vala \
 	functions.vala \
 	hashmap.vala \
 	hashmultimap.vala \
@@ -32,6 +33,7 @@ libgee_la_VALASOURCES = \
 	map.vala \
 	multimap.vala \
 	multiset.vala \
+	queue.vala \
 	readonlycollection.vala \
 	readonlylist.vala \
 	readonlymap.vala \
diff --git a/gee/deque.vala b/gee/deque.vala
new file mode 100644
index 0000000..8295fd3
--- /dev/null
+++ b/gee/deque.vala
@@ -0,0 +1,117 @@
+/* deque.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 double-ended queue.
+ *
+ * A deque can be used either as a queue (First-In-First-Out behavior) or as a
+ * stack (Last-In-First-Out behavior).
+ *
+ * The methods defined by this interface behaves exactely in the same way as
+ * the { link Queue} methods with respect to capacity bounds.
+ *
+ * The Deque interface inherits from the { link Queue} interface. Thus, to use
+ * a deque as a queue, you can equivalently use the folowing method set:
+ *
+ * ||<)(> ++Queue method++ ||<)(>  ++Deque method++ ||
+ * || { link Queue.offer}  || { link offer_tail}    ||
+ * || { link Queue.peek}   || { link peek_head}     ||
+ * || { link Queue.poll}   || { link poll_head}     ||
+ * || { link Queue.drain}  || { link drain_head}    ||
+ *
+ * To use a deque as a stack, just use the method set that acts at the head of
+ * the deque:
+ *
+ * ||<)(> ++Operation++ ||<)(>  ++Deque method++ ||
+ * || push an element   || { link offer_head}    ||
+ * || peek an element   || { link peek_head}     ||
+ * || pop an element    || { link poll_head}     ||
+ */
+public interface Gee.Deque<G> : Queue<G> {
+	/**
+	 * Offers the specified element to the head of this deque.
+	 *
+	 * @param element the element to offer to the queue
+	 *
+	 * @return        true if the element was added to the queue
+	 */
+	public abstract bool offer_head (G element);
+
+	/**
+	 * Peeks (retrieves, but not remove) an element from this queue.
+	 *
+	 * @return the element peeked from the queue (or null if none was available)
+	 */
+	public abstract G? peek_head ();
+
+	/**
+	 * Polls (retrieves and remove) an element from the head of this queue.
+	 *
+	 * @return the element polled from the queue (or null if none was available)
+	 */
+	public abstract G? poll_head ();
+
+	/**
+	 * Drains the specified amount of elements from the head of this queue in
+	 * the specified recipient collection.
+	 *
+	 * @param recipient the recipient collection to drain the elements to
+	 * @param amount    the amount of elements to drain
+	 *
+	 * @return          the amount of elements that were actually drained
+	 */
+	public abstract int drain_head (Collection<G> recipient, int amount = -1);
+
+	/**
+	 * Offers the specified element to the tail of this deque
+	 *
+	 * @param element the element to offer to the queue
+	 *
+	 * @return        true if the element was added to the queue
+	 */
+	public abstract bool offer_tail (G element);
+
+	/**
+	 * Peeks (retrieves, but not remove) an element from the tail of this queue.
+	 *
+	 * @return the element peeked from the queue (or null if none was available)
+	 */
+	public abstract G? peek_tail ();
+
+	/**
+	 * Polls (retrieves and remove) an element from the tail of this queue.
+	 *
+	 * @return the element polled from the queue (or null if none was available)
+	 */
+	public abstract G? poll_tail ();
+
+	/**
+	 * Drains the specified amount of elements from the tail of this queue in
+	 * the specified recipient collection.
+	 *
+	 * @param recipient the recipient collection to drain the elements to
+	 * @param amount    the amount of elements to drain
+	 *
+	 * @return          the amount of elements that were actually drained
+	 */
+	public abstract int drain_tail (Collection<G> recipient, int amount = -1);
+}
diff --git a/gee/linkedlist.vala b/gee/linkedlist.vala
index a35f97d..18ad724 100644
--- a/gee/linkedlist.vala
+++ b/gee/linkedlist.vala
@@ -32,7 +32,7 @@
  *
  * @see Gee.ArrayList
  */
-public class Gee.LinkedList<G> : AbstractList<G> {
+public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 	private int _size = 0;
 	private int _stamp = 0;
 	private Node? _head = null;
@@ -227,6 +227,142 @@ public class Gee.LinkedList<G> : AbstractList<G> {
 		return slice;
 	}
 
+	/**
+	 * @inheritDoc
+	 */
+	public int? capacity {
+		get { return null; }
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public int? remaining_capacity {
+		get { return null; }
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public bool is_full {
+		get { return false; }
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public bool offer (G element) {
+		return offer_tail (element);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? peek () {
+		return peek_head ();
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? poll () {
+		return poll_head ();
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public int drain (Collection<G> recipient, int amount = -1) {
+		return drain_head (recipient, amount);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public bool offer_head (G element) {
+		insert (0, element);
+		return true;
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? peek_head () {
+		if (this._size == 0) {
+			return null;
+		}
+		return get (0);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? poll_head () {
+		if (this._size == 0) {
+			return null;
+		}
+		return remove_at (0);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public int drain_head (Collection<G> recipient, int amount = -1) {
+		if (amount == -1) {
+			amount = this._size;
+		}
+		for (int i = 0; i < amount; i++) {
+			if (this._size == 0) {
+				return i;
+			}
+			recipient.add (remove_at (0));
+		}
+		return amount;
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public bool offer_tail (G element) {
+		return add (element);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? peek_tail () {
+		if (this._size == 0) {
+			return null;
+		}
+		return get (_size - 1);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? poll_tail () {
+		if (this._size == 0) {
+			return null;
+		}
+		return remove_at (_size - 1);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public int drain_tail (Collection<G> recipient, int amount = -1) {
+		if (amount == -1) {
+			amount = this._size;
+		}
+		for (int i = 0; i < amount; i++) {
+			if (this._size == 0) {
+				return i;
+			}
+			recipient.add (remove_at (this._size - 1));
+		}
+		return amount;
+	}
+
 	private class Node<G> { // Maybe a compact class should be used?
 		public G data;
 		public Node<G>? prev = null;
diff --git a/gee/queue.vala b/gee/queue.vala
new file mode 100644
index 0000000..321479b
--- /dev/null
+++ b/gee/queue.vala
@@ -0,0 +1,95 @@
+/* queue.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 collection designed for holding elements prior to processing.
+ *
+ * Although all Queue implementations do not limit the amount of elements they
+ * can contain, this interface supports for capacity-bounded queues. When
+ * capacity is not bound, then the { link capacity} and
+ * { link remaining_capacity} both return null.
+ *
+ * This interface defines methods that will never fail whatever the state of
+ * the queue is. For capacity-bounded queues, those methods will either return
+ * false or null to specify that the insert or retrieval did not occur because
+ * the queue was full or empty.
+ *
+ * Queue implementations are not limited to First-In-First-Out behavior and can
+ * propose different ordering of their elements. Each Queue implementation have
+ * to specify how it orders its elements.
+ *
+ * Queue implementations do not allow insertion of null elements, although some
+ * implementations, such as { link LinkedList}, do not prohibit insertion of
+ * null. Even in the implementations that permit it, null should not be
+ * inserted into a Queue, as null is also used as a special return value by the
+ * poll method to indicate that the queue contains no elements.
+ */
+public interface Gee.Queue<G> : Collection<G> {
+	/**
+	 * The capacity of this queue (or null if capacity is not bound).
+	 */
+	public abstract int? capacity { get; }
+
+	/**
+	 * The remaining capacity of this queue (or null if capacity is not bound).
+	 */
+	public abstract int? remaining_capacity { get; }
+
+	/**
+	 * Specifies whether this queue is full.
+	 */
+	public abstract bool is_full { get; }
+
+	/**
+	 * Offers the specified element to this queue.
+	 *
+	 * @param element the element to offer to the queue
+	 *
+	 * @return        true if the element was added to the queue
+	 */
+	public abstract bool offer (G element);
+
+	/**
+	 * Peeks (retrieves, but not remove) an element from this queue.
+	 *
+	 * @return the element peeked from the queue (or null if none was available)
+	 */
+	public abstract G? peek ();
+
+	/**
+	 * Polls (retrieves and remove) an element from this queue.
+	 *
+	 * @return the element polled from the queue (or null if none was available)
+	 */
+	public abstract G? poll ();
+
+	/**
+	 * Drains the specified amount of elements from this queue in the specified
+	 * recipient collection.
+	 *
+	 * @param recipient the recipient collection to drain the elements to
+	 * @param amount    the amount of elements to drain
+	 *
+	 * @return          the amount of elements that were actually drained
+	 */
+	public abstract int drain (Collection<G> recipient, int amount = -1);
+}
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");
+	}
+}