Class TernaryTree
- java.lang.Object
-
- com.itextpdf.layout.hyphenation.TernaryTree
-
- Direct Known Subclasses:
HyphenationTree
public class TernaryTree extends java.lang.Object
Ternary Search Tree.
A ternary search tree is a hybrid 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).
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
TernaryTree.TreeInsertionParams
-
Field Summary
Fields Modifier and Type Field Description protected static int
BLOCK_SIZE
allocation size for arraysprotected char[]
eq
Pointer to equal branch and to data when this node is a string terminator.protected char
freenode
free nodeprotected char[]
hi
Pointer to high branch.protected CharVector
kv
This vector holds the trailing of the keys when the branch is compressed.protected int
length
number of items in treeprotected 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
rootprotected char[]
sc
The character stored in this node: splitchar.
-
Constructor Summary
Constructors Constructor Description TernaryTree()
default constructorTernaryTree(TernaryTree tt)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
balance()
Balance the tree for best search performanceprivate void
compact(CharVector kx, TernaryTree map, char p)
int
find(char[] key, int start)
Find key.int
find(java.lang.String key)
Find key.protected void
init()
initializevoid
insert(char[] key, int start, char val)
Insert key.private char
insert(TernaryTree.TreeInsertionParams params)
The actual insertion function, recursive version.void
insert(java.lang.String key, char val)
Branches are initially compressed, needing one node per key plus the size of the string key.protected void
insertBalanced(java.lang.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.private char
insertIntoExistingBranch(TernaryTree.TreeInsertionParams params)
private java.lang.Character
insertNewBranchIfNeeded(TernaryTree.TreeInsertionParams params)
java.util.Enumeration
keys()
boolean
knows(java.lang.String key)
private void
redimNodeArrays(int newsize)
int
size()
static int
strcmp(char[] a, int startA, char[] b, int startB)
Compares 2 null terminated char arraysstatic int
strcmp(java.lang.String str, char[] a, int start)
Compares a string with null terminated char arraystatic 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).
-
-
-
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
-
kv
protected 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
-
-
Constructor Detail
-
TernaryTree
TernaryTree()
default constructor
-
TernaryTree
TernaryTree(TernaryTree tt)
-
-
Method Detail
-
init
protected void init()
initialize
-
insert
public void insert(java.lang.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 keyval
- a value
-
insert
public void insert(char[] key, int start, char val)
Insert key.- Parameters:
key
- the keystart
- offset into key arrayval
- a value
-
insertNewBranchIfNeeded
private java.lang.Character insertNewBranchIfNeeded(TernaryTree.TreeInsertionParams params)
-
insertIntoExistingBranch
private char insertIntoExistingBranch(TernaryTree.TreeInsertionParams params)
-
insert
private char insert(TernaryTree.TreeInsertionParams params)
The actual insertion function, recursive version. PLEASE NOTE that the implementation has been adapted to consume less stack memory
-
strcmp
public static int strcmp(char[] a, int startA, char[] b, int startB)
Compares 2 null terminated char arrays- Parameters:
a
- a character arraystartA
- an index into character arrayb
- a character arraystartB
- an index into character array- Returns:
- an integer
-
strcmp
public static int strcmp(java.lang.String str, char[] a, int start)
Compares a string with null terminated char array- Parameters:
str
- a stringa
- a character arraystart
- 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 arraydi
- an index into character arraysrc
- a character arraysi
- an index into character array
-
strlen
public static int strlen(char[] a, int start)
- Parameters:
a
- a character arraystart
- 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(java.lang.String key)
Find key.- Parameters:
key
- the key- Returns:
- result
-
find
public int find(char[] key, int start)
Find key.- Parameters:
key
- the keystart
- offset into key array- Returns:
- result
-
knows
public boolean knows(java.lang.String key)
- Parameters:
key
- a key- Returns:
- trye if key present
-
redimNodeArrays
private void redimNodeArrays(int newsize)
-
size
public int size()
- Returns:
- length
-
insertBalanced
protected void insertBalanced(java.lang.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 keysv
- array of valuesoffset
- where to insertn
- 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!).
-
compact
private void compact(CharVector kx, TernaryTree map, char p)
-
keys
public java.util.Enumeration keys()
- Returns:
- the keys
-
-