I found this trie implementation from Code Review, it works perfectly, I already changed it somehow to fit my program's needs now I want to manipulate the find()
function so I can have the results in an array.
Thanks.
Here's the class code:
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
public class AutoComplete {
private final Map<Character, HashMap> root = new HashMap<Character, HashMap>();
private final Character END_CHARACTER = '$';
/**
* Will create an empty AutoComplete
*/
public AutoComplete() {}
/**
* Will create an AutoComplete filled from a Collection of String items
*
* @param items A Collection (Vector, List etc.) of String items
*/
public AutoComplete (Collection<String> items)
{
for (String s : items)
{
internalAdd(s);
}
}
/**
* Will create an AutoComplete filled from an array of String items
*
* @param items An array of String items
*/
public AutoComplete (String[] items)
{
for (String s : items){
internalAdd(s);
}
}
/**
* Will add a String to the AutoComplete
*
* @param item The String item to add
* @return Returns true if item is added, false if item already exists
*/
public boolean add(String item)
{
if (find(item) != null)
{
internalAdd(item);
return true;
}
else
{
return false;
}
}
/**
* Will return an array of Strings that start with the given prefix
*
* @param prefix The prefix to search for
* @return An array of Strings starting with the prefix. Will return null if nothing is found.
*/
public String[] find(String prefix)
{
Map<Character, HashMap> node = root;
for (int i = 0; i < prefix.length(); i++)
{
if (node.isEmpty())
{
return null;
}
Character character = prefix.charAt(i);
if (node.containsKey(character))
{
node = node.get(character);
}
else
{
return null;
}
}
// return found items as an array
}
private boolean internalAdd(final String s)
{
Map<Character, HashMap> node = root;
for (int i = 0; i < s.length(); i++)
{
Character character = s.charAt(i);
if(node.isEmpty() || !node.containsKey(character))
{
internalAdd(s.substring(i), node);
break;
}
node = node.get(character);
}
node.put(END_CHARACTER, new HashMap());
return true;
}
private void internalAdd(final String s, Map<Character, HashMap> node)
{
for (int i = 0; i < s.length(); i++)
{
Character character = s.charAt(i);
node.put(character, new HashMap());
node = node.get(character);
}
}
}
I changed the whole class, now it returns the found items in an array. Here is the class code:
import java.util.ArrayList;
import java.util.Collection;
public class AutoComplete {
private class Node
{
public int value;
public Node firstChild;
public Node nextSibling;
public Node(int value)
{
this.value = value;
firstChild = null;
nextSibling = null;
}
}
public final static char DELIMITER = '\u0001';
private Node root;
private int maxDepth;
private int size;
public AutoComplete()
{
root = new Node('r');
size = 0;
}
public AutoComplete (Collection<String> items)
{
root = new Node('r');
size = 0;
for (String item : items)
{
if (!isEntry(item))
{
add(item);
}
}
}
public AutoComplete (String[] items)
{
root = new Node('r');
size = 0;
for (String item : items)
{
if (!isEntry(item))
{
add(item);
}
}
}
public boolean add(String item)
{
if (isEntry(item))
{
return false;
}
else if (add(root, item + DELIMITER, 0))
{
size++;
int n = item.length();
if (n > maxDepth)
{
maxDepth = n;
}
return true;
}
return false;
}
public String[] find(String prefix)
{
String[] result = suggest(root, prefix, 0);
if (result[0] == prefix)
{
return null;
}
else
{
return result;
}
}
private boolean add(Node root, String word, int offset)
{
if (offset == word.length())
{
return false;
}
int c = word.charAt(offset);
Node last = null, next = root.firstChild;
while (next != null)
{
if (next.value < c)
{
last = next;
next = next.nextSibling;
}
else if (next.value == c)
{
return add(next, word, offset + 1);
}
else
{
break;
}
}
Node node = new Node(c);
if (last == null)
{
root.firstChild = node;
node.nextSibling = next;
}
else
{
last.nextSibling = node;
node.nextSibling = next;
}
for (int i = offset + 1; i < word.length(); i++)
{
node.firstChild = new Node(word.charAt(i));
node = node.firstChild;
}
return true;
}
private boolean isEntry(String word)
{
return isEntry(root, word + DELIMITER, 0);
}
private boolean isEntry(Node root, String word, int offset)
{
if (offset == word.length())
{
return true;
}
int c = word.charAt(offset);
Node next = root.firstChild;
while (next != null)
{
if (next.value < c)
{
next = next.nextSibling;
}
else if (next.value == c)
{
return isEntry(next, word, offset + 1);
}
else
{
return false;
}
}
return false;
}
private String[] suggest(Node root, String word, int offset)
{
if (offset == word.length())
{
ArrayList<String> words = new ArrayList<String>(size);
char[] chars = new char[maxDepth];
for (int i = 0; i < offset; i++)
{
chars[i] = word.charAt(i);
}
getAll(root, words, chars, offset);
return words.toArray(new String[words.size()]);
}
int c = word.charAt(offset);
Node next = root.firstChild;
while (next != null)
{
if (next.value < c)
{
next = next.nextSibling;
}
else if (next.value == c)
{
return suggest(next, word, offset + 1);
}
else
{
break;
}
}
return new String[] { word };
}
private void getAll(Node root, ArrayList<String> words, char[] chars, int pointer)
{
Node n = root.firstChild;
while (n != null)
{
if (n.firstChild == null)
{
words.add(new String(chars, 0, pointer));
}
else
{
chars[pointer] = (char)n.value;
getAll(n, words, chars, pointer + 1);
}
n = n.nextSibling;
}
}
}