edu.iastate.jtm.dic
Class Trie

java.lang.Object
  edu.iastate.jtm.dic.Trie

public class Trie
extends java.lang.Object

An implementation of trie data structure.

Author:

Jing Ding

Constructor Summary

Trie(TrieNode rt)
Creates a new instance of Trie.

Method Summary

void	clear() Remove all child nodes.
java.lang.Object	get(java.lang.String key) Find and return the value associated with a key.
java.lang.String	getCompleteKey(TrieNode leaf)
TrieNode	getRoot() Return the root node.
TrieNode	incrementalGet(java.lang.CharSequence key, TrieNode rt) Find and return the node of a specific key.
boolean	isCaseSensitive()
java.util.Enumeration	keys()
void	print(java.io.PrintStream ps, boolean printValue) Print all entries in this trie.
void	put(java.lang.CharSequence key, java.lang.Object val, boolean replace) Put a key and value pair in the trie.
void	put(java.lang.String key, java.lang.Object val) Put a key and value pair in the trie.
java.lang.Object	remove(java.lang.CharSequence key) Remove an entry from the trie.
int	size() Return the number of entries in this trie.
java.lang.String[]	splitKey(java.lang.String key) Split a string into keys in the trie (greedy).
java.lang.String[]	splitKey(java.lang.String key, boolean greedy) Split a string into keys in the trie.
java.lang.String	supportedCharacters() Return supported characters by this Trie.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Trie

public Trie(TrieNode rt)

Creates a new instance of Trie.

Parameters:

rt - the root node of the trie.

Method Detail

getRoot

public TrieNode getRoot()

Return the root node.

Returns:

the root node.

put

public void put(java.lang.String key,
                java.lang.Object val)

Put a key and value pair in the trie. The key may be spreaded to several nodes. If the key already exists in the trie, the new value replaces the old one.

Parameters:

key - the key.

val - the value.

put

public void put(java.lang.CharSequence key,
                java.lang.Object val,
                boolean replace)

Put a key and value pair in the trie. The key may be spreaded to several nodes. If the key already exists in the trie, the new value may or may not replace the old one according to the 'replace' argument.

Parameters:

key - the key.

val - the value.

replace - replace the old value if true.

remove

public java.lang.Object remove(java.lang.CharSequence key)

Remove an entry from the trie. Set the corresponding node's value to null. The trie's node structure is unchanged.

Parameters:

key - key of the entry to be removed

Returns:

The removed value if exists in the trie

clear

public void clear()

Remove all child nodes.

incrementalGet

public TrieNode incrementalGet(java.lang.CharSequence key,
                               TrieNode rt)

Find and return the node of a specific key.

Parameters:

key - the key

rt - the node to start the search.

Returns:

the node matching the key. Null if no match can be found.

getCompleteKey

public java.lang.String getCompleteKey(TrieNode leaf)

get

public java.lang.Object get(java.lang.String key)

Find and return the value associated with a key.

Parameters:

key - the key.

Returns:

The value associated with the key. Null if the key does not exist in the trie.

splitKey

public java.lang.String[] splitKey(java.lang.String key,
                                   boolean greedy)

Split a string into keys in the trie. Todo: optimize to CharBuffer. Greedy split: depth-first search, match keys as long as possible.

Parameters:

key - the string to be splitted.

greedy - greedy or reluctant split.

Returns:

The array of splitted keys. Null if the string can't be completely splitted.

splitKey

public java.lang.String[] splitKey(java.lang.String key)

Split a string into keys in the trie (greedy).

Parameters:

key - the string to be splitted.

Returns:

The array of splitted keys. Null if the string can't be completely splitted.

supportedCharacters

public java.lang.String supportedCharacters()

Return supported characters by this Trie.

Returns:

supported characters by this Trie.

isCaseSensitive

public boolean isCaseSensitive()

size

public int size()

Return the number of entries in this trie.

Returns:

number of entries in this trie

keys

public java.util.Enumeration keys()

print

public void print(java.io.PrintStream ps,
                  boolean printValue)

Print all entries in this trie. Save to a file or display on screen.

Parameters:

ps - output destination.

printValue - Whether or not print associated values.