[libgee] Add left-leaning red-black tree based set and map

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

commit 01f1bc34185cf4fb8919a16d64e1b5d449d3abaa
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date:   Sun Jul 19 22:29:17 2009 +0200

    Add left-leaning red-black tree based set and map
    
    Fixes bug 583728.
    
    Signed-off-by: Didier 'Ptitjes <ptitjes free fr>

 gee/Makefile.am        |    3 +
 gee/functions.vala     |   36 ++++
 gee/treemap.vala       |  443 ++++++++++++++++++++++++++++++++++++++++++++++++
 gee/treeset.vala       |  317 ++++++++++++++++++++++++++++++++++
 tests/Makefile.am      |   18 ++
 tests/testtreemap.vala |  310 +++++++++++++++++++++++++++++++++
 tests/testtreeset.vala |  287 +++++++++++++++++++++++++++++++
 7 files changed, 1414 insertions(+), 0 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 7838a1e..dd0b35c 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -15,6 +15,7 @@ lib_LTLIBRARIES = \
 libgee_la_VALASOURCES = \
 	arraylist.vala \
 	collection.vala \
+	functions.vala \
 	hashmap.vala \
 	hashset.vala \
 	iterable.vala \
@@ -26,6 +27,8 @@ libgee_la_VALASOURCES = \
 	readonlymap.vala \
 	readonlyset.vala \
 	set.vala \
+	treemap.vala \
+	treeset.vala \
 	$(NULL)
 
 libgee_la_SOURCES = \
diff --git a/gee/functions.vala b/gee/functions.vala
new file mode 100644
index 0000000..85777f0
--- /dev/null
+++ b/gee/functions.vala
@@ -0,0 +1,36 @@
+/* functions.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 <uzytkownik2 gmail com>
+ */
+
+using GLib;
+
+namespace Gee {
+	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;
+		}
+	}
+}
diff --git a/gee/treemap.vala b/gee/treemap.vala
new file mode 100644
index 0000000..e286779
--- /dev/null
+++ b/gee/treemap.vala
@@ -0,0 +1,443 @@
+/* treemap.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 <uzytkownik2 gmail com>
+ */
+
+using GLib;
+
+/**
+ * Left-leaning red-black tree implementation of the Map interface.
+ */
+public class Gee.TreeMap<K,V> : Object, Map<K,V> {
+	public int size {
+		get { return _size; }
+	}
+
+	public CompareFunc key_compare_func { construct; get; }
+	public EqualFunc value_equal_func { construct; get; }
+
+	private int _size = 0;
+
+	public TreeMap (CompareFunc key_compare_func = Gee.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<K> get_keys () {
+		return new KeySet<K,V> (this);
+	}
+
+	public Collection<V> get_values () {
+		return new ValueCollection<K,V> (this);
+	}
+
+	private void rotate_right (ref Node<K, V> root) {
+		Node<K,V> pivot = (owned) root.left;
+		pivot.color = root.color;
+		root.color = Node.Color.RED;
+		root.left = (owned) pivot.right;
+		pivot.right = (owned) root;
+		root = (owned) pivot;
+	}
+
+	private void rotate_left (ref Node<K, V> root) {
+		Node<K,V> pivot = (owned) root.right;
+		pivot.color = root.color;
+		root.color = Node.Color.RED;
+		root.right = (owned) pivot.left;
+		pivot.left = (owned) root;
+		root = (owned) pivot;
+	}
+
+	private bool is_red (Node<K, V>? n) {
+		return n != null && n.color == Node.Color.RED;
+	}
+
+	private bool is_black (Node<K, V>? n) {
+		return n == null || n.color == Node.Color.BLACK;
+	}
+
+	public bool contains (K key) {
+		weak Node<K, V>? 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 new V? get (K key) {
+		weak Node<K, V>? 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<K, V>? node, K key, V value, Node<K, V>? prev, Node<K, V>? next) {
+		if (node == null) {
+			node = new Node<K,V> (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 new void set (K key, V value) {
+		set_to_node (ref root, key, value, null, null);
+		root.color = Node.Color.BLACK;
+	}
+
+	private void move_red_left (ref Node<K, V> root) {
+		root.flip ();
+		if (is_red (root.right.left)) {
+			rotate_right (ref root.right);
+			rotate_left (ref root);
+			root.flip ();
+		}
+	}
+
+	private void move_red_right (ref Node<K, V> root) {
+		root.flip ();
+		if (is_red (root.left.left)) {
+			rotate_right (ref root.right);
+			root.flip ();
+		}
+	}
+
+	private void remove_minimal (ref Node<K,V> node, out K key, out V value) {
+		if (node.left == null) {
+			Node<K,V> n = (owned) node;
+			key = (owned) n.key;
+			value = (owned) 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<K, V>? node, K key) {
+		if (node == null) {
+			return false;
+		} else if (key_compare_func (key, node.key) < 0) {
+			weak Node<K,V> 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<K,V> 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 void fix_up (ref Node<K,V> 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<K, V> {
+		public enum Color {
+			RED,
+			BLACK;
+
+			public Color flip () {
+				if (this == RED) {
+					return BLACK;
+				} else {
+					return RED;
+				}
+			}
+		}
+
+		public Node (owned K key, owned V value, Node<K,V>? prev, Node<K,V>? next) {
+			this.key = (owned) key;
+			this.value = (owned) 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<K, V>? left;
+		public Node<K, V>? right;
+		public weak Node<K, V>? prev;
+		public weak Node<K, V>? next;
+	}
+
+	private Node<K, V>? root;
+	private weak Node<K, V>? first;
+	private int stamp = 0;
+
+	private class KeySet<K,V> : Object, Iterable<K>, Collection<K>, Set<K> {
+		public TreeMap<K,V> map { construct; get; }
+
+		public KeySet (TreeMap<K,V> map) {
+			this.map = map;
+		}
+
+		public Type get_element_type () {
+			return typeof (K);
+		}
+
+		public Iterator<K> iterator () {
+			return new KeyIterator<K,V> (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<K,V> : Object, Iterable<K>, Collection<V> {
+		public TreeMap<K,V> map { construct; get; }
+
+		public ValueCollection (TreeMap map) {
+			this.map = map;
+		}
+
+		public Type get_element_type () {
+			return typeof (V);
+		}
+
+		public Iterator<V> iterator () {
+			return new ValueIterator<K,V> (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<V> it = iterator ();
+			while (it.next ()) {
+				if (map.value_equal_func (key, it.get ())) {
+					return true;
+				}
+			}
+			return false;
+		}
+	}
+
+	private class KeyIterator<K,V> : Object, Gee.Iterator<K> {
+		public TreeMap<K,V> map { construct; get; }
+		private int stamp;
+		construct {
+			stamp = map.stamp;
+		}
+
+		public KeyIterator (TreeMap<K,V> map) {
+			this.map = map;
+		}
+
+		public bool next () {
+			if (current != null) {
+				current = current.next;
+				return current != null;
+			} else if (!run){
+				run = true;
+				current = map.first;
+				return current != null;
+			} else {
+				return false;
+			}
+		}
+
+		public new K? get () {
+			assert (stamp == map.stamp);
+			assert (current != null);
+			return current.key;
+		}
+
+		private weak Node<K, V>? current;
+		private bool run = false;
+	}
+
+	private class ValueIterator<K,V> : Object, Gee.Iterator<V> {
+		public TreeMap<K,V> map { construct; get; }
+		private int stamp;
+		construct {
+			stamp = map.stamp;
+		}
+
+		public ValueIterator (TreeMap<K,V> map) {
+			this.map = map;
+		}
+
+		public bool next () {
+			if (current != null) {
+				current = current.next;
+				return current != null;
+			} else if (!run) {
+				run = true;
+				current = map.first;
+				return current != null;
+			} else {
+				return false;
+			}
+		}
+
+		public new V? get () {
+			assert (stamp == map.stamp);
+			assert (current != null);
+			return current.value;
+		}
+
+		private weak Node<K, V>? current;
+		private bool run = false;
+	}
+}
diff --git a/gee/treeset.vala b/gee/treeset.vala
new file mode 100644
index 0000000..0104bec
--- /dev/null
+++ b/gee/treeset.vala
@@ -0,0 +1,317 @@
+/* treeset.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 <uzytkownik2 gmail com>
+ */
+
+using GLib;
+
+/**
+ * Left-leaning red-black tree implementation of the Set interface.
+ */
+public class Gee.TreeSet<G> : Object, Iterable<G>, Collection<G>, Set<G> {
+	public int size {
+		get {return _size;}
+	}
+
+	public CompareFunc compare_func { construct; get; }
+
+	private int _size = 0;
+
+	public TreeSet (CompareFunc compare_func = Gee.direct_compare) {
+		this.compare_func = compare_func;
+	}
+
+	public bool contains (G item) {
+		weak Node<G>? 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 void rotate_right (ref Node<G> root) {
+		Node<G> pivot = (owned) root.left;
+		pivot.color = root.color;
+		root.color = Node.Color.RED;
+		root.left = (owned) pivot.right;
+		pivot.right = (owned) root;
+		root = (owned) pivot;
+	}
+
+	private void rotate_left (ref Node<G> root) {
+		Node<G> pivot = (owned) root.right;
+		pivot.color = root.color;
+		root.color = Node.Color.RED;
+		root.right = (owned) pivot.left;
+		pivot.left = (owned) root;
+		root = (owned) pivot;
+	}
+
+	private bool is_red (Node<G>? n) {
+		return n != null && n.color == Node.Color.RED;
+	}
+
+	private bool is_black (Node<G>? n) {
+		return n == null || n.color == Node.Color.BLACK;
+	}
+
+	private void fix_up (ref Node<G> 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<G>? node, owned G item, Node<G>? prev, Node<G>? next) {
+		if (node == null) {
+			node = new Node<G> ((owned) 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 void move_red_left (ref Node<G> root) {
+		root.flip ();
+		if (is_red (root.right.left)) {
+			rotate_right (ref root.right);
+			rotate_left (ref root);
+			root.flip ();
+		}
+	}
+
+	private void move_red_right (ref Node<G> root) {
+		root.flip ();
+		if (is_red (root.left.left)) {
+			rotate_right (ref root.right);
+			root.flip ();
+		}
+	}
+
+	private void remove_minimal (ref Node<G> node, out G key) {
+		if (node.left == null) {
+			Node<G> n = (owned) node;
+			key = (owned) 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<G>? node, G item) {
+		if (node == null) {
+			return false;
+		} else if (compare_func (item, node.key) < 0) {
+			weak Node<G> 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<G> 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<G> iterator () {
+		return  new Iterator<G> (this);
+	}
+
+	[Compact]
+	private class Node<G> {
+		public enum Color {
+			RED,
+			BLACK;
+
+			public Color flip () {
+				if (this == RED) {
+					return BLACK;
+				} else {
+					return RED;
+				}
+			}
+		}
+
+		public Node (owned G node, Node<G>? prev, Node<G>? next) {
+			this.key = (owned) 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<G>? left;
+		public Node<G>? right;
+		public weak Node<G>? prev;
+		public weak Node<G>? next;
+	}
+
+	private class Iterator<G> : Object, Gee.Iterator<G> {
+		public new TreeSet<G> set {construct; get;}
+		private int stamp;
+		construct {
+			stamp = set.stamp;
+		}
+
+		public Iterator (TreeSet<G> set) {
+			this.set = set;
+		}
+
+		public bool next () {
+			if (current != null) {
+				current = current.next;
+				return current != null;
+			} else if (!run){
+				run = true;
+				current = set.first;
+				return current != null;
+			} else {
+				return false;
+			}
+		}
+
+		public new G? get () {
+			assert (stamp == set.stamp);
+			assert (current != null);
+			return current.key;
+		}
+
+		private weak Node<G>? current;
+		private bool run = false;
+	}
+
+	private Node<G>? root;
+	private weak Node<G>? first;
+	private int stamp = 0;
+}
diff --git a/tests/Makefile.am b/tests/Makefile.am
index cbfcb34..68cfec5 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..b92f3ef
--- /dev/null
+++ b/tests/testtreemap.vala
@@ -0,0 +1,310 @@
+/* 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 <uzytkownik2 gmail com>
+ */
+
+using GLib;
+using Gee;
+
+const string CODE_NOT_REACHABLE = "*code should not be reached*";
+
+void test_treemap_get () {
+	var treemap = new TreeMap<string,string> ((CompareFunc) 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<string,string> ((CompareFunc) 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<string,string> ((CompareFunc) 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<string,string> ((CompareFunc) 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<int,int> ();
+
+	// 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<string,string> ((CompareFunc) 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<string,string> ((CompareFunc) 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<string,string> ((CompareFunc) 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<string,string> ((CompareFunc) 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..a3d6385
--- /dev/null
+++ b/tests/testtreeset.vala
@@ -0,0 +1,287 @@
+/* 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 <uzytkownik2 gmail com>
+ */
+
+using GLib;
+using Gee;
+
+void test_treeset_add () {
+	// Check adding of strings
+	var treeset = new TreeSet<string> ((CompareFunc) 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<int> ();
+
+	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<Object> ();
+
+	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<string> ((CompareFunc) 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<string> ((CompareFunc) 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<int> ();
+
+	// 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<string> ((CompareFunc) 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<int> ();
+
+	// 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<string> ((CompareFunc) 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<string> ((CompareFunc) 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 ();
+}