V
- the entry typepublic class ArrayTrie<V> extends AbstractTrie<V>
A Trie String lookup data structure using a fixed size array.
This implementation is always case insensitive and is optimal for a small number of fixed strings with few special characters. The Trie is stored in an array of lookup tables, each indexed by the next character of the key. Frequently used characters are directly indexed in each lookup table, whilst infrequently used characters must use a big character table.
This Trie is very space efficient if the key characters are from ' ', '+', '-', ':', ';', '.', 'A' to 'Z' or 'a' to 'z'. Other ISO-8859-1 characters can be used by the key, but less space efficiently.
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 | Field and Description |
---|---|
private static int[] |
__lookup
The index lookup table, this maps a character as a byte
(ISO-8859-1 or UTF8) to an index within a Trie row
|
private char[][] |
_bigIndex
A big index for each row.
|
private java.lang.String[] |
_key
The key (if any) for a Trie row.
|
private char[] |
_rowIndex
The Trie rows in a single array which allows a lookup of row,character
to the next row in the Trie.
|
private char |
_rows
The number of rows allocated
|
private V[] |
_value
The value (if any) for a Trie row.
|
private static int |
ROW_SIZE
The Size of a Trie row is how many characters can be looked
up directly without going to a big index.
|
_caseInsensitive
Modifier and Type | Method and Description |
---|---|
void |
clear() |
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(byte[] b,
int offset,
int len)
Get the best match from key in a byte array.
|
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,
int offset,
int len)
Get the best match from key in a String.
|
boolean |
isFull() |
java.util.Set<java.lang.String> |
keySet() |
private void |
keySet(java.util.Set<java.lang.String> set,
int t) |
boolean |
put(java.lang.String s,
V v)
Put an entry into the Trie
|
java.lang.String |
toString() |
private void |
toString(java.lang.Appendable out,
int t) |
get, get, getBest, isCaseInsensitive, put, remove
private static final int ROW_SIZE
private static final int[] __lookup
private final char[] _rowIndex
private final java.lang.String[] _key
private final V[] _value
private char[][] _bigIndex
private char _rows
public ArrayTrie()
public ArrayTrie(int capacity)
capacity
- The capacity of the trie, which at 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 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(byte[] b, int offset, int len)
Trie
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 keypublic V getBest(java.lang.String s, int offset, int len)
Trie
s
- The stringoffset
- The offset within the string of the keylen
- the length of the keyprivate V getBest(int t, java.lang.String s, int offset, int len)
private 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
private void toString(java.lang.Appendable out, int t)
public java.util.Set<java.lang.String> keySet()
private void keySet(java.util.Set<java.lang.String> set, int t)
public boolean isFull()