Top Description Inners Fields Constructors Methods
org.apache.commons.collections4.trie

pack-priv abstract Class AbstractPatriciaTrie<K, V>

extends AbstractBitwiseTrie<K, V>
Class Inheritance
Known Direct Subclasses
org.apache.commons.collections4.trie.PatriciaTrie
Imports
java.io.IOException, .ObjectInputStream, .ObjectOutputStream, java.util.AbstractCollection, .AbstractMap, .AbstractSet, .Collection, .Collections, .Comparator, .ConcurrentModificationException, .Iterator, .Map, .NoSuchElementException, .Set, .SortedMap, org.apache.commons.collections4.OrderedMapIterator
This class implements the base PATRICIA algorithm and everything that is related to the Map interface.
Since
4.0

Nested and Inner Type Summary

Modifier and TypeClass and Description
private class
AbstractPatriciaTrie.EntrySet

This is a entry set view of the Trie as returned by Map#entrySet().

private class
AbstractPatriciaTrie.KeySet

This is a key set view of the Trie as returned by Map#keySet().

private class
AbstractPatriciaTrie.PrefixRangeEntrySet

A prefix RangeEntrySet view of the Trie.

private class
AbstractPatriciaTrie.PrefixRangeMap

A submap used for prefix views over the Trie.

private class
AbstractPatriciaTrie.RangeEntryMap

A RangeMap that deals with Entrys.

private class
AbstractPatriciaTrie.RangeEntrySet

A Set view of a RangeMap.

private abstract class
AbstractPatriciaTrie.RangeMap

A range view of the Trie.

private static class
AbstractPatriciaTrie.Reference<E>

A Reference allows us to return something through a Method's argument list.

protected static class
AbstractPatriciaTrie.TrieEntry<K, V>

A org.apache.commons.collections4.Trie is a set of TrieEntry nodes.

pack-priv abstract class
AbstractPatriciaTrie.TrieIterator<E>

An iterator for the entries.

private class
AbstractPatriciaTrie.TrieMapIterator

An OrderedMapIterator for a Trie.

private class
AbstractPatriciaTrie.Values

This is a value view of the Trie as returned by Map#values().

Field Summary

Modifier and TypeField and Description
private transient volatile Set<Map.Entry<K, V>>
entrySet

private transient volatile Set<K>
keySet

Hides java.util.AbstractMap.keySet.

Each of these fields are initialized to contain an instance of the appropriate view the first time this view is requested.
protected transient int
modCount

The number of times this org.apache.commons.collections4.Trie has been modified.

private transient AbstractPatriciaTrie.TrieEntry<K, V>
root

The root node of the org.apache.commons.collections4.Trie.

private static final long
serialVersionUID

Hides org.apache.commons.collections4.trie.AbstractBitwiseTrie.serialVersionUID.

private transient int
size

The current size of the org.apache.commons.collections4.Trie.

private transient volatile Collection<V>
values

Hides java.util.AbstractMap.values.

Constructor Summary

AccessConstructor and Description
protected
AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer)

protected
AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer, final Map<? extends K, ? extends V> map)

Constructs a new org.apache.commons.collections4.Trie Trie using the given KeyAnalyzer and initializes the Trie with the values from the provided Map.

Method Summary

Modifier and TypeMethod and Description
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
addEntry(final AbstractPatriciaTrie.TrieEntry<K, V> entry, final int lengthInBits)

Adds the given TrieEntry to the Trie.

pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
ceilingEntry(final K key)

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

public void
clear()

Overrides java.util.AbstractMap.clear.

Implements java.util.Map.clear, org.apache.commons.collections4.Put.clear.

Removes all of the mappings from this map (optional operation).
public Comparator<? super K>
comparator()

Implements java.util.SortedMap.comparator.

Returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.
public boolean
containsKey(final Object
key whose presence in this map is to be tested
k)

Overrides java.util.AbstractMap.containsKey.

Implements java.util.Map.containsKey, org.apache.commons.collections4.Get.containsKey.

Returns true if this map contains a mapping for the specified key.
pack-priv void
decrementSize()

A helper method to decrement the Trie size and increment the modification counter.

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

Implements abstract java.util.AbstractMap.entrySet.

Implements java.util.SortedMap.entrySet, java.util.Map.entrySet, org.apache.commons.collections4.Get.entrySet.

Returns a Set view of the mappings contained in this map.
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
firstEntry()

Overrides default java.util.SequencedMap.firstEntry.

Returns the first entry the Trie is storing.
public K
firstKey()

Implements java.util.SortedMap.firstKey, org.apache.commons.collections4.OrderedMap.firstKey.

Returns the first (lowest) key currently in this map.
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
floorEntry(final K key)

Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
followLeft(AbstractPatriciaTrie.TrieEntry<K, V> node)

Goes left through the tree until it finds a valid node.

pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
followRight(AbstractPatriciaTrie.TrieEntry<K, V> node)

Traverses down the right path until it finds an uplink.

public V
get(final Object
the key whose associated value is to be returned
k)

Overrides java.util.AbstractMap.get.

Implements java.util.Map.get, org.apache.commons.collections4.Get.get.

Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
getEntry(final Object k)

Returns the entry associated with the specified key in the PatriciaTrieBase.

pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
getNearestEntryForKey(final K key, final int lengthInBits)

Returns the nearest entry for a given key.

private SortedMap<K, V>

Returns:

a SortedMap view of this Trie with all elements whose key is prefixed by the search key
getPrefixMapByBits(final K
the key to use in the search
key, final int
the prefix offset
offsetInBits, final int
the number of significant prefix bits
lengthInBits)

Returns a view of this Trie of all elements that are prefixed by the number of bits in the given Key.

public SortedMap<K, V>
headMap(final K
high endpoint (exclusive) of the keys in the returned map
toKey)

Implements java.util.SortedMap.headMap.

Returns a view of the portion of this map whose keys are strictly less than toKey.
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
higherEntry(final K key)

Returns an entry strictly higher than the given key, or null if no such entry exists.

private void
incrementModCount()

A helper method to increment the modification counter.

pack-priv void
incrementSize()

A helper method to increment the Trie size and the modification counter.

public Set<K>
keySet()

Overrides java.util.AbstractMap.keySet.

Implements java.util.SortedMap.keySet, java.util.Map.keySet, org.apache.commons.collections4.Get.keySet.

Returns a Set view of the keys contained in this map.
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
lastEntry()

Overrides default java.util.SequencedMap.lastEntry.

Returns the last entry the Trie is storing.
public K
lastKey()

Implements java.util.SortedMap.lastKey, org.apache.commons.collections4.OrderedMap.lastKey.

Returns the last (highest) key currently in this map.
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
lowerEntry(final K key)

Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

public OrderedMapIterator<K, V>
mapIterator()

Implements org.apache.commons.collections4.OrderedMap.mapIterator.

Obtains an OrderedMapIterator over the map.
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
nextEntry(final AbstractPatriciaTrie.TrieEntry<K, V> node)

Returns the entry lexicographically after the given entry.

pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
nextEntryImpl(final AbstractPatriciaTrie.TrieEntry<K, V> start, final AbstractPatriciaTrie.TrieEntry<K, V> previous, final AbstractPatriciaTrie.TrieEntry<K, V> tree)

Scans for the next node, starting at the specified point, and using 'previous' as a hint that the last node we returned was 'previous' (so we know not to return it again).

pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
nextEntryInSubtree(final AbstractPatriciaTrie.TrieEntry<K, V> node, final AbstractPatriciaTrie.TrieEntry<K, V> parentOfSubtree)

Returns the entry lexicographically after the given entry.

public K
nextKey(final K
the key to search for next from
key)

Implements org.apache.commons.collections4.OrderedMap.nextKey.

Gets the next key after the one specified.
public SortedMap<K, V>
prefixMap(final K
the key used in the search
key)

Implements org.apache.commons.collections4.Trie.prefixMap.

Returns a view of this Trie of all elements that are prefixed by the given key.
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
previousEntry(final AbstractPatriciaTrie.TrieEntry<K, V>
the start entry
start)

Returns the node lexicographically before the given node (or null if none).

public K
previousKey(final K
the key to search for previous from
key)

Implements org.apache.commons.collections4.OrderedMap.previousKey.

Gets the previous key before the one specified.
public V
put(final K
key with which the specified value is to be associated
key, final V
value to be associated with the specified key
value)

Overrides java.util.AbstractMap.put.

Implements java.util.Map.put, org.apache.commons.collections4.Put.put.

Associates the specified value with the specified key in this map (optional operation).
private void
readObject(final ObjectInputStream stream)

Reads the content of the stream.

public V
remove(final Object
key whose mapping is to be removed from the map
k)

Overrides java.util.AbstractMap.remove.

Implements java.util.Map.remove, org.apache.commons.collections4.Get.remove.

Removes the mapping for a key from this map if it is present (optional operation).
pack-priv V
removeEntry(final AbstractPatriciaTrie.TrieEntry<K, V> h)

Removes a single entry from the Trie.

private void
removeExternalEntry(final AbstractPatriciaTrie.TrieEntry<K, V> h)

Removes an external entry from the Trie.

private void
removeInternalEntry(final AbstractPatriciaTrie.TrieEntry<K, V> h)

Removes an internal entry from the Trie.

public Map.Entry<K, V>

Returns:

the java.util.Map.Entry whose key is closest in a bitwise XOR metric to the provided key
select(final K
the key to use in the search
key)

Returns the java.util.Map.Entry whose key is closest in a bitwise XOR metric to the given key.

public K

Returns:

the key that is closest in a bitwise XOR metric to the provided key
selectKey(final K
the key to use in the search
key)

Returns the key that is closest in a bitwise XOR metric to the provided key.

private boolean
selectR(final AbstractPatriciaTrie.TrieEntry<K, V> h, final int bitIndex, final K key, final int lengthInBits, final AbstractPatriciaTrie.Reference<Map.Entry<K, V>> reference)

This is equivalent to the other selectR(TrieEntry, int, Object, int, Cursor, Reference) method but without its overhead because we're selecting only one best matching Entry from the Trie.

public V

Returns:

the value whose key is closest in a bitwise XOR metric to the provided key
selectValue(final K
the key to use in the search
key)

Returns the value whose key is closest in a bitwise XOR metric to the provided key.

public int
size()

Overrides java.util.AbstractMap.size.

Implements java.util.Map.size, org.apache.commons.collections4.Get.size.

Returns the number of key-value mappings in this map.
public SortedMap<K, V>
subMap(final K
low endpoint (inclusive) of the keys in the returned map
fromKey, final K
high endpoint (exclusive) of the keys in the returned map
toKey)

Implements java.util.SortedMap.subMap.

Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
pack-priv AbstractPatriciaTrie.TrieEntry<K, V>
subtree(final K prefix, final int offsetInBits, final int lengthInBits)

Finds the subtree that contains the prefix.

public SortedMap<K, V>
tailMap(final K
low endpoint (inclusive) of the keys in the returned map
fromKey)

Implements java.util.SortedMap.tailMap.

Returns a view of the portion of this map whose keys are greater than or equal to fromKey.
public Collection<V>
values()

Overrides java.util.AbstractMap.values.

Implements java.util.SortedMap.values, java.util.Map.values, org.apache.commons.collections4.Get.values.

Returns a Collection view of the values contained in this map.
private void
writeObject(final ObjectOutputStream stream)

Writes the content to the stream for serialization.

Inherited from org.apache.commons.collections4.trie.AbstractBitwiseTrie:
bitIndexbitsPerElementcastKeycomparecompareKeysgetKeyAnalyzerisBitSetlengthInBitstoString