V
- Value type.public final class TernarySearchTree<V>
extends java.lang.Object
implements java.util.Map<java.lang.String,V>, java.io.Serializable
Map
interface. This implementation provides all
optional interface methods, allows null
values
but restricts keys to non-null java.lang.String
objects.
It must be pointed out that this implementation
of entrySet()
, keySet()
and
values()
does not return sets backed by the
map. Changes to the map are not reflected in the returned set
nor are changes to the returned set reflected in the map.
Note: this implementation is not synchronized. If multiple threads currently access this map and at least one thread modifies the map by adding or removing an entry, then this map must be externally synchronized. External synchronization is accomplished in two ways:
synchronized
block:
synchronized (tstMap)
{
tstMap.put("abcd", obj);
}
TernarySearchTree
within a
java.util.Collections.synchronizedMap()
:
Map m =
Collections.synchronizedMap(
new TernarySearchTree(...));
For more information on ternary search trees, see Bentley, J., and Sedgewick, R. Fast algorithms for sorting and searching strings. In Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (1997), SIAM Press.
Constructor and Description |
---|
TernarySearchTree()
Constructs an empty ternary search tree map.
|
TernarySearchTree(java.util.Map<java.lang.String,? extends V> m)
Construct a new
TernarySearchTree with the same
mappings as the specified Map . |
Modifier and Type | Method and Description |
---|---|
void |
clear()
Clears out all stored values, leaving an empty map.
|
boolean |
containsKey(java.lang.Object key)
Returns
true if the key is in the ternary
search tree and false otherwise. |
boolean |
containsValue(java.lang.Object value)
Returns
true if value is stored in the
ternary search tree and false otherwise. |
java.util.Set<java.util.Map.Entry<java.lang.String,V>> |
entrySet()
Returns the set of all key-value mappings.
|
java.util.Set<java.util.Map.Entry<java.lang.String,V>> |
entrySet(Pattern query)
Returns the set of all key-value mappings whose keys match
the given query.
|
java.util.Set<java.util.Map.Entry<java.lang.String,V>> |
entrySet(Pattern query,
int maxMatches)
Returns the set of at most
maxMatches key-value
mappings whose keys match the given query. |
V |
get(java.lang.Object key)
Returns the value associated with
key . |
boolean |
isEmpty()
Returns
true if this map contains no
key-value mappings and false otherwise. |
java.util.Set<java.lang.String> |
keySet()
Returns all keys currently stored in the tree.
|
java.util.Set<java.lang.String> |
keySet(Pattern query)
Returns the words matching the query.
|
java.util.Set<java.lang.String> |
keySet(Pattern query,
int maxMatches)
Returns at most
maxMatches words matching the
query. |
java.util.Collection<java.lang.String> |
nearSearch(java.lang.String s,
int distance)
Returns the keys which are within a specified Hamming
distance of character sequence
s . |
long |
nodeCount()
Returns the number of nodes used in this map.
|
V |
put(java.lang.String key,
V value)
Enters a value into the ternary search tree using the
text key.
|
void |
putAll(java.util.Map<? extends java.lang.String,? extends V> map)
Copies all the mappings from the specified map to this
tree.
|
V |
remove(java.lang.Object key)
Removes the key-value mapping from the tree and returns
the now removed value.
|
int |
size()
Returns the number of key-value mappings in this tree.
|
java.util.Collection<V> |
values()
Returns a collection of all the trees values.
|
java.util.Collection<V> |
values(Pattern query)
Returns a non-
null collection of all trees values
with keys matching the given pattern. |
java.util.Collection<V> |
values(Pattern query,
int maxMatches)
Returns a collection of at most
maxMatches values
whose keys match the given pattern. |
public TernarySearchTree()
public TernarySearchTree(java.util.Map<java.lang.String,? extends V> m)
TernarySearchTree
with the same
mappings as the specified Map
.m
- Copies mappings from here.public boolean isEmpty()
true
if this map contains no
key-value mappings and false
otherwise.isEmpty
in interface java.util.Map<java.lang.String,V>
true
if this map contains no
key-value mappings and false
otherwise.public int size()
size
in interface java.util.Map<java.lang.String,V>
public long nodeCount()
public void clear()
clear
in interface java.util.Map<java.lang.String,V>
public boolean containsKey(java.lang.Object key)
true
if the key is in the ternary
search tree and false
otherwise.containsKey
in interface java.util.Map<java.lang.String,V>
key
- Search for this key in the tree.true
if the key is in the ternary
search tree and false
otherwise.public boolean containsValue(java.lang.Object value)
true
if value
is stored in the
ternary search tree and false
otherwise.containsValue
in interface java.util.Map<java.lang.String,V>
value
- Searches for this value.true
if value
is stored in the
ternary search tree and false
otherwise.public V get(java.lang.Object key)
key
.
If the ternary search tree does not contain the key,
then returns null
.get
in interface java.util.Map<java.lang.String,V>
key
- Search for this key.key
.
If the ternary search tree does not contain the key,
then returns null
.public V put(java.lang.String key, V value)
null
is returned.put
in interface java.util.Map<java.lang.String,V>
key
- The text key.value
- The key's associated value.key
. May
return null
.public void putAll(java.util.Map<? extends java.lang.String,? extends V> map)
put(String, Object)
successively.putAll
in interface java.util.Map<java.lang.String,V>
map
- The copied map.public V remove(java.lang.Object key)
remove
in interface java.util.Map<java.lang.String,V>
key
- Remove the mapping at this key.null
if key
is not in the tree.public java.util.Set<java.lang.String> keySet()
keySet
in interface java.util.Map<java.lang.String,V>
public java.util.Set<java.lang.String> keySet(Pattern query)
query
- Match against this query.public java.util.Set<java.lang.String> keySet(Pattern query, int maxMatches)
maxMatches
words matching the
query. This set is not backed by the tree.
Changes to the returned set are not reflected in the tree
and changes to the tree are not reflected in the set.query
- Match against this query.maxMatches
- Match at most this many keys.java.lang.IllegalArgumentException
- if maxMatches
is <= zero.java.lang.IllegalStateException
- if maxMatches
is exceeded.public java.util.Collection<V> values()
values
in interface java.util.Map<java.lang.String,V>
public java.util.Collection<V> values(Pattern query)
null
collection of all trees values
with keys matching the given pattern. This collection is
not backed by the tree. Changes to the returned
collection are not reflected in the tree and changes to
the tree are not reflected in the collection.query
- match against this query.query
.public java.util.Collection<V> values(Pattern query, int maxMatches)
maxMatches
values
whose keys match the given pattern. This collection is
not backed by the tree. Changes to the returned
collection are not reflected in the tree and changes to
the tree are not reflected in the collection.query
- Match against this query.maxMatches
- Match at most this many keys.java.lang.IllegalArgumentException
- if maxMatches
is <= zero.java.lang.IllegalStateException
- if maxMatches
is exceeded.public java.util.Set<java.util.Map.Entry<java.lang.String,V>> entrySet()
entrySet
in interface java.util.Map<java.lang.String,V>
public java.util.Set<java.util.Map.Entry<java.lang.String,V>> entrySet(Pattern query)
query
- Match against this query.public java.util.Set<java.util.Map.Entry<java.lang.String,V>> entrySet(Pattern query, int maxMatches)
maxMatches
key-value
mappings whose keys match the given query. If this tree is
empty, then an empty set is returned. The returned set is
not backed by the tree. Changes to the returned set
or to this tree are not reflected in the other.query
- Match against this query.maxMatches
- Match at most this many keys.maxMatches
key-value
mappings.
Throws IllegalArgumentException
if maxMatches
is <= zero.public java.util.Collection<java.lang.String> nearSearch(java.lang.String s, int distance)
s
. The Hamming
distance between two strings of equal length is the
number of positions at which corresponding characters are
different. One string may be transformed into the other by
changing the characters at these positions to the other
strings values. The Hamming distance may be thought of as
the number of errors in one string.
If this ternary search tree contains a dictionary, then this method may be used to find possible correct spellings for a misspelled word.
s
- find the keys within the specified Hamming
distance to this character sequence.distance
- the desired Hamming distance.s
. If no such keys
are found, then returns an empty collection.Copyright © 2001 - 2024. Charles W. Rapp. All rights reserved.