Class FixedArrayTrie

java.lang.Object
  FixedArrayTrie

All Implemented Interfaces:

Trie

public class FixedArrayTrie

extends java.lang.Object

implements Trie

An implementation of tries with linked lists. Each node of the trie is a fixed-size array of pointers on its sons. All algorithms (addToTrie, isInTrie, removeFromTrie) are linear. The space used is bounded by Card(alphabet)*sum of lengths of words.

Field Summary

static Alphabet	alphabet The alphabet used to form the strings composing the trie.
FixedArrayTrie[]	next The array of sons of the node.
boolean	terminal True if the node is terminal.

Constructor Summary

FixedArrayTrie()

Method Summary

void	addToTrie(java.lang.String s) 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)
void	removeFromTrie(java.lang.String s) Removes the string s from the trie.
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

alphabet

public static Alphabet alphabet

The alphabet used to form the strings composing the trie.

terminal

public boolean terminal

True if the node is terminal.

next

public FixedArrayTrie[] next

The array of sons of the node.

Constructor Detail

FixedArrayTrie

public FixedArrayTrie()

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: linear in the length of s.

Specified by:

longestPrefixInTrie in interface Trie

Parameters:

s - the input string

j - the starting index

Returns:

the computed pair

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: linear in the length of s.

Specified by:

isInTrie in interface Trie

addToTrie

public void addToTrie(java.lang.String s)

Adds the word s to the trie. Implements the function AddToTrie() of Section 1.3.1. Complexity: linear in the length of s.

Specified by:

addToTrie in interface Trie

Parameters:

s - 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. Complexity: linear in the length of s.

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

main

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

Throws:

java.io.IOException