V
- public 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.
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 |
dump() |
V |
get(ByteBuffer b,
int offset,
int len)
Get and exact match from a segment of a ByteBuufer as key
|
V |
get(String s,
int offset,
int len)
Get and exact match from a String key
|
V |
getBest(ByteBuffer b,
int offset,
int len)
Get the best match from key in a byte buffer.
|
V |
getBest(String s)
Get the best match from key in a String.
|
V |
getBest(String s,
int offset,
int length)
Get the best match from key in a String.
|
static int |
hilo(int diff) |
boolean |
isFull() |
Set<String> |
keySet() |
boolean |
put(String s,
V v)
Put and entry into the Trie
|
String |
toString() |
get, get, getBest, isCaseInsensitive, put, remove
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
- factor
- public boolean put(String s, V v)
Trie
s
- The key for the entryv
- The value of the entrypublic V get(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(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(String s)
Trie
public V getBest(String s, int offset, int length)
Trie
s
- The stringoffset
- The offset within the string of the keylength
- the length of the keypublic V getBest(ByteBuffer b, int offset, int len)
Trie
b
- The bufferoffset
- The offset within the buffer of the keylen
- the length of the keypublic boolean isFull()
public static int hilo(int diff)
public void dump()
Copyright © 1995-2015 Webtide. All Rights Reserved.