TernarySearchTree6public 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.Object | get(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.Object | insert(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 int | nodeCount()
return (nextNode-INITIAL_NODE+1)/NODE_SIZE;
| | public java.lang.Object | put(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 void | release()
nodes = null;
objects = null;
| | public java.lang.Object | search(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;
|
|
