Class ForaxTrie

java.lang.Object
  extended byForaxTrie
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