au.id.pbw.hyfo.hyph
Class BigTernaryTree

java.lang.Object
  au.id.pbw.hyfo.hyph.BigTernaryTree

All Implemented Interfaces:

TernaryTree, Serializable

public class BigTernaryTree
extends Object
implements TernaryTree, Serializable

A TernaryTree whose node count may exceed Short.MAX_VALUE.

Author:

pbw

See Also:

Serialized Form

Nested Class Summary

class	BigTernaryTree.TernaryIterator Defines an in-order Iterator over the tree.
class	BigTernaryTree.TernaryTreeWalker This process walks the tree and feeds TreeElements into a blocking queue for reading by an Iterator.

Constructor Summary

BigTernaryTree(TernaryTreeDataStore data_store)
Creates a new instance of BigTernaryTree

Method Summary

void	add(int[] key, int index, int data, int node_num) Inserts the subkey represented by the array of Unicode codepoints and associated data.
Subsearch	find_next(int[] key, int index, int node_num) Returns a Subsearch representing a position in the tree at which non-null DATA was found while tracing a given key.
int	find(int[] key) Find the data pointer associated with a given key, or 0 if the key does not occur .
int	get_equal_node(int node) Gets the node pointed to by the equal pointer of the given node.
String	get_key(List<Integer> stack) Constructs the key from the series of entries in the key codepoint stack.
int	get_node_data_ptr(int node) Gets the node data.
void	initialize_data_array() Finalizes the data initialization of this BigTernaryTree.
void	insert_mid(String[] keys, Map<String,Integer> map, int lo, int hi) Given a ascending sorted array of keys, a map associating a datum with each key, the index of the least key to be inserted (lo) and the index of the greatest key to be inserted (hi), perform a balanced add of all of the keys between the least and the greatest, inclusive.
BigTernaryTree.TernaryIterator	iterator() Gets a TernaryIterator for in-order traversal of the tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

BigTernaryTree

public BigTernaryTree(TernaryTreeDataStore data_store)

Creates a new instance of BigTernaryTree

Parameters:

data_store - an implementation of TernaryTreeDataStore.

Method Detail

get_node_data_ptr

public int get_node_data_ptr(int node)

Gets the node data.

Specified by:

get_node_data_ptr in interface TernaryTree

Parameters:

node - the number of the data node.

Returns:

the node data payload.

find

public int find(int[] key)

Find the data pointer associated with a given key, or 0 if the key does not occur .

Specified by:

find in interface TernaryTree

Parameters:

key - the key, as an array of Unicode codepoints.

Returns:

the DATA or null.

find_next

public Subsearch find_next(int[] key,
                           int index,
                           int node_num)

Returns a Subsearch representing a position in the tree at which non-null DATA was found while tracing a given key. This is a match of a prefix of the search key. The returned Subsearch can subsequently be used to find the next longer prefix of the key with associated DATA.

Specified by:

find_next in interface TernaryTree

Parameters:

key - the key of which prefixes are being sought.

index - the next Unicode character of the search string. A prefix equal to or longer than this position of the key will be the next found, if one exists.

node_num - the node number at which the search commences.

Returns:

a Subsearch representing the next located prefix of the key, or null.

add

public void add(int[] key,
                int index,
                int data,
                int node_num)
         throws HyphenationException

Inserts the subkey represented by the array of Unicode codepoints and associated data.

Parameters:

key - the Unicode codepoints of the subkey.

index - the index within the key array fo the beginning of the add text.

data - the data associated with the key.

node_num - the node number at which the insertion is occuring.

Throws:

HyphenationException - if an invalid node number argument is passed.

insert_mid

public void insert_mid(String[] keys,
                       Map<String,Integer> map,
                       int lo,
                       int hi)
                throws HyphenationException

Given a ascending sorted array of keys, a map associating a datum with each key, the index of the least key to be inserted (lo) and the index of the greatest key to be inserted (hi), perform a balanced add of all of the keys between the least and the greatest, inclusive.

The datum for a key is an Integer, whose interpretation is left to the TernaryTreeDataStore implementation.

Parameters:

keys - the array of all keys.

map - the Map associating data with keys.

lo - the least key to be inserted from the array.

hi - the greatest key to be inserted from the array.

Throws:

HyphenationException - if the tree has already been initialized, indicating that tree building is finalized.

initialize_data_array

public void initialize_data_array()
                           throws HyphenationException

Finalizes the data initialization of this BigTernaryTree. This assumes that all required nodes have been added to the tree. The parallel arrays representing the node links (equal, less, greater, parent and the pointer to the node data are all reset to their minimum size.

Specified by:

initialize_data_array in interface TernaryTree

Throws:

HyphenationException - if the tree has already been initialized, indicating that tree building is finalized.

get_key

public String get_key(List<Integer> stack)

Constructs the key from the series of entries in the key codepoint stack.

Specified by:

get_key in interface TernaryTree

Parameters:

stack - the stack of Integers containing the codepoints of the key.

Returns:

the key as a String.

iterator

public BigTernaryTree.TernaryIterator iterator()

Gets a TernaryIterator for in-order traversal of the tree.

Specified by:

iterator in interface TernaryTree

Returns:

a TernaryIterator for in-order traversal of the tree.

get_equal_node

public int get_equal_node(int node)

Gets the node pointed to by the equal pointer of the given node.

Specified by:

get_equal_node in interface TernaryTree

Parameters:

node - the node whose equal pointer is returned.

Returns:

the equal pointer from node.