Trie.java

packagecom.jwetherell.algorithms.data_structures;

importjava.util.Arrays;

importcom.jwetherell.algorithms.data_structures.interfaces.ITree;

/**
 * A trie, or prefix tree, is an ordered tree data structure that is used to
 * store an associative array where the keys are usually strings.
 * <p>
 * NOTE: This is NOT a compact Trie
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Trie">Trie (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
@SuppressWarnings("unchecked")
publicclassTrie<CextendsCharSequence> implementsITree<C> {

protectedINodeCreatorcreator;
protectedNoderoot;

privateintsize = 0;

publicTrie() {
this.creator = newINodeCreator() {
/**
 * {@inheritDoc}
 */
@Override
publicNodecreateNewNode(Nodeparent, Charactercharacter, booleanisWord) {
return (newNode(parent, character, isWord));
 }
 };
 }

/**
 * Constructor with external Node creator.
 */
publicTrie(INodeCreatorcreator) {
this.creator = creator;
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleanadd(Cseq) {
return (this.addSequence(seq) != null);
 }

/**
 * Add sequence to trie.
 * 
 * @param seq
 * to add to the trie.
 * @return Node which was added to trie or null if it already exists.
 */
protectedNodeaddSequence(Cseq) {
if (root == null)
root = this.creator.createNewNode(null, Node.SENTINAL, false);

intlength = (seq.length() - 1);
Nodeprev = root;
// For each Character in the input, we'll either go to an already define
// child or create a child if one does not exist
for (inti = 0; i < length; i++) {
Noden = null;
Characterc = seq.charAt(i);
intindex = prev.childIndex(c);
// If 'prev' has a child which starts with Character c
if (index >= 0) {
// Go to the child
n = prev.getChild(index);
 } else {
// Create a new child for the character
n = this.creator.createNewNode(prev, c, false);
prev.addChild(n);
 }
prev = n;
 }

// Deal with the first character of the input string not found in the
// trie
Noden = null;
Characterc = seq.charAt(length);
intindex = prev.childIndex(c);
// If 'prev' already contains a child with the last Character
if (index >= 0) {
n = prev.getChild(index);
// If the node doesn't represent a string already
if (n.isWord == false) {
// Set the string to equal the full input string
n.character = c;
n.isWord = true;
size++;
returnn;
 }
// String already exists in Trie
returnnull;
 }
// Create a new node for the input string
n = this.creator.createNewNode(prev, c, true);
prev.addChild(n);
size++;
returnn;
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleancontains(Cseq) {
Noden = this.getNode(seq);
if (n == null || !n.isWord) returnfalse;

// If the node found in the trie does not have it's string
// field defined then input string was not found
returnn.isWord;
 }

/**
 * {@inheritDoc}
 */
@Override
publicCremove(Csequence) {
if (root == null) returnnull;

// Find the key in the Trie
Nodenode = getNode(sequence);
if (node==null) returnnull;

returnremove(node);
 }

protectedCremove(Nodenode) {
Nodeprevious = node.parent;
if (node.childrenSize > 0) {
// The node which contains the input string and has children, just
// NULL out the string
node.isWord = false;
 } else {
// The node which contains the input string does NOT have children
intindex = previous.childIndex(node.character);
// Remove node from previous node
previous.removeChild(index);
// Go back up the trie removing nodes until you find a node which
// represents a string
while (previous != null && previous.isWord == false && previous.childrenSize == 0) {
if (previous.parent != null) {
intidx = previous.parent.childIndex(previous.character);
if (idx >= 0)
previous.parent.removeChild(idx);
 }
previous = previous.parent;
 }
 }

size--;

return (C)(String.valueOf(node.character));
 }

/**
 * {@inheritDoc}
 */
@Override
publicvoidclear() {
root = null;
size = 0;
 }

/**
 * Get node which represents the sequence in the trie.
 * 
 * @param seq
 * to find a node for.
 * @return Node which represents the sequence or NULL if not found.
 */
protectedNodegetNode(Cseq) {
if (root == null) returnnull;

// Find the string in the trie
Noden = root;
intlength = (seq.length() - 1);
for (inti = 0; i <= length; i++) {
charc = seq.charAt(i);
intindex = n.childIndex(c);
if (index >= 0) {
n = n.getChild(index);
 } else {
// string does not exist in trie
returnnull;
 }
 }

returnn;
 }

/**
 * {@inheritDoc}
 */
@Override
publicintsize() {
returnsize;
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleanvalidate() {
java.util.Set<C> keys = newjava.util.HashSet<C>();
Nodenode = root;
if (node!=null && !validate(node,"",keys)) returnfalse;
return (keys.size()==size());
 }

privatebooleanvalidate(Nodenode, Stringstring, java.util.Set<C> keys) {
StringBuilderbuilder = newStringBuilder(string);
builder.append(node.character);
Strings = builder.toString();

if (node.isWord) {
Cc = (C)s;
if (c==null) returnfalse;
if (keys.contains(c)) returnfalse;
keys.add(c);
 }
for (inti=0; i<node.childrenSize; i++) {
Noden = node.getChild(i);
if (n==null) returnfalse;
if (n.parent!=node) returnfalse;
if (!validate(n,s,keys)) returnfalse;
 }
returntrue;
 }

/**
 * {@inheritDoc}
 */
@Override
publicjava.util.Collection<C> toCollection() {
return (newJavaCompatibleTrie<C>(this));
 }

/**
 * {@inheritDoc}
 */
@Override
publicStringtoString() {
returnTriePrinter.getString(this);
 }

protectedstaticclassNode {

privatestaticfinalintMINIMUM_SIZE = 2;

protectedstaticfinalcharSENTINAL = '\0';

protectedNode[] children = newNode[MINIMUM_SIZE];
protectedintchildrenSize = 0;
protectedNodeparent = null;
protectedbooleanisWord = false; // Signifies this node represents a word
protectedcharcharacter = SENTINAL; // First character that is different the parent's string

protectedNode(Nodeparent, Charactercharacter, booleanisWord) {
this.parent = parent;
this.character = character;
this.isWord = isWord;
 }

protectedvoidaddChild(Nodenode) {
intgrowSize = children.length;
if (childrenSize >= children.length) {
children = Arrays.copyOf(children, (growSize + (growSize>>1)));
 }
children[childrenSize++] = node;
 }

protectedbooleanremoveChild(intindex) {
if (index >= childrenSize) returnfalse;

children[index] = null;
childrenSize--;

// Shift down the array
System.arraycopy(children, index + 1, children, index, childrenSize - index);

intshrinkSize = childrenSize;
if (childrenSize >= MINIMUM_SIZE && childrenSize < (shrinkSize + (shrinkSize<<1))) {
System.arraycopy(children, 0, children, 0, childrenSize);
 }

returntrue;
 }

protectedintchildIndex(CharacterparentChar) {
for (inti = 0; i < childrenSize; i++) {
NodechildChar = children[i];
if (parentChar.equals(childChar.character)) returni;
 }
returnInteger.MIN_VALUE;
 }

protectedNodegetChild(intindex) {
if (index >= childrenSize) returnnull;
returnchildren[index];
 }

protectedintgetChildrenSize() {
returnchildrenSize;
 }

/**
 * {@inheritDoc}
 */
@Override
publicStringtoString() {
StringBuilderbuilder = newStringBuilder();
if (isWord == true) builder.append("Node=").append(isWord).append("\n");
for (inti = 0; i < childrenSize; i++) {
Nodec = children[i];
builder.append(c.toString());
 }
returnbuilder.toString();
 }
 }

protectedstaticinterfaceINodeCreator {

/**
 * Create a new node for sequence.
 * 
 * @param parent
 * node of the new node.
 * @param character
 * which represents this node.
 * @param isWord
 * signifies if the node represents a word.
 * @return Node which was created.
 */
publicNodecreateNewNode(Nodeparent, Charactercharacter, booleanisWord);
 }

protectedstaticclassTriePrinter {

publicstatic <CextendsCharSequence> voidprint(Trie<C> trie) {
System.out.println(getString(trie));
 }

publicstatic <CextendsCharSequence> StringgetString(Trie<C> tree) {
if (tree.root == null) 
return"Tree has no nodes.";
returngetString(tree.root, "", null, true);
 }

protectedstaticStringgetString(Nodenode, Stringprefix, StringpreviousString, booleanisTail) {
StringBuilderbuilder = newStringBuilder();
Stringstring = null;
if (node.character != Node.SENTINAL) {
Stringtemp = String.valueOf(node.character);
if (previousString != null)
string = previousString + temp;
else
string = temp;
 }
builder.append(prefix + (isTail ? "└── " : "├── ") + ((node.isWord == true) ? 
 ("(" + node.character + ") " + string)
 : 
node.character) + "\n"
 );
if (node.children != null) {
for (inti = 0; i < node.childrenSize - 1; i++) {
builder.append(getString(node.children[i], prefix + (isTail ? " " : "│ "), string, false));
 }
if (node.childrenSize >= 1) {
builder.append(getString(node.children[node.childrenSize - 1], prefix + (isTail ? " " : "│ "), string, true));
 }
 }
returnbuilder.toString();
 }
 }

publicstaticclassJavaCompatibleTrie<CextendsCharSequence> extendsjava.util.AbstractCollection<C> {

privateTrie<C> trie = null;

publicJavaCompatibleTrie(Trie<C> trie) {
this.trie = trie;
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleanadd(Cvalue) {
returntrie.add(value);
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleanremove(Objectvalue) {
return (trie.remove((C)value)!=null);
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleancontains(Objectvalue) {
returntrie.contains((C)value);
 }

/**
 * {@inheritDoc}
 */
@Override
publicintsize() {
returntrie.size;
 }

/**
 * {@inheritDoc}
 * 
 * WARNING: This iterator makes a copy of the trie's contents during it's construction!
 */
@Override
publicjava.util.Iterator<C> iterator() {
return (newTrieIterator<C>(trie));
 }

privatestaticclassTrieIterator<CextendsCharSequence> implementsjava.util.Iterator<C> {

privateTrie<C> trie = null;
privateTrie.NodelastNode = null;
privatejava.util.Iterator<java.util.Map.Entry<Node, String>> iterator = null;

protectedTrieIterator(Trie<C> trie) {
this.trie = trie;
java.util.Map<Trie.Node,String> map = newjava.util.LinkedHashMap<Trie.Node,String>();
if (this.trie.root!=null) {
getNodesWhichRepresentsWords(this.trie.root,"",map);
 }
iterator = map.entrySet().iterator();
 }

privatevoidgetNodesWhichRepresentsWords(Trie.Nodenode, Stringstring, java.util.Map<Trie.Node,String> nodesMap) {
StringBuilderbuilder = newStringBuilder(string);
if (node.character!=Node.SENTINAL) builder.append(node.character);
if (node.isWord) nodesMap.put(node,builder.toString());
for (inti=0; i<node.childrenSize; i++) {
Nodechild = node.getChild(i);
getNodesWhichRepresentsWords(child,builder.toString(),nodesMap);
 }
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleanhasNext() {
if (iterator!=null && iterator.hasNext()) returntrue;
returnfalse;
 }

/**
 * {@inheritDoc}
 */
@Override
publicCnext() {
if (iterator==null) returnnull;

java.util.Map.Entry<Trie.Node,String> entry = iterator.next();
lastNode = entry.getKey();
return (C)entry.getValue();
 }

/**
 * {@inheritDoc}
 */
@Override
publicvoidremove() {
if (iterator==null || trie==null) return;

iterator.remove();
this.trie.remove(lastNode);
 }
 }
 }
}