You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2013/06/13 23:01:01 UTC
svn commit: r1492866 [1/3] - in /commons/proper/collections/trunk/src:
main/java/org/apache/commons/collections4/trie/
main/java/org/apache/commons/collections4/trie/analyzer/
test/java/org/apache/commons/collections4/trie/
test/java/org/apache/commons...
Author: tn
Date: Thu Jun 13 21:01:00 2013
New Revision: 1492866
URL: http://svn.apache.org/r1492866
Log:
Refactor trie package: reduce interface by extending IterableSortedMap and only adding prefixMap method, remove all key analyzers but the StringKeyAnalyzer, refactor PatriciaTrie class by moving all remaining methods to AbstractPatriciaTrie and fixing the key type to String, integrating the test classes into the framework.
Added:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java
- copied, changed from r1491621, commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/PatriciaTrie2Test.java (with props)
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/UnmodifiableTrieTest.java (with props)
commons/proper/collections/trunk/src/test/resources/data/test/PatriciaTrie.emptyCollection.version4.obj (with props)
commons/proper/collections/trunk/src/test/resources/data/test/PatriciaTrie.fullCollection.version4.obj (with props)
commons/proper/collections/trunk/src/test/resources/data/test/UnmodifiableTrie.emptyCollection.version4.obj (with props)
commons/proper/collections/trunk/src/test/resources/data/test/UnmodifiableTrie.fullCollection.version4.obj (with props)
Removed:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/analyzer/ByteArrayKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/analyzer/ByteKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/analyzer/CharArrayKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/analyzer/CharacterKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/analyzer/IntegerKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/analyzer/LongKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/analyzer/ShortKeyAnalyzer.java
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/analyzer/
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java?rev=1492866&r1=1492865&r2=1492866&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java Thu Jun 13 21:01:00 2013
@@ -30,22 +30,22 @@ import org.apache.commons.collections4.T
* @since 4.0
* @version $Id$
*/
-abstract class AbstractBitwiseTrie<K, V> extends AbstractMap<K, V>
+public abstract class AbstractBitwiseTrie<K, V> extends AbstractMap<K, V>
implements Trie<K, V>, Serializable {
private static final long serialVersionUID = 5826987063535505652L;
- // TODO Privatise fields?
-
/**
* The {@link KeyAnalyzer} that's being used to build the PATRICIA {@link Trie}.
*/
- protected final KeyAnalyzer<? super K> keyAnalyzer;
+ private final KeyAnalyzer<? super K> keyAnalyzer;
/**
* Constructs a new {@link Trie} using the given {@link KeyAnalyzer}.
+ *
+ * @param keyAnalyzer the {@link KeyAnalyzer} to use
*/
- public AbstractBitwiseTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
+ protected AbstractBitwiseTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
if (keyAnalyzer == null) {
throw new NullPointerException("keyAnalyzer");
}
@@ -55,108 +55,12 @@ abstract class AbstractBitwiseTrie<K, V>
/**
* Returns the {@link KeyAnalyzer} that constructed the {@link Trie}.
+ * @return the {@link KeyAnalyzer} used by this {@link Trie}
*/
- public KeyAnalyzer<? super K> getKeyAnalyzer() {
+ protected KeyAnalyzer<? super K> getKeyAnalyzer() {
return keyAnalyzer;
}
- /**
- * Returns the {@link Entry} whose key is closest in a bitwise XOR
- * metric to the given key. This is NOT lexicographic closeness.
- * For example, given the keys:
- *
- * <ol>
- * <li>D = 1000100
- * <li>H = 1001000
- * <li>L = 1001100
- * </ol>
- *
- * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
- * return 'L', because the XOR distance between D & L is smaller
- * than the XOR distance between D & H.
- *
- * @param key the key to use in the search
- * @return the {@link Entry} whose key is closest in a bitwise XOR metric
- * to the provided key
- */
- public abstract Map.Entry<K, V> select(K key);
-
- /**
- * Returns the key that is closest in a bitwise XOR metric to the
- * provided key. This is NOT lexicographic closeness!
- *
- * For example, given the keys:
- *
- * <ol>
- * <li>D = 1000100
- * <li>H = 1001000
- * <li>L = 1001100
- * </ol>
- *
- * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
- * return 'L', because the XOR distance between D & L is smaller
- * than the XOR distance between D & H.
- *
- * @param key the key to use in the search
- * @return the key that is closest in a bitwise XOR metric to the provided key
- */
- public K selectKey(final K key) {
- final Map.Entry<K, V> entry = select(key);
- if (entry == null) {
- return null;
- }
- return entry.getKey();
- }
-
- /**
- * Returns the value whose key is closest in a bitwise XOR metric to
- * the provided key. This is NOT lexicographic closeness!
- *
- * For example, given the keys:
- *
- * <ol>
- * <li>D = 1000100
- * <li>H = 1001000
- * <li>L = 1001100
- * </ol>
- *
- * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
- * return 'L', because the XOR distance between D & L is smaller
- * than the XOR distance between D & H.
- *
- * @param key the key to use in the search
- * @return the value whose key is closest in a bitwise XOR metric
- * to the provided key
- */
- public V selectValue(final K key) {
- final Map.Entry<K, V> entry = select(key);
- if (entry == null) {
- return null;
- }
- return entry.getValue();
- }
-
- /**
- * Iterates through the {@link Trie}, starting with the entry whose bitwise
- * value is closest in an XOR metric to the given key. After the closest
- * entry is found, the {@link Trie} will call select on that entry and continue
- * calling select for each entry (traversing in order of XOR closeness,
- * NOT lexicographically) until the cursor returns {@link Cursor.Decision#EXIT}.
- * <p>
- * The cursor can return {@link Cursor.Decision#CONTINUE} to continue traversing.
- * <p>
- * {@link Cursor.Decision#REMOVE_AND_EXIT} is used to remove the current element
- * and stop traversing.
- * <p>
- * Note: The {@link Cursor.Decision#REMOVE} operation is not supported.
- *
- * @param key the key to use in the search
- * @param cursor the cursor used throughout the search
- * @return the entry the cursor returned {@link Cursor.Decision#EXIT} on, or null
- * if it continued till the end
- */
- public abstract Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor);
-
@Override
public String toString() {
final StringBuilder buffer = new StringBuilder();
@@ -248,17 +152,13 @@ abstract class AbstractBitwiseTrie<K, V>
protected V value;
- private final int hashCode;
-
public BasicEntry(final K key) {
this.key = key;
- this.hashCode = key != null ? key.hashCode() : 0;
}
public BasicEntry(final K key, final V value) {
this.key = key;
this.value = value;
- this.hashCode = (key != null ? key.hashCode() : 0) ^ (value != null ? value.hashCode() : 0);
}
/**
@@ -285,7 +185,8 @@ abstract class AbstractBitwiseTrie<K, V>
@Override
public int hashCode() {
- return hashCode;
+ return (getKey() == null ? 0 : getKey().hashCode()) ^
+ (getValue() == null ? 0 : getValue().hashCode());
}
@Override
Copied: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java (from r1491621, commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java)
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java?p2=commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java&p1=commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java&r1=1491621&r2=1492866&rev=1492866&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java Thu Jun 13 21:01:00 2013
@@ -16,16 +16,24 @@
*/
package org.apache.commons.collections4.trie;
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
import java.util.AbstractCollection;
+import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
+import java.util.SortedMap;
+import java.util.Map.Entry;
-import org.apache.commons.collections4.Trie.Cursor.Decision;
+import org.apache.commons.collections4.OrderedMapIterator;
/**
* This class implements the base PATRICIA algorithm and everything that
@@ -34,14 +42,12 @@ import org.apache.commons.collections4.T
* @since 4.0
* @version $Id$
*/
-abstract class PatriciaTrieBase<K, V> extends AbstractBitwiseTrie<K, V> {
+abstract class AbstractPatriciaTrie<K, V> extends AbstractBitwiseTrie<K, V> {
private static final long serialVersionUID = 5155253417231339498L;
- /**
- * The root node of the {@link Trie}.
- */
- final TrieEntry<K, V> root = new TrieEntry<K, V>(null, null, -1);
+ /** The root node of the {@link Trie}. */
+ private transient TrieEntry<K, V> root = new TrieEntry<K, V>(null, null, -1);
/**
* Each of these fields are initialized to contain an instance of the
@@ -53,7 +59,7 @@ abstract class PatriciaTrieBase<K, V> ex
private transient volatile Set<Map.Entry<K,V>> entrySet;
/** The current size of the {@link Trie}. */
- private int size = 0;
+ private transient int size = 0;
/**
* The number of times this {@link Trie} has been modified.
@@ -61,7 +67,7 @@ abstract class PatriciaTrieBase<K, V> ex
*/
protected transient int modCount = 0;
- public PatriciaTrieBase(final KeyAnalyzer<? super K> keyAnalyzer) {
+ protected AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
super(keyAnalyzer);
}
@@ -70,11 +76,13 @@ abstract class PatriciaTrieBase<K, V> ex
* {@link KeyAnalyzer} and initializes the {@link org.apache.commons.collections4.Trie Trie}
* with the values from the provided {@link Map}.
*/
- public PatriciaTrieBase(final KeyAnalyzer<? super K> keyAnalyzer, final Map<? extends K, ? extends V> m) {
+ protected AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer,
+ final Map<? extends K, ? extends V> map) {
super(keyAnalyzer);
- putAll(m);
+ putAll(map);
}
+ //-----------------------------------------------------------------------
@Override
public void clear() {
root.key = null;
@@ -253,6 +261,25 @@ abstract class PatriciaTrieBase<K, V> ex
return !entry.isEmpty() && compareKeys(key, entry.key) ? entry : null;
}
+ /**
+ * Returns the {@link Entry} whose key is closest in a bitwise XOR
+ * metric to the given key. This is NOT lexicographic closeness.
+ * For example, given the keys:
+ *
+ * <ol>
+ * <li>D = 1000100
+ * <li>H = 1001000
+ * <li>L = 1001100
+ * </ol>
+ *
+ * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
+ * return 'L', because the XOR distance between D & L is smaller
+ * than the XOR distance between D & H.
+ *
+ * @param key the key to use in the search
+ * @return the {@link Entry} whose key is closest in a bitwise XOR metric
+ * to the provided key
+ */
public Map.Entry<K, V> select(final K key) {
final int lengthInBits = lengthInBits(key);
final Reference<Map.Entry<K, V>> reference = new Reference<Map.Entry<K,V>>();
@@ -262,11 +289,59 @@ abstract class PatriciaTrieBase<K, V> ex
return null;
}
- public Map.Entry<K,V> select(final K key, final Cursor<? super K, ? super V> cursor) {
- final int lengthInBits = lengthInBits(key);
- final Reference<Map.Entry<K, V>> reference = new Reference<Map.Entry<K,V>>();
- selectR(root.left, -1, key, lengthInBits, cursor, reference);
- return reference.get();
+ /**
+ * Returns the key that is closest in a bitwise XOR metric to the
+ * provided key. This is NOT lexicographic closeness!
+ *
+ * For example, given the keys:
+ *
+ * <ol>
+ * <li>D = 1000100
+ * <li>H = 1001000
+ * <li>L = 1001100
+ * </ol>
+ *
+ * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
+ * return 'L', because the XOR distance between D & L is smaller
+ * than the XOR distance between D & H.
+ *
+ * @param key the key to use in the search
+ * @return the key that is closest in a bitwise XOR metric to the provided key
+ */
+ public K selectKey(final K key) {
+ final Map.Entry<K, V> entry = select(key);
+ if (entry == null) {
+ return null;
+ }
+ return entry.getKey();
+ }
+
+ /**
+ * Returns the value whose key is closest in a bitwise XOR metric to
+ * the provided key. This is NOT lexicographic closeness!
+ *
+ * For example, given the keys:
+ *
+ * <ol>
+ * <li>D = 1000100
+ * <li>H = 1001000
+ * <li>L = 1001100
+ * </ol>
+ *
+ * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
+ * return 'L', because the XOR distance between D & L is smaller
+ * than the XOR distance between D & H.
+ *
+ * @param key the key to use in the search
+ * @return the value whose key is closest in a bitwise XOR metric
+ * to the provided key
+ */
+ public V selectValue(final K key) {
+ final Map.Entry<K, V> entry = select(key);
+ if (entry == null) {
+ return null;
+ }
+ return entry.getValue();
}
/**
@@ -300,77 +375,6 @@ abstract class PatriciaTrieBase<K, V> ex
return false;
}
- private boolean selectR(final TrieEntry<K,V> h, final int bitIndex,
- final K key,
- final int lengthInBits,
- final Cursor<? super K, ? super V> cursor,
- final Reference<Map.Entry<K, V>> reference) {
-
- if (h.bitIndex <= bitIndex) {
- if (!h.isEmpty()) {
- final Decision decision = cursor.select(h);
- switch(decision) {
- case REMOVE:
- throw new UnsupportedOperationException("Cannot remove during select");
- case EXIT:
- reference.set(h);
- return false; // exit
- case REMOVE_AND_EXIT:
- final TrieEntry<K, V> entry = new TrieEntry<K, V>(
- h.getKey(), h.getValue(), -1);
- reference.set(entry);
- removeEntry(h);
- return false;
- case CONTINUE:
- // fall through.
- default:
- break;
- }
- }
- return true; // continue
- }
-
- if (!isBitSet(key, h.bitIndex, lengthInBits)) {
- if (selectR(h.left, h.bitIndex, key, lengthInBits, cursor, reference)) {
- return selectR(h.right, h.bitIndex, key, lengthInBits, cursor, reference);
- }
- } else {
- if (selectR(h.right, h.bitIndex, key, lengthInBits, cursor, reference)) {
- return selectR(h.left, h.bitIndex, key, lengthInBits, cursor, reference);
- }
- }
-
- return false;
- }
-
- public Map.Entry<K, V> traverse(final Cursor<? super K, ? super V> cursor) {
- TrieEntry<K, V> entry = nextEntry(null);
- while (entry != null) {
- final TrieEntry<K, V> current = entry;
-
- final Decision decision = cursor.select(current);
- entry = nextEntry(current);
-
- switch(decision) {
- case EXIT:
- return current;
- case REMOVE:
- removeEntry(current);
- break; // out of switch, stay in while loop
- case REMOVE_AND_EXIT:
- final Map.Entry<K, V> value = new TrieEntry<K, V>(
- current.getKey(), current.getValue(), -1);
- removeEntry(current);
- return value;
- case CONTINUE: // do nothing.
- default:
- break;
- }
- }
-
- return null;
- }
-
@Override
public boolean containsKey(final Object k) {
if (k == null) {
@@ -769,354 +773,1676 @@ abstract class PatriciaTrieBase<K, V> ex
}
/**
- * Returns true if 'next' is a valid uplink coming from 'from'.
- */
- static boolean isValidUplink(final TrieEntry<?, ?> next, final TrieEntry<?, ?> from) {
- return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty();
- }
-
- /**
- * A {@link Reference} allows us to return something through a Method's
- * argument list. An alternative would be to an Array with a length of
- * one (1) but that leads to compiler warnings. Computationally and memory
- * wise there's no difference (except for the need to load the
- * {@link Reference} Class but that happens only once).
+ * Gets the standard Map hashCode.
+ *
+ * @return the hash code defined in the Map interface
*/
- private static class Reference<E> {
-
- private E item;
+ @Override
+ public int hashCode() {
+ int total = 0;
+ final Iterator<Entry<K, V>> it = new MyEntryIterator();
- public void set(final E item) {
- this.item = item;
+ while (it.hasNext()) {
+ total += it.next().hashCode();
}
+ return total;
+ }
- public E get() {
- return item;
+ private class MyEntryIterator extends TrieIterator<Map.Entry<K,V>> {
+ public Map.Entry<K,V> next() {
+ return nextEntry();
}
}
- /**
- * A {@link Trie} is a set of {@link TrieEntry} nodes.
- */
- static class TrieEntry<K,V> extends BasicEntry<K, V> {
+ //-----------------------------------------------------------------------
- private static final long serialVersionUID = 4596023148184140013L;
+ public Comparator<? super K> comparator() {
+ return getKeyAnalyzer();
+ }
- /** The index this entry is comparing. */
- protected int bitIndex;
+ public K firstKey() {
+ if (size() == 0) {
+ throw new NoSuchElementException();
+ } else {
+ return firstEntry().getKey();
+ }
+ }
- /** The parent of this entry. */
- protected TrieEntry<K,V> parent;
+ public K lastKey() {
+ final TrieEntry<K, V> entry = lastEntry();
+ if (entry != null) {
+ return entry.getKey();
+ } else {
+ throw new NoSuchElementException();
+ }
+ }
- /** The left child of this entry. */
- protected TrieEntry<K,V> left;
+ public K nextKey(final K key) {
+ if (key == null) {
+ throw new NullPointerException();
+ }
+ final TrieEntry<K, V> entry = getEntry(key);
+ if (entry != null) {
+ final TrieEntry<K, V> nextEntry = nextEntry(entry);
+ return nextEntry != null ? nextEntry.getKey() : null;
+ } else {
+ return null;
+ }
+ }
- /** The right child of this entry. */
- protected TrieEntry<K,V> right;
+ public K previousKey(final K key) {
+ if (key == null) {
+ throw new NullPointerException();
+ }
+ final TrieEntry<K, V> entry = getEntry(key);
+ if (entry != null) {
+ final TrieEntry<K, V> prevEntry = previousEntry(entry);
+ return prevEntry != null ? prevEntry.getKey() : null;
+ } else {
+ return null;
+ }
+ }
- /** The entry who uplinks to this entry. */
- protected TrieEntry<K,V> predecessor;
+ public OrderedMapIterator<K, V> mapIterator() {
+ return new TrieMapIterator();
+ }
- public TrieEntry(final K key, final V value, final int bitIndex) {
- super(key, value);
+ public SortedMap<K, V> prefixMap(final K key) {
+ return getPrefixMapByBits(key, 0, lengthInBits(key));
+ }
- this.bitIndex = bitIndex;
+ /**
+ * Returns a view of this {@link Trie} of all elements that are prefixed
+ * by the number of bits in the given Key.
+ * <p>
+ * The view that this returns is optimized to have a very efficient
+ * {@link Iterator}. The {@link SortedMap#firstKey()},
+ * {@link SortedMap#lastKey()} & {@link Map#size()} methods must
+ * iterate over all possible values in order to determine the results.
+ * This information is cached until the PATRICIA {@link Trie} changes.
+ * All other methods (except {@link Iterator}) must compare the given
+ * key to the prefix to ensure that it is within the range of the view.
+ * The {@link Iterator}'s remove method must also relocate the subtree
+ * that contains the prefixes if the entry holding the subtree is
+ * removed or changes. Changing the subtree takes O(K) time.
+ *
+ * @param key the key to use in the search
+ * @param offsetInBits the prefix offset
+ * @param lengthInBits the number of significant prefix bits
+ * @return a {@link SortedMap} view of this {@link Trie} with all elements whose
+ * key is prefixed by the search key
+ */
+ private SortedMap<K, V> getPrefixMapByBits(final K key, final int offsetInBits, final int lengthInBits) {
- this.parent = null;
- this.left = this;
- this.right = null;
- this.predecessor = this;
+ final int offsetLength = offsetInBits + lengthInBits;
+ if (offsetLength > lengthInBits(key)) {
+ throw new IllegalArgumentException(offsetInBits + " + "
+ + lengthInBits + " > " + lengthInBits(key));
}
- /**
- * Whether or not the entry is storing a key.
- * Only the root can potentially be empty, all other
- * nodes must have a key.
- */
- public boolean isEmpty() {
- return key == null;
+ if (offsetLength == 0) {
+ return this;
}
- /**
- * Neither the left nor right child is a loopback.
- */
- public boolean isInternalNode() {
- return left != this && right != this;
- }
+ return new PrefixRangeMap(key, offsetInBits, lengthInBits);
+ }
- /**
- * Either the left or right child is a loopback.
- */
- public boolean isExternalNode() {
- return !isInternalNode();
- }
+ public SortedMap<K, V> headMap(final K toKey) {
+ return new RangeEntryMap(null, toKey);
+ }
- @Override
- public String toString() {
- final StringBuilder buffer = new StringBuilder();
+ public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
+ return new RangeEntryMap(fromKey, toKey);
+ }
- if (bitIndex == -1) {
- buffer.append("RootEntry(");
- } else {
- buffer.append("Entry(");
- }
+ public SortedMap<K, V> tailMap(final K fromKey) {
+ return new RangeEntryMap(fromKey, null);
+ }
- buffer.append("key=").append(getKey()).append(" [").append(bitIndex).append("], ");
- buffer.append("value=").append(getValue()).append(", ");
- //buffer.append("bitIndex=").append(bitIndex).append(", ");
+ /**
+ * Returns an entry strictly higher than the given key,
+ * or null if no such entry exists.
+ */
+ TrieEntry<K,V> higherEntry(final 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.)
+ final int lengthInBits = lengthInBits(key);
- if (parent != null) {
- if (parent.bitIndex == -1) {
- buffer.append("parent=").append("ROOT");
- } else {
- buffer.append("parent=").append(parent.getKey()).append(" [").append(parent.bitIndex).append("]");
+ if (lengthInBits == 0) {
+ if (!root.isEmpty()) {
+ // If data in root, and more after -- return it.
+ if (size() > 1) {
+ return nextEntry(root);
+ } else { // If no more after, no higher entry.
+ return null;
}
} else {
- buffer.append("parent=").append("null");
+ // Root is empty & we want something after empty, return first.
+ return firstEntry();
}
- buffer.append(", ");
+ }
- if (left != null) {
- if (left.bitIndex == -1) {
- buffer.append("left=").append("ROOT");
- } else {
- buffer.append("left=").append(left.getKey()).append(" [").append(left.bitIndex).append("]");
- }
- } else {
- buffer.append("left=").append("null");
- }
- buffer.append(", ");
+ final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
+ if (compareKeys(key, found.key)) {
+ return nextEntry(found);
+ }
- if (right != null) {
- if (right.bitIndex == -1) {
- buffer.append("right=").append("ROOT");
- } else {
- buffer.append("right=").append(right.getKey()).append(" [").append(right.bitIndex).append("]");
- }
+ final int bitIndex = bitIndex(key, found.key);
+ if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
+ final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
+ addEntry(added, lengthInBits);
+ incrementSize(); // must increment because remove will decrement
+ final TrieEntry<K, V> ceil = nextEntry(added);
+ removeEntry(added);
+ modCount -= 2; // we didn't really modify it.
+ return ceil;
+ } else if (KeyAnalyzer.isNullBitKey(bitIndex)) {
+ if (!root.isEmpty()) {
+ return firstEntry();
+ } else if (size() > 1) {
+ return nextEntry(firstEntry());
} else {
- buffer.append("right=").append("null");
- }
- buffer.append(", ");
-
- if (predecessor != null) {
- if(predecessor.bitIndex == -1) {
- buffer.append("predecessor=").append("ROOT");
- } else {
- buffer.append("predecessor=").append(predecessor.getKey()).append(" [").
- append(predecessor.bitIndex).append("]");
- }
+ return null;
}
-
- buffer.append(")");
- return buffer.toString();
+ } else if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
+ return nextEntry(found);
}
- }
+ // we should have exited above.
+ throw new IllegalStateException("invalid lookup: " + key);
+ }
/**
- * This is a entry set view of the {@link Trie} as returned by {@link Map#entrySet()}.
+ * 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.
*/
- private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
-
- @Override
- public Iterator<Map.Entry<K,V>> iterator() {
- return new EntryIterator();
- }
+ TrieEntry<K,V> ceilingEntry(final 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.)
+ final int lengthInBits = lengthInBits(key);
- @Override
- public boolean contains(final Object o) {
- if (!(o instanceof Map.Entry)) {
- return false;
+ if (lengthInBits == 0) {
+ if (!root.isEmpty()) {
+ return root;
+ } else {
+ return firstEntry();
}
-
- final TrieEntry<K,V> candidate = getEntry(((Map.Entry<?, ?>)o).getKey());
- return candidate != null && candidate.equals(o);
- }
-
- @Override
- public boolean remove(final Object o) {
- final int size = size();
- PatriciaTrieBase.this.remove(o);
- return size != size();
- }
-
- @Override
- public int size() {
- return PatriciaTrieBase.this.size();
}
- @Override
- public void clear() {
- PatriciaTrieBase.this.clear();
+ final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
+ if (compareKeys(key, found.key)) {
+ return found;
}
- /**
- * An {@link Iterator} that returns {@link Entry} Objects.
- */
- private class EntryIterator extends TrieIterator<Map.Entry<K,V>> {
- public Map.Entry<K,V> next() {
- return nextEntry();
+ final int bitIndex = bitIndex(key, found.key);
+ if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
+ final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
+ addEntry(added, lengthInBits);
+ incrementSize(); // must increment because remove will decrement
+ final TrieEntry<K, V> ceil = nextEntry(added);
+ removeEntry(added);
+ modCount -= 2; // we didn't really modify it.
+ return ceil;
+ } else if (KeyAnalyzer.isNullBitKey(bitIndex)) {
+ if (!root.isEmpty()) {
+ return root;
+ } else {
+ return firstEntry();
}
+ } else if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
+ return found;
}
+
+ // we should have exited above.
+ throw new IllegalStateException("invalid lookup: " + key);
}
/**
- * This is a key set view of the {@link Trie} as returned by {@link Map#keySet()}.
+ * Returns a key-value mapping associated with the greatest key
+ * strictly less than the given key, or null if there is no such key.
*/
- private class KeySet extends AbstractSet<K> {
+ TrieEntry<K,V> lowerEntry(final 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).
- @Override
- public Iterator<K> iterator() {
- return new KeyIterator();
- }
+ // 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.)
+ final int lengthInBits = lengthInBits(key);
+
+ if (lengthInBits == 0) {
+ return null; // there can never be anything before root.
+ }
+
+ final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
+ if (compareKeys(key, found.key)) {
+ return previousEntry(found);
+ }
+
+ final int bitIndex = bitIndex(key, found.key);
+ if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
+ final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
+ addEntry(added, lengthInBits);
+ incrementSize(); // must increment because remove will decrement
+ final TrieEntry<K, V> prior = previousEntry(added);
+ removeEntry(added);
+ modCount -= 2; // we didn't really modify it.
+ return prior;
+ } else if (KeyAnalyzer.isNullBitKey(bitIndex)) {
+ return null;
+ } else if (KeyAnalyzer.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(final 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.)
+ final int lengthInBits = lengthInBits(key);
+
+ if (lengthInBits == 0) {
+ if (!root.isEmpty()) {
+ return root;
+ } else {
+ return null;
+ }
+ }
+
+ final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
+ if (compareKeys(key, found.key)) {
+ return found;
+ }
+
+ final int bitIndex = bitIndex(key, found.key);
+ if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
+ final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
+ addEntry(added, lengthInBits);
+ incrementSize(); // must increment because remove will decrement
+ final TrieEntry<K, V> floor = previousEntry(added);
+ removeEntry(added);
+ modCount -= 2; // we didn't really modify it.
+ return floor;
+ } else if (KeyAnalyzer.isNullBitKey(bitIndex)) {
+ if (!root.isEmpty()) {
+ return root;
+ } else {
+ return null;
+ }
+ } else if (KeyAnalyzer.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.
+ */
+ TrieEntry<K, V> subtree(final K prefix, final int offsetInBits, final int lengthInBits) {
+ TrieEntry<K, V> current = root.left;
+ TrieEntry<K, V> path = root;
+ while(true) {
+ if (current.bitIndex <= path.bitIndex || lengthInBits < current.bitIndex) {
+ break;
+ }
+
+ path = current;
+ if (!isBitSet(prefix, offsetInBits + current.bitIndex, offsetInBits + lengthInBits)) {
+ current = current.left;
+ } else {
+ current = current.right;
+ }
+ }
+
+ // Make sure the entry is valid for a subtree.
+ final TrieEntry<K, V> entry = current.isEmpty() ? path : current;
+
+ // If entry is root, it can't be empty.
+ if (entry.isEmpty()) {
+ return null;
+ }
+
+ final int endIndexInBits = offsetInBits + lengthInBits;
+
+ // 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()) < endIndexInBits) {
+ return null;
+ }
+
+ // Found key's length-th bit differs from our key
+ // which means it cannot be the prefix...
+ if (isBitSet(prefix, endIndexInBits, endIndexInBits)
+ != isBitSet(entry.key, lengthInBits, lengthInBits(entry.key))) {
+ return null;
+ }
+
+ // ... or there are less than 'length' equal bits
+ final int bitIndex = getKeyAnalyzer().bitIndex(prefix, offsetInBits, lengthInBits,
+ entry.key, 0, lengthInBits(entry.getKey()));
+
+ if (bitIndex >= 0 && bitIndex < lengthInBits) {
+ return null;
+ }
+
+ return 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.
+ */
+ TrieEntry<K, V> lastEntry() {
+ return followRight(root.left);
+ }
+
+ /**
+ * Traverses down the right path until it finds an uplink.
+ */
+ 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
+ */
+ TrieEntry<K, V> previousEntry(final TrieEntry<K, V> start) {
+ if (start.predecessor == null) {
+ throw new IllegalArgumentException("must have come from somewhere!");
+ }
+
+ if (start.predecessor.right == start) {
+ if (isValidUplink(start.predecessor.left, start.predecessor)) {
+ return start.predecessor.left;
+ } else {
+ return followRight(start.predecessor.left);
+ }
+ } else {
+ 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) {
+ if (root.isEmpty()) {
+ return null;
+ } else {
+ return 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.
+ */
+ TrieEntry<K, V> nextEntryInSubtree(final TrieEntry<K, V> node,
+ final TrieEntry<K, V> parentOfSubtree) {
+ if (node == null) {
+ return firstEntry();
+ } else {
+ return nextEntryImpl(node.predecessor, node, parentOfSubtree);
+ }
+ }
+
+ /**
+ * Returns true if 'next' is a valid uplink coming from 'from'.
+ */
+ static boolean isValidUplink(final TrieEntry<?, ?> next, final TrieEntry<?, ?> from) {
+ return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty();
+ }
+
+ /**
+ * A {@link Reference} allows us to return something through a Method's
+ * argument list. An alternative would be to an Array with a length of
+ * one (1) but that leads to compiler warnings. Computationally and memory
+ * wise there's no difference (except for the need to load the
+ * {@link Reference} Class but that happens only once).
+ */
+ private static class Reference<E> {
+
+ private E item;
+
+ public void set(final E item) {
+ this.item = item;
+ }
+
+ public E get() {
+ return item;
+ }
+ }
+
+ /**
+ * A {@link Trie} is a set of {@link TrieEntry} nodes.
+ */
+ protected static class TrieEntry<K,V> extends BasicEntry<K, V> {
+
+ private static final long serialVersionUID = 4596023148184140013L;
+
+ /** The index this entry is comparing. */
+ protected int bitIndex;
+
+ /** The parent of this entry. */
+ protected TrieEntry<K,V> parent;
+
+ /** The left child of this entry. */
+ protected TrieEntry<K,V> left;
+
+ /** The right child of this entry. */
+ protected TrieEntry<K,V> right;
+
+ /** The entry who uplinks to this entry. */
+ protected TrieEntry<K,V> predecessor;
+
+ public TrieEntry(final K key, final V value, final int bitIndex) {
+ super(key, value);
+
+ this.bitIndex = bitIndex;
+
+ this.parent = null;
+ this.left = this;
+ this.right = null;
+ this.predecessor = this;
+ }
+
+ /**
+ * Whether or not the entry is storing a key.
+ * Only the root can potentially be empty, all other
+ * nodes must have a key.
+ */
+ public boolean isEmpty() {
+ return key == null;
+ }
+
+ /**
+ * Neither the left nor right child is a loopback.
+ */
+ public boolean isInternalNode() {
+ return left != this && right != this;
+ }
+
+ /**
+ * Either the left or right child is a loopback.
+ */
+ public boolean isExternalNode() {
+ return !isInternalNode();
+ }
+
+ @Override
+ public String toString() {
+ final StringBuilder buffer = new StringBuilder();
+
+ if (bitIndex == -1) {
+ buffer.append("RootEntry(");
+ } else {
+ buffer.append("Entry(");
+ }
+
+ buffer.append("key=").append(getKey()).append(" [").append(bitIndex).append("], ");
+ buffer.append("value=").append(getValue()).append(", ");
+ //buffer.append("bitIndex=").append(bitIndex).append(", ");
+
+ if (parent != null) {
+ if (parent.bitIndex == -1) {
+ buffer.append("parent=").append("ROOT");
+ } else {
+ buffer.append("parent=").append(parent.getKey()).append(" [").append(parent.bitIndex).append("]");
+ }
+ } else {
+ buffer.append("parent=").append("null");
+ }
+ buffer.append(", ");
+
+ if (left != null) {
+ if (left.bitIndex == -1) {
+ buffer.append("left=").append("ROOT");
+ } else {
+ buffer.append("left=").append(left.getKey()).append(" [").append(left.bitIndex).append("]");
+ }
+ } else {
+ buffer.append("left=").append("null");
+ }
+ buffer.append(", ");
+
+ if (right != null) {
+ if (right.bitIndex == -1) {
+ buffer.append("right=").append("ROOT");
+ } else {
+ buffer.append("right=").append(right.getKey()).append(" [").append(right.bitIndex).append("]");
+ }
+ } else {
+ buffer.append("right=").append("null");
+ }
+ buffer.append(", ");
+
+ if (predecessor != null) {
+ if(predecessor.bitIndex == -1) {
+ buffer.append("predecessor=").append("ROOT");
+ } else {
+ buffer.append("predecessor=").append(predecessor.getKey()).append(" [").
+ append(predecessor.bitIndex).append("]");
+ }
+ }
+
+ buffer.append(")");
+ return buffer.toString();
+ }
+ }
+
+
+ /**
+ * This is a entry set view of the {@link Trie} as returned by {@link Map#entrySet()}.
+ */
+ private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
+
+ @Override
+ public Iterator<Map.Entry<K,V>> iterator() {
+ return new EntryIterator();
+ }
+
+ @Override
+ public boolean contains(final Object o) {
+ if (!(o instanceof Map.Entry)) {
+ return false;
+ }
+
+ final TrieEntry<K,V> candidate = getEntry(((Map.Entry<?, ?>)o).getKey());
+ return candidate != null && candidate.equals(o);
+ }
+
+ @Override
+ public boolean remove(final Object obj) {
+ if (obj instanceof Map.Entry == false) {
+ return false;
+ }
+ if (contains(obj) == false) {
+ return false;
+ }
+ final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
+ AbstractPatriciaTrie.this.remove(entry.getKey());
+ return true;
+ }
+
+ @Override
+ public int size() {
+ return AbstractPatriciaTrie.this.size();
+ }
+
+ @Override
+ public void clear() {
+ AbstractPatriciaTrie.this.clear();
+ }
+
+ /**
+ * An {@link Iterator} that returns {@link Entry} Objects.
+ */
+ private class EntryIterator extends TrieIterator<Map.Entry<K,V>> {
+ public Map.Entry<K,V> next() {
+ return nextEntry();
+ }
+ }
+ }
+
+ /**
+ * This is a key set view of the {@link Trie} as returned by {@link Map#keySet()}.
+ */
+ private class KeySet extends AbstractSet<K> {
+
+ @Override
+ public Iterator<K> iterator() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public int size() {
+ return AbstractPatriciaTrie.this.size();
+ }
+
+ @Override
+ public boolean contains(final Object o) {
+ return containsKey(o);
+ }
+
+ @Override
+ public boolean remove(final Object o) {
+ final int size = size();
+ AbstractPatriciaTrie.this.remove(o);
+ return size != size();
+ }
+
+ @Override
+ public void clear() {
+ AbstractPatriciaTrie.this.clear();
+ }
+
+ /**
+ * An {@link Iterator} that returns Key Objects.
+ */
+ private class KeyIterator extends TrieIterator<K> {
+ public K next() {
+ return nextEntry().getKey();
+ }
+ }
+ }
+
+ /**
+ * This is a value view of the {@link Trie} as returned by {@link Map#values()}.
+ */
+ private class Values extends AbstractCollection<V> {
+
+ @Override
+ public Iterator<V> iterator() {
+ return new ValueIterator();
+ }
@Override
public int size() {
- return PatriciaTrieBase.this.size();
+ return AbstractPatriciaTrie.this.size();
+ }
+
+ @Override
+ public boolean contains(final Object o) {
+ return containsValue(o);
+ }
+
+ @Override
+ public void clear() {
+ AbstractPatriciaTrie.this.clear();
+ }
+
+ @Override
+ public boolean remove(final Object o) {
+ for (final Iterator<V> it = iterator(); it.hasNext(); ) {
+ final V value = it.next();
+ if (compare(value, o)) {
+ it.remove();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * An {@link Iterator} that returns Value Objects.
+ */
+ private class ValueIterator extends TrieIterator<V> {
+ public V next() {
+ return nextEntry().getValue();
+ }
+ }
+ }
+
+ /**
+ * An iterator for the entries.
+ */
+ abstract class TrieIterator<E> implements Iterator<E> {
+
+ /** For fast-fail. */
+ protected int expectedModCount = AbstractPatriciaTrie.this.modCount;
+
+ protected TrieEntry<K, V> next; // the next node to return
+ protected TrieEntry<K, V> current; // the current entry we're on
+
+ /**
+ * Starts iteration from the root.
+ */
+ protected TrieIterator() {
+ next = AbstractPatriciaTrie.this.nextEntry(null);
+ }
+
+ /**
+ * Starts iteration at the given entry.
+ */
+ protected TrieIterator(final TrieEntry<K, V> firstEntry) {
+ next = firstEntry;
+ }
+
+ /**
+ * Returns the next {@link TrieEntry}.
+ */
+ protected TrieEntry<K,V> nextEntry() {
+ if (expectedModCount != AbstractPatriciaTrie.this.modCount) {
+ throw new ConcurrentModificationException();
+ }
+
+ final TrieEntry<K,V> e = next;
+ if (e == null) {
+ throw new NoSuchElementException();
+ }
+
+ next = findNext(e);
+ current = e;
+ return e;
+ }
+
+ /**
+ * @see PatriciaTrie#nextEntry(TrieEntry)
+ */
+ protected TrieEntry<K, V> findNext(final TrieEntry<K, V> prior) {
+ return AbstractPatriciaTrie.this.nextEntry(prior);
+ }
+
+ public boolean hasNext() {
+ return next != null;
+ }
+
+ public void remove() {
+ if (current == null) {
+ throw new IllegalStateException();
+ }
+
+ if (expectedModCount != AbstractPatriciaTrie.this.modCount) {
+ throw new ConcurrentModificationException();
+ }
+
+ final TrieEntry<K, V> node = current;
+ current = null;
+ AbstractPatriciaTrie.this.removeEntry(node);
+
+ expectedModCount = AbstractPatriciaTrie.this.modCount;
+ }
+ }
+
+ /**
+ * An {@link OrderedMapIterator} for a {@link Trie}.
+ */
+ private class TrieMapIterator extends TrieIterator<K> implements OrderedMapIterator<K, V> {
+
+ protected TrieEntry<K, V> previous; // the previous node to return
+
+ public K next() {
+ return nextEntry().getKey();
+ }
+
+ public K getKey() {
+ if (current == null) {
+ throw new IllegalStateException();
+ }
+ return current.getKey();
+ }
+
+ public V getValue() {
+ if (current == null) {
+ throw new IllegalStateException();
+ }
+ return current.getValue();
+ }
+
+ public V setValue(final V value) {
+ if (current == null) {
+ throw new IllegalStateException();
+ }
+ return current.setValue(value);
+ }
+
+ public boolean hasPrevious() {
+ return previous != null;
+ }
+
+ public K previous() {
+ return previousEntry().getKey();
+ }
+
+ @Override
+ protected TrieEntry<K, V> nextEntry() {
+ final TrieEntry<K, V> nextEntry = super.nextEntry();
+ previous = nextEntry;
+ return nextEntry;
+ }
+
+ protected TrieEntry<K,V> previousEntry() {
+ if (expectedModCount != AbstractPatriciaTrie.this.modCount) {
+ throw new ConcurrentModificationException();
+ }
+
+ final TrieEntry<K,V> e = previous;
+ if (e == null) {
+ throw new NoSuchElementException();
+ }
+
+ previous = AbstractPatriciaTrie.this.previousEntry(e);
+ next = current;
+ current = e;
+ return current;
+ }
+
+ }
+
+ /**
+ * 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();
+
+ public Comparator<? super K> comparator() {
+ return AbstractPatriciaTrie.this.comparator();
+ }
+
+ @Override
+ public boolean containsKey(final Object key) {
+ if (!inRange(castKey(key))) {
+ return false;
+ }
+
+ return AbstractPatriciaTrie.this.containsKey(key);
+ }
+
+ @Override
+ public V remove(final Object key) {
+ if (!inRange(castKey(key))) {
+ return null;
+ }
+
+ return AbstractPatriciaTrie.this.remove(key);
+ }
+
+ @Override
+ public V get(final Object key) {
+ if (!inRange(castKey(key))) {
+ return null;
+ }
+
+ return AbstractPatriciaTrie.this.get(key);
+ }
+
+ @Override
+ public V put(final K key, final V value) {
+ if (!inRange(key)) {
+ throw new IllegalArgumentException("Key is out of range: " + key);
+ }
+ return AbstractPatriciaTrie.this.put(key, value);
+ }
+
+ @Override
+ public Set<Map.Entry<K, V>> entrySet() {
+ if (entrySet == null) {
+ entrySet = createEntrySet();
+ }
+ return entrySet;
+ }
+
+ public SortedMap<K, V> subMap(final K fromKey, final 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 boolean contains(final Object o) {
- return containsKey(o);
+ public SortedMap<K, V> headMap(final K toKey) {
+ if (!inRange2(toKey)) {
+ throw new IllegalArgumentException("ToKey is out of range: " + toKey);
+ }
+ return createRangeMap(getFromKey(), isFromInclusive(), toKey, isToInclusive());
}
- @Override
- public boolean remove(final Object o) {
- final int size = size();
- PatriciaTrieBase.this.remove(o);
- return size != size();
+ public SortedMap<K, V> tailMap(final K fromKey) {
+ if (!inRange2(fromKey)) {
+ throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
+ }
+ return createRangeMap(fromKey, isFromInclusive(), getToKey(), isToInclusive());
}
- @Override
- public void clear() {
- PatriciaTrieBase.this.clear();
+ /**
+ * Returns true if the provided key is greater than TO and less than FROM.
+ */
+ protected boolean inRange(final K key) {
+ final K fromKey = getFromKey();
+ final K toKey = getToKey();
+
+ return (fromKey == null || inFromRange(key, false)) && (toKey == null || inToRange(key, false));
}
/**
- * An {@link Iterator} that returns Key Objects.
+ * This form allows the high endpoint (as well as all legit keys).
*/
- private class KeyIterator extends TrieIterator<K> {
- public K next() {
- return nextEntry().getKey();
+ protected boolean inRange2(final K key) {
+ final K fromKey = getFromKey();
+ final 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(final K key, final boolean forceInclusive) {
+ final K fromKey = getFromKey();
+ final boolean fromInclusive = isFromInclusive();
+
+ final int ret = getKeyAnalyzer().compare(key, fromKey);
+ if (fromInclusive || forceInclusive) {
+ return ret >= 0;
+ } else {
+ return ret > 0;
+ }
+ }
+
+ /**
+ * Returns true if the provided key is in the TO range of the {@link RangeMap}.
+ */
+ protected boolean inToRange(final K key, final boolean forceInclusive) {
+ final K toKey = getToKey();
+ final boolean toInclusive = isToInclusive();
+
+ final int ret = getKeyAnalyzer().compare(key, toKey);
+ if (toInclusive || forceInclusive) {
+ return ret <= 0;
+ } else {
+ return 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);
}
- /**
- * This is a value view of the {@link Trie} as returned by {@link Map#values()}.
+ /**
+ * A {@link RangeMap} that deals with {@link Entry}s.
+ */
+ private class RangeEntryMap extends RangeMap {
+
+ /** The key to start from, null if the beginning. */
+ private final K fromKey;
+
+ /** The key to end at, null if till the end. */
+ private final K toKey;
+
+ /** Whether or not the 'from' is inclusive. */
+ private final boolean fromInclusive;
+
+ /** Whether or not the 'to' is inclusive. */
+ private final boolean toInclusive;
+
+ /**
+ * Creates a {@link RangeEntryMap} with the fromKey included and
+ * the toKey excluded from the range.
+ */
+ protected RangeEntryMap(final K fromKey, final K toKey) {
+ this(fromKey, true, toKey, false);
+ }
+
+ /**
+ * Creates a {@link RangeEntryMap}.
+ */
+ protected RangeEntryMap(final K fromKey, final boolean fromInclusive,
+ final K toKey, final boolean toInclusive) {
+
+ if (fromKey == null && toKey == null) {
+ throw new IllegalArgumentException("must have a from or to!");
+ }
+
+ if (fromKey != null && toKey != null && getKeyAnalyzer().compare(fromKey, toKey) > 0) {
+ throw new IllegalArgumentException("fromKey > toKey");
+ }
+
+ this.fromKey = fromKey;
+ this.fromInclusive = fromInclusive;
+ this.toKey = toKey;
+ this.toInclusive = toInclusive;
+ }
+
+ public K firstKey() {
+ Map.Entry<K,V> e = null;
+ if (fromKey == null) {
+ e = firstEntry();
+ } else {
+ if (fromInclusive) {
+ e = ceilingEntry(fromKey);
+ } else {
+ e = higherEntry(fromKey);
+ }
+ }
+
+ final K first = e != null ? e.getKey() : null;
+ if (e == null || toKey != null && !inToRange(first, false)) {
+ throw new NoSuchElementException();
+ }
+ return first;
+ }
+
+ public K lastKey() {
+ Map.Entry<K,V> e;
+ if (toKey == null) {
+ e = lastEntry();
+ } else {
+ if (toInclusive) {
+ e = floorEntry(toKey);
+ } else {
+ e = lowerEntry(toKey);
+ }
+ }
+
+ final 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(final K fromKey, final boolean fromInclusive,
+ final K toKey, final boolean toInclusive) {
+ return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
+ }
+ }
+
+ /**
+ * A {@link Set} view of a {@link RangeMap}.
*/
- private class Values extends AbstractCollection<V> {
+ private class RangeEntrySet extends AbstractSet<Map.Entry<K, V>> {
+
+ private final RangeMap delegate;
+
+ private transient int size = -1;
+
+ private transient int expectedModCount;
+
+ /**
+ * Creates a {@link RangeEntrySet}.
+ */
+ public RangeEntrySet(final RangeMap delegate) {
+ if (delegate == null) {
+ throw new NullPointerException("delegate");
+ }
+
+ this.delegate = delegate;
+ }
@Override
- public Iterator<V> iterator() {
- return new ValueIterator();
+ public Iterator<Map.Entry<K, V>> iterator() {
+ final K fromKey = delegate.getFromKey();
+ final K toKey = delegate.getToKey();
+
+ TrieEntry<K, V> first = null;
+ if (fromKey == null) {
+ first = firstEntry();
+ } else {
+ first = ceilingEntry(fromKey);
+ }
+
+ TrieEntry<K, V> last = null;
+ if (toKey != null) {
+ last = ceilingEntry(toKey);
+ }
+
+ return new EntryIterator(first, last);
}
@Override
public int size() {
- return PatriciaTrieBase.this.size();
+ if (size == -1 || expectedModCount != AbstractPatriciaTrie.this.modCount) {
+ size = 0;
+
+ for (final Iterator<?> it = iterator(); it.hasNext(); it.next()) {
+ ++size;
+ }
+
+ expectedModCount = AbstractPatriciaTrie.this.modCount;
+ }
+ return size;
}
@Override
- public boolean contains(final Object o) {
- return containsValue(o);
+ public boolean isEmpty() {
+ return !iterator().hasNext();
}
+ @SuppressWarnings("unchecked")
@Override
- public void clear() {
- PatriciaTrieBase.this.clear();
+ public boolean contains(final Object o) {
+ if (!(o instanceof Map.Entry)) {
+ return false;
+ }
+
+ final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
+ final K key = entry.getKey();
+ if (!delegate.inRange(key)) {
+ return false;
+ }
+
+ final TrieEntry<K, V> node = getEntry(key);
+ return node != null && compare(node.getValue(), entry.getValue());
}
+ @SuppressWarnings("unchecked")
@Override
public boolean remove(final Object o) {
- for (final Iterator<V> it = iterator(); it.hasNext(); ) {
- final V value = it.next();
- if (compare(value, o)) {
- it.remove();
- return true;
- }
+ if (!(o instanceof Map.Entry)) {
+ return false;
+ }
+
+ final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
+ final K key = entry.getKey();
+ if (!delegate.inRange(key)) {
+ return false;
+ }
+
+ final TrieEntry<K, V> node = getEntry(key);
+ if (node != null && compare(node.getValue(), entry.getValue())) {
+ removeEntry(node);
+ return true;
}
return false;
}
/**
- * An {@link Iterator} that returns Value Objects.
+ * An {@link Iterator} for {@link RangeEntrySet}s.
*/
- private class ValueIterator extends TrieIterator<V> {
- public V next() {
- return nextEntry().getValue();
+ private final class EntryIterator extends TrieIterator<Map.Entry<K,V>> {
+
+ private final K excludedKey;
+
+ /**
+ * Creates a {@link EntryIterator}.
+ */
+ private EntryIterator(final TrieEntry<K,V> first, final TrieEntry<K,V> last) {
+ super(first);
+ this.excludedKey = last != null ? last.getKey() : null;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return next != null && !compare(next.key, excludedKey);
+ }
+
+ public Map.Entry<K,V> next() {
+ if (next == null || compare(next.key, excludedKey)) {
+ throw new NoSuchElementException();
+ }
+ return nextEntry();
}
}
}
/**
- * An iterator for the entries.
+ * A submap used for prefix views over the {@link Trie}.
*/
- abstract class TrieIterator<E> implements Iterator<E> {
+ private class PrefixRangeMap extends RangeMap {
- /** For fast-fail. */
- protected int expectedModCount = PatriciaTrieBase.this.modCount;
+ private final K prefix;
- protected TrieEntry<K, V> next; // the next node to return
- protected TrieEntry<K, V> current; // the current entry we're on
+ private final int offsetInBits;
+
+ private final int lengthInBits;
+
+ private K fromKey = null;
+
+ private K toKey = null;
+
+ private transient int expectedModCount = 0;
+
+ private int size = -1;
/**
- * Starts iteration from the root.
+ * Creates a {@link PrefixRangeMap}.
*/
- protected TrieIterator() {
- next = PatriciaTrieBase.this.nextEntry(null);
+ private PrefixRangeMap(final K prefix, final int offsetInBits, final int lengthInBits) {
+ this.prefix = prefix;
+ this.offsetInBits = offsetInBits;
+ this.lengthInBits = lengthInBits;
}
/**
- * Starts iteration at the given entry.
+ * This method does two things. It determines 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.
*/
- protected TrieIterator(final TrieEntry<K, V> firstEntry) {
- next = firstEntry;
+ private int fixup() {
+ // The trie has changed since we last found our toKey / fromKey
+ if (size == - 1 || AbstractPatriciaTrie.this.modCount != expectedModCount) {
+ final 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) {
+ final 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 = AbstractPatriciaTrie.this.modCount;
+ }
+
+ return size;
}
- /**
- * Returns the next {@link TrieEntry}.
- */
- protected TrieEntry<K,V> nextEntry() {
- if (expectedModCount != PatriciaTrieBase.this.modCount) {
- throw new ConcurrentModificationException();
+ public K firstKey() {
+ fixup();
+
+ Map.Entry<K,V> e = null;
+ if (fromKey == null) {
+ e = firstEntry();
+ } else {
+ e = higherEntry(fromKey);
}
- final TrieEntry<K,V> e = next;
- if (e == null) {
+ final K first = e != null ? e.getKey() : null;
+ if (e == null || !getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, first)) {
throw new NoSuchElementException();
}
- next = findNext(e);
- current = e;
- return e;
+ return first;
+ }
+
+ public K lastKey() {
+ fixup();
+
+ Map.Entry<K,V> e = null;
+ if (toKey == null) {
+ e = lastEntry();
+ } else {
+ e = lowerEntry(toKey);
+ }
+
+ final K last = e != null ? e.getKey() : null;
+ if (e == null || !getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, last)) {
+ throw new NoSuchElementException();
+ }
+
+ return last;
}
/**
- * @see PatriciaTrie#nextEntry(TrieEntry)
+ * Returns true if this {@link PrefixRangeMap}'s key is a prefix of the provided key.
*/
- protected TrieEntry<K, V> findNext(final TrieEntry<K, V> prior) {
- return PatriciaTrieBase.this.nextEntry(prior);
+ @Override
+ protected boolean inRange(final K key) {
+ return getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, key);
}
- public boolean hasNext() {
- return next != null;
+ /**
+ * Same as {@link #inRange(Object)}.
+ */
+ @Override
+ protected boolean inRange2(final K key) {
+ return inRange(key);
}
- public void remove() {
- if (current == null) {
- throw new IllegalStateException();
+ /**
+ * Returns true if the provided Key is in the FROM range of the {@link PrefixRangeMap}.
+ */
+ @Override
+ protected boolean inFromRange(final K key, final boolean forceInclusive) {
+ return getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, key);
+ }
+
+ /**
+ * Returns true if the provided Key is in the TO range of the {@link PrefixRangeMap}.
+ */
+ @Override
+ protected boolean inToRange(final K key, final boolean forceInclusive) {
+ return getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, key);
+ }
+
+ @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(final K fromKey, final boolean fromInclusive,
+ final K toKey, final 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 = 0;
+
+ /**
+ * Creates a {@link PrefixRangeEntrySet}.
+ */
+ public PrefixRangeEntrySet(final PrefixRangeMap delegate) {
+ super(delegate);
+ this.delegate = delegate;
+ }
+
+ @Override
+ public int size() {
+ return delegate.fixup();
+ }
+
+ @Override
+ public Iterator<Map.Entry<K,V>> iterator() {
+ if (AbstractPatriciaTrie.this.modCount != expectedModCount) {
+ prefixStart = subtree(delegate.prefix, delegate.offsetInBits, delegate.lengthInBits);
+ expectedModCount = AbstractPatriciaTrie.this.modCount;
}
- if (expectedModCount != PatriciaTrieBase.this.modCount) {
- throw new ConcurrentModificationException();
+ if (prefixStart == null) {
+ final Set<Map.Entry<K,V>> empty = Collections.emptySet();
+ return empty.iterator();
+ } else if (delegate.lengthInBits >= prefixStart.bitIndex) {
+ return new SingletonIterator(prefixStart);
+ } else {
+ return new EntryIterator(prefixStart, delegate.prefix, delegate.offsetInBits, delegate.lengthInBits);
}
+ }
- final TrieEntry<K, V> node = current;
- current = null;
- PatriciaTrieBase.this.removeEntry(node);
+ /**
+ * 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(final TrieEntry<K, V> entry) {
+ this.entry = entry;
+ }
+
+ public boolean hasNext() {
+ return hit == 0;
+ }
+
+ public Map.Entry<K, V> next() {
+ if (hit != 0) {
+ throw new NoSuchElementException();
+ }
+
+ ++hit;
+ return entry;
+ }
+
+ public void remove() {
+ if (hit != 1) {
+ throw new IllegalStateException();
+ }
+
+ ++hit;
+ AbstractPatriciaTrie.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.
+ private final K prefix;
+ private final int offset;
+ private final int lengthInBits;
+ private boolean lastOne;
+
+ private TrieEntry<K, V> subtree; // the subtree to search within
+
+ /**
+ * Starts iteration at the given entry & search only
+ * within the given subtree.
+ */
+ EntryIterator(final TrieEntry<K, V> startScan, final K prefix,
+ final int offset, final int lengthInBits) {
+ subtree = startScan;
+ next = AbstractPatriciaTrie.this.followLeft(startScan);
+ this.prefix = prefix;
+ this.offset = offset;
+ this.lengthInBits = lengthInBits;
+ }
+
+ public Map.Entry<K,V> next() {
+ final Map.Entry<K, V> entry = nextEntry();
+ if (lastOne) {
+ next = null;
+ }
+ return entry;
+ }
+
+ @Override
+ protected TrieEntry<K, V> findNext(final TrieEntry<K, V> prior) {
+ return AbstractPatriciaTrie.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;
+ final int bitIdx = subtree.bitIndex;
+ if (current == subtree) {
+ needsFixing = true;
+ }
+
+ super.remove();
- expectedModCount = PatriciaTrieBase.this.modCount;
+ // If the subtree changed its bitIndex or we
+ // removed the old subtree, get a new one.
+ if (bitIdx != subtree.bitIndex || needsFixing) {
+ subtree = subtree(prefix, offset, lengthInBits);
+ }
+
+ // If the subtree's bitIndex is less than the
+ // length of our prefix, it's the last item
+ // in the prefix tree.
+ if (lengthInBits >= subtree.bitIndex) {
+ lastOne = true;
+ }
+ }
+ }
+ }
+
+ //-----------------------------------------------------------------------
+
+ /**
+ * Reads the content of the stream.
+ */
+ @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
+ private void readObject(final ObjectInputStream stream) throws IOException, ClassNotFoundException{
+ stream.defaultReadObject();
+ root = new TrieEntry<K, V>(null, null, -1);
+ int size = stream.readInt();
+ for(int i = 0; i < size; i++){
+ K k = (K) stream.readObject();
+ V v = (V) stream.readObject();
+ put(k, v);
+ }
+ }
+
+ /**
+ * Writes the content to the stream for serialization.
+ */
+ private void writeObject(final ObjectOutputStream stream) throws IOException{
+ stream.defaultWriteObject();
+ stream.writeInt(this.size());
+ for (final Entry<K, V> entry : entrySet()) {
+ stream.writeObject(entry.getKey());
+ stream.writeObject(entry.getValue());
}
}
+
}