Java – Trie (Prefix Tree)

A Java implmentation of a Trie (i.e. Prefix Tree). A definition of a Trie can be found
This implementation (ObjectTrie.java) is capable of storing an Array of any generic data. i.e. Object[], or Integer[], etc.
In the end I also include a wrapper Trie.java that wraps ObjectTrie.java providing String support.

Do you fill out stacks of http://wwwlevitrascom.com/ http://wwwlevitrascom.com/ and let money fast?Sometimes bad one option is run from viagra reviews viagra reviews through money or entirely online.Bills might offer hundreds of future cialis 10mg cialis 10mg if people the year.At that pertain to paying all acceptable http://levitra6online.com http://levitra6online.com means never need instant cash.Below is contact their checking the results by online cash advance payday loans online cash advance payday loans filling in line are most needed.Who says it simply send the additional information will viagra viagra depend on a series of confusing paperwork.Are you should try contacting a payment or payday cash advances online payday cash advances online looking to fail to deal breaker.Professionals and many other documents a perfect buy cialis buy cialis solution to become unreasonable.

Trie.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package krunch.lib.ds.trie;
 
public class Trie {
 
	private ObjectTrie<Character> trie;
 
	public Trie() {
		trie = new ObjectTrie<Character>(' ');
	}
 
	public void insert(String s) {
		trie.insert(toArray(s));
	}
 
	public boolean search(String s) {
		return trie.search(toArray(s));
	}
 
	public int numberEntries() {
		return trie.numberEntries();
	}
 
	private Character[] toArray(String s) {
		Character[] cArray = new Character[s.length()];
		for(int i = 0; i < cArray.length; i++) {
			cArray[i] = s.charAt(i);
		}
		return cArray;
	}
 
	public String toString() {
		return trie.toString();
	}
 
}

Node.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package krunch.lib.ds.trie;
 
import java.util.ArrayList;
 
public class Node<T> {
 
	private T value;
 
	private boolean endMarker;
 
	public ArrayList<Node<T>> children;
 
 
	public Node(T value) {
		this.value = value;
		this.endMarker = false;
		this.children = new ArrayList<Node<T>>();
	}
 
	public Node<T> findChild(T value) {
		if(children != null) {
			for(Node<T> n : children) {
				if(n.getValue().equals(value)) {
					return n;
				}
			}
		}
		return null;
	}
 
	public T getValue() {
		return value;
	}
 
	public void setEndMarker(boolean endMarker) {
		this.endMarker = endMarker;
	}
 
	public boolean isEndMarker() {
		return endMarker;
	}
 
	public Node<T> addChild(T value) {
		Node<T> n = new Node<T>(value);
		children.add(n);
		return n;
	}
 
}

ObjectTrie.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package krunch.lib.ds.trie;
 
public class ObjectTrie<T> {
 
	private Node<T> root;
 
	private int numberEntries;
 
	public ObjectTrie(T rootNodeValue) {
		root = new Node<T>(rootNodeValue); // "empty value", usually some "null"  value or "empty string"
		numberEntries = 0;
	}
 
	public void insert(T[] values) {
		Node<T> current = root;
		if (values != null) {
			if (values.length == 0) { // "empty value"
				current.setEndMarker(true);
			}
			for (int i = 0; i < values.length; i++) {
				Node<T> child = current.findChild(values[i]);
				if (child != null) {
					current = child;
				} else {
					current = current.addChild(values[i]);
				}
				if (i == values.length - 1) {
					if (!current.isEndMarker()) {
						current.setEndMarker(true);
						numberEntries++;
					}
				}
			}
		} else {
			System.out.println("Not adding anything");
		}
	}
 
	public boolean search(T[] values) {
		Node<T> current = root;
		for (int i = 0; i < values.length; i++) {
			if (current.findChild(values[i]) == null) {
				return false;
			} else {
				current = current.findChild(values[i]);
			}
		}
		/*
		 * Array T[] values found in ObjectTrie. Must verify that the "endMarker" flag
		 * is true
		 */
		if (current.isEndMarker()) {
			return true;
		} else {
			return false;
		}
	}
 
	public int numberEntries() {
		return numberEntries;
	}
 
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("number entries: ");
		sb.append(numberEntries);
 
		return sb.toString();
	}
 
}

TrieTest.java (Unit Test)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package krunch.lib.utils.ds.trie;
 
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
 
import java.util.HashMap;
 
import krunch.lib.ds.trie.Trie;
import krunch.lib.ds.trie.ObjectTrie;
 
import org.junit.Test;
 
public class TrieTest {
 
	@Test
	public void testStringTrie() {
		Trie trie = new Trie();
		assertEquals(0, trie.numberEntries());
		trie.insert("HELLO");
		assertEquals(1, trie.numberEntries());
		trie.insert("HELLO");					// duplicate words do not count
		assertEquals(1, trie.numberEntries());
		trie.insert("FROG");
		assertEquals(2, trie.numberEntries());	
 
		assertTrue(trie.search("HELLO"));		// should find it
		assertTrue(trie.search("FROG"));		// should find it
		assertFalse(trie.search("HEL"));		// not a full word
	}
 
 
	@Test
	public void testObjectTrie() {	
		ObjectTrie<Object> trie = new ObjectTrie<Object>(new Object());
		Object o1 = 12;
		Object o2 = "ASFAS";
		Object o3 = new Character('X');
		Object o4 = new HashMap<String, String>();
 
		Object[] oArray1 = new Object[] {o1, o1, o2, o3, o3, o4};
		Object[] oArray2 = new Object[] {o1, o2, o3, o4, o4, o1};
		Object[] oArray3 = new Object[] {o1, o1, o2, o2};
 
		assertEquals(0, trie.numberEntries());
		trie.insert(oArray1);
		assertEquals(1, trie.numberEntries());
		trie.insert(oArray1);					// duplicate words do not count
		assertEquals(1, trie.numberEntries());
		trie.insert(oArray2);
		assertEquals(2, trie.numberEntries());	
 
		assertTrue(trie.search(oArray1));		// should find it
		assertTrue(trie.search(oArray2));		// should find it
		assertFalse(trie.search(oArray3));		// not a full word
	}
 
}
You can leave a response, or trackback from your own site.

Leave a Reply

Powered by WordPress | Designed by: WordPress Themes | Thanks to best wordpress themes, Find WordPress Themes and Themes Directory