PatriciaTrie.java
/*
* Copyright 2005-2010 Roger Kapsi, Sam Berlin
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.cassandra.index.sasi.utils.trie;
import java.io.Serializable;
import java.util.*;
/**
* This class is taken from https://github.com/rkapsi/patricia-trie (v0.6), and slightly modified
* to correspond to Cassandra code style, as the only Patricia Trie implementation,
* which supports pluggable key comparators (e.g. commons-collections PatriciaTrie (which is based
* on rkapsi/patricia-trie project) only supports String keys)
* but unfortunately is not deployed to the maven central as a downloadable artifact.
*/
/**
* <h3>PATRICIA {@link Trie}</h3>
*
* <i>Practical Algorithm to Retrieve Information Coded in Alphanumeric</i>
*
* <p>A PATRICIA {@link Trie} is a compressed {@link Trie}. Instead of storing
* all data at the edges of the {@link Trie} (and having empty internal nodes),
* PATRICIA stores data in every node. This allows for very efficient traversal,
* insert, delete, predecessor, successor, prefix, range, and {@link #select(Object)}
* operations. All operations are performed at worst in O(K) time, where K
* is the number of bits in the largest item in the tree. In practice,
* operations actually take O(A(K)) time, where A(K) is the average number of
* bits of all items in the tree.
*
* <p>Most importantly, PATRICIA requires very few comparisons to keys while
* doing any operation. While performing a lookup, each comparison (at most
* K of them, described above) will perform a single bit comparison against
* the given key, instead of comparing the entire key to another key.
*
* <p>The {@link Trie} can return operations in lexicographical order using the
* {@link #traverse(Cursor)}, 'prefix', 'submap', or 'iterator' methods. The
* {@link Trie} can also scan for items that are 'bitwise' (using an XOR
* metric) by the 'select' method. Bitwise closeness is determined by the
* {@link KeyAnalyzer} returning true or false for a bit being set or not in
* a given key.
*
* <p>Any methods here that take an {@link Object} argument may throw a
* {@link ClassCastException} if the method is expecting an instance of K
* and it isn't K.
*
* @see <a href="http://en.wikipedia.org/wiki/Radix_tree">Radix Tree</a>
* @see <a href="http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA">PATRICIA</a>
* @see <a href="http://www.imperialviolet.org/binary/critbit.pdf">Crit-Bit Tree</a>
*
* @author Roger Kapsi
* @author Sam Berlin
*/
public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Serializable
{
private static final long serialVersionUID = -2246014692353432660L;
public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)
{
super(keyAnalyzer);
}
public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> m)
{
super(keyAnalyzer, m);
}
@Override
public Comparator<? super K> comparator()
{
return keyAnalyzer;
}
@Override
public SortedMap<K, V> prefixMap(K prefix)
{
return lengthInBits(prefix) == 0 ? this : new PrefixRangeMap(prefix);
}
@Override
public K firstKey()
{
return firstEntry().getKey();
}
@Override
public K lastKey()
{
TrieEntry<K, V> entry = lastEntry();
return entry != null ? entry.getKey() : null;
}
@Override
public SortedMap<K, V> headMap(K toKey)
{
return new RangeEntryMap(null, toKey);
}
@Override
public SortedMap<K, V> subMap(K fromKey, K toKey)
{
return new RangeEntryMap(fromKey, toKey);
}
@Override
public SortedMap<K, V> tailMap(K fromKey)
{
return new RangeEntryMap(fromKey, null);
}
/**
* Returns an entry strictly higher than the given key,
* or null if no such entry exists.
*/
private TrieEntry<K,V> higherEntry(K key)
{
// TODO: Cleanup so that we don't actually have to add/remove from the
// tree. (We do it here because there are other well-defined
// functions to perform the search.)
int lengthInBits = lengthInBits(key);
if (lengthInBits == 0)
{
if (!root.isEmpty())
{
// If data in root, and more after -- return it.
return size() > 1 ? nextEntry(root) : null;
}
else
{
// Root is empty & we want something after empty, return first.
return firstEntry();
}
}
TrieEntry<K, V> found = getNearestEntryForKey(key);
if (compareKeys(key, found.key))
return nextEntry(found);
int bitIndex = bitIndex(key, found.key);
if (Tries.isValidBitIndex(bitIndex))
{
return replaceCeil(key, bitIndex);
}
else if (Tries.isNullBitKey(bitIndex))
{
if (!root.isEmpty())
{
return firstEntry();
}
else if (size() > 1)
{
return nextEntry(firstEntry());
}
else
{
return null;
}
}
else if (Tries.isEqualBitKey(bitIndex))
{
return nextEntry(found);
}
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + 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.
*/
TrieEntry<K,V> ceilingEntry(K key)
{
// Basically:
// Follow the steps of adding an entry, but instead...
//
// - If we ever encounter a situation where we found an equal
// key, we return it immediately.
//
// - If we hit an empty root, return the first iterable item.
//
// - If we have to add a new item, we temporarily add it,
// find the successor to it, then remove the added item.
//
// These steps ensure that the returned value is either the
// entry for the key itself, or the first entry directly after
// the key.
// TODO: Cleanup so that we don't actually have to add/remove from the
// tree. (We do it here because there are other well-defined
// functions to perform the search.)
int lengthInBits = lengthInBits(key);
if (lengthInBits == 0)
{
if (!root.isEmpty())
{
return root;
}
else
{
return firstEntry();
}
}
TrieEntry<K, V> found = getNearestEntryForKey(key);
if (compareKeys(key, found.key))
return found;
int bitIndex = bitIndex(key, found.key);
if (Tries.isValidBitIndex(bitIndex))
{
return replaceCeil(key, bitIndex);
}
else if (Tries.isNullBitKey(bitIndex))
{
if (!root.isEmpty())
{
return root;
}
else
{
return firstEntry();
}
}
else if (Tries.isEqualBitKey(bitIndex))
{
return found;
}
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + key);
}
private TrieEntry<K, V> replaceCeil(K key, int bitIndex)
{
TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
addEntry(added);
incrementSize(); // must increment because remove will decrement
TrieEntry<K, V> ceil = nextEntry(added);
removeEntry(added);
modCount -= 2; // we didn't really modify it.
return ceil;
}
private TrieEntry<K, V> replaceLower(K key, int bitIndex)
{
TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
addEntry(added);
incrementSize(); // must increment because remove will decrement
TrieEntry<K, V> prior = previousEntry(added);
removeEntry(added);
modCount -= 2; // we didn't really modify it.
return prior;
}
/**
* Returns a key-value mapping associated with the greatest key
* strictly less than the given key, or null if there is no such key.
*/
TrieEntry<K,V> lowerEntry(K key)
{
// Basically:
// Follow the steps of adding an entry, but instead...
//
// - If we ever encounter a situation where we found an equal
// key, we return it's previousEntry immediately.
//
// - If we hit root (empty or not), return null.
//
// - If we have to add a new item, we temporarily add it,
// find the previousEntry to it, then remove the added item.
//
// These steps ensure that the returned value is always just before
// the key or null (if there was nothing before it).
// TODO: Cleanup so that we don't actually have to add/remove from the
// tree. (We do it here because there are other well-defined
// functions to perform the search.)
int lengthInBits = lengthInBits(key);
if (lengthInBits == 0)
return null; // there can never be anything before root.
TrieEntry<K, V> found = getNearestEntryForKey(key);
if (compareKeys(key, found.key))
return previousEntry(found);
int bitIndex = bitIndex(key, found.key);
if (Tries.isValidBitIndex(bitIndex))
{
return replaceLower(key, bitIndex);
}
else if (Tries.isNullBitKey(bitIndex))
{
return null;
}
else if (Tries.isEqualBitKey(bitIndex))
{
return previousEntry(found);
}
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + 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.
*/
TrieEntry<K,V> floorEntry(K key) {
// TODO: Cleanup so that we don't actually have to add/remove from the
// tree. (We do it here because there are other well-defined
// functions to perform the search.)
int lengthInBits = lengthInBits(key);
if (lengthInBits == 0)
{
return !root.isEmpty() ? root : null;
}
TrieEntry<K, V> found = getNearestEntryForKey(key);
if (compareKeys(key, found.key))
return found;
int bitIndex = bitIndex(key, found.key);
if (Tries.isValidBitIndex(bitIndex))
{
return replaceLower(key, bitIndex);
}
else if (Tries.isNullBitKey(bitIndex))
{
if (!root.isEmpty())
{
return root;
}
else
{
return null;
}
}
else if (Tries.isEqualBitKey(bitIndex))
{
return found;
}
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + key);
}
/**
* Finds the subtree that contains the prefix.
*
* This is very similar to getR but with the difference that
* we stop the lookup if h.bitIndex > lengthInBits.
*/
private TrieEntry<K, V> subtree(K prefix)
{
int lengthInBits = lengthInBits(prefix);
TrieEntry<K, V> current = root.left;
TrieEntry<K, V> path = root;
while(true)
{
if (current.bitIndex <= path.bitIndex || lengthInBits < current.bitIndex)
break;
path = current;
current = !isBitSet(prefix, current.bitIndex)
? current.left : current.right;
}
// Make sure the entry is valid for a subtree.
TrieEntry<K, V> entry = current.isEmpty() ? path : current;
// If entry is root, it can't be empty.
if (entry.isEmpty())
return null;
// if root && length of root is less than length of lookup,
// there's nothing.
// (this prevents returning the whole subtree if root has an empty
// string and we want to lookup things with "\0")
if (entry == root && lengthInBits(entry.getKey()) < lengthInBits)
return null;
// Found key's length-th bit differs from our key
// which means it cannot be the prefix...
if (isBitSet(prefix, lengthInBits) != isBitSet(entry.key, lengthInBits))
return null;
// ... or there are less than 'length' equal bits
int bitIndex = bitIndex(prefix, entry.key);
return (bitIndex >= 0 && bitIndex < lengthInBits) ? null : entry;
}
/**
* Returns the last entry the {@link Trie} is storing.
*
* <p>This is implemented by going always to the right until
* we encounter a valid uplink. That uplink is the last key.
*/
private TrieEntry<K, V> lastEntry()
{
return followRight(root.left);
}
/**
* Traverses down the right path until it finds an uplink.
*/
private TrieEntry<K, V> followRight(TrieEntry<K, V> node)
{
// if Trie is empty, no last entry.
if (node.right == null)
return null;
// Go as far right as possible, until we encounter an uplink.
while (node.right.bitIndex > node.bitIndex)
{
node = node.right;
}
return node.right;
}
/**
* Returns the node lexicographically before the given node (or null if none).
*
* This follows four simple branches:
* - If the uplink that returned us was a right uplink:
* - If predecessor's left is a valid uplink from predecessor, return it.
* - Else, follow the right path from the predecessor's left.
* - If the uplink that returned us was a left uplink:
* - Loop back through parents until we encounter a node where
* node != node.parent.left.
* - If node.parent.left is uplink from node.parent:
* - If node.parent.left is not root, return it.
* - If it is root & root isEmpty, return null.
* - If it is root & root !isEmpty, return root.
* - If node.parent.left is not uplink from node.parent:
* - Follow right path for first right child from node.parent.left
*
* @param start the start entry
*/
private TrieEntry<K, V> previousEntry(TrieEntry<K, V> start)
{
if (start.predecessor == null)
throw new IllegalArgumentException("must have come from somewhere!");
if (start.predecessor.right == start)
{
return isValidUplink(start.predecessor.left, start.predecessor)
? start.predecessor.left
: followRight(start.predecessor.left);
}
TrieEntry<K, V> node = start.predecessor;
while (node.parent != null && node == node.parent.left)
{
node = node.parent;
}
if (node.parent == null) // can be null if we're looking up root.
return null;
if (isValidUplink(node.parent.left, node.parent))
{
if (node.parent.left == root)
{
return root.isEmpty() ? null : root;
}
else
{
return node.parent.left;
}
}
else
{
return followRight(node.parent.left);
}
}
/**
* Returns the entry lexicographically after the given entry.
* If the given entry is null, returns the first node.
*
* This will traverse only within the subtree. If the given node
* is not within the subtree, this will have undefined results.
*/
private TrieEntry<K, V> nextEntryInSubtree(TrieEntry<K, V> node, TrieEntry<K, V> parentOfSubtree)
{
return (node == null) ? firstEntry() : nextEntryImpl(node.predecessor, node, parentOfSubtree);
}
private boolean isPrefix(K key, K prefix)
{
return keyAnalyzer.isPrefix(key, prefix);
}
/**
* A range view of the {@link Trie}
*/
private abstract class RangeMap extends AbstractMap<K, V> implements SortedMap<K, V>
{
/**
* The {@link #entrySet()} view
*/
private transient volatile Set<Map.Entry<K, V>> entrySet;
/**
* Creates and returns an {@link #entrySet()}
* view of the {@link RangeMap}
*/
protected abstract Set<Map.Entry<K, V>> createEntrySet();
/**
* Returns the FROM Key
*/
protected abstract K getFromKey();
/**
* Whether or not the {@link #getFromKey()} is in the range
*/
protected abstract boolean isFromInclusive();
/**
* Returns the TO Key
*/
protected abstract K getToKey();
/**
* Whether or not the {@link #getToKey()} is in the range
*/
protected abstract boolean isToInclusive();
@Override
public Comparator<? super K> comparator()
{
return PatriciaTrie.this.comparator();
}
@Override
public boolean containsKey(Object key)
{
return inRange(Tries.<K>cast(key)) && PatriciaTrie.this.containsKey(key);
}
@Override
public V remove(Object key)
{
return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.remove(key);
}
@Override
public V get(Object key)
{
return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.get(key);
}
@Override
public V put(K key, V value)
{
if (!inRange(key))
throw new IllegalArgumentException("Key is out of range: " + key);
return PatriciaTrie.this.put(key, value);
}
@Override
public Set<Map.Entry<K, V>> entrySet()
{
if (entrySet == null)
entrySet = createEntrySet();
return entrySet;
}
@Override
public SortedMap<K, V> subMap(K fromKey, K toKey)
{
if (!inRange2(fromKey))
throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
if (!inRange2(toKey))
throw new IllegalArgumentException("ToKey is out of range: " + toKey);
return createRangeMap(fromKey, isFromInclusive(), toKey, isToInclusive());
}
@Override
public SortedMap<K, V> headMap(K toKey)
{
if (!inRange2(toKey))
throw new IllegalArgumentException("ToKey is out of range: " + toKey);
return createRangeMap(getFromKey(), isFromInclusive(), toKey, isToInclusive());
}
@Override
public SortedMap<K, V> tailMap(K fromKey)
{
if (!inRange2(fromKey))
throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
return createRangeMap(fromKey, isFromInclusive(), getToKey(), isToInclusive());
}
/**
* Returns true if the provided key is greater than TO and
* less than FROM
*/
protected boolean inRange(K key)
{
K fromKey = getFromKey();
K toKey = getToKey();
return (fromKey == null || inFromRange(key, false))
&& (toKey == null || inToRange(key, false));
}
/**
* This form allows the high endpoint (as well as all legit keys)
*/
protected boolean inRange2(K key)
{
K fromKey = getFromKey();
K toKey = getToKey();
return (fromKey == null || inFromRange(key, false))
&& (toKey == null || inToRange(key, true));
}
/**
* Returns true if the provided key is in the FROM range
* of the {@link RangeMap}
*/
protected boolean inFromRange(K key, boolean forceInclusive)
{
K fromKey = getFromKey();
boolean fromInclusive = isFromInclusive();
int ret = keyAnalyzer.compare(key, fromKey);
return (fromInclusive || forceInclusive) ? ret >= 0 : ret > 0;
}
/**
* Returns true if the provided key is in the TO range
* of the {@link RangeMap}
*/
protected boolean inToRange(K key, boolean forceInclusive)
{
K toKey = getToKey();
boolean toInclusive = isToInclusive();
int ret = keyAnalyzer.compare(key, toKey);
return (toInclusive || forceInclusive) ? ret <= 0 : ret < 0;
}
/**
* Creates and returns a sub-range view of the current {@link RangeMap}
*/
protected abstract SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);
}
/**
* A {@link RangeMap} that deals with {@link Entry}s
*/
private class RangeEntryMap extends RangeMap
{
/**
* The key to start from, null if the beginning.
*/
protected final K fromKey;
/**
* The key to end at, null if till the end.
*/
protected final K toKey;
/**
* Whether or not the 'from' is inclusive.
*/
protected final boolean fromInclusive;
/**
* Whether or not the 'to' is inclusive.
*/
protected final boolean toInclusive;
/**
* Creates a {@link RangeEntryMap} with the fromKey included and
* the toKey excluded from the range
*/
protected RangeEntryMap(K fromKey, K toKey)
{
this(fromKey, true, toKey, false);
}
/**
* Creates a {@link RangeEntryMap}
*/
protected RangeEntryMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
{
if (fromKey == null && toKey == null)
throw new IllegalArgumentException("must have a from or to!");
if (fromKey != null && toKey != null && keyAnalyzer.compare(fromKey, toKey) > 0)
throw new IllegalArgumentException("fromKey > toKey");
this.fromKey = fromKey;
this.fromInclusive = fromInclusive;
this.toKey = toKey;
this.toInclusive = toInclusive;
}
@Override
public K firstKey()
{
Map.Entry<K,V> e = fromKey == null
? firstEntry()
: fromInclusive ? ceilingEntry(fromKey) : higherEntry(fromKey);
K first = e != null ? e.getKey() : null;
if (e == null || toKey != null && !inToRange(first, false))
throw new NoSuchElementException();
return first;
}
@Override
public K lastKey()
{
Map.Entry<K,V> e = toKey == null
? lastEntry()
: toInclusive ? floorEntry(toKey) : lowerEntry(toKey);
K last = e != null ? e.getKey() : null;
if (e == null || fromKey != null && !inFromRange(last, false))
throw new NoSuchElementException();
return last;
}
@Override
protected Set<Entry<K, V>> createEntrySet()
{
return new RangeEntrySet(this);
}
@Override
public K getFromKey()
{
return fromKey;
}
@Override
public K getToKey()
{
return toKey;
}
@Override
public boolean isFromInclusive()
{
return fromInclusive;
}
@Override
public boolean isToInclusive()
{
return toInclusive;
}
@Override
protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
{
return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
}
}
/**
* A {@link Set} view of a {@link RangeMap}
*/
private class RangeEntrySet extends AbstractSet<Map.Entry<K, V>>
{
private final RangeMap delegate;
private int size = -1;
private int expectedModCount = -1;
/**
* Creates a {@link RangeEntrySet}
*/
public RangeEntrySet(RangeMap delegate)
{
if (delegate == null)
throw new NullPointerException("delegate");
this.delegate = delegate;
}
@Override
public Iterator<Map.Entry<K, V>> iterator()
{
K fromKey = delegate.getFromKey();
K toKey = delegate.getToKey();
TrieEntry<K, V> first = fromKey == null ? firstEntry() : ceilingEntry(fromKey);
TrieEntry<K, V> last = null;
if (toKey != null)
last = ceilingEntry(toKey);
return new EntryIterator(first, last);
}
@Override
public int size()
{
if (size == -1 || expectedModCount != PatriciaTrie.this.modCount)
{
size = 0;
for (Iterator<?> it = iterator(); it.hasNext(); it.next())
{
++size;
}
expectedModCount = PatriciaTrie.this.modCount;
}
return size;
}
@Override
public boolean isEmpty()
{
return !iterator().hasNext();
}
@Override
public boolean contains(Object o)
{
if (!(o instanceof Map.Entry<?, ?>))
return false;
@SuppressWarnings("unchecked")
Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
K key = entry.getKey();
if (!delegate.inRange(key))
return false;
TrieEntry<K, V> node = getEntry(key);
return node != null && Tries.areEqual(node.getValue(), entry.getValue());
}
@Override
public boolean remove(Object o)
{
if (!(o instanceof Map.Entry<?, ?>))
return false;
@SuppressWarnings("unchecked")
Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
K key = entry.getKey();
if (!delegate.inRange(key))
return false;
TrieEntry<K, V> node = getEntry(key);
if (node != null && Tries.areEqual(node.getValue(), entry.getValue()))
{
removeEntry(node);
return true;
}
return false;
}
/**
* An {@link Iterator} for {@link RangeEntrySet}s.
*/
private final class EntryIterator extends TrieIterator<Map.Entry<K,V>>
{
private final K excludedKey;
/**
* Creates a {@link EntryIterator}
*/
private EntryIterator(TrieEntry<K,V> first, TrieEntry<K,V> last)
{
super(first);
this.excludedKey = (last != null ? last.getKey() : null);
}
@Override
public boolean hasNext()
{
return next != null && !Tries.areEqual(next.key, excludedKey);
}
@Override
public Map.Entry<K,V> next()
{
if (next == null || Tries.areEqual(next.key, excludedKey))
throw new NoSuchElementException();
return nextEntry();
}
}
}
/**
* A submap used for prefix views over the {@link Trie}.
*/
private class PrefixRangeMap extends RangeMap
{
private final K prefix;
private K fromKey = null;
private K toKey = null;
private int expectedModCount = -1;
private int size = -1;
/**
* Creates a {@link PrefixRangeMap}
*/
private PrefixRangeMap(K prefix)
{
this.prefix = prefix;
}
/**
* This method does two things. It determinates the FROM
* and TO range of the {@link PrefixRangeMap} and the number
* of elements in the range. This method must be called every
* time the {@link Trie} has changed.
*/
private int fixup()
{
// The trie has changed since we last
// found our toKey / fromKey
if (size == - 1 || PatriciaTrie.this.modCount != expectedModCount)
{
Iterator<Map.Entry<K, V>> it = entrySet().iterator();
size = 0;
Map.Entry<K, V> entry = null;
if (it.hasNext())
{
entry = it.next();
size = 1;
}
fromKey = entry == null ? null : entry.getKey();
if (fromKey != null)
{
TrieEntry<K, V> prior = previousEntry((TrieEntry<K, V>)entry);
fromKey = prior == null ? null : prior.getKey();
}
toKey = fromKey;
while (it.hasNext())
{
++size;
entry = it.next();
}
toKey = entry == null ? null : entry.getKey();
if (toKey != null)
{
entry = nextEntry((TrieEntry<K, V>)entry);
toKey = entry == null ? null : entry.getKey();
}
expectedModCount = PatriciaTrie.this.modCount;
}
return size;
}
@Override
public K firstKey()
{
fixup();
Map.Entry<K,V> e = fromKey == null ? firstEntry() : higherEntry(fromKey);
K first = e != null ? e.getKey() : null;
if (e == null || !isPrefix(first, prefix))
throw new NoSuchElementException();
return first;
}
@Override
public K lastKey()
{
fixup();
Map.Entry<K,V> e = toKey == null ? lastEntry() : lowerEntry(toKey);
K last = e != null ? e.getKey() : null;
if (e == null || !isPrefix(last, prefix))
throw new NoSuchElementException();
return last;
}
/**
* Returns true if this {@link PrefixRangeMap}'s key is a prefix
* of the provided key.
*/
@Override
protected boolean inRange(K key)
{
return isPrefix(key, prefix);
}
/**
* Same as {@link #inRange(Object)}
*/
@Override
protected boolean inRange2(K key)
{
return inRange(key);
}
/**
* Returns true if the provided Key is in the FROM range
* of the {@link PrefixRangeMap}
*/
@Override
protected boolean inFromRange(K key, boolean forceInclusive)
{
return isPrefix(key, prefix);
}
/**
* Returns true if the provided Key is in the TO range
* of the {@link PrefixRangeMap}
*/
@Override
protected boolean inToRange(K key, boolean forceInclusive)
{
return isPrefix(key, prefix);
}
@Override
protected Set<Map.Entry<K, V>> createEntrySet()
{
return new PrefixRangeEntrySet(this);
}
@Override
public K getFromKey()
{
return fromKey;
}
@Override
public K getToKey()
{
return toKey;
}
@Override
public boolean isFromInclusive()
{
return false;
}
@Override
public boolean isToInclusive()
{
return false;
}
@Override
protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive)
{
return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
}
}
/**
* A prefix {@link RangeEntrySet} view of the {@link Trie}
*/
private final class PrefixRangeEntrySet extends RangeEntrySet
{
private final PrefixRangeMap delegate;
private TrieEntry<K, V> prefixStart;
private int expectedModCount = -1;
/**
* Creates a {@link PrefixRangeEntrySet}
*/
public PrefixRangeEntrySet(PrefixRangeMap delegate)
{
super(delegate);
this.delegate = delegate;
}
@Override
public int size()
{
return delegate.fixup();
}
@Override
public Iterator<Map.Entry<K,V>> iterator()
{
if (PatriciaTrie.this.modCount != expectedModCount)
{
prefixStart = subtree(delegate.prefix);
expectedModCount = PatriciaTrie.this.modCount;
}
if (prefixStart == null)
{
Set<Map.Entry<K,V>> empty = Collections.emptySet();
return empty.iterator();
}
else if (lengthInBits(delegate.prefix) >= prefixStart.bitIndex)
{
return new SingletonIterator(prefixStart);
}
else
{
return new EntryIterator(prefixStart, delegate.prefix);
}
}
/**
* An {@link Iterator} that holds a single {@link TrieEntry}.
*/
private final class SingletonIterator implements Iterator<Map.Entry<K, V>>
{
private final TrieEntry<K, V> entry;
private int hit = 0;
public SingletonIterator(TrieEntry<K, V> entry)
{
this.entry = entry;
}
@Override
public boolean hasNext()
{
return hit == 0;
}
@Override
public Map.Entry<K, V> next()
{
if (hit != 0)
throw new NoSuchElementException();
++hit;
return entry;
}
@Override
public void remove()
{
if (hit != 1)
throw new IllegalStateException();
++hit;
PatriciaTrie.this.removeEntry(entry);
}
}
/**
* An {@link Iterator} for iterating over a prefix search.
*/
private final class EntryIterator extends TrieIterator<Map.Entry<K, V>>
{
// values to reset the subtree if we remove it.
protected final K prefix;
protected boolean lastOne;
protected TrieEntry<K, V> subtree; // the subtree to search within
/**
* Starts iteration at the given entry & search only
* within the given subtree.
*/
EntryIterator(TrieEntry<K, V> startScan, K prefix)
{
subtree = startScan;
next = PatriciaTrie.this.followLeft(startScan);
this.prefix = prefix;
}
@Override
public Map.Entry<K,V> next()
{
Map.Entry<K, V> entry = nextEntry();
if (lastOne)
next = null;
return entry;
}
@Override
protected TrieEntry<K, V> findNext(TrieEntry<K, V> prior)
{
return PatriciaTrie.this.nextEntryInSubtree(prior, subtree);
}
@Override
public void remove()
{
// If the current entry we're removing is the subtree
// then we need to find a new subtree parent.
boolean needsFixing = false;
int bitIdx = subtree.bitIndex;
if (current == subtree)
needsFixing = true;
super.remove();
// If the subtree changed its bitIndex or we
// removed the old subtree, get a new one.
if (bitIdx != subtree.bitIndex || needsFixing)
subtree = subtree(prefix);
// If the subtree's bitIndex is less than the
// length of our prefix, it's the last item
// in the prefix tree.
if (lengthInBits(prefix) >= subtree.bitIndex)
lastOne = true;
}
}
}
}