AlphaTrie

AlphaTrie.hx

class AlphaTrie
{
	
	// an implementation of a trie specifically for storing and looking up english dictionary words
	
	public var chars : Hash<AlphaTrie>;
	public var ending : Bool;
	
	public function new()
	{
		chars = new Hash();
		ending = false;
	}
	
	public function find(word : String)
	{
		var cur = this;
		for (idx in 0...word.length)
		{
			var chr = word.charAt(idx);
			var next = cur.chars.get(chr);
			if (next==null)
			{
				return false;
			}
			cur = next;
		}
		return cur.ending;
	}
	
	public function continuation(word : String)
	{
		var cur = this;
		for (idx in 0...word.length)
		{
			var chr = word.charAt(idx);
			var next = cur.chars.get(chr);
			if (next==null)
			{
				return false;
			}
			cur = next;
		}
		var ct = Lambda.count(cur.chars);
		return ct>0;
	}
	
	public function available(word : String)
	{
		var cur = this;
		for (idx in 0...word.length)
		{
			var chr = word.charAt(idx);
			var next = cur.chars.get(chr);
			if (next==null)
			{
				return null;
			}
			cur = next;
		}
		var result = new Hash<Bool>();
		for (k in cur.chars.keys())
			result.set(k, true);
		return result;
	}
	
	public function store(word : String)
	{
		var cur = this;
		for (idx in 0...word.length)
		{
			var chr = word.charAt(idx);
			var next = cur.chars.get(chr);
			if (next==null)
			{
				next = new AlphaTrie();
				cur.chars.set(chr, next);				
			}
			cur = next;
		}
		cur.ending = true;
	}
	
}