[libgee] Introduce the SortedSet interface and implement it in TreeSet



commit d5e6a680d6ebb0ffc5a9985a09f70473001f5e9f
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date:   Mon Sep 14 20:09:43 2009 +0200

    Introduce the SortedSet interface and implement it in TreeSet

 gee/Makefile.am          |    1 +
 gee/sortedset.vala       |  129 ++++++
 gee/treeset.vala         |  617 ++++++++++++++++++++++++++++--
 tests/Makefile.am        |    1 +
 tests/testsortedset.vala |  974 ++++++++++++++++++++++++++++++++++++++++++++++
 tests/testtreeset.vala   |   50 +---
 6 files changed, 1694 insertions(+), 78 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index e4b9b73..74adec8 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -46,6 +46,7 @@ libgee_la_VALASOURCES = \
 	readonlymap.vala \
 	readonlyset.vala \
 	set.vala \
+	sortedset.vala \
 	timsort.vala \
 	treemap.vala \
 	treemultiset.vala \
diff --git a/gee/sortedset.vala b/gee/sortedset.vala
new file mode 100644
index 0000000..2992859
--- /dev/null
+++ b/gee/sortedset.vala
@@ -0,0 +1,129 @@
+/* sortedset.vala
+ *
+ * Copyright (C) 2009  Didier Villevalois, 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>
+ */
+
+/**
+ * A sorted set, which you can navigate over and get sub-sets of.
+ */
+public interface Gee.SortedSet<G> : Gee.Set<G> {
+	/**
+	 * Returns the first element of the sorted set. Set must not be empty.
+	 *
+	 * @return the first element in the sorted set
+	 */
+	public abstract G first ();
+
+	/**
+	 * Returns the last element of the sorted set. Set must not be empty.
+	 *
+	 * @return the last element in the sorted set
+	 */
+	public abstract G last ();
+
+	/**
+	 * Returns a { link BidirIterator} that can be used for bi-directional
+	 * iteration over this sorted set.
+	 *
+	 * @return a { link BidirIterator} over this sorted set
+	 */
+	public abstract BidirIterator<G> bidir_iterator ();
+
+	/**
+	 * Returns a { link BidirIterator} initialy pointed at the specified
+	 * element.
+	 *
+	 * @param element the element to point the iterator at
+	 *
+	 * @return        a { link BidirIterator} over this sorted set, or null if
+	 *                the specified element is not in this set
+	 */
+	public abstract BidirIterator<G>? iterator_at (G element);
+
+	/**
+	 * Returns the element which is strictly lower than the specified element.
+	 *
+	 * @param element the element which you want the lower element for
+	 *
+	 * @return        the corresponding element
+	 */
+	public abstract G? lower (G element);
+
+	/**
+	 * Returns the element which is strictly higher than the specified element.
+	 *
+	 * @param element the element which you want the strictly higher element
+	 *                for
+	 *
+	 * @return        the corresponding element
+	 */
+	public abstract G? higher (G element);
+
+	/**
+	 * Returns the element which is lower or equal then the specified element.
+	 *
+	 * @param element the element which you want the lower or equal element for
+	 *
+	 * @return        the corresponding element
+	 */
+	public abstract G? floor (G element);
+
+	/**
+	 * Returns the element which is higher or equal then the specified element.
+	 *
+	 * @param element the element which you want the higher or equal element
+	 *                for
+	 *
+	 * @return        the corresponding element
+	 */
+	public abstract G? ceil (G element);
+
+	/**
+	 * Returns the sub-set of this sorted set containing elements strictly
+	 * lower than the specified element.
+	 *
+	 * @param from the lower inclusive bound for the sub-set
+	 *
+	 * @return     the corresponding sub-set of this sorted set
+	 */
+	public abstract SortedSet<G> head_set (G before);
+
+	/**
+	 * Returns the sub-set of this sorted set containing elements equal or
+	 * higher than the specified element.
+	 *
+	 * @param to the higher exclusive bound for the sub-set
+	 *
+	 * @return   the corresponding sub-set of this sorted set
+	 */
+	public abstract SortedSet<G> tail_set (G after);
+
+	/**
+	 * Returns the right-open sub-set of this sorted set, thus containing
+	 * elements equal or higher than the specified `from` element, and stricly
+	 * lower than the specified `to` element.
+	 *
+	 * @param from the lower inclusive bound for the sub-set
+	 * @param to   the higher exclusive bound for the sub-set
+	 *
+	 * @return     the corresponding sub-set of this sorted set
+	 */
+	public abstract SortedSet<G> sub_set (G from, G to);
+}
diff --git a/gee/treeset.vala b/gee/treeset.vala
index a49b67d..89ef142 100644
--- a/gee/treeset.vala
+++ b/gee/treeset.vala
@@ -32,7 +32,7 @@ using GLib;
  *
  * @see Gee.HashSet
  */
-public class Gee.TreeSet<G> : AbstractSet<G> {
+public class Gee.TreeSet<G> : AbstractSet<G>, SortedSet<G> {
 	/**
 	 * @inheritDoc
 	 */
@@ -136,10 +136,10 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 		if (node == null) {
 			node = new Node<G> ((owned) item, prev, next);
 			if (prev == null) {
-				first = node;
+				_first = node;
 			}
 			if (next == null) {
-				last = node;
+				_last = node;
 			}
 			_size++;
 			return true;
@@ -208,18 +208,18 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 	}
 
 	private inline void fix_removal (ref Node<G> node, out G? key = null) {
-		Node<G> n = (owned) node;
+		Node<G> n = (owned)node;
 		if (&key != null)
 			key = (owned) n.key;
 		if (n.prev != null) {
 			n.prev.next = n.next;
 		} else {
-			first = n.next;
+			_first = n.next;
 		}
 		if (n.next != null) {
 			n.next.prev = n.prev;
 		} else {
-			last = n.prev;
+			_last = n.prev;
 		}
 		node = null;
 		_size--;
@@ -240,7 +240,7 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 		fix_up (ref node);
 	}
 
-	private bool remove_from_node (ref Node<G>? node, G item) {
+	private bool remove_from_node (ref Node<G>? node, G item, out weak Node<G>? prev = null, out weak Node<G>? next = null) {
 #if DEBUG
 		stdout.printf ("Removing %s from %s\n", (string)item, node != null ? (string)node.key : null);
 #endif
@@ -254,7 +254,7 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 			if (is_black (left) && is_black (left.left)) {
 				move_red_left (ref node);
 			}
-			bool r = remove_from_node (ref node.left, item);
+			bool r = remove_from_node (ref node.left, item, out prev, out next);
 			fix_up (ref node);
 			return r;
 		} else {
@@ -264,6 +264,10 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 
 			weak Node<G>? r = node.right;
 			if (compare_func (item, node.key) == 0 && r == null) {
+				if (&prev != null)
+					prev = node.prev;
+				if (&next != null)
+					next = node.next;
 				fix_removal (ref node, null);
 				return true;
 			}
@@ -271,11 +275,15 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 				move_red_right (ref node);
 			}
 			if (compare_func (item, node.key) == 0) {
+				if (&prev != null)
+					prev = node.prev;
+				if (&next != null)
+					next = node;
 				remove_minimal (ref node.right, out node.key);
 				fix_up (ref node);
 				return true;
 			} else {
-				bool re = remove_from_node (ref node.right, item);
+				bool re = remove_from_node (ref node.right, item, out prev, out next);
 				fix_up (ref node);
 				return re;
 			}
@@ -323,9 +331,149 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 		return new Iterator<G> (this);
 	}
 
+	private inline G? lift_null_get (Node<G>? node) {
+		return node != null ? node.key : null;
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G first () {
+		assert (_first != null);
+		return _first.key;
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G last () {
+		assert (_last != null);
+		return _last.key;
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public SortedSet<G> head_set (G before) {
+		return new SubSet<G>.head (this, before);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public SortedSet<G> tail_set (G after) {
+		return new SubSet<G>.tail (this, after);
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public SortedSet<G> sub_set (G after, G before) {
+		return new SubSet<G> (this, after, before);
+	}
+
+	private inline weak Node<G>? find_node (G item) {
+		weak Node<G>? cur = root;
+		while (cur != null) {
+			int res = compare_func (item, cur.key);
+			if (res == 0) {
+				return cur;
+			} else if (res < 0) {
+				cur = cur.left;
+			} else {
+				cur = cur.right;
+			}
+		}
+		return null;
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public BidirIterator<G>? iterator_at (G item) {
+		weak Node<G>? node = find_node (item);
+		return node != null ? new Iterator<G>.pointing (this, node) : null;
+	}
+
+	private inline weak Node<G>? find_nearest (G item) {
+		weak Node<G>? cur = root;
+		while (cur != null) {
+			int res = compare_func (item, cur.key);
+			if (res == 0) {
+				return cur;
+			} else if (res < 0) {
+				if (cur.left == null)
+					return cur;
+				cur = cur.left;
+			} else {
+				if (cur.right == null)
+					return cur;
+				cur = cur.right;
+			}
+		}
+		return null;
+	}
+
+	private inline weak Node<G>? find_lower (G item) {
+		weak Node<G>? node = find_nearest (item);
+		if (node == null)
+			return null;
+		return compare_func (item, node.key) <= 0 ? node.prev : node;
+	}
+
+	private inline weak Node<G>? find_higher (G item) {
+		weak Node<G>? node = find_nearest (item);
+		if (node == null)
+			return null;
+		return compare_func (item, node.key) >= 0 ? node.next : node;
+	}
+
+	private inline weak Node<G>? find_floor (G item) {
+		weak Node<G>? node = find_nearest (item);
+		if (node == null)
+			return null;
+		return compare_func (item, node.key) < 0 ? node.prev : node;
+	}
+
+	private inline weak Node<G>? find_ceil (G item) {
+		weak Node<G>? node = find_nearest (item);
+		if (node == null)
+			return null;
+		return compare_func (item, node.key) > 0 ? node.next : node;
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? lower (G item) {
+		return lift_null_get (find_lower (item));
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? higher (G item) {
+		return lift_null_get (find_higher (item));
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? floor (G item) {
+		return lift_null_get (find_floor (item));
+	}
+
+	/**
+	 * @inheritDoc
+	 */
+	public G? ceil (G item) {
+		return lift_null_get (find_ceil (item));
+	}
+
 #if CONSISTENCY_CHECKS
 	public inline void check () {
 		check_subtree (root);
+		assert (root == null || root.color == Node.Color.BLACK);
 #if DEBUG
 		stdout.printf ("%s\n", dump ());
 #endif
@@ -415,46 +563,71 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 			stamp = _set.stamp;
 		}
 
+		public Iterator.pointing (TreeSet<G> set, Node<G> current) {
+			this._set = set;
+			this.current = current;
+			this.stamp = set.stamp;
+			this.started = true;
+		}
+
 		public bool next () {
 			assert (stamp == _set.stamp);
 			if (current != null) {
-				current = current.next;
+				if (current.next != null) {
+					current = current.next;
+					return true;
+				} else {
+					return false;
+				}
 			} else if (!started) {
-				current = _set.first;
+				current = _set._first;
 				started = true;
+				return current != null;
 			} else {
 				current = _next;
-				_next = null;
-				_prev = null;
+				if (current != null) {
+					_next = null;
+					_prev = null;
+				}
+				return current != null;
 			}
-			return current != null;
 		}
 
 		public bool has_next () {
 			assert (stamp == _set.stamp);
-			return (!started && _set.first != null) ||
+			return (!started && _set._first != null) ||
 			       (current == null && _next != null) ||
 			       (current != null && current.next != null);
 		}
 
 		public bool first () {
 			assert (stamp == _set.stamp);
-			current = _set.first;
+			current = _set._first;
 			_next = null;
 			_prev = null;
+			started = true;
 			return current != null; // on false it is null anyway
 		}
 
 		public bool previous () {
 			assert (stamp == _set.stamp);
 			if (current != null) {
-				current = current.prev;
+				if (current.prev != null) {
+					current = current.prev;
+					return true;
+				} else {
+					return false;
+				}
 			} else {
-				current = _prev;
-				_next = null;
-				_prev = null;
+				if (_prev != null) {
+					current = _prev;
+					_next = null;
+					_prev = null;
+					return true;
+				} else {
+					return false;
+				}
 			}
-			return current != null;
 		}
 
 		public bool has_previous () {
@@ -465,9 +638,10 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 
 		public bool last () {
 			assert (stamp == _set.stamp);
-			current = _set.last;
+			current = _set._last;
 			_next = null;
 			_prev = null;
+			started = true;
 			return current != null; // on false it is null anyway
 		}
 
@@ -480,12 +654,30 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 		public void remove () {
 			assert (stamp == _set.stamp);
 			assert (current != null);
-			_next = current.next;
-			_prev = current.prev;
-			_set.remove (get ());
-			stamp++;
+			_set.remove_from_node (ref _set.root, current.key, out _prev, out _next);
+			_set.root.color = Node.Color.BLACK;
 			current = null;
-			assert (stamp == _set.stamp);
+			assert (stamp++ == _set.stamp++);
+		}
+
+		internal bool safe_next_get (out G val) {
+			if (current != null) {
+				val = _set.lift_null_get (current.next);
+				return current.next != null;
+			} else {
+				val = _set.lift_null_get (_next);
+				return _next != null;
+			}
+		}
+
+		internal bool safe_previous_get (out G val) {
+			if (current != null) {
+				val = _set.lift_null_get (current.prev);
+				return current.prev != null;
+			} else {
+				val = _set.lift_null_get (_prev);
+				return _next != null;
+			}
 		}
 
 		private weak Node<G>? current = null;
@@ -494,8 +686,375 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 		private bool started = false;
 	}
 
+	private inline G min (G a, G b) {
+		return compare_func (a, b) <= 0 ? a : b;
+	}
+
+	private inline G max (G a, G b) {
+		return compare_func (a, b) > 0 ? a : b;
+	}
+
+	private struct Range<G> {
+		public Range (TreeSet<G> set, G after, G before) {
+			this.set = set;
+			if (set.compare_func (after, before) < 0) {
+				this.after = after;
+				this.before = before;
+				type = RangeType.BOUNDED;
+			} else {
+				type = RangeType.EMPTY;
+			}
+		}
+
+		public Range.head (TreeSet<G> set, G before) {
+			this.set = set;
+			this.before = before;
+			type = RangeType.HEAD;
+		}
+
+		public Range.tail (TreeSet<G> set, G after) {
+			this.set = set;
+			this.after = after;
+			type = RangeType.TAIL;
+		}
+
+#if false
+		public Range.empty (TreeSet<G> set) {
+			this.set = set;
+			type = RangeType.EMPTY;
+		}
+#endif
+
+		public Range<G> cut_head (G after) {
+			switch (type) {
+			case RangeType.HEAD:
+				return Range<G> (set, after, before);
+			case RangeType.TAIL:
+				return Range<G>.tail (set, set.max (after, this.after));
+			case RangeType.EMPTY:
+				return this;
+			case RangeType.BOUNDED:
+				var _after = set.max (after, this.after);
+				return Range<G> (set, _after, before);
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public Range<G> cut_tail (G before) {
+			switch (type) {
+			case RangeType.HEAD:
+				return Range<G>.head (set, set.min (before, this.before));
+			case RangeType.TAIL:
+				return Range<G> (set, after, before);
+			case RangeType.EMPTY:
+				return this;
+			case RangeType.BOUNDED:
+				var _before = set.min (before, this.before);
+				return Range<G> (set, after, _before);
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public Range<G> cut (G after, G before) {
+			if (type == RangeType.EMPTY)
+				return this;
+			var _before = type != RangeType.TAIL ? set.min (before, this.before) : before;
+			var _after = type != RangeType.HEAD ? set.max (after, this.after) : after;
+			return Range<G> (set, _after, _before);
+		}
+
+		public bool in_range (G item) {
+			return type == RangeType.EMPTY ? false : compare_range(item) == 0;
+		}
+
+		public int compare_range (G item) {
+			switch (type) {
+			case RangeType.HEAD:
+				return set.compare_func (item, before) < 0 ? 0 : 1;
+			case RangeType.TAIL:
+				return set.compare_func (item, after) >= 0 ? 0 : -1;
+			case RangeType.EMPTY:
+				return 0; // For simplicity - please make sure it does not break anything
+			case RangeType.BOUNDED:
+				return set.compare_func (item, after) >= 0 ?
+					(set.compare_func (item, before) < 0 ? 0 : 1) : -1;
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public bool empty_subset () {
+			switch (type) {
+			case RangeType.HEAD:
+				return !in_range (set._first.key);
+			case RangeType.TAIL:
+				return !in_range (set._last.key);
+			case RangeType.EMPTY:
+				return true;
+			case RangeType.BOUNDED:
+				return first () == null;
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public weak Node<G>? first () {
+			switch (type) {
+			case RangeType.EMPTY:
+				return null;
+			case RangeType.HEAD:
+				return set._first;
+			default:
+				return set.find_floor (after);
+			}
+		}
+
+		public weak Node<G>? last () {
+			switch (type) {
+			case RangeType.EMPTY:
+				return null;
+			case RangeType.TAIL:
+				return set._last;
+			default:
+				return set.find_lower (before);
+			}
+		}
+
+		private new TreeSet<G> set;
+		private G after;
+		private G before;
+		private RangeType type;
+	}
+
+	private enum RangeType {
+		HEAD,
+		TAIL,
+		EMPTY,
+		BOUNDED
+	}
+
+	private class SubSet<G> : AbstractSet<G>, SortedSet<G> {
+		public SubSet (TreeSet<G> set, G after, G before) {
+			this.set = set;
+			this.range = Range<G> (set, after, before);
+		}
+
+		public SubSet.head (TreeSet<G> set, G before) {
+			this.set = set;
+			this.range = Range<G>.head (set, before);
+		}
+
+		public SubSet.tail (TreeSet<G> set, G after) {
+			this.set = set;
+			this.range = Range<G>.tail (set, after);
+		}
+
+		public SubSet.from_range (TreeSet<G> set, Range<G> range) {
+			this.set = set;
+			this.range = range;
+		}
+
+		public override int size {
+			get {
+				var i = 0;
+				Gee.Iterator<G> iterator = iterator ();
+				while (iterator.next ())
+					i++;
+				return i;
+			}
+		}
+
+		public override bool is_empty {
+			get {
+				return range.empty_subset ();
+			}
+		}
+
+		public override bool contains (G item) {
+			return range.in_range (item) && set.contains (item);
+		}
+
+		public override bool add (G item) {
+			return range.in_range (item) && set.add (item);
+		}
+
+		public override bool remove (G item) {
+			return range.in_range (item) && set.remove (item);
+		}
+
+		public override void clear () {
+			var iter = iterator ();
+			while (iter.next ()) {
+				iter.remove ();
+			}
+		}
+
+		public override Gee.Iterator<G> iterator () {
+			return new SubIterator<G> (set, range);
+		}
+
+		public BidirIterator<G> bidir_iterator () {
+			return new SubIterator<G> (set, range);
+		}
+
+		public G first () {
+			weak Node<G>? _first = range.first ();
+			assert (_first != null);
+			return _first.key;
+		}
+
+		public G last () {
+			weak Node<G>? _last = range.last ();
+			assert (_last != null);
+			return _last.key;
+		}
+
+		public SortedSet<G> head_set (G before) {
+			return new SubSet<G>.from_range (set, range.cut_tail (before));
+		}
+
+		public SortedSet<G> tail_set (G after) {
+			return new SubSet<G>.from_range (set, range.cut_head (after));
+		}
+
+		public SortedSet<G> sub_set (G after, G before) {
+			return new SubSet<G>.from_range (set, range.cut (after, before));
+		}
+
+		public BidirIterator<G>? iterator_at (G item) {
+			if (!range.in_range (item))
+				return null;
+			weak Node<G>? n = set.find_node (item);
+			if (n == null)
+				return null;
+			return new SubIterator<G>.pointing (set, range, n);
+		}
+
+		public G? lower (G item) {
+			var res = range.compare_range (item);
+			if (res > 0)
+				return last ();
+			var l = set.lower (item);
+			return l != null && range.in_range (l) ? l : null;
+		}
+
+		public G? higher (G item) {
+			var res = range.compare_range (item);
+			if (res < 0)
+				return first ();
+			var h = set.higher (item);
+			return h != null && range.in_range (h) ? h : null;
+		}
+
+		public G? floor (G item) {
+			var res = range.compare_range (item);
+			if (res > 0)
+				return last ();
+			var l = set.floor (item);
+			return l != null && range.in_range (l) ? l : null;
+		}
+
+		public G? ceil (G item) {
+			var res = range.compare_range (item);
+			if (res < 0)
+				return first ();
+			var h = set.ceil (item);
+			return h != null && range.in_range (h) ? h : null;
+		}
+
+		private new TreeSet<G> set;
+		private Range<G> range;
+	}
+
+	private class SubIterator<G> : Object, Gee.Iterator<G>, BidirIterator<G> {
+		public SubIterator (TreeSet<G> set, Range<G> range) {
+			this.set = set;
+			this.range = range;
+		}
+
+		public SubIterator.pointing (TreeSet<G> set, Range<G> range, Node<G> node) {
+			this.set = set;
+			this.range = range;
+			this.iterator = new Iterator<G>.pointing (set, node);
+		}
+
+		public bool next () {
+			if (iterator != null) {
+				G next;
+				if (iterator.safe_next_get (out next) && range.in_range (next)) {
+					assert (iterator.next ());
+					return true;
+				} else {
+					return false;
+				}
+			} else {
+				return first ();
+			}
+		}
+
+		public bool has_next () {
+			if (iterator != null) {
+				G next;
+				return (iterator.safe_next_get (out next) && range.in_range (next));
+			} else {
+				return range.first () != null;
+			}
+		}
+
+		public bool first () {
+			weak Node<G>? node = range.first ();
+			if (node == null)
+				return false;
+			iterator = new Iterator<G>.pointing (set, node);
+			return true;
+		}
+
+		public bool previous () {
+			if (iterator == null)
+				return false;
+			G prev;
+			if (iterator.safe_previous_get (out prev) && range.in_range (prev)) {
+				assert (iterator.previous ());
+				return true;
+			} else {
+				return false;
+			}
+		}
+
+		public bool has_previous () {
+			if (iterator == null)
+				return false;
+			G prev;
+			return iterator.safe_previous_get (out prev) && range.in_range (prev);
+		}
+
+		public bool last () {
+			weak Node<G>? node = range.last ();
+			if (node == null)
+				return false;
+			iterator = new Iterator<G>.pointing (set, node);
+			return true;
+		}
+
+		public new G get () {
+			assert (iterator != null);
+			return iterator.get ();
+		}
+
+		public void remove () {
+			assert (iterator != null);
+			iterator.remove ();
+		}
+
+		private new TreeSet<G> set;
+		private Range<G> range;
+		private Iterator<G>? iterator = null;
+	}
+
 	private Node<G>? root = null;
-	private weak Node<G>? first = null;
-	private weak Node<G>? last = null;
+	private weak Node<G>? _first = null;
+	private weak Node<G>? _last = null;
 	private int stamp = 0;
 }
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 6b2377c..ba30e77 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -38,6 +38,7 @@ tests_VALASOURCES = \
        testreadonlymap.vala \
        testreadonlyset.vala \
        testset.vala \
+       testsortedset.vala \
        testtreemap.vala \
        testtreemultiset.vala \
        testtreeset.vala \
diff --git a/tests/testsortedset.vala b/tests/testsortedset.vala
new file mode 100644
index 0000000..2ca6007
--- /dev/null
+++ b/tests/testsortedset.vala
@@ -0,0 +1,974 @@
+/* ordered.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;
+using Gee;
+
+public abstract class SortedSetTests : SetTests {
+
+	public SortedSetTests (string name) {
+		base (name);
+		add_test ("[SortedSet] first", test_first);
+		add_test ("[SortedSet] last", test_last);
+		add_test ("[SortedSet] ordering", test_ordering);
+		add_test ("[SortedSet] iterator at", test_iterator_at);
+		add_test ("[SortedSet] lower", test_lower);
+		add_test ("[SortedSet] higher", test_higher);
+		add_test ("[SortedSet] floor", test_floor);
+		add_test ("[SortedSet] ceil", test_ceil);
+		add_test ("[SortedSet] bi-directional iterators can go backward",
+		          test_bidir_iterator_can_go_backward);
+		add_test ("[SortedSet] bi-directional iterators are mutable",
+		          test_mutable_bidir_iterator);
+		add_test ("[SortedSet] bi-directional iterators can to end",
+		          test_bidir_iterator_last);
+		get_suite ().add_suite (new SubSet (this, SubSet.Type.HEAD).get_suite ());
+		get_suite ().add_suite (new SubSet (this, SubSet.Type.TAIL).get_suite ());
+		get_suite ().add_suite (new SubSet (this, SubSet.Type.SUB).get_suite ());
+		get_suite ().add_suite (new SubSet (this, SubSet.Type.EMPTY).get_suite ());
+	}
+
+	public void test_ordering () {
+		var test_set = test_collection as SortedSet<string>;
+
+		// Check the set exists
+		assert (test_set != null);
+
+		test_set.add ("one");
+		test_set.add ("two");
+		test_set.add ("three");
+		test_set.add ("four");
+		test_set.add ("five");
+		test_set.add ("six");
+		test_set.add ("seven");
+		test_set.add ("eight");
+		test_set.add ("nine");
+		test_set.add ("ten");
+		test_set.add ("eleven");
+		test_set.add ("twelve");
+
+		Iterator<string> iterator = test_set.iterator ();
+		assert (iterator.next ());
+		assert (iterator.get () == "eight");
+		assert (iterator.next ());
+		assert (iterator.get () == "eleven");
+		assert (iterator.next ());
+		assert (iterator.get () == "five");
+		assert (iterator.next ());
+		assert (iterator.get () == "four");
+		assert (iterator.next ());
+		assert (iterator.get () == "nine");
+		assert (iterator.next ());
+		assert (iterator.get () == "one");
+		assert (iterator.next ());
+		assert (iterator.get () == "seven");
+		assert (iterator.next ());
+		assert (iterator.get () == "six");
+		assert (iterator.next ());
+		assert (iterator.get () == "ten");
+		assert (iterator.next ());
+		assert (iterator.get () == "three");
+		assert (iterator.next ());
+		assert (iterator.get () == "twelve");
+		assert (iterator.next ());
+		assert (iterator.get () == "two");
+		assert (iterator.next () == false);
+	}
+
+	public void test_first () {
+		var test_set = test_collection as SortedSet<string>;
+
+		if (Test.trap_fork (0, TestTrapFlags.SILENCE_STDOUT |
+		                       TestTrapFlags.SILENCE_STDERR)) {
+			test_set.first ();
+			return;
+		}
+		Test.trap_assert_failed ();
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+		assert (test_set.add ("four"));
+		assert (test_set.add ("five"));
+		assert (test_set.add ("six"));
+
+		assert (test_set.first () == "five");
+	}
+
+	public void test_last () {
+		var test_set = test_collection as SortedSet<string>;
+
+		if (Test.trap_fork (0, TestTrapFlags.SILENCE_STDOUT |
+		                       TestTrapFlags.SILENCE_STDERR)) {
+			test_set.last ();
+			return;
+		}
+		Test.trap_assert_failed ();
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+		assert (test_set.add ("four"));
+		assert (test_set.add ("five"));
+		assert (test_set.add ("six"));
+
+		assert (test_set.last () == "two");
+	}
+
+	public void test_iterator_at () {
+		var test_set = test_collection as SortedSet<string>;
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+
+		var iter = test_set.iterator_at ("one");
+		assert (iter != null);
+		assert (iter.get () == "one");
+
+		iter = test_set.iterator_at ("two");
+		assert (iter != null);
+		assert (iter.get () == "two");
+
+		iter = test_set.iterator_at ("three");
+		assert (iter != null);
+		assert (iter.get () == "three");
+
+		iter = test_set.iterator_at ("zero");
+		assert (iter == null);
+	}
+
+	public void test_lower () {
+		var test_set = test_collection as SortedSet<string>;
+
+		assert (test_set.lower ("one") == null);
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+		assert (test_set.add ("four"));
+		assert (test_set.add ("five"));
+		assert (test_set.add ("six"));
+
+		assert (test_set.lower ("one") == "four");
+		assert (test_set.lower ("o") == "four");
+		assert (test_set.lower ("two") == "three");
+		assert (test_set.lower ("t") == "six");
+		assert (test_set.lower ("three") == "six");
+		assert (test_set.lower ("four") == "five");
+		assert (test_set.lower ("f") == null);
+		assert (test_set.lower ("five") == null);
+		assert (test_set.lower ("six") == "one");
+		assert (test_set.lower ("s") == "one");
+	}
+
+	public void test_higher () {
+		var test_set = test_collection as SortedSet<string>;
+
+		assert (test_set.higher ("one") == null);
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+		assert (test_set.add ("four"));
+		assert (test_set.add ("five"));
+		assert (test_set.add ("six"));
+
+		assert (test_set.higher ("one") == "six");
+		assert (test_set.higher ("o") == "one");
+		assert (test_set.higher ("two") == null);
+		assert (test_set.higher ("t") == "three");
+		assert (test_set.higher ("three") == "two");
+		assert (test_set.higher ("four") == "one");
+		assert (test_set.higher ("f") == "five");
+		assert (test_set.higher ("five") == "four");
+		assert (test_set.higher ("six") == "three");
+		assert (test_set.higher ("s") == "six");
+	}
+
+	public void test_floor () {
+		var test_set = test_collection as SortedSet<string>;
+
+		assert (test_set.floor ("one") == null);
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+		assert (test_set.add ("four"));
+		assert (test_set.add ("five"));
+		assert (test_set.add ("six"));
+
+		assert (test_set.floor ("one") == "one");
+		assert (test_set.floor ("o") == "four");
+		assert (test_set.floor ("two") == "two");
+		assert (test_set.floor ("t") == "six");
+		assert (test_set.floor ("three") == "three");
+		assert (test_set.floor ("four") == "four");
+		assert (test_set.floor ("f") == null);
+		assert (test_set.floor ("five") == "five");
+		assert (test_set.floor ("six") == "six");
+		assert (test_set.floor ("s") == "one");
+	}
+
+	public void test_ceil () {
+		var test_set = test_collection as SortedSet<string>;
+
+		assert (test_set.ceil ("one") == null);
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+		assert (test_set.add ("four"));
+		assert (test_set.add ("five"));
+		assert (test_set.add ("six"));
+
+		assert (test_set.ceil ("one") == "one");
+		assert (test_set.ceil ("o") == "one");
+		assert (test_set.ceil ("two") == "two");
+		assert (test_set.ceil ("t") == "three");
+		assert (test_set.ceil ("three") == "three");
+		assert (test_set.ceil ("four") == "four");
+		assert (test_set.ceil ("f") == "five");
+		assert (test_set.ceil ("five") == "five");
+		assert (test_set.ceil ("six") == "six");
+		assert (test_set.ceil ("s") == "six");
+	}
+
+	public void test_bidir_iterator_can_go_backward () {
+		var test_set = test_collection as SortedSet<string>;
+
+		var iterator = test_set.bidir_iterator ();
+		assert (!iterator.has_previous ());
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+		assert (test_set.add ("four"));
+		assert (test_set.add ("five"));
+		assert (test_set.add ("six"));
+
+		iterator = test_set.bidir_iterator ();
+		assert (iterator.next ());
+		assert (iterator.get () == "five");
+		assert (!iterator.has_previous ());
+		assert (iterator.next ());
+		assert (iterator.get () == "four");
+		assert (iterator.has_previous ());
+		assert (iterator.next ());
+		assert (iterator.get () == "one");
+		assert (iterator.has_previous ());
+		assert (iterator.next ());
+		assert (iterator.get () == "six");
+		assert (iterator.has_previous ());
+		assert (iterator.next ());
+		assert (iterator.get () == "three");
+		assert (iterator.has_previous ());
+		assert (iterator.next ());
+		assert (iterator.get () == "two");
+		assert (iterator.has_previous ());
+		assert (!iterator.next ());
+		assert (iterator.previous ());
+		assert (iterator.get () == "three");
+		assert (iterator.previous ());
+		assert (iterator.get () == "six");
+		assert (iterator.previous ());
+		assert (iterator.get () == "one");
+		assert (iterator.previous ());
+		assert (iterator.get () == "four");
+		assert (iterator.previous ());
+		assert (iterator.get () == "five");
+		assert (!iterator.previous ());
+		assert (iterator.get () == "five");
+	}
+
+	public void test_bidir_iterator_last () {
+		var test_set = test_collection as SortedSet<string>;
+
+		var iterator = test_set.bidir_iterator ();
+
+		assert (!iterator.last ());
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+		assert (test_set.add ("four"));
+		assert (test_set.add ("five"));
+		assert (test_set.add ("six"));
+
+		iterator = test_set.bidir_iterator ();
+		assert (iterator.last ());
+		assert (iterator.get () == "two");
+	}
+
+	public void test_mutable_bidir_iterator () {
+		var test_set = test_collection as SortedSet<string>;
+
+		var iterator = test_set.bidir_iterator ();
+		assert (!iterator.has_previous ());
+
+		assert (test_set.add ("one"));
+		assert (test_set.add ("two"));
+		assert (test_set.add ("three"));
+		assert (test_set.add ("four"));
+		assert (test_set.add ("five"));
+		assert (test_set.add ("six"));
+
+		iterator = test_set.bidir_iterator ();
+
+		if (Test.trap_fork (0, TestTrapFlags.SILENCE_STDOUT |
+		                       TestTrapFlags.SILENCE_STDERR)) {
+			iterator.remove ();
+			return;
+		}
+		Test.trap_assert_failed ();
+
+		assert (iterator.next ());
+		assert (iterator.get () == "five");
+		iterator.remove ();
+		assert (!test_set.contains ("five"));
+		assert (iterator.has_next ());
+		assert (!iterator.has_previous ());
+		if (Test.trap_fork (0, TestTrapFlags.SILENCE_STDOUT |
+		                       TestTrapFlags.SILENCE_STDERR)) {
+			iterator.get ();
+			return;
+		}
+		assert (!iterator.previous ());
+
+		assert (iterator.next ());
+		assert (iterator.get () == "four");
+		assert (iterator.next ());
+		assert (iterator.get () == "one");
+		iterator.remove ();
+		assert (!test_set.contains ("one"));
+		assert (iterator.has_next ());
+		assert (iterator.has_previous ());
+		assert (iterator.previous ());
+		assert (iterator.get () == "four");
+	}
+
+	public class SubSet : Gee.TestCase {
+		private SortedSet<string> master;
+		private SortedSet<string> subset;
+		private SortedSetTests test;
+		public enum Type {
+			HEAD,
+			TAIL,
+			SUB,
+			EMPTY;
+			public unowned string to_string () {
+				switch (this) {
+				case Type.HEAD: return "Head";
+				case Type.TAIL: return "Tail";
+				case Type.SUB: return "Range";
+				case Type.EMPTY: return "Empty";
+				default: assert_not_reached ();
+				}
+			}
+		}
+		private Type type;
+
+		public SubSet(SortedSetTests test, Type type) {
+			base("%s Subset".printf (type.to_string ()));
+			this.test = test;
+			this.type = type;
+			add_test("[Collection] size", test_size);
+			add_test("[Collection] contains", test_contains);
+			add_test("[Collection] add", test_add);
+			add_test("[Collection] remove", test_remove);
+			add_test("[Collection] iterator", test_iterator);
+			add_test("[Collection] clear", test_clear);
+			add_test("[SortedSet] iterator at", test_iterator_at);
+			add_test("[SortedSet] lower", test_lower);
+			add_test("[SortedSet] higher", test_higher);
+			add_test("[SortedSet] ceil", test_ceil);
+			add_test("[SortedSet] floor", test_floor);
+			add_test("[SortedSet] subsets", test_subsets);
+			add_test("[SortedSet] boundaries", test_boundaries);
+		}
+
+		public override void set_up () {
+			test.set_up ();
+			master = test.test_collection as SortedSet<string>;
+			switch (type) {
+			case Type.HEAD:
+				subset = master.head_set ("one"); break;
+			case Type.TAIL:
+				subset = master.tail_set ("six"); break;
+			case Type.SUB:
+				subset = master.sub_set ("four", "three"); break;
+			case Type.EMPTY:
+				subset = master.sub_set ("three", "four"); break;
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public override void tear_down () {
+			test.tear_down ();
+		}
+
+		public void test_size () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			switch (type) {
+			case Type.HEAD:
+				assert (!subset.is_empty);
+				assert (subset.size == 2);
+				break;
+			case Type.TAIL:
+				assert (!subset.is_empty);
+				assert (subset.size == 3);
+				break;
+			case Type.SUB:
+				assert (!subset.is_empty);
+				assert (subset.size == 3);
+				break;
+			case Type.EMPTY:
+				assert (subset.is_empty);
+				assert (subset.size == 0);
+				break;
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public void test_contains () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			string[] contains, not_contains;
+			switch (type) {
+			case Type.HEAD:
+				contains = {"four", "five"};
+				not_contains = {"one", "two", "three", "six"};
+				break;
+			case Type.TAIL:
+				contains = {"two", "three", "six"};
+				not_contains = {"one", "four", "five"};
+				break;
+			case Type.SUB:
+				contains = {"one", "four", "six"};
+				not_contains = {"two", "three", "five"};
+				break;
+			case Type.EMPTY:
+				contains = {};
+				not_contains = {"one", "two", "three", "four", "five", "six"};
+				break;
+			default:
+				assert_not_reached ();
+			}
+
+			foreach (var s in contains)
+				assert (subset.contains (s));
+			foreach (var s in not_contains)
+				assert (!subset.contains (s));
+		}
+
+		public void test_add () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			string[] success, fail;
+			switch (type) {
+			case Type.HEAD:
+				success = {"a", "o"};
+				fail = {"oz", "z"};
+				break;
+			case Type.TAIL:
+				success = {"siz", "z"};
+				fail = {"sia", "a"};
+				break;
+			case Type.SUB:
+				success = {"o", "th"};
+				fail = {"f", "u"};
+				break;
+			case Type.EMPTY:
+				success = {};
+				fail = {"o", "th", "f", "u"};
+				break;
+			default:
+				assert_not_reached ();
+			}
+
+			foreach (var s in success) {
+				assert (subset.add (s));
+				assert (subset.contains (s));
+				assert (master.contains (s));
+			}
+
+			foreach (var s in fail) {
+				assert (!subset.add (s));
+				assert (!subset.contains (s));
+				assert (!master.contains (s));
+			}
+
+			assert (master.size == 6 + success.length);
+		}
+
+		public void test_remove () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			string[] contains, not_contains;
+			switch (type) {
+			case Type.HEAD:
+				contains = {"four", "five"};
+				not_contains = {"one", "two", "three", "six"};
+				break;
+			case Type.TAIL:
+				contains = {"two", "three", "six"};
+				not_contains = {"one", "four", "five"};
+				break;
+			case Type.SUB:
+				contains = {"one", "four", "six"};
+				not_contains = {"two", "three", "five"};
+				break;
+			case Type.EMPTY:
+				contains = {};
+				not_contains = {"one", "two", "three", "four", "five", "six"};
+				break;
+			default:
+				assert_not_reached ();
+			}
+
+			foreach (var s in contains) {
+				assert (subset.remove (s));
+				assert (!master.contains (s));
+			}
+			foreach (var s in not_contains) {
+				assert (!subset.remove (s));
+				assert (master.contains (s));
+			}
+
+			assert (master.size == 6 - contains.length);
+		}
+
+		public void test_iterator () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			string[] contains;
+			switch (type) {
+			case Type.HEAD:
+				contains = {"five", "four"};
+				break;
+			case Type.TAIL:
+				contains = {"six", "three", "two"};
+				break;
+			case Type.SUB:
+				contains = {"four", "one", "six"};
+				break;
+			case Type.EMPTY:
+				contains = {};
+				break;
+			default:
+				assert_not_reached ();
+			}
+
+			uint i = 0;
+			foreach (var e in subset) {
+				assert (e == contains[i++]);
+			}
+			assert (i == contains.length);
+
+
+			var iter = subset.bidir_iterator ();
+			if (type != Type.EMPTY) {
+				assert (iter.last ());
+				assert (iter.get () == contains[contains.length - 1]);
+				assert (iter.first ());
+
+				assert (iter.get () == contains[0]);
+				assert (iter.has_next ());
+				assert (iter.next ());
+				assert (iter.get () == contains[1]);
+				assert (iter.has_previous ());
+				iter.remove ();
+				assert (iter.has_previous ());
+				if (type != Type.HEAD)
+					assert (iter.has_next ());
+				else
+					assert (!iter.has_next ());
+				assert (iter.previous ());
+				assert (iter.get () == contains[0]);
+			} else {
+				assert (!iter.first ());
+				if (Test.trap_fork (0, TestTrapFlags.SILENCE_STDOUT |
+				                       TestTrapFlags.SILENCE_STDERR)) {
+					iter.remove ();
+					return;
+				}
+				Test.trap_assert_failed ();
+			}
+		}
+
+		public void test_clear () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			string[] contains, not_contains;
+			switch (type) {
+			case Type.HEAD:
+				contains = {"four", "five"};
+				not_contains = {"one", "two", "three", "six"};
+				break;
+			case Type.TAIL:
+				contains = {"two", "three", "six"};
+				not_contains = {"one", "four", "five"};
+				break;
+			case Type.SUB:
+				contains = {"one", "four", "six"};
+				not_contains = {"two", "three", "five"};
+				break;
+			case Type.EMPTY:
+				contains = {};
+				not_contains = {"one", "two", "three", "four", "five", "six"};
+				break;
+			default:
+				assert_not_reached ();
+			}
+
+			subset.clear ();
+			foreach (var s in contains)
+				assert (!master.contains (s));
+			foreach (var s in not_contains)
+				assert (master.contains (s));
+		}
+
+		public void test_boundaries () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			switch (type) {
+			case Type.HEAD:
+				assert (subset.first () == "five");
+				assert (subset.last () == "four");
+				break;
+			case Type.TAIL:
+				assert (subset.first () == "six");
+				assert (subset.last () == "two");
+				break;
+			case Type.SUB:
+				assert (subset.first () == "four");
+				assert (subset.last () == "six");
+				break;
+			case Type.EMPTY:
+				if (Test.trap_fork (0, TestTrapFlags.SILENCE_STDOUT |
+				                       TestTrapFlags.SILENCE_STDERR)) {
+					subset.first ();
+				}
+				Test.trap_assert_failed ();
+				if (Test.trap_fork (0, TestTrapFlags.SILENCE_STDOUT |
+				                       TestTrapFlags.SILENCE_STDERR)) {
+					subset.last ();
+				}
+				Test.trap_assert_failed ();
+				break;
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public void test_iterator_at () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			string[] contains, not_contains;
+			switch (type) {
+			case Type.HEAD:
+				contains = {"four", "five"};
+				not_contains = {"one", "two", "three", "six"};
+				break;
+			case Type.TAIL:
+				contains = {"two", "three", "six"};
+				not_contains = {"one", "four", "five"};
+				break;
+			case Type.SUB:
+				contains = {"one", "four", "six"};
+				not_contains = {"two", "three", "five"};
+				break;
+			case Type.EMPTY:
+				contains = {};
+				not_contains = {"one", "two", "three", "four", "five", "six"};
+				break;
+			default:
+				assert_not_reached ();
+			}
+
+			foreach (var s in contains) {
+				var iter = subset.iterator_at (s);
+				assert (iter != null);
+				assert (iter.get () == s);
+			}
+			foreach (var s in not_contains) {
+				var iter = subset.iterator_at (s);
+				assert (iter == null);
+			}
+		}
+
+		public void test_lower () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			switch (type) {
+			case Type.HEAD:
+				assert (subset.lower ("a") == null);
+				assert (subset.lower ("five") == null);
+				assert (subset.lower ("four") == "five");
+				assert (subset.lower ("six") == "four");
+				break;
+			case Type.TAIL:
+				assert (subset.lower ("one") == null);
+				assert (subset.lower ("six") == null);
+				assert (subset.lower ("three") == "six");
+				assert (subset.lower ("two") == "three");
+				assert (subset.lower ("z") == "two");
+				break;
+			case Type.SUB:
+				assert (subset.lower ("five") == null);
+				assert (subset.lower ("four") == null);
+				assert (subset.lower ("one") == "four");
+				assert (subset.lower ("six") == "one");
+				assert (subset.lower ("three") == "six");
+				break;
+			case Type.EMPTY:
+				assert (subset.lower ("six") == null);
+				break;
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public void test_higher () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			switch (type) {
+			case Type.HEAD:
+				assert (subset.higher ("a") == "five");
+				assert (subset.higher ("five") == "four");
+				assert (subset.higher ("four") == null);
+				assert (subset.higher ("six") == null);
+				break;
+			case Type.TAIL:
+				assert (subset.higher ("one") == "six");
+				assert (subset.higher ("six") == "three");
+				assert (subset.higher ("three") == "two");
+				assert (subset.higher ("two") == null);
+				assert (subset.higher ("z") == null);
+				break;
+			case Type.SUB:
+				assert (subset.higher ("five") == "four");
+				assert (subset.higher ("four") == "one");
+				assert (subset.higher ("one") == "six");
+				assert (subset.higher ("six") == null);
+				assert (subset.higher ("three") == null);
+				break;
+			case Type.EMPTY:
+				assert (subset.higher ("six") == null);
+				break;
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public void test_floor () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			switch (type) {
+			case Type.HEAD:
+				assert (subset.floor ("a") == null);
+				assert (subset.floor ("five") == "five");
+				assert (subset.floor ("four") == "four");
+				assert (subset.floor ("six") == "four");
+				break;
+			case Type.TAIL:
+				assert (subset.floor ("one") == null);
+				assert (subset.floor ("six") == "six");
+				assert (subset.floor ("three") == "three");
+				assert (subset.floor ("two") == "two");
+				assert (subset.floor ("z") == "two");
+				break;
+			case Type.SUB:
+				assert (subset.floor ("five") == null);
+				assert (subset.floor ("four") == "four");
+				assert (subset.floor ("one") == "one");
+				assert (subset.floor ("six") == "six");
+				assert (subset.floor ("three") == "six");
+				break;
+			case Type.EMPTY:
+				assert (subset.floor ("six") == null);
+				break;
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public void test_ceil () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			switch (type) {
+			case Type.HEAD:
+				assert (subset.ceil ("a") == "five");
+				assert (subset.ceil ("five") == "five");
+				assert (subset.ceil ("four") == "four");
+				assert (subset.ceil ("six") == null);
+				break;
+			case Type.TAIL:
+				assert (subset.ceil ("one") == "six");
+				assert (subset.ceil ("six") == "six");
+				assert (subset.ceil ("three") == "three");
+				assert (subset.ceil ("two") == "two");
+				assert (subset.ceil ("z") == null);
+				break;
+			case Type.SUB:
+				assert (subset.ceil ("five") == "four");
+				assert (subset.ceil ("four") == "four");
+				assert (subset.ceil ("one") == "one");
+				assert (subset.ceil ("six") == "six");
+				assert (subset.ceil ("three") == null);
+				break;
+			case Type.EMPTY:
+				assert (subset.ceil ("six") == null);
+				break;
+			default:
+				assert_not_reached ();
+			}
+		}
+
+		public void test_subsets () {
+			assert (master.add ("one"));
+			assert (master.add ("two"));
+			assert (master.add ("three"));
+			assert (master.add ("four"));
+			assert (master.add ("five"));
+			assert (master.add ("six"));
+			assert (master.size == 6);
+
+			switch (type) {
+			case Type.HEAD:
+				var subsubset = subset.head_set ("four");
+				assert (subsubset.size == 1);
+				subsubset = subset.tail_set ("four");
+				assert (subsubset.size == 1);
+				subsubset = subset.sub_set ("four", "one");
+				assert (subsubset.size == 1);
+				subsubset = subset.sub_set ("four", "four");
+				assert (subsubset.size == 0);
+				break;
+			case Type.TAIL:
+				var subsubset = subset.head_set ("two");
+				assert (subsubset.size == 2);
+				subsubset = subset.tail_set ("three");
+				assert (subsubset.size == 2);
+				subsubset = subset.sub_set ("three", "two");
+				assert (subsubset.size == 1);
+				break;
+			case Type.SUB:
+				var subsubset = subset.head_set ("six");
+				assert (subsubset.size == 2);
+				subsubset = subset.tail_set ("one");
+				assert (subsubset.size == 2);
+				subsubset = subset.sub_set ("one", "six");
+				assert (subsubset.size == 1);
+				subsubset = subset.sub_set ("five", "two");
+				assert (subsubset.size == 3);
+				break;
+			case Type.EMPTY:
+				var subsubset = subset.head_set ("six");
+				assert (subsubset.size == 0);
+				subsubset = subset.tail_set ("three");
+				assert (subsubset.size == 0);
+				subsubset = subset.sub_set ("one", "six");
+				assert (subsubset.size == 0);
+				break;
+			default:
+				assert_not_reached ();
+			}
+		}
+	}
+}
+
diff --git a/tests/testtreeset.vala b/tests/testtreeset.vala
index bf0a67a..6d754bc 100644
--- a/tests/testtreeset.vala
+++ b/tests/testtreeset.vala
@@ -23,13 +23,12 @@
 
 using Gee;
 
-public class TreeSetTests : SetTests {
+public class TreeSetTests : SortedSetTests {
 
 	public TreeSetTests () {
 		base ("TreeSet");
 		add_test ("[TreeSet] selected functions", test_selected_functions);
 		add_test ("[TreeSet] GObject properties", test_gobject_properties);
-		add_test ("[TreeSet] ordering", test_ordering);
 		add_test ("[TreeSet] add and remove", test_add_remove);
 	}
 
@@ -64,53 +63,6 @@ public class TreeSetTests : SetTests {
 		value.unset ();
 	}
 
-	public void test_ordering () {
-		var test_set = test_collection as Set<string>;
-
-		// Check the set exists
-		assert (test_set != null);
-
-		test_set.add ("one");
-		test_set.add ("two");
-		test_set.add ("three");
-		test_set.add ("four");
-		test_set.add ("five");
-		test_set.add ("six");
-		test_set.add ("seven");
-		test_set.add ("eight");
-		test_set.add ("nine");
-		test_set.add ("ten");
-		test_set.add ("eleven");
-		test_set.add ("twelve");
-
-		Iterator<string> iterator = test_set.iterator ();
-		assert (iterator.next () == true);
-		assert (iterator.get () == "eight");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "eleven");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "five");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "four");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "nine");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "one");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "seven");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "six");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "ten");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "three");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "twelve");
-		assert (iterator.next () == true);
-		assert (iterator.get () == "two");
-		assert (iterator.next () == false);
-	}
-
 	public new void test_add_remove () {
 		var test_set = test_collection as TreeSet<string>;
 



[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]