Package | Description |
---|---|
org.apache.commons.collections4.trie |
This package contains implementations of the
Trie interface. |
Modifier and Type | Field and Description |
---|---|
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieIterator.current |
private AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.PrefixRangeEntrySet.SingletonIterator.entry |
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieEntry.left
The left child of this entry.
|
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieIterator.next |
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieEntry.parent
The parent of this entry.
|
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieEntry.predecessor
The entry who uplinks to this entry.
|
private AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.PrefixRangeEntrySet.prefixStart |
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieMapIterator.previous |
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieEntry.right
The right child of this entry.
|
private AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.root
The root node of the
Trie . |
private AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.PrefixRangeEntrySet.EntryIterator.subtree |
Modifier and Type | Method and Description |
---|---|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.addEntry(AbstractPatriciaTrie.TrieEntry<K,V> entry,
int lengthInBits)
Adds the given
AbstractPatriciaTrie.TrieEntry to the Trie . |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.ceilingEntry(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.
|
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieIterator.findNext(AbstractPatriciaTrie.TrieEntry<K,V> prior) |
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.PrefixRangeEntrySet.EntryIterator.findNext(AbstractPatriciaTrie.TrieEntry<K,V> prior) |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.firstEntry()
Returns the first entry the
Trie is storing. |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.floorEntry(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.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.followLeft(AbstractPatriciaTrie.TrieEntry<K,V> node)
Goes left through the tree until it finds a valid node.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.followRight(AbstractPatriciaTrie.TrieEntry<K,V> node)
Traverses down the right path until it finds an uplink.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.getEntry(java.lang.Object k)
Returns the entry associated with the specified key in the
PatriciaTrieBase.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.getNearestEntryForKey(K key,
int lengthInBits)
Returns the nearest entry for a given key.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.higherEntry(K key)
Returns an entry strictly higher than the given key,
or null if no such entry exists.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.lastEntry()
Returns the last entry the
Trie is storing. |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.lowerEntry(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.
|
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieIterator.nextEntry()
Returns the next
AbstractPatriciaTrie.TrieEntry . |
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieMapIterator.nextEntry() |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.nextEntry(AbstractPatriciaTrie.TrieEntry<K,V> node)
Returns the entry lexicographically after the given entry.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.nextEntryImpl(AbstractPatriciaTrie.TrieEntry<K,V> start,
AbstractPatriciaTrie.TrieEntry<K,V> previous,
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).
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.nextEntryInSubtree(AbstractPatriciaTrie.TrieEntry<K,V> node,
AbstractPatriciaTrie.TrieEntry<K,V> parentOfSubtree)
Returns the entry lexicographically after the given entry.
|
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieMapIterator.previousEntry() |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.previousEntry(AbstractPatriciaTrie.TrieEntry<K,V> start)
Returns the node lexicographically before the given node (or null if none).
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.subtree(K prefix,
int offsetInBits,
int lengthInBits)
Finds the subtree that contains the prefix.
|
Modifier and Type | Method and Description |
---|---|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.addEntry(AbstractPatriciaTrie.TrieEntry<K,V> entry,
int lengthInBits)
Adds the given
AbstractPatriciaTrie.TrieEntry to the Trie . |
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.TrieIterator.findNext(AbstractPatriciaTrie.TrieEntry<K,V> prior) |
protected AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.PrefixRangeEntrySet.EntryIterator.findNext(AbstractPatriciaTrie.TrieEntry<K,V> prior) |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.followLeft(AbstractPatriciaTrie.TrieEntry<K,V> node)
Goes left through the tree until it finds a valid node.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.followRight(AbstractPatriciaTrie.TrieEntry<K,V> node)
Traverses down the right path until it finds an uplink.
|
(package private) static boolean |
AbstractPatriciaTrie.isValidUplink(AbstractPatriciaTrie.TrieEntry<?,?> next,
AbstractPatriciaTrie.TrieEntry<?,?> from)
Returns true if 'next' is a valid uplink coming from 'from'.
|
(package private) static boolean |
AbstractPatriciaTrie.isValidUplink(AbstractPatriciaTrie.TrieEntry<?,?> next,
AbstractPatriciaTrie.TrieEntry<?,?> from)
Returns true if 'next' is a valid uplink coming from 'from'.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.nextEntry(AbstractPatriciaTrie.TrieEntry<K,V> node)
Returns the entry lexicographically after the given entry.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.nextEntryImpl(AbstractPatriciaTrie.TrieEntry<K,V> start,
AbstractPatriciaTrie.TrieEntry<K,V> previous,
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).
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.nextEntryImpl(AbstractPatriciaTrie.TrieEntry<K,V> start,
AbstractPatriciaTrie.TrieEntry<K,V> previous,
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).
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.nextEntryImpl(AbstractPatriciaTrie.TrieEntry<K,V> start,
AbstractPatriciaTrie.TrieEntry<K,V> previous,
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).
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.nextEntryInSubtree(AbstractPatriciaTrie.TrieEntry<K,V> node,
AbstractPatriciaTrie.TrieEntry<K,V> parentOfSubtree)
Returns the entry lexicographically after the given entry.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.nextEntryInSubtree(AbstractPatriciaTrie.TrieEntry<K,V> node,
AbstractPatriciaTrie.TrieEntry<K,V> parentOfSubtree)
Returns the entry lexicographically after the given entry.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
AbstractPatriciaTrie.previousEntry(AbstractPatriciaTrie.TrieEntry<K,V> start)
Returns the node lexicographically before the given node (or null if none).
|
(package private) V |
AbstractPatriciaTrie.removeEntry(AbstractPatriciaTrie.TrieEntry<K,V> h)
Removes a single entry from the
Trie . |
private void |
AbstractPatriciaTrie.removeExternalEntry(AbstractPatriciaTrie.TrieEntry<K,V> h)
Removes an external entry from the
Trie . |
private void |
AbstractPatriciaTrie.removeInternalEntry(AbstractPatriciaTrie.TrieEntry<K,V> h)
Removes an internal entry from the
Trie . |
private boolean |
AbstractPatriciaTrie.selectR(AbstractPatriciaTrie.TrieEntry<K,V> h,
int bitIndex,
K key,
int lengthInBits,
AbstractPatriciaTrie.Reference<java.util.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 . |
Constructor and Description |
---|
EntryIterator(AbstractPatriciaTrie.TrieEntry<K,V> first,
AbstractPatriciaTrie.TrieEntry<K,V> last)
Creates a
AbstractPatriciaTrie.EntrySet.EntryIterator . |
EntryIterator(AbstractPatriciaTrie.TrieEntry<K,V> first,
AbstractPatriciaTrie.TrieEntry<K,V> last)
Creates a
AbstractPatriciaTrie.EntrySet.EntryIterator . |
EntryIterator(AbstractPatriciaTrie.TrieEntry<K,V> startScan,
K prefix,
int offset,
int lengthInBits)
Starts iteration at the given entry & search only
within the given subtree.
|
SingletonIterator(AbstractPatriciaTrie.TrieEntry<K,V> entry) |
TrieIterator(AbstractPatriciaTrie.TrieEntry<K,V> firstEntry)
Starts iteration at the given entry.
|