content: /*
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to You under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License.  You may obtain a copy of the License at
   * 
   *      http://www.apache.org/licenses/LICENSE-2.0
   * 
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package org.apache.lucene.analysis.compound.hyphenation;
  
  import java.util.Enumeration;
  import java.util.Stack;
  import java.io.Serializable;
  
  /**
   * <h2>Ternary Search Tree.</h2>
   * 
   * <p>
   * 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).
   * </p>
   * 
   * <p>
   * 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.
   * </p>
   * 
   * <p>
   * 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.
   * </p>
   * 
   * This class has been taken from the Apache FOP project (http://xmlgraphics.apache.org/fop/). They have been slightly modified. 
   */
  
  public class TernaryTree implements Cloneable, Serializable {
  
    /**
     * 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.
     */
  
    /**
     * 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;
  
    /**
     * Pointer to high branch.
     */
    protected char[] hi;
  
    /**
     * Pointer to equal branch and to data when this node is a string terminator.
     */
    protected char[] eq;
  
    /**
     * <P>
     * The character stored in this node: splitchar. Two special values are
     * reserved:
     * </P>
     * <ul>
     * <li>0x0000 as string terminator</li>
     * <li>0xFFFF to indicate that the branch starting at this node is compressed</li>
     * </ul>
     * <p>
     * This shouldn't be a problem if we give the usual semantics to strings since
     * 0xFFFF is guaranteed not to be an Unicode character.
     * </p>
     */
    protected char[] sc;
  
    /**
     * This vector holds the trailing of the keys when the branch is compressed.
     */
    protected CharVector kv;
  
    protected char root;
  
    protected char freenode;
  
    protected int length; // number of items in tree
  
    protected static final int BLOCK_SIZE = 2048; // allocation size for arrays
  
    TernaryTree() {
      init();
    }
  
    protected void init() {
      root = 0;
      freenode = 1;
      length = 0;
      lo = new char[BLOCK_SIZE];
      hi = new char[BLOCK_SIZE];
      eq = new char[BLOCK_SIZE];
      sc = new char[BLOCK_SIZE];
      kv = new CharVector();
    }
  
    /**
     * 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.
     */
    public void insert(String key, char val) {
      // make sure we have enough room in the arrays
      int len = key.length() + 1; // maximum number of nodes that may be generated
      if (freenode + len > eq.length) {
        redimNodeArrays(eq.length + BLOCK_SIZE);
      }
      char strkey[] = new char[len--];
      key.getChars(0, len, strkey, 0);
      strkey[len] = 0;
      root = insert(root, strkey, 0, val);
    }
  
    public void insert(char[] key, int start, char val) {
      int len = strlen(key) + 1;
      if (freenode + len > eq.length) {
        redimNodeArrays(eq.length + BLOCK_SIZE);
      }
      root = insert(root, key, start, val);
    }
  
    /**
     * The actual insertion function, recursive version.
     */
    private char insert(char p, char[] key, int start, char val) {
      int len = strlen(key, start);
      if (p == 0) {
        // this means there is no branch, this node will start a new branch.
        // Instead of doing that, we store the key somewhere else and create
        // only one node with a pointer to the key
        p = freenode++;
        eq[p] = val; // holds data
        length++;
        hi[p] = 0;
        if (len > 0) {
          sc[p] = 0xFFFF; // indicates branch is compressed
          lo[p] = (char) kv.alloc(len + 1); // use 'lo' to hold pointer to key
          strcpy(kv.getArray(), lo[p], key, start);
        } else {
          sc[p] = 0;
          lo[p] = 0;
        }
        return p;
      }
  
      if (sc[p] == 0xFFFF) {
        // branch is compressed: need to decompress
        // this will generate garbage in the external key array
        // but we can do some garbage collection later
        char pp = freenode++;
        lo[pp] = lo[p]; // previous pointer to key
        eq[pp] = eq[p]; // previous pointer to data
        lo[p] = 0;
        if (len > 0) {
          sc[p] = kv.get(lo[pp]);
          eq[p] = pp;
          lo[pp]++;
          if (kv.get(lo[pp]) == 0) {
            // key completly decompressed leaving garbage in key array
            lo[pp] = 0;
            sc[pp] = 0;
            hi[pp] = 0;
          } else {
            // we only got first char of key, rest is still there
            sc[pp] = 0xFFFF;
          }
        } else {
          // In this case we can save a node by swapping the new node
          // with the compressed node
          sc[pp] = 0xFFFF;
          hi[p] = pp;
          sc[p] = 0;
          eq[p] = val;
          length++;
          return p;
        }
      }
      char s = key[start];
      if (s < sc[p]) {
        lo[p] = insert(lo[p], key, start, val);
      } else if (s == sc[p]) {
        if (s != 0) {
          eq[p] = insert(eq[p], key, start + 1, val);
        } else {
          // key already in tree, overwrite data
          eq[p] = val;
        }
      } else {
        hi[p] = insert(hi[p], key, start, val);
      }
      return p;
    }
  
    /**
     * Compares 2 null terminated char arrays
     */
    public static int strcmp(char[] a, int startA, char[] b, int startB) {
      for (; a[startA] == b[startB]; startA++, startB++) {
        if (a[startA] == 0) {
          return 0;
        }
      }
      return a[startA] - b[startB];
    }
  
    /**
     * Compares a string with null terminated char array
     */
    public static int strcmp(String str, char[] a, int start) {
      int i, d, len = str.length();
      for (i = 0; i < len; i++) {
        d = (int) str.charAt(i) - a[start + i];
        if (d != 0) {
          return d;
        }
        if (a[start + i] == 0) {
          return d;
        }
      }
      if (a[start + i] != 0) {
        return -a[start + i];
      }
      return 0;
  
    }
  
    public static void strcpy(char[] dst, int di, char[] src, int si) {
      while (src[si] != 0) {
        dst[di++] = src[si++];
      }
      dst[di] = 0;
    }
  
    public static int strlen(char[] a, int start) {
      int len = 0;
      for (int i = start; i < a.length && a[i] != 0; i++) {
        len++;
      }
      return len;
    }
  
    public static int strlen(char[] a) {
      return strlen(a, 0);
    }
  
    public int find(String key) {
      int len = key.length();
      char strkey[] = new char[len + 1];
      key.getChars(0, len, strkey, 0);
      strkey[len] = 0;
  
      return find(strkey, 0);
    }
  
    public int find(char[] key, int start) {
      int d;
      char p = root;
      int i = start;
      char c;
  
      while (p != 0) {
        if (sc[p] == 0xFFFF) {
          if (strcmp(key, i, kv.getArray(), lo[p]) == 0) {
            return eq[p];
          } else {
            return -1;
          }
        }
        c = key[i];
        d = c - sc[p];
        if (d == 0) {
          if (c == 0) {
            return eq[p];
          }
          i++;
          p = eq[p];
        } else if (d < 0) {
          p = lo[p];
        } else {
          p = hi[p];
        }
      }
      return -1;
    }
  
    public boolean knows(String key) {
      return (find(key) >= 0);
    }
  
    // redimension the arrays
    private void redimNodeArrays(int newsize) {
      int len = newsize < lo.length ? newsize : lo.length;
      char[] na = new char[newsize];
      System.arraycopy(lo, 0, na, 0, len);
      lo = na;
      na = new char[newsize];
      System.arraycopy(hi, 0, na, 0, len);
      hi = na;
      na = new char[newsize];
      System.arraycopy(eq, 0, na, 0, len);
      eq = na;
      na = new char[newsize];
      System.arraycopy(sc, 0, na, 0, len);
      sc = na;
    }
  
    public int size() {
      return length;
    }
  
    @Override
    public Object clone() {
      TernaryTree t = new TernaryTree();
      t.lo = this.lo.clone();
      t.hi = this.hi.clone();
      t.eq = this.eq.clone();
      t.sc = this.sc.clone();
      t.kv = (CharVector) this.kv.clone();
      t.root = this.root;
      t.freenode = this.freenode;
      t.length = this.length;
  
      return t;
    }
  
    /**
     * 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.
     */
    protected void insertBalanced(String[] k, char[] v, int offset, int n) {
      int m;
      if (n < 1) {
        return;
      }
      m = n >> 1;
  
      insert(k[m + offset], v[m + offset]);
      insertBalanced(k, v, offset, m);
  
      insertBalanced(k, v, offset + m + 1, n - m - 1);
    }
  
    /**
     * Balance the tree for best search performance
     */
    public void balance() {
      // System.out.print("Before root splitchar = ");
      // System.out.println(sc[root]);
  
      int i = 0, n = length;
      String[] k = new String[n];
      char[] v = new char[n];
      Iterator iter = new Iterator();
      while (iter.hasMoreElements()) {
        v[i] = iter.getValue();
        k[i++] = iter.nextElement();
      }
      init();
      insertBalanced(k, v, 0, n);
  
      // With uniform letter distribution sc[root] should be around 'm'
      // System.out.print("After root splitchar = ");
      // System.out.println(sc[root]);
    }
  
    /**
     * 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!).
     * 
     */
    public void trimToSize() {
      // first balance the tree for best performance
      balance();
  
      // redimension the node arrays
      redimNodeArrays(freenode);
  
      // ok, compact kv array
      CharVector kx = new CharVector();
      kx.alloc(1);
      TernaryTree map = new TernaryTree();
      compact(kx, map, root);
      kv = kx;
      kv.trimToSize();
    }
  
    private void compact(CharVector kx, TernaryTree map, char p) {
      int k;
      if (p == 0) {
        return;
      }
      if (sc[p] == 0xFFFF) {
        k = map.find(kv.getArray(), lo[p]);
        if (k < 0) {
          k = kx.alloc(strlen(kv.getArray(), lo[p]) + 1);
          strcpy(kx.getArray(), k, kv.getArray(), lo[p]);
          map.insert(kx.getArray(), k, (char) k);
        }
        lo[p] = (char) k;
      } else {
        compact(kx, map, lo[p]);
        if (sc[p] != 0) {
          compact(kx, map, eq[p]);
        }
        compact(kx, map, hi[p]);
      }
    }
  
    public Enumeration<String> keys() {
      return new Iterator();
    }
  
    public class Iterator implements Enumeration<String> {
  
      /**
       * current node index
       */
      int cur;
  
      /**
       * current key
       */
      String curkey;
  
      private class Item implements Cloneable {
        char parent;
  
        char child;
  
        public Item() {
          parent = 0;
          child = 0;
        }
  
        public Item(char p, char c) {
          parent = p;
          child = c;
        }
  
        @Override
        public Object clone() {
          return new Item(parent, child);
        }
  
      }
  
      /**
       * Node stack
       */
      Stack<Item> ns;
  
      /**
       * key stack implemented with a StringBuilder
       */
      StringBuilder ks;
  
      public Iterator() {
        cur = -1;
        ns = new Stack<Item>();
        ks = new StringBuilder();
        rewind();
      }
  
      public void rewind() {
        ns.removeAllElements();
        ks.setLength(0);
        cur = root;
        run();
      }
  
      public String nextElement() {
        String res = new String(curkey);
        cur = up();
        run();
        return res;
      }
  
      public char getValue() {
        if (cur >= 0) {
          return eq[cur];
        }
        return 0;
      }
  
      public boolean hasMoreElements() {
        return (cur != -1);
      }
  
      /**
       * traverse upwards
       */
      private int up() {
        Item i = new Item();
        int res = 0;
  
        if (ns.empty()) {
          return -1;
        }
  
        if (cur != 0 && sc[cur] == 0) {
          return lo[cur];
        }
  
        boolean climb = true;
  
        while (climb) {
          i = ns.pop();
          i.child++;
          switch (i.child) {
            case 1:
              if (sc[i.parent] != 0) {
                res = eq[i.parent];
                ns.push((Item) i.clone());
                ks.append(sc[i.parent]);
              } else {
                i.child++;
                ns.push((Item) i.clone());
                res = hi[i.parent];
              }
              climb = false;
              break;
  
            case 2:
              res = hi[i.parent];
              ns.push((Item) i.clone());
              if (ks.length() > 0) {
                ks.setLength(ks.length() - 1); // pop
              }
              climb = false;
              break;
  
            default:
              if (ns.empty()) {
                return -1;
              }
              climb = true;
              break;
          }
        }
        return res;
      }
  
      /**
       * traverse the tree to find next key
       */
      private int run() {
        if (cur == -1) {
          return -1;
        }
  
        boolean leaf = false;
        while (true) {
          // first go down on low branch until leaf or compressed branch
          while (cur != 0) {
            if (sc[cur] == 0xFFFF) {
              leaf = true;
              break;
            }
            ns.push(new Item((char) cur, '\u0000'));
            if (sc[cur] == 0) {
              leaf = true;
              break;
            }
            cur = lo[cur];
          }
          if (leaf) {
            break;
          }
          // nothing found, go up one node and try again
          cur = up();
          if (cur == -1) {
            return -1;
          }
        }
        // The current node should be a data node and
        // the key should be in the key stack (at least partially)
        StringBuilder buf = new StringBuilder(ks.toString());
        if (sc[cur] == 0xFFFF) {
          int p = lo[cur];
          while (kv.get(p) != 0) {
            buf.append(kv.get(p++));
          }
        }
        curkey = buf.toString();
        return 0;
      }
  
    }
  
    public void printStats() {
      System.out.println("Number of keys = " + Integer.toString(length));
      System.out.println("Node count = " + Integer.toString(freenode));
      // System.out.println("Array length = " + Integer.toString(eq.length));
      System.out.println("Key Array length = " + Integer.toString(kv.length()));
  
      /*
       * for(int i=0; i<kv.length(); i++) if ( kv.get(i) != 0 )
       * System.out.print(kv.get(i)); else System.out.println("");
       * System.out.println("Keys:"); for(Enumeration enum = keys();
       * enum.hasMoreElements(); ) System.out.println(enum.nextElement());
       */
  
    }
  
    public static void main(String[] args) throws Exception {
      TernaryTree tt = new TernaryTree();
      tt.insert("Carlos", 'C');
      tt.insert("Car", 'r');
      tt.insert("palos", 'l');
      tt.insert("pa", 'p');
      tt.trimToSize();
      System.out.println((char) tt.find("Car"));
      System.out.println((char) tt.find("Carlos"));
      System.out.println((char) tt.find("alto"));
      tt.printStats();
    }
  
  }
  