Class TernaryTree

Namespace

iText.Layout.Hyphenation

Assembly

itext.layout.dll

Ternary Search Tree.

public class TernaryTree

Inheritance

object

TernaryTree

Derived

HyphenationTree

Inherited Members

object.GetType()

object.MemberwiseClone()

object.ToString()

object.Equals(object)

object.Equals(object, object)

object.ReferenceEquals(object, object)

object.GetHashCode()

Remarks

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).

Fields

BLOCK_SIZE

allocation size for arrays

protected const int BLOCK_SIZE = 2048

Field Value

int

eq

Pointer to equal branch and to data when this node is a string terminator.

protected char[] eq

Field Value

char[]

freenode

free node

protected char freenode

Field Value

char

hi

Pointer to high branch.

protected char[] hi

Field Value

char[]

kv

This vector holds the trailing of the keys when the branch is compressed.

protected CharVector kv

Field Value

CharVector

length

number of items in tree

protected int length

Field Value

int

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[] lo

Field Value

char[]

root

root

protected char root

Field Value

char

sc

The character stored in this node: splitchar.

protected char[] sc

Field Value

char[]

Remarks

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.

Methods

Balance()

Balance the tree for best search performance

public virtual void Balance()

Find(char[], int)

Find key.

public virtual int Find(char[] key, int start)

Parameters

key char[]

the key

start int

offset into key array

Returns

int

result

Find(string)

Find key.

public virtual int Find(string key)

Parameters

key string

the key

Returns

int

result

Init()

initialize

protected virtual void Init()

Insert(char[], int, char)

Insert key.

public virtual void Insert(char[] key, int start, char val)

Parameters

key char[]

the key

start int

offset into key array

val char

a value

Insert(string, char)

Branches are initially compressed, needing one node per key plus the size of the string key.

public virtual void Insert(string key, char val)

Parameters

key string

the key

val char

a value

Remarks

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.

InsertBalanced(string[], char[], int, int)

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.

protected virtual void InsertBalanced(string[] k, char[] v, int offset, int n)

Parameters

k string[]

array of keys

v char[]

array of values

offset int

where to insert

n int

count to insert

Remarks

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.

Keys()

public virtual IEnumerator Keys()

Returns

IEnumerator

the keys

Knows(string)

public virtual bool Knows(string key)

Parameters

key string

a key

Returns

bool

trye if key present

Size()

public virtual int Size()

Returns

int

length

Strcmp(char[], int, char[], int)

Compares 2 null terminated char arrays

public static int Strcmp(char[] a, int startA, char[] b, int startB)

Parameters

a char[]

a character array

startA int

an index into character array

b char[]

a character array

startB int

an index into character array

Returns

int

an integer

Strcmp(string, char[], int)

Compares a string with null terminated char array

public static int Strcmp(string str, char[] a, int start)

Parameters

str string

a string

a char[]

a character array

start int

an index into character array

Returns

int

an integer

Strcpy(char[], int, char[], int)

public static void Strcpy(char[] dst, int di, char[] src, int si)

Parameters

dst char[]

a character array

di int

an index into character array

src char[]

a character array

si int

an index into character array

Strlen(char[])

public static int Strlen(char[] a)

Parameters

a char[]

a character array

Returns

int

an integer

Strlen(char[], int)

public static int Strlen(char[] a, int start)

Parameters

a char[]

a character array

start int

an index into character array

Returns

int

an integer

TrimToSize()

Each node stores a character (splitchar) which is part of some key(s).

public virtual void TrimToSize()

Remarks

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!).