public class StringPrefixTree<Type> extends Object
String
in a set.
This class is not thread safe so external synchronization may be needed in
multi threaded environment.
Modifier and Type | Class and Description |
---|---|
private class |
StringPrefixTree.Node
Prefix tree internal node representing single character of stored
strings.
|
private class |
StringPrefixTree.StackItem
Stack data storage.
|
Modifier and Type | Field and Description |
---|---|
private boolean |
caseSensitive
Case sensitivity turned on (
true )
or off (false ). |
private StringPrefixTree.Node |
root
Root tree node.
|
private int |
size
Size of tree (number of stored strings.
|
Constructor and Description |
---|
StringPrefixTree(boolean caseSensitive) |
Modifier and Type | Method and Description |
---|---|
boolean |
add(String str,
Type value)
Add new
String into prefix tree and set value mapped
to this string. |
void |
clear()
Clear content of
String prefix tree. |
private void |
finishExistingStringWithValue(StringPrefixTree.Node node,
Type value)
Add value into node and finish
|
private void |
finishNewStringWithValue(StringPrefixTree.Node node,
char c,
Type value)
Add value into node and finish
|
Type |
match(CharSequence str)
Exact match of given
CharSequence argument against
String s stored in prefix tree. |
Type |
match(CharSequence str,
int offset)
Exact match of given
CharSequence argument against
String s stored in prefix tree. |
Type |
matchCyclicBuffer(char[] buff,
int len,
int beg)
Longest possible match of given cyclic buffer
buff argument
against String s stored in prefix tree. |
Type |
prefixMatch(CharSequence str)
Match longest possible
CharSequence stored in prefix tree
against given String argument and return value stored under
this String . |
Type |
prefixMatch(CharSequence str,
int offset)
Match longest possible
CharSequence stored in prefix tree
against given String argument and return value stored under
this String . |
Type |
remove(String str)
Remove
String from prefix tree and remove value mapped
to this string. |
private void |
removeValuefromString(StringPrefixTree.Node node)
Remove value from node and mark node state as inner.
|
int |
size()
Get number of strings stored in prefix tree.
|
private StringPrefixTree.Node root
private int size
private boolean caseSensitive
true
)
or off (false
).
All strings are stored and compared as upper case when turned on.private void finishExistingStringWithValue(StringPrefixTree.Node node, Type value)
String
.
node
- Node to be marked as final and used to store value.value
- Value to be stored into node.private void removeValuefromString(StringPrefixTree.Node node)
String
being removed.
node
- Node to be marked as inner and to remove its valueprivate void finishNewStringWithValue(StringPrefixTree.Node node, char c, Type value)
String
under given node which represents character
before last one or nodes root.
node
- Node where new node with last character will be attached.value
- Value to be stored into newly attached node.public void clear()
String
prefix tree.public boolean add(String str, Type value)
String
into prefix tree and set value mapped
to this string.
null
value of str
argument is considered as
empty string.
str
- String
to be added into prefix tree.value
- Value mapped to newly added String
.true
if given String
has been
added or false
if given String
was
already stored in prefix tree before and nothing has changed.public Type remove(String str)
String
from prefix tree and remove value mapped
to this string.
str
- String
to be removed from prefix tree.public Type match(CharSequence str)
CharSequence
argument against
String
s stored in prefix tree.
null
value of str
argument is considered as
empty string. Matching is done from the beginning of given
String
argument.
str
- String to match against tree.String
or null
if
no matching String
was found.public Type match(CharSequence str, int offset)
CharSequence
argument against
String
s stored in prefix tree.
null
value of str
argument is considered as
empty string. Matching is done from the beginning of given
String
argument.
str
- String to match against tree.offset
- Beginning index for searching.String
or null
if
no matching String
was found.public Type matchCyclicBuffer(char[] buff, int len, int beg)
buff
argument
against String
s stored in prefix tree.
Search starts at beg
index in buff
. Next index
is evaluated as (<current index> + 1) % buff.length
.
Maximum of len
characters are compared and longest possible
String
stored in prefix tree is evaluated as matching. Zero
length is evaluated as empty string.
buff
- Cyclic buffer containing source string.len
- Length of string to be compared.beg
- Index of beginning of the string (1st character) in
cyclic buffer.String
or null
if
no matching String
was found.public Type prefixMatch(CharSequence str)
CharSequence
stored in prefix tree
against given String
argument and return value stored under
this String
.
null
value of str
argument is considered as
empty string. Matching is done from the beginning of given
String
argument.
str
- String
used to prefixMatch prefix tree against.String
stored in prefix
tree that is matching given String
argument prefix
or null
if no such stored String
was
found.public Type prefixMatch(CharSequence str, int offset)
CharSequence
stored in prefix tree
against given String
argument and return value stored under
this String
.
null
value of str
argument is considered as
empty string. Matching is done from the beginning of given
String
argument.
offset
- Beginning index for searching.str
- String
used to prefixMatch prefix tree against.String
stored in prefix
tree that is matching given String
argument prefix
or null
if no such stored String
was
found.public int size()
Copyright © 2013. All Rights Reserved.