/**
 * Simple Ternary Tree port of: http://bitbucket.org/woadwarrior/trie/src/tip/python/tst.py
 * 
 * License:
 * Copyright (c) 2009 Jeethu Rao <jeethu@jeethurao.com>
 * Port to D Copyright (c) 2009 Robert Fraser <fraserofthenight@gmail.com>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
module candy.util.TreeNode;

import tango.core.Array : sort;

import candy.util.memory;
import candy.util.array;

public struct TernaryTree(K, V)
{
	public static struct SearchResult
	{
		private TernaryTree* tree;
		private TreeNode* result;
		
		public int opApply(int delegate(ref K[], ref V) dg)
		{
			return tree.apply(result, dg);
		}
	}
	
	private static struct TreeNode
	{
		TreeNode* left;
		TreeNode* right;
	    TreeNode* mid;
		K split;
		K[] key;
		V value;
	}
	
	private StructPool!(TreeNode) pool;
	private TreeNode* root;
    
	public void add(K[] k, V v)
	{
		assert(k.length);
		
		// NOTE: the compiler wasn't unrolling the tail call, so this is
		// presented non-recursively for your enjoyment
		TreeNode* node = root;
		size_t i = 0;
		size_t len = k.length;
		
		if(!node)
		{
			root = pool.alloc();
			root.split = k[i];
			node = root;
			i++;
			goto Lrest;
		}
		
		while(i < len)
		{
			K e = k[i];
			K ne = node.split;
			
			if(e < ne)
			{
				if(node.left)
				{
					node = node.left;
					continue;
				}
				else
				{
					node = node.left = pool.alloc();
					node.split = e;
					i++;
					goto Lrest;
				}
			}
			else if(e > ne)
			{
				if(node.right)
				{
					node = node.right;
					continue;
				}
				else
				{
					node = node.right = pool.alloc();
					node.split = e;
					i++;
					goto Lrest;
				}
			}
			
			i++;
			if(i < len)
			{
				if(node.mid)
				{
					node = node.mid;
					continue;
				}
				else
				{
					Lrest:
					while(i < len)
					{
						node = node.mid = pool.alloc();
						node.split = k[i];
						i++;
					}
					node.value = v;
					node.key = k;
					return;
				}
			}
			else
			{
				node.value = v;
				node.key = k;
				return;
			}
			
			// We should have broken or continued before this point
			assert(false);
		}
	}
	
	public bool get(K[] k, ref V v)
	{
		TreeNode* node = search(k);
		if(node && node.key.length)
		{
			v = node.value;
			return true;
		}
		return false;
	}
	
	public void addAll(K[][] keys, V[] values, bool keysSorted = false)
	{
		assert(keys.length == values.length);
		if(!keys.length)
			return;
		if(!keysSorted)
			sort(keys);
		addAll(keys, values, 0, keys.length);
	}
	
	public void free()
	{
		root = null;
		pool.free();
	}
	
	public SearchResult prefixSearch(K[] k)
	{
		return SearchResult(this, search(k));
	}
	
	public int opApply(int delegate(ref K[], ref V) dg)
	{
		return apply(root, dg);
	}
	
	public bool contains(K[] k)
	{
		return search(k) !is null;
	}
	
	private TreeNode* search(K[] k)
	{
		assert(k.length);
		
		TreeNode* node = root;
		while(node)
		{
			K e = k[0];
			if(e < node.split)
			{
				node = node.left;
				continue;
			}
			else if(e > node.split)
			{
				node = node.right;
				continue;
			}
			else
			{
				k = k[1 .. $];
				if(!k.length)
				{
					return node;
				}
				else
				{
					node = node.mid;
					continue;
				}
			}
		}
		return null;
	}
	
	private int apply(TreeNode* node, int delegate(ref K[], ref V) dg)
	{
		int result = 0;
		if(!node)
			return result;
		
		Stack!(TreeNode*, 1024) stack;
		
		while(true)
		{
			if(node.right)   stack.push(node.right);
			if(node.mid)     stack.push(node.mid);
			if(node.left)    stack.push(node.left);
			
			if(node.key.length)
			{
				result = dg(node.key, node.value);
				if(result)
					return result;
			}
			
			if(stack.isEmpty)
				return result;
			node = stack.pop();
		}
	}
	
	private void addAll(K[][] keys, V[] values, size_t low, size_t high)
	{
		uint diff = high - low;
		if(diff == 1)
		{
			add(keys[low], values[low]);
			return;
		}
		else if(diff == 2)
		{
			add(keys[low], values[low]);
			add(keys[low+1], values[low+1]);
			return;
		}
		else
		{
			size_t mid = low + (high / 2);
			add(keys[mid], values[mid]);
			// OPTIMIZE iterative.. also is 2 is the best cutoff value here?
			addAll(keys, values, mid + 1, high);
			addAll(keys, values, low, mid);
		}
	}
}