[libgee] Introduce Queue and Deque interfaces, and implement them in LinkedList
- From: Didier 'Ptitjes' Villevalois <dvillevalois src gnome org>
- To: svn-commits-list gnome org
- Cc:
- Subject: [libgee] Introduce Queue and Deque interfaces, and implement them in LinkedList
- Date: Fri, 11 Sep 2009 17:21:49 +0000 (UTC)
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");
+ }
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]