+++ /dev/null
-/*
- * 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();
- }
-
-}
fnp / pylucene.git / blobdiff