Digit Trie

DigitTrie.java

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.LinkedList;

/**
 * Put list of prefixes and their corresponding labels.
 * Then get the label for longest matching prefix.
 *
 * @author Vihang Patil <vihang.patil@gmail.com>
 */
public class DigitTrie {

    private static final Logger LOG = LoggerFactory.getLogger(DigitTrie.class);

    private int key = -1;
    private String value;
    private final DigitTrie[] children = new DigitTrie[10];

    public void put(String key, String value) {
        /*
        Root node will not have any key & value, just children
        */
        if (keyIsInvalid(key)) {
            return;
        }
        LinkedList<Integer> list = split(key);
        if (children[list.peek()] == null) {
            children[list.peek()] = new DigitTrie();
        }
        DigitTrie child = children[list.peek()];
        child.put(list, value);
    }

    private void put(LinkedList<Integer> list, String value) {
        if (list.isEmpty()) {
            return;
        }
        this.key = list.poll();
        if (list.isEmpty()) {
            // means this was last element in list, which was removed by poll().
            // value is set only on last digit node.
            this.value = value;
            return;
        }
        if (children[list.peek()] == null) {
            children[list.peek()] = new DigitTrie();
        }
        DigitTrie child = children[list.peek()];
        child.put(list, value);
    }

    public String get(String key) {
        if (keyIsInvalid(key)) {
            return null;
        }
        LinkedList<Integer> list = split(key);
        if (children[list.peek()] != null) {
            return children[list.peek()].get(list);
        }
        return null;
    }

    private String get(LinkedList<Integer> list) {
        if (list.isEmpty())
            return null;
        if (list.poll() != key) {
            return null;
        }
        if (list.isEmpty()) {
            // means this was last element in list, which was removed by poll().
            return value;
        }
        String childValue = null;
        if (children[list.peek()] != null) {
            childValue = children[list.peek()].get(list);
        }
        if (childValue != null) {
            return childValue;
        }
        return value;
    }

    private LinkedList<Integer> split(String key) {
        char[] chars = key.toCharArray();
        LinkedList<Integer> list = new LinkedList<>();
        for (char c : chars) {
            list.add(Integer.valueOf(Character.toString(c)));
        }
        return list;
    }

    private boolean keyIsInvalid(String key) {
        if (key == null || key.isEmpty()) {
            LOG.warn("Key is null or empty");
            return true;
        }
        if (!key.matches("[0-9]*")) {
            LOG.warn("Key:{} is not a number", key);
            return true;
        }
        return false;
    }
}