V
- the Entry typepublic class ArrayTernaryTrie<V> extends AbstractTrie<V>
A Ternary Trie String lookup data structure.
This Trie is of a fixed size and cannot grow (which can be a good thing with regards to DOS when used as a cache).
The Trie is stored in 3 arrays:
The lookup of a value will iterate through the _tree array matching characters. If the equal tree branch is followed, then the _key array is looked up to see if this is a complete match. If a match is found then the _value array is looked up to return the matching value.
This Trie may be instantiated either as case sensitive or insensitive.
This Trie is not Threadsafe and contains no mutual exclusion or deliberate memory barriers. It is intended for an ArrayTrie to be built by a single thread and then used concurrently by multiple threads and not mutated during that access. If concurrent mutations of the Trie is required external locks need to be applied.
Modifier and Type | Class and Description |
---|---|
static class |
ArrayTernaryTrie.Growing<V> |
Modifier and Type | Field and Description |
---|---|
private java.lang.String[] |
_key
The key (if any) for a Trie row.
|
private char |
_rows
The number of rows allocated
|
private char[] |
_tree
The Trie rows in a single array which allows a lookup of row,character
to the next row in the Trie.
|
private V[] |
_value
The value (if any) for a Trie row.
|
private static int |
EQ |
private static int |
HI |
private static int |
LO |
private static int |
ROW_SIZE
The Size of a Trie row is the char, and the low, equal and high
child pointers
|
_caseInsensitive
Constructor and Description |
---|
ArrayTernaryTrie()
Create a case insensitive Trie of default capacity.
|
ArrayTernaryTrie(ArrayTernaryTrie<V> trie,
double factor)
Copy Trie and change capacity by a factor
|
ArrayTernaryTrie(boolean insensitive)
Create a Trie of default capacity
|
ArrayTernaryTrie(boolean insensitive,
int capacity)
Create a Trie
|
ArrayTernaryTrie(int capacity)
Create a case insensitive Trie
|
Modifier and Type | Method and Description |
---|---|
void |
clear() |
void |
dump() |
java.util.Set<java.util.Map.Entry<java.lang.String,V>> |
entrySet() |
V |
get(java.nio.ByteBuffer b,
int offset,
int len)
Get an exact match from a segment of a ByteBuufer as key
|
V |
get(java.lang.String s,
int offset,
int len)
Get an exact match from a String key
|
V |
getBest(java.nio.ByteBuffer b,
int offset,
int len)
Get the best match from key in a byte buffer.
|
private V |
getBest(int t,
byte[] b,
int offset,
int len) |
private V |
getBest(int t,
java.nio.ByteBuffer b,
int offset,
int len) |
private V |
getBest(int t,
java.lang.String s,
int offset,
int len) |
V |
getBest(java.lang.String s)
Get the best match from key in a String.
|
V |
getBest(java.lang.String s,
int offset,
int length)
Get the best match from key in a String.
|
static int |
hilo(int diff) |
boolean |
isEmpty() |
boolean |
isFull() |
java.util.Set<java.lang.String> |
keySet() |
boolean |
put(java.lang.String s,
V v)
Put an entry into the Trie
|
int |
size() |
java.lang.String |
toString() |
get, get, getBest, isCaseInsensitive, put, remove
private static int LO
private static int EQ
private static int HI
private static final int ROW_SIZE
private final char[] _tree
private final java.lang.String[] _key
private final V[] _value
private char _rows
public ArrayTernaryTrie()
public ArrayTernaryTrie(boolean insensitive)
insensitive
- true if the Trie is insensitive to the case of the key.public ArrayTernaryTrie(int capacity)
capacity
- The capacity of the Trie, which is in the worst case
is the total number of characters of all keys stored in the Trie.
The capacity needed is dependent of the shared prefixes of the keys.
For example, a capacity of 6 nodes is required to store keys "foo"
and "bar", but a capacity of only 4 is required to
store "bar" and "bat".public ArrayTernaryTrie(boolean insensitive, int capacity)
insensitive
- true if the Trie is insensitive to the case of the key.capacity
- The capacity of the Trie, which is in the worst case
is the total number of characters of all keys stored in the Trie.
The capacity needed is dependent of the shared prefixes of the keys.
For example, a capacity of 6 nodes is required to store keys "foo"
and "bar", but a capacity of only 4 is required to
store "bar" and "bat".public ArrayTernaryTrie(ArrayTernaryTrie<V> trie, double factor)
trie
- the trie to copy fromfactor
- the factor to grow the capacity bypublic void clear()
public boolean put(java.lang.String s, V v)
Trie
s
- The key for the entryv
- The value of the entrypublic V get(java.lang.String s, int offset, int len)
Trie
s
- The keyoffset
- The offset within the string of the keylen
- the length of the keypublic V get(java.nio.ByteBuffer b, int offset, int len)
Trie
b
- The bufferoffset
- The offset within the buffer of the keylen
- the length of the keypublic V getBest(java.lang.String s)
Trie
public V getBest(java.lang.String s, int offset, int length)
Trie
s
- The stringoffset
- The offset within the string of the keylength
- the length of the keyprivate V getBest(int t, java.lang.String s, int offset, int len)
public V getBest(java.nio.ByteBuffer b, int offset, int len)
Trie
b
- The bufferoffset
- The offset within the buffer of the keylen
- the length of the keyprivate V getBest(int t, byte[] b, int offset, int len)
private V getBest(int t, java.nio.ByteBuffer b, int offset, int len)
public java.lang.String toString()
toString
in class java.lang.Object
public java.util.Set<java.lang.String> keySet()
public int size()
public boolean isEmpty()
public java.util.Set<java.util.Map.Entry<java.lang.String,V>> entrySet()
public boolean isFull()
public static int hilo(int diff)
public void dump()