001package org.conqat.lib.commons.tree;
002
003import java.util.HashMap;
004import java.util.Map;
005
006import org.conqat.lib.commons.string.StringUtils;
007
008/**
009 * Simple, efficient implementation of a trie that maps prefixes to objects of
010 * the generic type.
011 */
012public class Trie<T> {
013
014        private class TrieNode {
015                private T value;
016                private Map<Character, TrieNode> next = new HashMap<>();
017        }
018
019        private TrieNode root = new TrieNode();
020
021        /**
022         * Map the prefix to the given value.
023         */
024        public void put(String prefix, T value) {
025                TrieNode currentNode = root;
026                for (Character ch : StringUtils.splitChars(prefix)) {
027                        TrieNode nextNode = currentNode.next.get(ch);
028                        if (nextNode == null) {
029                                nextNode = new TrieNode();
030                                currentNode.next.put(ch, nextNode);
031                        }
032                        currentNode = nextNode;
033                }
034                currentNode.value = value;
035        }
036
037        /**
038         * Returns the value associated with the longest known prefix of this sequence,
039         * or null if no known prefix exists.
040         */
041        public T getLongestPrefix(String sequence) {
042                T currentBestMatch = null;
043                TrieNode currentNode = root;
044                for (Character ch : StringUtils.splitChars(sequence)) {
045                        currentNode = currentNode.next.get(ch);
046                        if (currentNode == null) {
047                                // Reached a leaf node in the Trie
048                                return currentBestMatch;
049                        } else if (currentNode.value != null) {
050                                currentBestMatch = currentNode.value;
051                        }
052                }
053                return currentBestMatch;
054        }
055}