info.rolandkrueger.roklib.util
Class TernarySearchTreeMap<V>

java.lang.Object
  java.util.AbstractMap<CharSequence,V>
      info.rolandkrueger.roklib.util.TernarySearchTreeMap<V>

All Implemented Interfaces:

ITernarySearchTreeMap<V>, Serializable, Map<CharSequence,V>, SortedMap<CharSequence,V>

public class TernarySearchTreeMap<V>
extends AbstractMap<CharSequence,V>
implements Serializable, ITernarySearchTreeMap<V>

This class implements a ternary search tree that can be used to store and access a large amount of data efficiently and with low memory requirements.

The search tree's implementation is based on Wally Flint's article on Ternary Search Trees on the Javaworld webpage. The article can be found here. The code of method get is adapted from a code example in that article.

This class can be used to store either key/value mappings or simple string values. Note that in the first case the key's string representation is used as the actual key. After a key/value pair has been stored in the tree the key object's data except for its string representation is no longer known to the data structure. So it is not possible to restore the key object from the search tree thereafter.

If the search tree is used to store values without an assigned key the single-argument version of put can be used. Note that as above only the value's string representation is preserved within the data structure.

The search tree's iterator is best used if single values are stored in the data structure. It returns the tree's data elements in sorted order. If an iterator is applied with the data structure handling key/value pairs, only the values are returned sorted by their keys.

Version:

CVS $Id: TernarySearchTreeMap.java 211 2010-11-22 19:21:26Z roland $

Author:

Roland Krueger

See Also:

Serialized Form

Nested Class Summary

private static class	TernarySearchTreeMap.NodeType
private class	TernarySearchTreeMap.TSTEntry<EntryK extends CharSequence,EntryV extends V>
private class	TernarySearchTreeMap.TSTEntrySet
(package private) class	TernarySearchTreeMap.TSTIterator
(package private) class	TernarySearchTreeMap.TSTKeySet
private class	TernarySearchTreeMap.TSTNode<NodeValue>
private class	TernarySearchTreeMap.TSTStackNode<NodeValue>
private class	TernarySearchTreeMap.TSTSubMap
private class	TernarySearchTreeMap.TSTValuesCollection

Nested classes/interfaces inherited from class java.util.AbstractMap

AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K,V>

Field Summary

private Comparator<? super CharSequence>	mComparator
private boolean	mContainsEmptyStringKey
private V	mEmptyStringKeyValue
private int	mLengthTolerance
private TreeSet<CharSequence>	mMatchingKeys
private int	mNodeCount
private TernarySearchTreeMap.TSTNode<V>	mRootNode
private static long	serialVersionUID

Constructor Summary

TernarySearchTreeMap()
Private default constructor.

TernarySearchTreeMap(Map<CharSequence,V> map)

TernarySearchTreeMap(SortedMap<CharSequence,V> map)

Method Summary

void	clear()
Comparator<? super CharSequence>	comparator()
private int	compare(CharSequence firstKey, CharSequence secondKey)
boolean	containsKey(Object key)
boolean	containsValue(Object value)
Set<Map.Entry<CharSequence,V>>	entrySet()
CharSequence	firstKey()
V	get(Object key)
private TernarySearchTreeMap.TSTEntry<CharSequence,V>	getElementAt(int index) Returns either the key at the specified position if getKey is true or the value otherwise.
Map.Entry<CharSequence,V>	getEntry(Object key)
private Iterator<Map.Entry<CharSequence,V>>	getIterator(CharSequence fromKey, CharSequence toKey)
CharSequence	getKeyAt(int index)
Iterable<CharSequence>	getKeysForPrefix(CharSequence prefix)
String	getMapStructureAsString()
Iterator<Map.Entry<CharSequence,V>>	getPrefixSubtreeIterator(String prefix)
Iterator<Map.Entry<CharSequence,V>>	getPrefixSubtreeIterator(String pPrefix, boolean inverseSearch)
V	getValueAt(int index)
SortedMap<CharSequence,V>	headMap(CharSequence toKey)
int	indexOf(CharSequence key) Returns the index of the specified key if it is stored in the map.
boolean	isEmpty()
Set<CharSequence>	keySet()
CharSequence	lastKey()
SortedSet<CharSequence>	matchAlmost(CharSequence key, int distance, int lengthTolerance) Generates an ordered list of keys that partially match the method's argument key.
private void	matchAlmost(String key, int i, TernarySearchTreeMap.TSTNode<V> currentNode, int distance, StringBuilder prefix, int keyLength)
Map.Entry<CharSequence,V>	predecessor(Object keyObject)
V	put(CharSequence key, V value)
void	putAll(Map<? extends CharSequence,? extends V> t)
V	remove(Object key)
int	size()
SortedMap<CharSequence,V>	subMap(CharSequence fromKey, CharSequence toKey)
Map.Entry<CharSequence,V>	successor(Object keyObject)
SortedMap<CharSequence,V>	tailMap(CharSequence fromKey)
Collection<V>	values()

Methods inherited from class java.util.AbstractMap

clone, equals, hashCode, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

equals, hashCode

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

mRootNode

private TernarySearchTreeMap.TSTNode<V> mRootNode

mMatchingKeys

private TreeSet<CharSequence> mMatchingKeys

mLengthTolerance

private int mLengthTolerance

mComparator

private Comparator<? super CharSequence> mComparator

mContainsEmptyStringKey

private boolean mContainsEmptyStringKey

mEmptyStringKeyValue

private V mEmptyStringKeyValue

mNodeCount

private int mNodeCount

Constructor Detail

TernarySearchTreeMap

public TernarySearchTreeMap()

Private default constructor.

TernarySearchTreeMap

public TernarySearchTreeMap(Map<CharSequence,V> map)

TernarySearchTreeMap

public TernarySearchTreeMap(SortedMap<CharSequence,V> map)

Method Detail

getMapStructureAsString

public String getMapStructureAsString()

clear

public void clear()

Specified by:

clear in interface Map<CharSequence,V>

Overrides:

clear in class AbstractMap<CharSequence,V>

containsKey

public boolean containsKey(Object key)

Specified by:

containsKey in interface Map<CharSequence,V>

Overrides:

containsKey in class AbstractMap<CharSequence,V>

containsValue

public boolean containsValue(Object value)

Specified by:

containsValue in interface Map<CharSequence,V>

Overrides:

containsValue in class AbstractMap<CharSequence,V>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Map<CharSequence,V>

Overrides:

isEmpty in class AbstractMap<CharSequence,V>

getIterator

private Iterator<Map.Entry<CharSequence,V>> getIterator(CharSequence fromKey,
                                                        CharSequence toKey)

keySet

public Set<CharSequence> keySet()

Specified by:

keySet in interface Map<CharSequence,V>

Specified by:

keySet in interface SortedMap<CharSequence,V>

Overrides:

keySet in class AbstractMap<CharSequence,V>

compare

private int compare(CharSequence firstKey,
                    CharSequence secondKey)

putAll

public void putAll(Map<? extends CharSequence,? extends V> t)

Specified by:

putAll in interface Map<CharSequence,V>

Overrides:

putAll in class AbstractMap<CharSequence,V>

remove

public V remove(Object key)

Specified by:

remove in interface Map<CharSequence,V>

Overrides:

remove in class AbstractMap<CharSequence,V>

values

public Collection<V> values()

Specified by:

values in interface Map<CharSequence,V>

Specified by:

values in interface SortedMap<CharSequence,V>

Overrides:

values in class AbstractMap<CharSequence,V>

comparator

public Comparator<? super CharSequence> comparator()

Specified by:

comparator in interface SortedMap<CharSequence,V>

firstKey

public CharSequence firstKey()

Specified by:

firstKey in interface SortedMap<CharSequence,V>

lastKey

public CharSequence lastKey()

Specified by:

lastKey in interface SortedMap<CharSequence,V>

headMap

public SortedMap<CharSequence,V> headMap(CharSequence toKey)

Specified by:

headMap in interface SortedMap<CharSequence,V>

subMap

public SortedMap<CharSequence,V> subMap(CharSequence fromKey,
                                        CharSequence toKey)

Specified by:

subMap in interface SortedMap<CharSequence,V>

tailMap

public SortedMap<CharSequence,V> tailMap(CharSequence fromKey)

Specified by:

tailMap in interface SortedMap<CharSequence,V>

matchAlmost

public SortedSet<CharSequence> matchAlmost(CharSequence key,
                                           int distance,
                                           int lengthTolerance)

Description copied from interface: ITernarySearchTreeMap

Generates an ordered list of keys that partially match the method's argument key. This can be useful for spell checking or the like. The method's framework and its underlying algorithm is adopted from the above mentioned article on Javaworld by Wally Flint.

Specified by:

matchAlmost in interface ITernarySearchTreeMap<V>

Parameters:

key - The key's toString() method is used to generate a string representation of that key in order to find a set of partially matching keys differing only by a number of distance characters.

distance - The number of maximum characters that may be different from the characters of key.

lengthTolerance - specifies by how many characters the length of the resulting set's strings may differ from the length of the search key.

matchAlmost

private void matchAlmost(String key,
                         int i,
                         TernarySearchTreeMap.TSTNode<V> currentNode,
                         int distance,
                         StringBuilder prefix,
                         int keyLength)

get

public V get(Object key)

Specified by:

get in interface Map<CharSequence,V>

Overrides:

get in class AbstractMap<CharSequence,V>

getEntry

public Map.Entry<CharSequence,V> getEntry(Object key)

Specified by:

getEntry in interface ITernarySearchTreeMap<V>

getValueAt

public V getValueAt(int index)
             throws IndexOutOfBoundsException

Specified by:

getValueAt in interface ITernarySearchTreeMap<V>

Throws:

IndexOutOfBoundsException

getKeyAt

public CharSequence getKeyAt(int index)
                      throws IndexOutOfBoundsException

Specified by:

getKeyAt in interface ITernarySearchTreeMap<V>

Throws:

IndexOutOfBoundsException

getElementAt

private TernarySearchTreeMap.TSTEntry<CharSequence,V> getElementAt(int index)
                                                            throws IndexOutOfBoundsException

Returns either the key at the specified position if getKey is true or the value otherwise.

Parameters:

index -

Returns:

Object

Throws:

IndexOutOfBoundsException

indexOf

public int indexOf(CharSequence key)

Description copied from interface: ITernarySearchTreeMap

Returns the index of the specified key if it is stored in the map. Otherwise -1 is returned. The indexing is the same as with arrays, i.e. the first element in the map has index 0 and the last element has index size()-1.

Specified by:

indexOf in interface ITernarySearchTreeMap<V>

Parameters:

key - The key whose index is to be returned.

Returns:

int the key's index or -1 if the key isn't an element of the map.

getKeysForPrefix

public Iterable<CharSequence> getKeysForPrefix(CharSequence prefix)

Specified by:

getKeysForPrefix in interface ITernarySearchTreeMap<V>

getPrefixSubtreeIterator

public Iterator<Map.Entry<CharSequence,V>> getPrefixSubtreeIterator(String prefix)

Specified by:

getPrefixSubtreeIterator in interface ITernarySearchTreeMap<V>

getPrefixSubtreeIterator

public Iterator<Map.Entry<CharSequence,V>> getPrefixSubtreeIterator(String pPrefix,
                                                                    boolean inverseSearch)

Specified by:

getPrefixSubtreeIterator in interface ITernarySearchTreeMap<V>

put

public V put(CharSequence key,
             V value)

Specified by:

put in interface Map<CharSequence,V>

Overrides:

put in class AbstractMap<CharSequence,V>

predecessor

public Map.Entry<CharSequence,V> predecessor(Object keyObject)

Specified by:

predecessor in interface ITernarySearchTreeMap<V>

successor

public Map.Entry<CharSequence,V> successor(Object keyObject)

Specified by:

successor in interface ITernarySearchTreeMap<V>

size

public int size()

Specified by:

size in interface Map<CharSequence,V>

Overrides:

size in class AbstractMap<CharSequence,V>

entrySet

public Set<Map.Entry<CharSequence,V>> entrySet()

Specified by:

entrySet in interface Map<CharSequence,V>

Specified by:

entrySet in interface SortedMap<CharSequence,V>

Specified by:

entrySet in class AbstractMap<CharSequence,V>

See Also:

Map.entrySet()