Class ForaxTrie

java.lang.Object
  ForaxTrie

All Implemented Interfaces:

Trie

public class ForaxTrie

extends java.lang.Object

implements Trie

Implements Tries with ordered lists of sons for each node. The complexity of all algorithms to process a word of length n is n*log(k) where k is the size of the alphabet.

Method Summary

ForaxTrie	add(char c) Returns the son labeled c if there is one and creates it otherwise.
void	addToTrie(java.lang.String text) Adds the word s to the trie.
void	fromFile(java.lang.String name) Builds a trie representing the list of strings read from a file line by line.
boolean	isInTrie(java.lang.String s) Returns true if the trie contains s.
boolean	isLeaf() Returns true if the node p is a leaf of the trie.
Pair	longestPrefixInTrie(java.lang.String s, int j) Computes the pair composed of the length of the longest prefix of s[j..n-1] in the trie and the vertex reached by this prefix.
static void	main(java.lang.String[] args)
ForaxTrie	next(char c) Returns the son of label c if it exists and null otherwise.
void	print(java.io.PrintStream output)
void	removeFromTrie(java.lang.String s) Removes the string s from the trie.
Dawg	toDawg()
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Method Detail

longestPrefixInTrie

public Pair longestPrefixInTrie(java.lang.String s,
                                int j)

Computes the pair composed of the length of the longest prefix of s[j..n-1] in the trie and the vertex reached by this prefix. Implements the function LongestPrefixInTrie() of Section 1.3.1. Complexity: O(|s|*log(k)) on an alphabet of size k<:code>.

Specified by:

longestPrefixInTrie in interface Trie

Parameters:

s - the input string

j - the starting index

Returns:

the computed pair

next

public ForaxTrie next(char c)

Returns the son of label c if it exists and null otherwise.

isInTrie

public boolean isInTrie(java.lang.String s)

Returns true if the trie contains s. Implements the function IsInTrie() of Section 1.3.1. Complexity: O(|s|*log(k)) on an alphabet of size k<:code>.

Specified by:

isInTrie in interface Trie

add

public ForaxTrie add(char c)

Returns the son labeled c if there is one and creates it otherwise. Complexity: log(k) where k is the number of sons (uses a binary search on the on the oredered array nodes).

addToTrie

public void addToTrie(java.lang.String text)

Adds the word s to the trie. Implements the function AddToTrie() of Section 1.3.1. Complexity: n*log(k) where n is the length of text and k is the size of the alphabet.

Specified by:

addToTrie in interface Trie

Parameters:

text - the string to be added.

isLeaf

public boolean isLeaf()

Returns true if the node p is a leaf of the trie. Implements the function IsLeaf() of Section 1.3.1.

Specified by:

isLeaf in interface Trie

removeFromTrie

public void removeFromTrie(java.lang.String s)

Removes the string s from the trie. Implements the function RemoveFromTrie() of Section 1.3.1. To be written.

Specified by:

removeFromTrie in interface Trie

Parameters:

s - the string to be removed

toString

public java.lang.String toString()

fromFile

public void fromFile(java.lang.String name)
              throws java.io.IOException

Builds a trie representing the list of strings read from a file line by line.

Specified by:

fromFile in interface Trie

Parameters:

name - the name of the file

Throws:

java.io.IOException

print

public void print(java.io.PrintStream output)

toDawg

public Dawg toDawg()

main

public static void main(java.lang.String[] args)
                 throws java.io.IOException

Throws:

java.io.IOException