edu.ucla.sspace.util

Class TrieMap<V>

java.lang.Object

java.util.AbstractMap<String,V>

edu.ucla.sspace.util.TrieMap<V>

All Implemented Interfaces:

Serializable, Map<String,V>

public class TrieMap<V>
extends AbstractMap<String,V>
implements Serializable

A trie-based Map implementation that uses String instances as keys. Keys are returned in alphabetical order. This class is optimized for space efficiency. For a string of length n, operations are at worst case n * log(k), where k is the number of unique characters. In most cases, the cost will be much closer to linear in the number of characters in the string.

This class does not permit null keys or values. However, this class does permit the use of the empty string (a String of length 0).

This class is not synchronized. If concurrent updating behavior is required, the map should be wrapped using Collections.synchronizedMap(Map). This map will never throw a ConcurrentModificationException during iteration. The behavior is unspecified if the map is modified while an iterator is being used.

Author:

David Jurgens

See Also:

Serialized Form

Nested Class Summary

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>

Constructor Summary

Constructors

Constructor and Description
TrieMap() Constructs an empty trie
TrieMap(Map<String,? extends V> m) Constructs this trie, adding all of the provided mappings

Method Summary

Methods

Modifier and Type	Method and Description
void	clear() Removes all of the mappings from this map.
boolean	containsKey(Object key) Returns true if this map contains a mapping for the specified key.
Set<Map.Entry<String,V>>	entrySet() Returns a Set view of the mappings contained in this map.
V	get(Object key) Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
Set<String>	keySet() Returns a Set view of the keys contained in this map.
V	put(String key, V value) Adds the mapping from the provided key to the value.
V	remove(Object key) Removes the mapping for a key from this map if it is present and returns the value to which this map previously associated the key, or null if the map contained no mapping for the key.
int	size() Returns the number of key-value mappings in this trie.
Collection<V>	values() Returns a Collection view of the values contained in this map.

Methods inherited from class java.util.AbstractMap

clone, containsValue, equals, hashCode, isEmpty, putAll, toString

Methods inherited from class java.lang.Object

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

Constructor Detail

TrieMap

public TrieMap()

Constructs an empty trie

TrieMap

public TrieMap(Map<String,? extends V> m)

Constructs this trie, adding all of the provided mappings

Method Detail

clear

public void clear()

Removes all of the mappings from this map.

Specified by:

clear in interface Map<String,V>

Overrides:

clear in class AbstractMap<String,V>

containsKey

public boolean containsKey(Object key)

Returns true if this map contains a mapping for the specified key.

Specified by:

containsKey in interface Map<String,V>

Overrides:

containsKey in class AbstractMap<String,V>

Throws:

NullPointerException - if key is null

ClassCastException - if key is not an instance of String

entrySet

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

Returns a Set view of the mappings contained in this map.

Specified by:

entrySet in interface Map<String,V>

Specified by:

entrySet in class AbstractMap<String,V>

get

public V get(Object key)

Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

Specified by:

get in interface Map<String,V>

Overrides:

get in class AbstractMap<String,V>

keySet

public Set<String> keySet()

Returns a Set view of the keys contained in this map.

Specified by:

keySet in interface Map<String,V>

Overrides:

keySet in class AbstractMap<String,V>

put

public V put(String key,
    V value)

Adds the mapping from the provided key to the value.

Specified by:

put in interface Map<String,V>

Overrides:

put in class AbstractMap<String,V>

Parameters:

key -

value -

Throws:

NullPointerException

IllegalArgumentException

remove

public V remove(Object key)

Removes the mapping for a key from this map if it is present and returns the value to which this map previously associated the key, or null if the map contained no mapping for the key.

Specified by:

remove in interface Map<String,V>

Overrides:

remove in class AbstractMap<String,V>

Parameters:

key - key whose mapping is to be removed from the map

Returns:

the previous value associated with key, or null if there was no mapping for key.

size

public int size()

Returns the number of key-value mappings in this trie.

Specified by:

size in interface Map<String,V>

Overrides:

size in class AbstractMap<String,V>

values

public Collection<V> values()

Returns a Collection view of the values contained in this map.

Specified by:

values in interface Map<String,V>

Overrides:

values in class AbstractMap<String,V>