com.atilika.kuromoji.trie

Class PatriciaTrie<V>

java.lang.Object

com.atilika.kuromoji.trie.PatriciaTrie<V>

Type Parameters:

V - value type

All Implemented Interfaces:

java.util.Map<java.lang.String,V>

public class PatriciaTrie<V>
extends java.lang.Object
implements java.util.Map<java.lang.String,V>

Convenient and compact structure for storing key-value pairs and quickly looking them up, including doing prefix searches

Implements the Map<String, V> interface

Note that values(), keySet(), entrySet() and containsValue() have naive implementations

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	PatriciaTrie.KeyMapper<K> Generic interface to map a key to bits
static class	PatriciaTrie.PatriciaNode<V> Nodes used in a PatriciaTrie containing a String key and associated value data
static class	PatriciaTrie.StringKeyMapper A PatriciaTrie.KeyMapper mapping Strings to bits

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

java.util.Map.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field and Description
protected int	entries Number of entries in the trie
protected PatriciaTrie.PatriciaNode<V>	root Root value is left -- right is unused

Constructor Summary

Constructors

Constructor and Description
PatriciaTrie() Constructs and empty trie

Method Summary

Modifier and Type	Method and Description
void	clear() Clears this trie by removing all its key-value pairs
boolean	containsKey(java.lang.Object key) Test membership in this trie
boolean	containsKeyPrefix(java.lang.String prefix) Test key prefix membership in this trie (prefix search using key)
boolean	containsValue(java.lang.Object value) Predicate to test value membership
java.util.Set<java.util.Map.Entry<java.lang.String,V>>	entrySet() Returns a copy of the mappings contained in this trie as a Set
V	get(java.lang.Object key) Get value associated with specified key in this trie
PatriciaTrie.KeyMapper<java.lang.String>	getKeyMapper() Should only be used by PatriciaTrieFormatter
PatriciaTrie.PatriciaNode<V>	getRoot() Should only be used by PatriciaTrieFormatter
boolean	isEmpty() Predicate indicating whether this trie is empty
java.util.Set<java.lang.String>	keySet() Returns a copy of the keys contained in this trie as a Set
V	put(java.lang.String key, V value) Puts value into trie identifiable by key into this trie (key should be non-null)
void	putAll(java.util.Map<? extends java.lang.String,? extends V> map) Inserts all key and value entries in a map into this trie
V	remove(java.lang.Object key) Removes entry identified by key from this trie (currently unsupported)
int	size() Returns the number of key-value mappings in this trie
java.util.Collection<V>	values() Returns a copy of the values contained in this trie as a Set

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, equals, forEach, getOrDefault, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll

Field Detail

root

protected PatriciaTrie.PatriciaNode<V> root

Root value is left -- right is unused

entries

protected int entries

Number of entries in the trie

Constructor Detail

PatriciaTrie

public PatriciaTrie()

Constructs and empty trie

Method Detail

get

public V get(java.lang.Object key)

Get value associated with specified key in this trie

Specified by:

get in interface java.util.Map<java.lang.String,V>

Parameters:

key - key to retrieve value for

Returns:

value or null if non-existent

put

public V put(java.lang.String key,
             V value)

Puts value into trie identifiable by key into this trie (key should be non-null)

Specified by:

put in interface java.util.Map<java.lang.String,V>

Parameters:

key - key to associate with value

value - value be inserted

Returns:

value inserted

Throws:

java.lang.NullPointerException - in case key is null

putAll

public void putAll(java.util.Map<? extends java.lang.String,? extends V> map)

Inserts all key and value entries in a map into this trie

Specified by:

putAll in interface java.util.Map<java.lang.String,V>

Parameters:

map - map with entries to insert

remove

public V remove(java.lang.Object key)

Removes entry identified by key from this trie (currently unsupported)

Specified by:

remove in interface java.util.Map<java.lang.String,V>

Parameters:

key - to remove

Returns:

value removed

Throws:

java.lang.UnsupportedOperationException - is always thrown since this operation is unimplemented

containsKey

public boolean containsKey(java.lang.Object key)

Test membership in this trie

Specified by:

containsKey in interface java.util.Map<java.lang.String,V>

Parameters:

key - to test if exists

Returns:

true if trie contains key

keySet

public java.util.Set<java.lang.String> keySet()

Returns a copy of the keys contained in this trie as a Set

Specified by:

keySet in interface java.util.Map<java.lang.String,V>

Returns:

keys in the trie, not null

values

public java.util.Collection<V> values()

Returns a copy of the values contained in this trie as a Set

Specified by:

values in interface java.util.Map<java.lang.String,V>

Returns:

values in the trie, not null

containsKeyPrefix

public boolean containsKeyPrefix(java.lang.String prefix)

Test key prefix membership in this trie (prefix search using key)

Parameters:

prefix - key prefix to search

Returns:

true if trie contains key prefix

size

public int size()

Returns the number of key-value mappings in this trie

Specified by:

size in interface java.util.Map<java.lang.String,V>

Returns:

number of entries in trie

isEmpty

public boolean isEmpty()

Predicate indicating whether this trie is empty

Specified by:

isEmpty in interface java.util.Map<java.lang.String,V>

Returns:

true if and only ff the trie is empty

clear

public void clear()

Clears this trie by removing all its key-value pairs

Specified by:

clear in interface java.util.Map<java.lang.String,V>

containsValue

public boolean containsValue(java.lang.Object value)

Predicate to test value membership

Specified by:

containsValue in interface java.util.Map<java.lang.String,V>

Parameters:

value - value to test if is contained in the trie

Returns:

true if and only if trie contains value

entrySet

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

Returns a copy of the mappings contained in this trie as a Set

Specified by:

entrySet in interface java.util.Map<java.lang.String,V>

Returns:

entries in the trie, not null

getRoot

public PatriciaTrie.PatriciaNode<V> getRoot()

Should only be used by PatriciaTrieFormatter

Returns:

trie root, not null

getKeyMapper

public PatriciaTrie.KeyMapper<java.lang.String> getKeyMapper()

Should only be used by PatriciaTrieFormatter

Returns:

key mapper used to map key to bit strings