--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/impl/hoofbaby/util/set.d	Mon Jul 06 08:06:28 2009 -0700
@@ -0,0 +1,186 @@
+/**
+ * Hoofbaby -- http://www.dsource.org/projects/hoofbaby
+ * Copyright (C) 2009 Robert Fraser
+ * 
+ * This program is free software; you can redistribute it andor
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ * 
+ * This program 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 General Public License for more details.
+ */
+
+module hoofbaby.util.set;
+
+import tango.core.Traits;
+import candy.util.redblack;
+import candy.util.memory;
+import candy.util.array;
+
+/**
+ * Basic set implementation using Tango's RedBlack struct with my memory
+ * allocator. Since Tango's RedBlack is package-access only, I copied it
+ * to candy.util.RedBlack.
+ */
+public struct Set(T)
+{
+	private alias RedBlack!(T) TreeNode;
+
+	private StructPool!(TreeNode) pool;
+	private TreeNode* root;
+	private size_t count = 0;
+	
+	public bool add(T value)
+	{
+		return add(value, null);
+	}
+	
+	private bool add(T value, TreeNode* node)
+	{
+		if(root is null)
+		{
+			root = node ? node : pool.alloc.set(value);
+		}
+		else
+		{
+			TreeNode* t = root;
+			while(true)
+			{
+				int diff = cmp(value, t.value);
+				if(0 == diff)
+				{
+					return false;
+				}
+				else if(diff < 0)
+				{
+					if(t.left)
+						t = t.left;
+					else
+					{
+						root = t.insertLeft(node ? node : pool.alloc.set(value), root);
+						break;
+					}
+				}
+				else
+				{
+					if(t.right)
+						t = t.right;
+					else
+					{
+						root = t.insertRight(node ? node : pool.alloc.set(value), root);
+						break;
+					}
+				}
+			}
+		}
+		count++;
+		return true;
+	}
+
+	public void addAll(Iterable)(Iterable iter)
+	{
+		foreach(e; iter)
+			add(e);
+	}
+	
+	// TODO find out if there's a better way to do this
+	public alias addAll merge;
+
+	public int opApply(int delegate(ref T value) dg)
+	{
+		int result = 0;
+		if(!root)
+			return result;
+		TreeNode* node = root.leftmost();
+		while(node)
+		{
+			result = dg(node.value);
+			if(result)
+				break;
+			node = node.successor();
+		}
+		return result;
+	}
+	
+	public char[] toString()
+	{
+		if(!root)
+			return "{}";
+		bool comma = false;
+		Array!(char) r;
+		r ~= "{";
+		TreeNode* node = root.leftmost();
+		while(node)
+		{
+			if(comma)
+				r ~= ", ";
+			r ~= node.value.toString();
+			node = node.successor();
+			comma = true;
+		}
+		r ~= "}";
+		return r.toArray();
+	}
+	
+	public T[] toArray()
+	{
+		if(!root)
+			return null;
+		T[] arr = new T[count];
+		TreeNode* node = root.leftmost();
+		size_t i = 0;
+		while(node)
+		{
+			arr[i] = node.value;
+			node = node.successor();
+			i++;
+		}
+		assert(i == count);
+		return arr;
+	}
+	
+	public size_t length()
+	{
+		return count;
+	}
+	
+	public bool contains(T value)
+	{
+		return root.find(value, &cmp) !is null;
+	}
+	
+	final bool remove(T value)
+    {
+		TreeNode* node = root.find(value, &cmp);
+		if(value)
+		{
+			root = node.remove(root);
+			count--;
+			return true;
+		}
+		else
+			return false;
+    }
+	
+	static if(isReferenceType!(T) && !is(typeof(&((new T).opCmp))))
+	{
+		// Hack to allow classes/structs without an opCmp to be compared by their address
+		private static int cmp(ref T a, ref T b)
+		{
+			return cast(void*) a - cast(void*) b;
+		}
+	}
+	else
+	{
+		private static int cmp(ref T a, ref T b)
+		{
+			if(a is b)
+				return 0;
+			return typeid(T).compare(&a, &b);
+	    }
+	}
+	
+}
\ No newline at end of file