/**
 * 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);
	    }
	}
	
}