From 5a58c3dd444bda3d11750b03159f9b5c7f85c827 Mon Sep 17 00:00:00 2001 From: Maciej Piechotka Date: Sat, 21 Mar 2009 18:55:43 +0100 Subject: [PATCH] Added left-leaning red-black tree based set and map --- gee/Makefile.am | 2 + gee/gee.h | 1 + gee/treemap.vala | 429 ++++++++++++++++++++++++++++++++++++++++++++++++ gee/treeset.vala | 305 ++++++++++++++++++++++++++++++++++ tests/Makefile.am | 18 ++ tests/testtreemap.vala | 314 +++++++++++++++++++++++++++++++++++ tests/testtreeset.vala | 288 ++++++++++++++++++++++++++++++++ 7 files changed, 1357 insertions(+), 0 deletions(-) create mode 100644 gee/treemap.vala create mode 100644 gee/treeset.vala create mode 100644 tests/testtreemap.vala create mode 100644 tests/testtreeset.vala diff --git a/gee/Makefile.am b/gee/Makefile.am index ad326b0..6f2ea68 100644 --- a/gee/Makefile.am +++ b/gee/Makefile.am @@ -27,6 +27,8 @@ libgee_la_VALASOURCES = \ readonlymap.vala \ readonlyset.vala \ set.vala \ + treemap.vala \ + treeset.vala \ $(NULL) libgee_la_SOURCES = \ diff --git a/gee/gee.h b/gee/gee.h index e0f1185..3487510 100644 --- a/gee/gee.h +++ b/gee/gee.h @@ -36,6 +36,7 @@ #include #include #include +#include #endif diff --git a/gee/treemap.vala b/gee/treemap.vala new file mode 100644 index 0000000..ac184a7 --- /dev/null +++ b/gee/treemap.vala @@ -0,0 +1,429 @@ +/* set.vala + * + * Copyright (C) 2009 Maciej Piechotka + * + * 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: + * Maciej Piechotka + */ + +using GLib; + +/** + * Left-leaning red-black tree implementation of Map interface. + */ +public class Gee.TreeMap : Object, Map { + public static int direct_compare (void *_val1, void *_val2) { + long val1 = (long)_val1, val2 = (long)_val2; + if (val1 > val2) + return 1; + else if (val1 == val2) + return 0; + else + return -1; + } + + public int size {get {return _size;} } + private int _size = 0; + + public CompareFunc key_compare_func {construct; get;} + public EqualFunc value_equal_func {construct; get;} + + public TreeMap (CompareFunc key_compare_func = TreeMap.direct_compare, EqualFunc value_equal_func = GLib.direct_equal) { + this.key_compare_func = key_compare_func; + this.value_equal_func = value_equal_func; + } + + public Set get_keys () { + return new KeySet (this); + } + + public Collection get_values () { + return new ValueCollection (this); + } + + private static void rotate_right (ref Node root) { + Node pivot = #root.left; + pivot.color = root.color; + root.color = Node.Color.RED; + root.left = #pivot.right; + pivot.right = #root; + root = #pivot; + } + + private static void rotate_left (ref Node root) { + Node pivot = #root.right; + pivot.color = root.color; + root.color = Node.Color.RED; + root.right = #pivot.left; + pivot.left = #root; + root = #pivot; + } + + private static bool is_red (Node? n) { + return n != null && n.color == Node.Color.RED; + } + + private static bool is_black (Node? n) { + return n == null || n.color == Node.Color.BLACK; + } + + public bool contains (K key) { + weak Node? cur = root; + while (cur != null) { + int res = key_compare_func (key, cur.key); + if (res == 0) { + return true; + } else if (res < 0) { + cur = cur.left; + } else { + cur = cur.right; + } + } + return false; + } + + public V? get (K key) { + weak Node? cur = root; + while (cur != null) { + int res = key_compare_func (key, cur.key); + if (res == 0) { + return cur.value; + } else if (res < 0) { + cur = cur.left; + } else { + cur = cur.right; + } + } + return null; + } + + private void set_to_node (ref Node? node, K key, V value, Node? prev, Node? next) { + if (node == null) { + node = new Node(key, value, prev, next); + if (prev == null) + first = node; + _size++; + } + + if (is_red (node.left) && is_red (node.right)) + node.flip (); + + int cmp = key_compare_func (key, node.key); + if (cmp == 0) { + node.value = value; + } else if (cmp < 0) { + set_to_node (ref node.left, key, value, node.prev, node); + } else { + set_to_node (ref node.right, key, value, node, node.next); + } + + fix_up (ref node); + } + + public void set (K key, V value) { + set_to_node (ref root, key, value, null, null); + root.color = Node.Color.BLACK; + } + + private static void move_red_left (ref Node root) { + root.flip (); + if (is_red (root.right.left)) { + rotate_right (ref root.right); + rotate_left (ref root); + root.flip (); + } + } + + private static void move_red_right (ref Node root) { + root.flip (); + if (is_red (root.left.left)) { + rotate_right (ref root.right); + root.flip (); + } + } + + private void remove_minimal (ref Node node, out K key, out V value) { + if (node.left == null) { + Node n = #node; + key = #n.key; + value = #n.value; + node = null; + return; + } + + if (is_black (node.left) && is_black (node.left.left)) + move_red_left (ref node); + + remove_minimal (ref node.left, out key, out value); + + fix_up (ref node); + } + + private bool remove_from_node (ref Node? node, K key) { + if (node == null) { + return false; + } else if (key_compare_func (key, node.key) < 0) { + weak Node left = node.left; + if (left == null) + return false; + if (is_black (left) && is_black (left.left)) + move_red_left (ref node); + bool r = remove_from_node (ref node.left, key); + fix_up (ref node); + return r; + } else { + if (is_red (node.left)) + rotate_right (ref node); + + weak Node r = node.right; + if (key_compare_func (key, node.key) == 0 && r == null) { + node = null; + _size--; + return true; + } + if (is_black (r) && is_black (r.left) ) + move_red_right (ref node); + if (key_compare_func (key, node.key) == 0) { + remove_minimal (ref node.right, out node.key, out node.value); + fix_up (ref node); + _size--; + return true; + } else { + bool re = remove_from_node (ref node.right, key); + fix_up (ref node); + return re; + } + } + } + + private static void fix_up (ref Node node) { + if (is_black (node.left) && is_red (node.right)) + rotate_left (ref node); + if (is_red (node.left) && is_black (node.right)) + rotate_right (ref node); + } + + public bool remove (K key) { + bool b = remove_from_node (ref root, key); + if (root != null) + root.color = Node.Color.BLACK; + stamp++; + return b; + } + + public void clear () { + root = null; + _size = 0; + stamp++; + } + + [Compact] + private class Node { + public enum Color { + RED, + BLACK; + public Color flip () { + if (this == RED) + return BLACK; + else + return RED; + } + } + + public Node (K# key, V# value, Node? prev, Node? next) { + this.key = #key; + this.value = #value; + this.color = Color.RED; + this.prev = prev; + this.next = next; + if (prev != null) + prev.next = this; + if (next != null) + next.prev = this; + } + + ~Node () { + if (prev != null) + prev.next = this.next; + if (next != null) + next.prev = this.prev; + } + + public void flip () { + color.flip (); + if (left != null) left.color = left.color.flip (); + if (right != null) right.color = right.color.flip (); + } + + public K key; + public V value; + public Color color; + public Node? left; + public Node? right; + public weak Node? prev; + public weak Node? next; + } + + private Node? root; + private weak Node? first; + private int stamp = 0; + + private class KeySet : Object, Iterable, Collection, Set { + public TreeMap map {construct; get;} + + public KeySet (TreeMap map) { + this.map = map; + } + + public Type get_element_type () { + return typeof (K); + } + + public Iterator iterator () { + return new KeyIterator (map); + } + + public int size { + get { return map.size; } + } + + public bool add (K key) { + assert_not_reached (); + } + + public void clear () { + assert_not_reached (); + } + + public bool remove (K key) { + assert_not_reached (); + } + + public bool contains (K key) { + return map.contains (key); + } + } + + private class ValueCollection : Object, Iterable, Collection { + public TreeMap map {construct; get;} + + public ValueCollection (TreeMap map) { + this.map = map; + } + + public Type get_element_type () { + return typeof (V); + } + + public Iterator iterator () { + return new ValueIterator (map); + } + + public int size { + get { return map.size; } + } + + public bool add (V key) { + assert_not_reached (); + } + + public void clear () { + assert_not_reached (); + } + + public bool remove (V key) { + assert_not_reached (); + } + + public bool contains (V key) { + Iterator it = iterator (); + while (it.next ()) { + if (map.value_equal_func (key, it.get ())) + return true; + } + return false; + } + } + + private class KeyIterator : Object, Gee.Iterator { + public TreeMap map {construct; get;} + private int stamp; + construct { + stamp = map.stamp; + } + + public KeyIterator (TreeMap map) { + this.map = map; + } + + public bool next () { + if (cur != null) { + cur = cur.next; + return cur != null; + } else if (!run){ + run = true; + cur = map.first; + return cur != null; + } else { + return false; + } + } + + public K? get () { + assert (stamp == map.stamp); + assert (cur != null); + return cur.key; + } + + private weak Node? cur; + private bool run = false; + } + + private class ValueIterator : Object, Gee.Iterator { + public TreeMap map {construct; get;} + private int stamp; + construct { + stamp = map.stamp; + } + + public ValueIterator (TreeMap map) { + this.map = map; + } + + public bool next () { + if (cur != null) { + cur = cur.next; + return cur != null; + } else if (!run){ + run = true; + cur = map.first; + return cur != null; + } else { + return false; + } + } + + public V? get () { + assert (stamp == map.stamp); + assert (cur != null); + return cur.value; + } + + private weak Node? cur; + private bool run = false; + } +} diff --git a/gee/treeset.vala b/gee/treeset.vala new file mode 100644 index 0000000..8f04a71 --- /dev/null +++ b/gee/treeset.vala @@ -0,0 +1,305 @@ +/* set.vala + * + * Copyright (C) 2009 Maciej Piechotka + * + * 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: + * Maciej Piechotka + */ + +using GLib; + +/** + * Left-leaning red-black tree implementation of Set interface. + */ +public class Gee.TreeSet : Object, Iterable, Collection, Set +{ + public static int direct_compare (void *_val1, void *_val2) { + long val1 = (long)_val1, val2 = (long)_val2; + if (val1 > val2) + return 1; + else if (val1 == val2) + return 0; + else + return -1; + } + + public int size {get {return _size;} } + private int _size = 0; + + public TreeSet (CompareFunc compare_func = TreeSet.direct_compare) { + this.compare_func = compare_func; + } + + public CompareFunc compare_func {construct; get;} + + public bool contains (G item) { + weak Node? cur = root; + while (cur != null) { + int res = compare_func (item, cur.key); + if (res == 0) { + return true; + } else if (res < 0) { + cur = cur.left; + } else { + cur = cur.right; + } + } + return false; + } + + private static void rotate_right (ref Node root) { + Node pivot = #root.left; + pivot.color = root.color; + root.color = Node.Color.RED; + root.left = #pivot.right; + pivot.right = #root; + root = #pivot; + } + + private static void rotate_left (ref Node root) { + Node pivot = #root.right; + pivot.color = root.color; + root.color = Node.Color.RED; + root.right = #pivot.left; + pivot.left = #root; + root = #pivot; + } + + private static bool is_red (Node? n) { + return n != null && n.color == Node.Color.RED; + } + + private static bool is_black (Node? n) { + return n == null || n.color == Node.Color.BLACK; + } + + private static void fix_up (ref Node node) { + if (is_black (node.left) && is_red (node.right)) + rotate_left (ref node); + if (is_red (node.left) && is_black (node.right)) + rotate_right (ref node); + } + + private bool add_to_node (ref Node? node, G #item, Node? prev, Node? next) { + if (node == null) { + node = new Node(#item, prev, next); + if (prev == null) + first = node; + _size++; + return true; + } + + if (is_red (node.left) && is_red (node.right)) + node.flip (); + + int cmp = compare_func (item, node.key); + if (cmp == 0) { + fix_up (ref node); + return false; + } else if (cmp < 0) { + bool r = add_to_node (ref node.left, item, node.prev, node); + fix_up (ref node); + return r; + } else { + bool r = add_to_node (ref node.right, item, node, node.next); + fix_up (ref node); + return r; + } + } + + public bool add (G item) { + bool r = add_to_node (ref root, item, null, null); + root.color = Node.Color.BLACK; + stamp++; + return r; + } + + private static void move_red_left (ref Node root) { + root.flip (); + if (is_red (root.right.left)) { + rotate_right (ref root.right); + rotate_left (ref root); + root.flip (); + } + } + + private static void move_red_right (ref Node root) { + root.flip (); + if (is_red (root.left.left)) { + rotate_right (ref root.right); + root.flip (); + } + } + + private void remove_minimal (ref Node node, out G key) { + if (node.left == null) { + Node n = #node; + key = #n.key; + node = null; + return; + } + + if (is_black (node.left) && is_black (node.left.left)) + move_red_left (ref node); + + remove_minimal (ref node.left, out key); + + fix_up (ref node); + } + + private bool remove_from_node (ref Node? node, G item) { + if (node == null) { + return false; + } else if (compare_func (item, node.key) < 0) { + weak Node left = node.left; + if (left == null) + return false; + if (is_black (left) && is_black (left.left)) + move_red_left (ref node); + bool r = remove_from_node (ref node.left, item); + fix_up (ref node); + return r; + } else { + if (is_red (node.left)) + rotate_right (ref node); + + weak Node r = node.right; + if (compare_func (item, node.key) == 0 && r == null) { + node = null; + _size--; + return true; + } + if (is_black (r) && is_black (r.left) ) + move_red_right (ref node); + if (compare_func (item, node.key) == 0) { + remove_minimal (ref node.right, out node.key); + fix_up (ref node); + _size--; + return true; + } else { + bool re = remove_from_node (ref node.right, item); + fix_up (ref node); + return re; + } + } + } + + public bool remove (G item) { + bool b = remove_from_node (ref root, item); + if (root != null) + root.color = Node.Color.BLACK; + stamp++; + return b; + } + + public void clear () { + root = null; + _size = 0; + stamp++; + } + + public Type get_element_type () { + return typeof (G); + } + + public Gee.Iterator iterator () { + return new Iterator (this); + } + + [Compact] + private class Node { + public enum Color { + RED, + BLACK; + public Color flip () { + if (this == RED) + return BLACK; + else + return RED; + } + } + + public Node (G# node, Node? prev, Node? next) { + this.key = #node; + this.color = Color.RED; + this.prev = prev; + this.next = next; + if (prev != null) + prev.next = this; + if (next != null) + next.prev = this; + } + + ~Node () { + if (prev != null) + prev.next = this.next; + if (next != null) + next.prev = this.prev; + } + + public void flip () { + color.flip (); + if (left != null) left.color = left.color.flip (); + if (right != null) right.color = right.color.flip (); + } + + public G key; + public Color color; + public Node? left; + public Node? right; + public weak Node? prev; + public weak Node? next; + } + + private class Iterator : Object, Gee.Iterator { + public TreeSet set {construct; get;} + private int stamp; + construct { + stamp = set.stamp; + } + + public Iterator (TreeSet set) { + this.set = set; + } + + public bool next () { + if (cur != null) { + cur = cur.next; + return cur != null; + } else if (!run){ + run = true; + cur = set.first; + return cur != null; + } else { + return false; + } + } + + public G? get () { + assert (stamp == set.stamp); + assert (cur != null); + return cur.key; + } + + private weak Node? cur; + private bool run = false; + } + + private Node? root; + private weak Node? first; + private int stamp = 0; +} diff --git a/tests/Makefile.am b/tests/Makefile.am index 18255e1..74cc981 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -38,3 +38,21 @@ $(testhashset_SOURCES): $(testhashset_VALASOURCES) testhashset_LDADD = $(progs_ldadd) EXTRA_DIST += $(testhashset_VALASOURCES) +TEST_PROGS += testtreeset +testtreeset_VALASOURCES = testtreeset.vala +testtreeset_SOURCES = testtreeset.c testtreeset.h +$(testtreeset_SOURCES): $(testtreeset_VALASOURCES) + $(VALAC) -C --basedir $(top_srcdir) --vapidir $(top_srcdir)/gee --pkg gee-1.0 $^ + touch $@ +testtreeset_LDADD = $(progs_ldadd) +EXTRA_DIST += $(testtreeset_VALASOURCES) + +TEST_PROGS += testtreemap +testtreemap_VALASOURCES = testtreemap.vala +testtreemap_SOURCES = testtreemap.c testtreemap.h +$(testtreemap_SOURCES): $(testtreemap_VALASOURCES) + $(VALAC) -C --basedir $(top_srcdir) --vapidir $(top_srcdir)/gee --pkg gee-1.0 $^ + touch $@ +testtreemap_LDADD = $(progs_ldadd) +EXTRA_DIST += $(testtreemap_VALASOURCES) + diff --git a/tests/testtreemap.vala b/tests/testtreemap.vala new file mode 100644 index 0000000..5daddac --- /dev/null +++ b/tests/testtreemap.vala @@ -0,0 +1,314 @@ +/* testtreeset.vala + * + * Copyright (C) 2008 Maciej Piechotka + * + * 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: + * Maciej Piechotka + */ + +using GLib; +using Gee; + +const string CODE_NOT_REACHABLE = "*code should not be reached*"; + +void test_treemap_get () { + var treemap = new TreeMap (strcmp, str_equal); + + // Check get from empty map + assert (treemap.get ("foo") == null); + + // Check get from map with one items + treemap.set ("key", "value"); + assert (treemap.get ("key") == "value"); + + // Check get from non-existing key + assert (treemap.get ("foo") == null); + + // Check get from map with multiple items + treemap.set ("key2", "value2"); + treemap.set ("key3", "value3"); + assert (treemap.get ("key") == "value"); + assert (treemap.get ("key2") == "value2"); + assert (treemap.get ("key3") == "value3"); + +} + +void test_treemap_set () { + var treemap = new TreeMap (strcmp, str_equal); + + // check map is empty + assert (treemap.size == 0); + + // check set an item to map + treemap.set ("abc", "one"); + assert (treemap.contains ("abc")); + assert (treemap.get ("abc") == "one"); + assert (treemap.size == 1); + + // check set an item to map with same value + treemap.set ("def", "one"); + assert (treemap.contains ("def")); + assert (treemap.get ("abc") == "one"); + assert (treemap.get ("def") == "one"); + assert (treemap.size == 2); + + // check set with same key + treemap.set ("def", "two"); + assert (treemap.contains ("def")); + assert (treemap.get ("abc") == "one"); + assert (treemap.get ("def") == "two"); + assert (treemap.size == 2); +} + +void test_treemap_remove () { + var treemap = new TreeMap (strcmp, str_equal); + + // check removing when map is empty + treemap.remove ("foo"); + assert (treemap.size == 0); + + // add items + treemap.set ("aaa", "111"); + treemap.set ("bbb", "222"); + treemap.set ("ccc", "333"); + treemap.set ("ddd", "444"); + assert (treemap.size == 4); + + // check remove on first place + treemap.remove ("aaa"); + assert (treemap.size == 3); + + // check remove in between + treemap.remove ("ccc"); + assert (treemap.size == 2); + + // check remove in last place + treemap.remove ("ddd"); + assert (treemap.size == 1); + + // check remove invalid key + treemap.remove ("bar"); + + // check remove last in map + treemap.remove ("bbb"); + assert (treemap.size == 0); +} + +void test_treemap_contains () { + var treemap = new TreeMap (strcmp, str_equal); + + // Check on empty map + assert (!treemap.contains ("111")); + + // Check items + treemap.set ("10", "111"); + assert (treemap.contains ("10")); + assert (!treemap.contains ("20")); + assert (!treemap.contains ("30")); + + assert (treemap.get ("10") == "111"); + + treemap.set ("20", "222"); + assert (treemap.contains ("10")); + assert (treemap.contains ("20")); + assert (!treemap.contains ("30")); + + assert (treemap.get ("10") == "111"); + assert (treemap.get ("20") == "222"); + + treemap.set ("30", "333"); + assert (treemap.contains ("10")); + assert (treemap.contains ("20")); + assert (treemap.contains ("30")); + + assert (treemap.get ("10") == "111"); + assert (treemap.get ("20") == "222"); + assert (treemap.get ("30") == "333"); + + // Clear and recheck + treemap.clear (); + assert (!treemap.contains ("10")); + assert (!treemap.contains ("20")); + assert (!treemap.contains ("30")); + + var treemapOfInt = new TreeMap (); + + // Check items + treemapOfInt.set (10, 111); + assert (treemapOfInt.contains (10)); + assert (!treemapOfInt.contains (20)); + assert (!treemapOfInt.contains (30)); + + assert (treemapOfInt.get (10) == 111); + + treemapOfInt.set (20, 222); + assert (treemapOfInt.contains (10)); + assert (treemapOfInt.contains (20)); + assert (!treemapOfInt.contains (30)); + + assert (treemapOfInt.get (10) == 111); + assert (treemapOfInt.get (20) == 222); + + treemapOfInt.set (30, 333); + assert (treemapOfInt.contains (10)); + assert (treemapOfInt.contains (20)); + assert (treemapOfInt.contains (30)); + + assert (treemapOfInt.get (10) == 111); + assert (treemapOfInt.get (20) == 222); + assert (treemapOfInt.get (30) == 333); +} + +void test_treemap_size () { + var treemap = new TreeMap (strcmp, str_equal); + + // Check empty map + assert (treemap.size == 0); + + // Check when one item + treemap.set ("1", "1"); + assert (treemap.size == 1); + + // Check when more items + treemap.set ("2", "2"); + assert (treemap.size == 2); + + // Check when items cleared + treemap.clear (); + assert (treemap.size == 0); +} + +void test_treemap_get_keys () { + var treemap = new TreeMap (strcmp, str_equal); + + // Check keys on empty map + var keySet = treemap.get_keys (); + assert (keySet.size == 0); + + // Check keys on map with one item + treemap.set ("aaa", "111"); + assert (keySet.size == 1); + assert (keySet.contains ("aaa")); + keySet = treemap.get_keys (); + assert (keySet.size == 1); + assert (keySet.contains ("aaa")); + + // Check modify key set directly + if (Test.trap_fork (0, TestTrapFlags.SILENCE_STDOUT | TestTrapFlags.SILENCE_STDERR)) { + keySet.add ("ccc"); + return; + } + Test.trap_assert_failed (); + Test.trap_assert_stderr (CODE_NOT_REACHABLE); + + // Check keys on map with multiple items + treemap.set ("bbb", "222"); + assert (keySet.size == 2); + assert (keySet.contains ("aaa")); + assert (keySet.contains ("bbb")); + keySet = treemap.get_keys (); + assert (keySet.size == 2); + assert (keySet.contains ("aaa")); + assert (keySet.contains ("bbb")); + + // Check keys on map clear + treemap.clear (); + assert (keySet.size == 0); + keySet = treemap.get_keys (); + assert (keySet.size == 0); + +} + +void test_treemap_get_values () { + var treemap = new TreeMap (strcmp, str_equal); + + // Check keys on empty map + var valueCollection = treemap.get_values (); + assert (valueCollection.size == 0); + + // Check keys on map with one item + treemap.set ("aaa", "111"); + assert (valueCollection.size == 1); + assert (valueCollection.contains ("111")); + valueCollection = treemap.get_values (); + assert (valueCollection.size == 1); + assert (valueCollection.contains ("111")); + + // Check modify key set directly + if (Test.trap_fork (0, TestTrapFlags.SILENCE_STDOUT | TestTrapFlags.SILENCE_STDERR)) { + valueCollection.add ("ccc"); + return; + } + Test.trap_assert_failed (); + Test.trap_assert_stderr (CODE_NOT_REACHABLE); + + // Check keys on map with multiple items + treemap.set ("bbb", "222"); + assert (valueCollection.size == 2); + assert (valueCollection.contains ("111")); + assert (valueCollection.contains ("222")); + valueCollection = treemap.get_values (); + assert (valueCollection.size == 2); + assert (valueCollection.contains ("111")); + assert (valueCollection.contains ("222")); + + // Check keys on map clear + treemap.clear (); + assert (valueCollection.size == 0); + valueCollection = treemap.get_values (); + assert (valueCollection.size == 0); + +} + +void test_treemap_clear () { + var treemap = new TreeMap (strcmp, str_equal); + assert (treemap.size == 0); + + // Check clear on empty map + treemap.clear (); + assert (treemap.size == 0); + + // Check clear one item + treemap.set ("1", "1"); + assert (treemap.size == 1); + treemap.clear (); + assert (treemap.size == 0); + + // Check clear multiple items + treemap.set ("1", "1"); + treemap.set ("2", "2"); + treemap.set ("3", "3"); + assert (treemap.size == 3); + treemap.clear (); + assert (treemap.size == 0); +} + +void main (string[] args) { + Test.init (ref args); + + Test.add_func ("/TreeMap/Map/get", test_treemap_get); + Test.add_func ("/TreeMap/Map/set", test_treemap_set); + Test.add_func ("/TreeMap/Map/remove", test_treemap_remove); + Test.add_func ("/TreeMap/Map/contains", test_treemap_contains); + Test.add_func ("/TreeMap/Map/size", test_treemap_size); + Test.add_func ("/TreeMap/Map/get_keys", test_treemap_get_keys); + Test.add_func ("/TreeMap/Map/get_values", test_treemap_get_values); + Test.add_func ("/TreeMap/Map/clear", test_treemap_clear); + + Test.run (); +} + diff --git a/tests/testtreeset.vala b/tests/testtreeset.vala new file mode 100644 index 0000000..00f871a --- /dev/null +++ b/tests/testtreeset.vala @@ -0,0 +1,288 @@ +/* testtreeset.vala + * + * Copyright (C) 2008 Maciej Piechotka + * + * 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: + * Maciej Piechotka + */ + +using GLib; +using Gee; + +void test_treeset_add () { + // Check adding of strings + var treeset = new TreeSet (strcmp); + + treeset.add ("42"); + assert (treeset.contains ("42")); + assert (treeset.size == 1); + + treeset.add ("43"); + assert (treeset.contains ("42")); + assert (treeset.contains ("43")); + assert (treeset.size == 2); + + // Check add same element + assert (treeset.size == 2); + treeset.add ("43"); + assert (treeset.contains ("42")); + assert (treeset.contains ("43")); + assert (treeset.size == 2); + + // Check adding of ints + var treesetInt = new TreeSet (); + + treesetInt.add (42); + assert (treesetInt.contains (42)); + assert (treesetInt.size == 1); + + treesetInt.add (43); + assert (treesetInt.contains (42)); + assert (treesetInt.contains (43)); + assert (treesetInt.size == 2); + + // Check add same element + assert (treesetInt.size == 2); + treesetInt.add (43); + assert (treesetInt.contains (42)); + assert (treesetInt.contains (43)); + assert (treesetInt.size == 2); + + // Check adding of objects + var treesetObject = new TreeSet (); + + var fooObject = new Object(); + treesetObject.add (fooObject); + assert (treesetObject.contains (fooObject)); + assert (treesetObject.size == 1); + + var fooObject2 = new Object(); + treesetObject.add (fooObject2); + assert (treesetObject.contains (fooObject)); + assert (treesetObject.contains (fooObject2)); + assert (treesetObject.size == 2); + + // Check add same element + assert (treesetObject.size == 2); + treesetObject.add (fooObject2); + assert (treesetObject.contains (fooObject)); + assert (treesetObject.contains (fooObject2)); + assert (treesetObject.size == 2); +} + +void test_treeset_clear () { + var treeset = new TreeSet (strcmp); + assert (treeset.size == 0); + + // Check clear on empty set + treeset.clear (); + assert (treeset.size == 0); + + // Check clear one item + treeset.add ("1"); + assert (treeset.size == 1); + treeset.clear (); + assert (treeset.size == 0); + + // Check clear multiple items + treeset.add ("1"); + treeset.add ("2"); + treeset.add ("3"); + assert (treeset.size == 3); + treeset.clear (); + assert (treeset.size == 0); +} + +void test_treeset_contains () { + var treesetString = new TreeSet (strcmp); + + // Check on empty set + assert (!treesetString.contains ("1")); + + // Check items + treesetString.add ("10"); + assert (treesetString.contains ("10")); + assert (!treesetString.contains ("20")); + assert (!treesetString.contains ("30")); + + treesetString.add ("20"); + assert (treesetString.contains ("10")); + assert (treesetString.contains ("20")); + assert (!treesetString.contains ("30")); + + treesetString.add ("30"); + assert (treesetString.contains ("10")); + assert (treesetString.contains ("20")); + assert (treesetString.contains ("30")); + + // Clear and recheck + treesetString.clear (); + assert (!treesetString.contains ("10")); + assert (!treesetString.contains ("20")); + assert (!treesetString.contains ("30")); + + var treesetInt = new TreeSet (); + + // Check items + treesetInt.add (10); + assert (treesetInt.contains (10)); + assert (!treesetInt.contains (20)); + assert (!treesetInt.contains (30)); + + treesetInt.add (20); + assert (treesetInt.contains (10)); + assert (treesetInt.contains (20)); + assert (!treesetInt.contains (30)); + + treesetInt.add (30); + assert (treesetInt.contains (10)); + assert (treesetInt.contains (20)); + assert (treesetInt.contains (30)); + + // Clear and recheck + treesetInt.clear (); + assert (!treesetInt.contains (10)); + assert (!treesetInt.contains (20)); + assert (!treesetInt.contains (30)); +} + +void test_treeset_remove () { + var treesetString = new TreeSet (strcmp); + + // Check remove if list is empty + treesetString.remove ("42"); + + // Add 5 different elements + treesetString.add ("42"); + treesetString.add ("43"); + treesetString.add ("44"); + treesetString.add ("45"); + treesetString.add ("46"); + assert (treesetString.size == 5); + + // Check remove first + treesetString.remove ("42"); + assert (treesetString.size == 4); + assert (treesetString.contains ("43")); + assert (treesetString.contains ("44")); + assert (treesetString.contains ("45")); + assert (treesetString.contains ("46")); + + // Check remove last + treesetString.remove ("46"); + assert (treesetString.size == 3); + assert (treesetString.contains ("43")); + assert (treesetString.contains ("44")); + assert (treesetString.contains ("45")); + + // Check remove in between + treesetString.remove ("44"); + assert (treesetString.size == 2); + assert (treesetString.contains ("43")); + assert (treesetString.contains ("45")); + + // Check removing of int element + var treesetInt = new TreeSet (); + + // Add 5 different elements + treesetInt.add (42); + treesetInt.add (43); + treesetInt.add (44); + treesetInt.add (45); + treesetInt.add (46); + assert (treesetInt.size == 5); + + // Remove first + treesetInt.remove (42); + assert (treesetInt.size == 4); + assert (treesetInt.contains (43)); + assert (treesetInt.contains (44)); + assert (treesetInt.contains (45)); + assert (treesetInt.contains (46)); + + // Remove last + treesetInt.remove (46); + assert (treesetInt.size == 3); + assert (treesetInt.contains (43)); + assert (treesetInt.contains (44)); + assert (treesetInt.contains (45)); + + // Remove in between + treesetInt.remove (44); + assert (treesetInt.size == 2); + assert (treesetInt.contains (43)); + assert (treesetInt.contains (45)); +} + +void test_treeset_size () { + var treeset = new TreeSet (strcmp); + + // Check empty list + assert (treeset.size == 0); + + // Check when one item + treeset.add ("1"); + assert (treeset.size == 1); + + // Check when more items + treeset.add ("2"); + assert (treeset.size == 2); + + // Check when items cleared + treeset.clear (); + assert (treeset.size == 0); +} + +void test_treeset_iterator () { + var treeset = new TreeSet (strcmp); + + // Check iterate empty list + var iterator = treeset.iterator (); + assert (!iterator.next()); + + // Check iterate list + treeset.add ("42"); + treeset.add ("43"); + + iterator = treeset.iterator (); + + assert (iterator.next()); + string firstString = iterator.get(); + assert (treeset.contains (firstString)); + assert (firstString == "42") + + assert (iterator.next()); + string secondString = iterator.get(); + assert (treeset.contains (secondString)); + assert (secondString == "43"); + + assert (!iterator.next()); +} +void main (string[] args) { + Test.init (ref args); + + Test.add_func ("/TreeSet/Collection/add", test_treeset_add); + Test.add_func ("/TreeSet/Collection/clear", test_treeset_clear); + Test.add_func ("/TreeSet/Collection/contains", test_treeset_contains); + Test.add_func ("/TreeSet/Collection/remove", test_treeset_remove); + Test.add_func ("/TreeSet/Collection/size", test_treeset_size); + + Test.add_func ("/TreeSet/Iterable/iterator", test_treeset_iterator); + + Test.run (); +} + -- 1.6.2