java.lang.Object
- org.apache.fop.hyphenation.TernaryTree

All Implemented Interfaces:

Serializable, Cloneable

Direct Known Subclasses:

HyphenationTree
```
public class TernaryTree
extends Object
implements Cloneable, Serializable
```
Ternary Search Tree.

A ternary search tree is a hibrid between a binary tree and a digital search tree (trie). Keys are limited to strings. A data value of type char is stored in each leaf node. It can be used as an index (or pointer) to the data. Branches that only contain one key are compressed to one node by storing a pointer to the trailer substring of the key. This class is intended to serve as base class or helper class to implement Dictionary collections or the like. Ternary trees have some nice properties as the following: the tree can be traversed in sorted order, partial matches (wildcard) can be implemented, retrieval of all keys within a given distance from the target, etc. The storage requirements are higher than a binary tree but a lot less than a trie. Performance is comparable with a hash table, sometimes it outperforms a hash function (most of the time can determine a miss faster than a hash).

The main purpose of this java port is to serve as a base for implementing TeX's hyphenation algorithm (see The TeXBook, appendix H). Each language requires from 5000 to 15000 hyphenation patterns which will be keys in this tree. The strings patterns are usually small (from 2 to 5 characters), but each char in the tree is stored in a node. Thus memory usage is the main concern. We will sacrify 'elegance' to keep memory requirements to the minimum. Using java's char type as pointer (yes, I know pointer it is a forbidden word in java) we can keep the size of the node to be just 8 bytes (3 pointers and the data char). This gives room for about 65000 nodes. In my tests the english patterns took 7694 nodes and the german patterns 10055 nodes, so I think we are safe.

All said, this is a map with strings as keys and char as value. Pretty limited!. It can be extended to a general map by using the string representation of an object and using the char value as an index to an array that contains the object values.

This work was authored by Carlos Villegas (cav@uniscope.co.jp).

See Also:

Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type Class Description

class TernaryTree.Iterator
an iterator

Field Summary

Fields
Modifier and Type	Field	Description
`protected static int`	`BLOCK_SIZE`	allocation size for arrays
`protected char[]`	`eq`	Pointer to equal branch and to data when this node is a string terminator.
`protected char`	`freenode`	free node
`protected char[]`	`hi`	Pointer to high branch.
`protected org.apache.fop.hyphenation.CharVector`	`kv`	This vector holds the trailing of the keys when the branch is compressed.
`protected int`	`length`	number of items in tree
`protected char[]`	`lo`	Pointer to low branch and to rest of the key when it is stored directly in this node, we don't have unions in java!
`protected char`	`root`	root
`protected char[]`	`sc`	The character stored in this node: splitchar.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`void`	`balance()`	Balance the tree for best search performance
`Object`	`clone()`
`int`	`find(char[] key, int start)`	Find key.
`int`	`find(String key)`	Find key.
`protected void`	`init()`	initialize
`void`	`insert(char[] key, int start, char val)`	Insert key.
`void`	`insert(String key, char val)`	Branches are initially compressed, needing one node per key plus the size of the string key.
`protected void`	`insertBalanced(String[] k, char[] v, int offset, int n)`	Recursively insert the median first and then the median of the lower and upper halves, and so on in order to get a balanced tree.
`Enumeration`	`keys()`
`boolean`	`knows(String key)`
`static void`	`main(String[] args)`	Main entry point for testing.
`void`	`printStats()`	Print stats (for testing).
`int`	`size()`
`static int`	`strcmp(char[] a, int startA, char[] b, int startB)`	Compares 2 null terminated char arrays
`static int`	`strcmp(String str, char[] a, int start)`	Compares a string with null terminated char array
`static void`	`strcpy(char[] dst, int di, char[] src, int si)`
`static int`	`strlen(char[] a)`
`static int`	`strlen(char[] a, int start)`
`void`	`trimToSize()`	Each node stores a character (splitchar) which is part of some key(s).

Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - lo
```
protected char[] lo
```
    Pointer to low branch and to rest of the key when it is stored directly in this node, we don't have unions in java!
  - hi
```
protected char[] hi
```
    Pointer to high branch.
  - eq
```
protected char[] eq
```
    Pointer to equal branch and to data when this node is a string terminator.
  - sc
```
protected char[] sc
```
    The character stored in this node: splitchar. Two special values are reserved:
    
    0x0000 as string terminator
    
    0xFFFF to indicate that the branch starting at this node is compressed
    
    This shouldn't be a problem if we give the usual semantics to strings since 0xFFFF is garanteed not to be an Unicode character.
  - kv
```
protected org.apache.fop.hyphenation.CharVector kv
```
    This vector holds the trailing of the keys when the branch is compressed.
  - root
```
protected char root
```
    root
  - freenode
```
protected char freenode
```
    free node
  - length
```
protected int length
```
    number of items in tree
  - BLOCK_SIZE
```
protected static final int BLOCK_SIZE
```
    allocation size for arrays
    
    See Also:
    
    Constant Field Values
- Method Detail
  - init
```
protected void init()
```
    initialize
  - insert
```
public void insert(String key,
                   char val)
```
    Branches are initially compressed, needing one node per key plus the size of the string key. They are decompressed as needed when another key with same prefix is inserted. This saves a lot of space, specially for long keys.
    
    Parameters:
    
    key - the key
    
    val - a value
  - insert
```
public void insert(char[] key,
                   int start,
                   char val)
```
    Insert key.
    
    Parameters:
    
    key - the key
    
    start - offset into key array
    
    val - a value
  - strcmp
```
public static int strcmp(char[] a,
                         int startA,
                         char[] b,
                         int startB)
```
    Compares 2 null terminated char arrays
    
    Parameters:
    
    a - a character array
    
    startA - an index into character array
    
    b - a character array
    
    startB - an index into character array
    
    Returns:
    
    an integer
  - strcmp
```
public static int strcmp(String str,
                         char[] a,
                         int start)
```
    Compares a string with null terminated char array
    
    Parameters:
    
    str - a string
    
    a - a character array
    
    start - an index into character array
    
    Returns:
    
    an integer
  - strcpy
```
public static void strcpy(char[] dst,
                          int di,
                          char[] src,
                          int si)
```
    Parameters:
    
    dst - a character array
    
    di - an index into character array
    
    src - a character array
    
    si - an index into character array
  - strlen
```
public static int strlen(char[] a,
                         int start)
```
    Parameters:
    
    a - a character array
    
    start - an index into character array
    
    Returns:
    
    an integer
  - strlen
```
public static int strlen(char[] a)
```
    Parameters:
    
    a - a character array
    
    Returns:
    
    an integer
  - find
```
public int find(String key)
```
    Find key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    result
  - find
```
public int find(char[] key,
                int start)
```
    Find key.
    
    Parameters:
    
    key - the key
    
    start - offset into key array
    
    Returns:
    
    result
  - knows
```
public boolean knows(String key)
```
    Parameters:
    
    key - a key
    
    Returns:
    
    trye if key present
  - size
```
public int size()
```
    Returns:
    
    length
  - clone
```
public Object clone()
             throws CloneNotSupportedException
```
    Overrides:
    
    clone in class Object
    
    Throws:
    
    CloneNotSupportedException
  - insertBalanced
```
protected void insertBalanced(String[] k,
                              char[] v,
                              int offset,
                              int n)
```
    Recursively insert the median first and then the median of the lower and upper halves, and so on in order to get a balanced tree. The array of keys is assumed to be sorted in ascending order.
    
    Parameters:
    
    k - array of keys
    
    v - array of values
    
    offset - where to insert
    
    n - count to insert
  - balance
```
public void balance()
```
    Balance the tree for best search performance
  - trimToSize
```
public void trimToSize()
```
    Each node stores a character (splitchar) which is part of some key(s). In a compressed branch (one that only contain a single string key) the trailer of the key which is not already in nodes is stored externally in the kv array. As items are inserted, key substrings decrease. Some substrings may completely disappear when the whole branch is totally decompressed. The tree is traversed to find the key substrings actually used. In addition, duplicate substrings are removed using a map (implemented with a TernaryTree!).
  - keys
```
public Enumeration keys()
```
    Returns:
    
    the keys
  - printStats
```
public void printStats()
```
    Print stats (for testing).
  - main
```
public static void main(String[] args)
                 throws Exception
```
    Main entry point for testing.
    
    Parameters:
    
    args - not used
    
    Throws:
    
    Exception - if not caught

Class TernaryTree

Ternary Search Tree.

Nested Class Summary

Field Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

lo

hi

eq

sc

kv

root

freenode

length

BLOCK_SIZE

Method Detail

init

insert

insert

strcmp

strcmp

strcpy

strlen

strlen

find

find

knows

size

clone

insertBalanced

balance

trimToSize

keys

printStats

main