au.id.pbw.hyfo.hyph
Class BigTernaryTree

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


Copyright © 2005-2006 Peter B. West.