FileDocCategorySizeDatePackage
TernarySearchTree6.javaAPI DocExample4744Fri Dec 18 12:23:32 GMT 1998tuning.struct

TernarySearchTree6

public class TernarySearchTree6 extends Object

Fields Summary
static final int
LOW_OFFSET
static final int
HIGH_OFFSET
static final int
EQUAL_OFFSET
static final int
VALUE_OFFSET
static final int
NODE_SIZE
static final int
INITIAL_TRIE_NODE
static final int
INITIAL_NODE
static final int
TRIE_CHAR_SIZE
char[]
buff
int[]
nodes
Object[]
objects
int
nextNode
int
nextObject
int
initial
Object[]
trie1Objects
int[]
trie2
Object[]
trie2Objects
Constructors Summary
public TernarySearchTree6()

    this(200000);
  
public TernarySearchTree6(int size)

    trie1Objects = new Object[TRIE_CHAR_SIZE];
    trie2 = new int[TRIE_CHAR_SIZE][TRIE_CHAR_SIZE];
    trie2Objects = new Object[TRIE_CHAR_SIZE][TRIE_CHAR_SIZE];
    nodes = new int[NODE_SIZE*size+1];
    objects = new Object[size];
  
Methods Summary
public java.lang.Objectget(java.lang.String key)

    int len = key.length();
    key.getChars(0, len, buff, 0);
    int first = buff[0];
    int second = buff[1];
    if (len == 1 && (first < TRIE_CHAR_SIZE))
    {
      return trie1Objects[first];
    }
    else if (len == 2 && (first < TRIE_CHAR_SIZE) && (second < TRIE_CHAR_SIZE))
    {
      return trie2Objects[first][second];
    }
    else if ((first < TRIE_CHAR_SIZE) && (second < TRIE_CHAR_SIZE))
    {
      int nodep = trie2[first][second];
      if (nodep == 0)
      {
        return null;
      }
      return search(buff, 2, len-1, nodep);
    }
    else
    {
      //Use node[0] as a flag to determine if enetered here
      if (nodes[0] == 0)
      {
        return null;
      }
      return search(buff, 0, len-1, INITIAL_NODE);
    }
  
public java.lang.Objectinsert(char[] str, int strIdx, int strMaxIdx, java.lang.Object value, int p)

//    int p = INITIAL_NODE;
    int c = str[strIdx];
    int cdiff;
    Object old;
    for(;;)
    {
      if ( (cdiff = c - nodes[p]) < 0)
      {
	if (nodes[p+LOW_OFFSET] == 0)
	{
	  nodes[p+LOW_OFFSET] = nextNode;
	  nodes[nextNode] = c;
	  nextNode+=NODE_SIZE;
	}
        p = nodes[p+LOW_OFFSET];
      }
      else if (cdiff == 0)
      {
	if (strIdx == strMaxIdx)
	{
	  if (nodes[p+VALUE_OFFSET] == 0)
	  {
	    nodes[p+VALUE_OFFSET] = nextObject;
	    nextObject++;
	  }
	  old = objects[nodes[p+VALUE_OFFSET]];
	  objects[nodes[p+VALUE_OFFSET]] = value;
	  return old;
	}
        else
        {
          strIdx++;
	  c=str[strIdx];
	  if (nodes[p+EQUAL_OFFSET] == 0)
	  {
	    nodes[p+EQUAL_OFFSET] = nextNode;
	    nodes[nextNode] = c;
	    nextNode+=NODE_SIZE;
	  }
          p = nodes[p+EQUAL_OFFSET];
        }
      }
      else
      {
	if (nodes[p+HIGH_OFFSET] == 0)
	{
	  nodes[p+HIGH_OFFSET] = nextNode;
	  nodes[nextNode] = c;
	  nextNode+=NODE_SIZE;
	}
        p = nodes[p+HIGH_OFFSET];
      }
    }
  
public intnodeCount()


      return (nextNode-INITIAL_NODE+1)/NODE_SIZE;
public java.lang.Objectput(java.lang.String key, java.lang.Object value)

    int len = key.length();
    key.getChars(0, len, buff, 0);
    int first = buff[0];
    int second = buff[1];
    if (len == 1 && (first < TRIE_CHAR_SIZE))
    {
      Object old = trie1Objects[first];
      trie1Objects[first] = value;
      return old;
    }
    else if (len == 2 && (first < TRIE_CHAR_SIZE) && (second < TRIE_CHAR_SIZE))
    {
      Object old = trie2Objects[first][second];
      trie2Objects[first][second] = value;
      return old;
    }
    else if ((first < TRIE_CHAR_SIZE) && (second < TRIE_CHAR_SIZE))
    {
      int nodep = trie2[first][second];
      if (nodep == 0)
      {
        nodep = trie2[first][second] = nextNode;
        nodes[nextNode] = buff[2];
        nextNode+=NODE_SIZE;
      }
      return insert(buff, 2, len-1, value, nodep);
    }
    else
    {
      //Use node[0] as a flag to determine if enetered here
      if (nodes[0] == 0)
      {
        nodes[0] = 1;
        nodes[INITIAL_NODE] = first;
      }
      return insert(buff, 0, len-1, value, INITIAL_NODE);
    }
  
public voidrelease()

    nodes = null;
    objects = null;
  
public java.lang.Objectsearch(char[] str, int strIdx, int strMaxIdx, int p)

//    int p = INITIAL_NODE;
    int c;
    while (p != 0)
    {
      if ( (c = str[strIdx]) < nodes[p])
        p = nodes[p+LOW_OFFSET];
      else if (c == nodes[p])
      {
        if (strIdx == strMaxIdx)
	  return objects[nodes[p+VALUE_OFFSET]];
        else
        {
          strIdx++;
	  p = nodes[p+EQUAL_OFFSET];
        }
      }
      else
	p = nodes[p+HIGH_OFFSET];
    }
    return null;