| java.lang.Object
 com.lowagie.text.pdf.hyphenation.TernaryTree
All known Subclasses: com.lowagie.text.pdf.hyphenation.HyphenationTree,
| TernaryTree | | public class TernaryTree implements Cloneable,Serializable(Code) | | 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 requirenments 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.
author:
cav@uniscope.co.jp |
| Inner Class :public class Iterator implements Enumeration | |
| Field Summary | |
| final protected static int | BLOCK_SIZE
| | protected char[] | eq
Pointer to equal branch and to data when this node is a string terminator. | | protected char | freenode
| | protected 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
| | protected char[] | lo
| | protected char | root
| | protected char[] | sc
The character stored in this node: splitchar. |
| Method Summary | |
| public void | balance()
| | public Object | clone()
| | public int | find(String key)
| | public int | find(char[] key, int start)
| | protected void | init()
| | public void | insert(String key, char val)
Branches are initially compressed, needing
one node per key plus the size of the string
key. | | public void | insert(char[] key, int start, char val)
| | 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. | | public Enumeration | keys()
| | public boolean | knows(String key)
| | public void | printStats()
| | public int | size()
| | public static int | strcmp(char[] a, int startA, char[] b, int startB)
| | public static int | strcmp(String str, char[] a, int start)
| | public static void | strcpy(char[] dst, int di, char[] src, int si)
| | public static int | strlen(char[] a, int start)
| | public static int | strlen(char[] a)
| | public void | trimToSize()
Each node stores a character (splitchar) which is part of
some key(s). |
| BLOCK_SIZE | | final protected static int BLOCK_SIZE(Code) | | |
| eq | | protected char[] eq(Code) | | Pointer to equal branch and to data when this node is a string terminator.
|
| freenode | | protected char freenode(Code) | | |
| hi | | protected char[] hi(Code) | | Pointer to high branch.
|
| kv | | protected CharVector kv(Code) | | This vector holds the trailing of the keys when the branch is compressed.
|
| length | | protected int length(Code) | | |
| lo | | protected char[] lo(Code) | | 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!
|
| sc | | protected char[] sc(Code) | | 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.
|
| TernaryTree | | TernaryTree()(Code) | | |
| balance | | public void balance()(Code) | | Balance the tree for best search performance
|
| find | | public int find(char[] key, int start)(Code) | | |
| init | | protected void init()(Code) | | |
| insert | | public void insert(String key, char val)(Code) | | 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.
|
| insert | | public void insert(char[] key, int start, char val)(Code) | | |
| insertBalanced | | protected void insertBalanced(String[] k, char[] v, int offset, int n)(Code) | | 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.
|
| printStats | | public void printStats()(Code) | | |
| strcmp | | public static int strcmp(char[] a, int startA, char[] b, int startB)(Code) | | Compares 2 null terminated char arrays
|
| strcmp | | public static int strcmp(String str, char[] a, int start)(Code) | | Compares a string with null terminated char array
|
| strcpy | | public static void strcpy(char[] dst, int di, char[] src, int si)(Code) | | |
| strlen | | public static int strlen(char[] a, int start)(Code) | | |
| strlen | | public static int strlen(char[] a)(Code) | | |
| trimToSize | | public void trimToSize()(Code) | | 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!).
|
|
|