A simple Java trie for collated (hex-encoded) strings

CollateTrie.java

package org.kman.Compat.util;

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;

/**
 * Created by kman on 8/30/16.
 *
 * Works only with collated strings (hex encoded)
 */
public class CollateTrie<V> {

	// Hex digits
	private static final int CHILDREN_COUNT = ('9' - '0' + 1) + ('f' - 'a' + 1) + ('F' - 'A' + 1);

	public CollateTrie() {
		mRoot = new KeyNode(null);
	}

	public void add(String key, V value) {
		final int len = key.length();
		if (len == 0) {
			return;
		}

		int depth = 0;
		KeyNode<V> knode = mRoot;
		for (int i = 0; i < len; ++i) {
			final int index = getCharIndex(key.charAt(i));

			if (knode.children == null) {
				knode.children = new KeyNode[CHILDREN_COUNT];
			}
			if (knode.children[index] == null) {
				knode.children[index] = new KeyNode(key.substring(0, i + 1));
			}
			knode = knode.children[index];

			++depth;
		}

		if (knode.value == value) {
			return;
		}

		if (knode.value == null) {
			knode.value = value;
		} else {
			for (ValueNode<V> vnode = knode.values; vnode != null; vnode = vnode.next) {
				if (vnode.value == value) {
					return;
				}
			}
			knode.values = new ValueNode<V>(value, knode.values);
		}

		if (mMaxDepth < depth) {
			mMaxDepth = depth;
		}
		++mItemCount;
	}

	public void getStartsWithValues(String key, Collection<V> results) {
		final int len = key.length();
		if (len == 0) {
			return;
		}

		KeyNode<V> knode = mRoot;
		for (int i = 0; i < len; ++i) {
			final int index = getCharIndex(key.charAt(i));
			if (knode.children == null) {
				return;
			}
			knode = knode.children[index];
			if (knode == null) {
				return;
			}
		}

		final Deque<KeyNode<V>> deque = new ArrayDeque<KeyNode<V>>(CHILDREN_COUNT);
		deque.addLast(knode);

		while ((knode = deque.pollFirst()) != null) {
			if (knode.value != null) {
				results.add(knode.value);
			}
			for (ValueNode<V> vnode = knode.values; vnode != null; vnode = vnode.next) {
				results.add(vnode.value);
			}
			if (knode.children != null) {
				for (KeyNode<V> child : knode.children) {
					if (child != null) {
						deque.addLast(child);
					}
				}
			}
		}
	}

	private int getCharIndex(char ch) {
		if (ch >= '0' && ch <= '9') {
			return ch - '0';
		}
		if (ch >= 'a' && ch <= 'f') {
			return ('9' - '0' + 1) + ch - 'a';
		}
		if (ch >= 'A' && ch <= 'F') {
			return ('9' - '0' + 1) + ('f' - 'a' + 1) + ch - 'A';
		}
		return 0;
	}

	static class KeyNode<V> {
		final String key;

		KeyNode<V>[] children;
		V value;
		ValueNode<V> values;

		KeyNode(String k) {
			key = k;
		}
	}

	static class ValueNode<V> {
		final V value;
		final ValueNode<V> next;

		ValueNode(V v, ValueNode<V> n) {
			value = v;
			next = n;
		}
	}

	private final KeyNode<V> mRoot;
	private int mItemCount;
	private int mMaxDepth;
}