package us.bannister.structures.trie2;

import us.bannister.structures.Trie;
import us.bannister.structures.Value;
import us.bannister.structures.Visitor;

public class FixedTrie implements Trie {
	protected final static class Slot {
		char c;
		Object value;
		Slot[] list;
		final Slot findSlot(char c) {
			for (Slot o : list) {
				if (c == o.c) {
					return o;
				}
			}
			return null;
		}
		int countNodes() {
			int n = 1;
			for (Slot slot : list) {
				n += slot.countNodes();
			}
			return n;
		}
		int countSlots() {
			int n = (null == value) ? 0 : 1;
			for (Slot slot : list) {
				n += slot.countSlots();
			}
			return n;
		}
		int depth() {
			int n = 0;
			for (Slot slot : list) {
				n = Math.max(n, slot.depth());
			}
			return 1 + n;
		}
		int size() {
			int n = (null == value) ? 0 : 1;
			for (Slot slot : list) {
				n += slot.size();
			}
			return n;
		}
	}

	Slot root = new Slot();
	
	@Override public int countNodes() {
		return root.countNodes();
	}
	@Override public int countSlots() {
		return root.countSlots();
	}
	@Override public int depth() {
		return root.depth();
	}
	protected Slot findSlot(String k) {
		Slot slot = root;
		for (char c : k.toCharArray()) {
			slot = slot.findSlot(c);
			if (null == slot) {
				return null;
			}
		}
		return slot;
	}
	@Override public Object get(String k) {
		Slot slot = findSlot(k);
		return (null == slot) ? null : slot.value;
	}
	@Override public void put(String k, Object v) {
		// Trie is immutable once constructed.
	}
	@Override public void zap() {
		// Trie is immutable once constructed.
	}
	@Override public int size() {
		return root.size();
	}
	@Override public String[] keys() {
		final String[] a = new String[size()];
		walk("",new Visitor() {
			private int n = 0;
			@Override public void each(String k, Value v) {
				a[n++] = k;
			}
		});
		return a;
	}

	private class Walker implements Value {
		private int n = 0;
		private char[] a;
		private Slot slot;
		private void start(String k) {
			slot = findSlot(k);
			n = k.length();
			a = new char[n + slot.depth()];
			char[] a1 = k.toCharArray();
			System.arraycopy(a1, 0, a, 0, a1.length);
		}
		private void walk(Visitor visitor) {
			if (null != slot.value) {
				visitor.each(new String(a, 0, n), this);
			}
			Slot[] list = slot.list;
			int i = n++;
			for (Slot o : list) {
				slot = o;
				a[i] = slot.c;
				walk(visitor);
			}
			n = i;
		}
		@Override public Object get() {
			return slot.value;
		}
		@Override public void put(Object v) {
			slot.value = v;
		}
		void walk(String k, Visitor visitor) {
			start(k);
			walk(visitor);
		}
	}
	@Override public void walk(String k, Visitor visitor) {
		Walker w = new Walker();
		w.walk(k, visitor);
	}
}