Class TernaryTree

java.lang.Object
com.lowagie.text.pdf.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 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 sacrifice '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.

See Also:
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    class 
     
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected static final int
     
    protected char[]
    Pointer to equal branch and to data when this node is a string terminator.
    protected char
     
    protected char[]
    Pointer to high branch.
    protected CharVector
    This vector holds the trailing of the keys when the branch is compressed.
    protected int
     
    protected char[]
    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
     
    protected char[]
    The character stored in this node: splitchar.
    private static final long
    We use 4 arrays to represent a node.
  • Constructor Summary

    Constructors
    Constructor
    Description
     
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    Balance the tree for best search performance
     
    private void
    compact(CharVector kx, TernaryTree map, char p)
     
    int
    find(char[] key, int start)
     
    int
    find(String key)
     
    protected void
     
    void
    insert(char[] key, int start, char val)
     
    private char
    insert(char p, char[] key, int start, char val)
    The actual insertion function, recursive version.
    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.
     
    boolean
     
    void
     
    private void
    redimNodeArrays(int newsize)
     
    int
     
    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
    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 Details

    • BLOCK_SIZE

      protected static final int BLOCK_SIZE
      See Also:
    • serialVersionUID

      private static final long serialVersionUID
      We use 4 arrays to represent a node. I guess I should have created a proper node class, but somehow Knuth's pascal code made me forget we now have a portable language with virtual memory management and automatic garbage collection! And now is kind of late, furthermore, if it ain't broken, don't fix it.
      See Also:
    • 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 guaranteed not to be an Unicode character.

    • kv

      protected CharVector kv
      This vector holds the trailing of the keys when the branch is compressed.
    • root

      protected char root
    • freenode

      protected char freenode
    • length

      protected int length
  • Constructor Details

    • TernaryTree

      TernaryTree()
  • Method Details

    • strcmp

      public static int strcmp(char[] a, int startA, char[] b, int startB)
      Compares 2 null terminated char arrays
      Parameters:
      a - The first char array to compare - must end by null
      startA - The index to start comparing for a
      b - The second char array to compare - must end by null
      startB - The index to start comparing for b
      Returns:
      0 if equals, otherwise the difference of the first different characters
    • strcmp

      public static int strcmp(String str, char[] a, int start)
      Compares a string with null terminated char array
      Parameters:
      str - The String to compare
      a - The char array to compare - last index has null
      start - The index to start comparing from
      Returns:
      0 if equals, otherwise the difference of the first different characters
    • strcpy

      public static void strcpy(char[] dst, int di, char[] src, int si)
    • strlen

      public static int strlen(char[] a, int start)
    • strlen

      public static int strlen(char[] a)
    • init

      protected void init()
    • 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 to insert
      val - The char to insert
    • insert

      public void insert(char[] key, int start, char val)
    • insert

      private char insert(char p, char[] key, int start, char val)
      The actual insertion function, recursive version.
    • find

      public int find(String key)
    • find

      public int find(char[] key, int start)
    • knows

      public boolean knows(String key)
    • redimNodeArrays

      private void redimNodeArrays(int newsize)
    • size

      public int size()
    • clone

      public Object clone()
      Overrides:
      clone in class Object
    • 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 - The array of keya - assumed to be sorted in ascending order
      v - The character to insert first
      offset - The offset
      n - n
    • 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 Enumeration keys()
    • printStats

      public void printStats()