PROTON-2575 Add sub map and navigable map APIs to splay map
Provide a means of operating over a fixed range in the tracking
map for cases where dispositions arrive with a range of first
to last delivery ids. This allows a more efficient handling of
these ranged dispositions and produces intermediate objects.
Also fixes an issue where the tracking map could be corrupted if
a remove and update operation falls within a very specific range
of values in the map tree.
diff --git a/protonj2/src/main/java/org/apache/qpid/protonj2/engine/impl/ProtonSessionIncomingWindow.java b/protonj2/src/main/java/org/apache/qpid/protonj2/engine/impl/ProtonSessionIncomingWindow.java
index ea6f28a..5e43a56 100644
--- a/protonj2/src/main/java/org/apache/qpid/protonj2/engine/impl/ProtonSessionIncomingWindow.java
+++ b/protonj2/src/main/java/org/apache/qpid/protonj2/engine/impl/ProtonSessionIncomingWindow.java
@@ -16,6 +16,10 @@
*/
package org.apache.qpid.protonj2.engine.impl;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NavigableMap;
+
import org.apache.qpid.protonj2.buffer.ProtonBuffer;
import org.apache.qpid.protonj2.engine.exceptions.ProtocolViolationException;
import org.apache.qpid.protonj2.engine.util.SequenceNumber;
@@ -157,7 +161,7 @@
final int first = (int) disposition.getFirst();
if (disposition.hasLast() && disposition.getLast() != first) {
- handleRangedDisposition(disposition);
+ handleRangedDisposition(unsettled, disposition);
} else {
final ProtonIncomingDelivery delivery = disposition.getSettled() ?
unsettled.remove(first) : unsettled.get(first);
@@ -170,23 +174,34 @@
return disposition;
}
- private void handleRangedDisposition(Disposition disposition) {
- final int first = (int) disposition.getFirst();
- final int last = (int) disposition.getLast();
+ private static void handleRangedDisposition(NavigableMap<UnsignedInteger, ProtonIncomingDelivery> unsettled, Disposition disposition) {
+ final UnsignedInteger first = UnsignedInteger.valueOf(disposition.getFirst());
+ final UnsignedInteger last = UnsignedInteger.valueOf(disposition.getLast());
+
+ // Dispositions cover a contiguous range in the map requires a single sub-map
+ // which we can iterate whereas a range that wraps requires two iterations over
+ // a split between the higher portion and the lower portion of the map.
+ if (first.compareTo(last) <= 0) {
+ handleDispositions(unsettled.subMap(first, true, last, true), disposition);
+ } else {
+ handleDispositions(unsettled.tailMap(first, true), disposition);
+ handleDispositions(unsettled.headMap(last, true), disposition);
+ }
+ }
+
+ private static void handleDispositions(Map<UnsignedInteger, ProtonIncomingDelivery> deliveries, Disposition disposition) {
final boolean settled = disposition.getSettled();
- int index = first;
- ProtonIncomingDelivery delivery;
+ Iterator<ProtonIncomingDelivery> deliveriesIter = deliveries.values().iterator();
+ while (deliveriesIter.hasNext()) {
+ ProtonIncomingDelivery delivery = deliveriesIter.next();
- // TODO: If SplayMap gets a subMap that works we could get the ranged view which would
- // be more efficient.
- do {
- delivery = settled ? unsettled.remove(index) : unsettled.get(index);
-
- if (delivery != null) {
- delivery.getLink().remoteDisposition(disposition, delivery);
+ if (settled) {
+ deliveriesIter.remove();
}
- } while (index++ != last);
+
+ delivery.getLink().remoteDisposition(disposition, delivery);
+ }
}
long updateIncomingWindow() {
diff --git a/protonj2/src/main/java/org/apache/qpid/protonj2/engine/impl/ProtonSessionOutgoingWindow.java b/protonj2/src/main/java/org/apache/qpid/protonj2/engine/impl/ProtonSessionOutgoingWindow.java
index 0c1bcaa..8fc5854 100644
--- a/protonj2/src/main/java/org/apache/qpid/protonj2/engine/impl/ProtonSessionOutgoingWindow.java
+++ b/protonj2/src/main/java/org/apache/qpid/protonj2/engine/impl/ProtonSessionOutgoingWindow.java
@@ -16,12 +16,16 @@
*/
package org.apache.qpid.protonj2.engine.impl;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NavigableMap;
import java.util.Set;
import org.apache.qpid.protonj2.buffer.ProtonBuffer;
import org.apache.qpid.protonj2.engine.OutgoingAMQPEnvelope;
import org.apache.qpid.protonj2.engine.util.SplayMap;
import org.apache.qpid.protonj2.types.DeliveryTag;
+import org.apache.qpid.protonj2.types.UnsignedInteger;
import org.apache.qpid.protonj2.types.transport.Begin;
import org.apache.qpid.protonj2.types.transport.Disposition;
import org.apache.qpid.protonj2.types.transport.Flow;
@@ -218,7 +222,7 @@
final int first = (int) disposition.getFirst();
if (disposition.hasLast() && disposition.getLast() != first) {
- handleRangedDisposition(disposition);
+ handleRangedDisposition(unsettled, disposition);
} else {
final ProtonOutgoingDelivery delivery = disposition.getSettled() ?
unsettled.remove(first) : unsettled.get(first);
@@ -231,23 +235,34 @@
return disposition;
}
- private void handleRangedDisposition(Disposition disposition) {
- final int first = (int) disposition.getFirst();
- final int last = (int) disposition.getLast();
+ private static void handleRangedDisposition(NavigableMap<UnsignedInteger, ProtonOutgoingDelivery> unsettled, Disposition disposition) {
+ final UnsignedInteger first = UnsignedInteger.valueOf(disposition.getFirst());
+ final UnsignedInteger last = UnsignedInteger.valueOf(disposition.getLast());
+
+ // Dispositions cover a contiguous range in the map requires a single sub-map
+ // which we can iterate whereas a range that wraps requires two iterations over
+ // a split between the higher portion and the lower portion of the map.
+ if (first.compareTo(last) <= 0) {
+ handleDispositions(unsettled.subMap(first, true, last, true), disposition);
+ } else {
+ handleDispositions(unsettled.tailMap(first, true), disposition);
+ handleDispositions(unsettled.headMap(last, true), disposition);
+ }
+ }
+
+ private static void handleDispositions(Map<UnsignedInteger, ProtonOutgoingDelivery> deliveries, Disposition disposition) {
final boolean settled = disposition.getSettled();
- int index = first;
- ProtonOutgoingDelivery delivery;
+ Iterator<ProtonOutgoingDelivery> deliveriesIter = deliveries.values().iterator();
+ while (deliveriesIter.hasNext()) {
+ ProtonOutgoingDelivery delivery = deliveriesIter.next();
- // TODO: If SplayMap gets a subMap that works we could get the ranged view which would
- // be more efficient.
- do {
- delivery = settled ? unsettled.remove(index) : unsettled.get(index);
-
- if (delivery != null) {
- delivery.getLink().remoteDisposition(disposition, delivery);
+ if (settled) {
+ deliveriesIter.remove();
}
- } while (index++ != last);
+
+ delivery.getLink().remoteDisposition(disposition, delivery);
+ }
}
//----- Handle sender link actions in the session window context
diff --git a/protonj2/src/main/java/org/apache/qpid/protonj2/engine/util/LinkedSplayMap.java b/protonj2/src/main/java/org/apache/qpid/protonj2/engine/util/LinkedSplayMap.java
index 0d8e698..69f8dff 100644
--- a/protonj2/src/main/java/org/apache/qpid/protonj2/engine/util/LinkedSplayMap.java
+++ b/protonj2/src/main/java/org/apache/qpid/protonj2/engine/util/LinkedSplayMap.java
@@ -22,6 +22,7 @@
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
+import java.util.NavigableSet;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
@@ -52,14 +53,6 @@
}
@Override
- public Set<UnsignedInteger> keySet() {
- if (keySet == null) {
- keySet = new LinkedSplayMapKeySet();
- }
- return keySet;
- }
-
- @Override
public Collection<E> values() {
if (values == null) {
values = new LinkedSplayMapValues();
@@ -76,6 +69,14 @@
}
@Override
+ public NavigableSet<UnsignedInteger> navigableKeySet() {
+ if (keySet == null) {
+ keySet = new LinkedSplayMapKeySet();
+ }
+ return keySet;
+ }
+
+ @Override
public void forEach(BiConsumer<? super UnsignedInteger, ? super E> action) {
Objects.requireNonNull(action);
@@ -285,7 +286,7 @@
}
}
- private final class LinkedSplayMapKeySet extends AbstractSet<UnsignedInteger> {
+ private final class LinkedSplayMapKeySet extends SplayMapKeySet {
@Override
public Iterator<UnsignedInteger> iterator() {
@@ -293,16 +294,6 @@
}
@Override
- public int size() {
- return LinkedSplayMap.this.size;
- }
-
- @Override
- public boolean contains(Object o) {
- return LinkedSplayMap.this.containsKey(o);
- }
-
- @Override
public boolean remove(Object target) {
final SplayedEntry<E> root = LinkedSplayMap.this.entries;
@@ -330,11 +321,6 @@
throw new ConcurrentModificationException();
}
}
-
- @Override
- public void clear() {
- LinkedSplayMap.this.clear();
- }
}
private final class LinkedSplayMapEntrySet extends AbstractSet<Entry<UnsignedInteger, E>> {
diff --git a/protonj2/src/main/java/org/apache/qpid/protonj2/engine/util/SplayMap.java b/protonj2/src/main/java/org/apache/qpid/protonj2/engine/util/SplayMap.java
index 6e8d97d..7cffd29 100644
--- a/protonj2/src/main/java/org/apache/qpid/protonj2/engine/util/SplayMap.java
+++ b/protonj2/src/main/java/org/apache/qpid/protonj2/engine/util/SplayMap.java
@@ -17,8 +17,10 @@
package org.apache.qpid.protonj2.engine.util;
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;
@@ -29,6 +31,7 @@
import java.util.Objects;
import java.util.Set;
import java.util.SortedMap;
+import java.util.SortedSet;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
@@ -49,7 +52,8 @@
*/
public class SplayMap<E> implements NavigableMap<UnsignedInteger, E> {
- private static final UnsignedComparator COMPARATOR = new UnsignedComparator();
+ protected static final Comparator<UnsignedInteger> COMPARATOR = new UnsignedComparator();
+ protected static final Comparator<UnsignedInteger> REVERSE_COMPARATOR = Collections.reverseOrder(COMPARATOR);
protected final RingQueue<SplayedEntry<E>> entryPool = new RingQueue<>(64);
@@ -106,6 +110,31 @@
}
/**
+ * Gets the value of the element stored in the {@link Map} with the key (treated as an
+ * unsigned integer for comparison.
+ *
+ * As a side effect of calling this method the tree that comprises the Map can be modified
+ * to bring up the found key or the last accessed key if the key given is not in the {@link Map}.
+ * For entries at the root of the tree that match the given search key the method returns
+ * immediately without modifying the {@link Map}.
+ *
+ * @param key
+ * the integer key value to search for in the {@link SplayMap}.
+ * @param defaultValue
+ * the default value to return if the key is not stored in this {@link Map}.
+ *
+ * @return the value stored for the given key if found the default value if not in the {@link Map}.
+ */
+ public E getOrDefault(int key, E defaultValue) {
+ E result = get(key);
+ if (result == null && root != null && root.key == key) {
+ return null;
+ }
+
+ return defaultValue;
+ }
+
+ /**
* Puts the value into the in the {@link Map} at the entry specified by the given key (treated as an
* unsigned integer for comparison.
*
@@ -151,11 +180,6 @@
return oldValue;
}
- @Override
- public E putIfAbsent(UnsignedInteger key, E value) {
- return putIfAbsent(key.intValue(), value);
- }
-
/**
* If the specified key is not already associated with a value associates it with the given value and
* returns null, otherwise returns the current value.
@@ -293,11 +317,21 @@
}
@Override
+ public E putIfAbsent(UnsignedInteger key, E value) {
+ return putIfAbsent(key.intValue(), value);
+ }
+
+ @Override
public E get(Object key) {
return get(Number.class.cast(key).intValue());
}
@Override
+ public E getOrDefault(Object key, E defaultValue) {
+ return getOrDefault(Number.class.cast(key).intValue(), defaultValue);
+ }
+
+ @Override
public E remove(Object key) {
return remove(Number.class.cast(key).intValue());
}
@@ -332,21 +366,63 @@
return false;
}
- // Once requested we will create an store a single instance to a collection
- // with no state for each of the key, values and entries types. Since the
- // types are stateless the trivial race on create is not important to the
- // eventual outcome of having a cached instance.
+ @Override
+ public int hashCode() {
+ int hash = 0;
+ for (SplayedEntry<E> entry = firstEntry(root); entry != null; entry = successor(entry)) {
+ hash += entry.hashCode();
+ }
+ return hash;
+ }
- protected Set<UnsignedInteger> keySet;
+ @Override
+ public boolean equals(Object o) {
+ if (o == this) {
+ return true;
+ }
+ if (!(o instanceof Map)) {
+ return false;
+ }
+
+ Map<?,?> m = (Map<?,?>) o;
+ if (m.size() != size()) {
+ return false;
+ }
+
+ try {
+ for (SplayedEntry<E> entry = firstEntry(root); entry != null; entry = successor(entry)) {
+ UnsignedInteger key = entry.getKey();
+ E value = entry.getValue();
+ if (value == null) {
+ if (!(m.get(key) == null && m.containsKey(key))) {
+ return false;
+ }
+ } else {
+ if (!value.equals(m.get(key))) {
+ return false;
+ }
+ }
+ }
+ } catch (ClassCastException | NullPointerException ignored) {
+ return false;
+ }
+
+ return true;
+ }
+
+ // Once requested we will create an store a single instance to a collection
+ // with no state for each of the key, values ,entries types and the descending
+ // Map view. Since the types are stateless the trivial race on create is not
+ // important to the eventual outcome of having a cached instance.
+
+ protected NavigableSet<UnsignedInteger> keySet;
protected Collection<E> values;
protected Set<Entry<UnsignedInteger, E>> entrySet;
+ protected NavigableMap<UnsignedInteger, E> descendingMapView;
@Override
public Set<UnsignedInteger> keySet() {
- if (keySet == null) {
- keySet = new SplayMapKeySet();
- }
- return keySet;
+ return navigableKeySet();
}
@Override
@@ -511,7 +587,7 @@
*
*/
- private SplayedEntry<E> rightRotate(SplayedEntry<E> node) {
+ private static <E> SplayedEntry<E> rightRotate(SplayedEntry<E> node) {
SplayedEntry<E> rotated = node.left;
node.left = rotated.right;
rotated.right = node;
@@ -526,7 +602,7 @@
return rotated;
}
- private SplayedEntry<E> leftRotate(SplayedEntry<E> node) {
+ private static <E> SplayedEntry<E> leftRotate(SplayedEntry<E> node) {
SplayedEntry<E> rotated = node.right;
node.right = rotated.left;
rotated.left = node;
@@ -547,7 +623,7 @@
* as it is likely it will be the next accessed or one of the neighboring nodes which
* reduces the search time for that cluster.
*/
- private SplayedEntry<E> splay(SplayedEntry<E> root, int key) {
+ private static <E> SplayedEntry<E> splay(SplayedEntry<E> root, int key) {
if (root == null || root.key == key) {
return root;
}
@@ -653,6 +729,9 @@
if (node.left != null) {
replacement = splay(node.left, node.key);
replacement.right = node.right;
+ if (replacement.right != null) {
+ replacement.right.parent = replacement;
+ }
}
if (replacement != null) {
@@ -679,7 +758,23 @@
modCount++;
}
- private SplayedEntry<E> firstEntry(SplayedEntry<E> node) {
+ private SplayedEntry<E> findEntry(int key) {
+ if (root == null) {
+ return null;
+ } else if (root.key == key) {
+ return root;
+ } else {
+ root = splay(root, key);
+
+ if (root.key == key) {
+ return root;
+ } else {
+ return null;
+ }
+ }
+ }
+
+ private static <E> SplayedEntry<E> firstEntry(SplayedEntry<E> node) {
SplayedEntry<E> firstEntry = node;
if (firstEntry != null) {
while (firstEntry.left != null) {
@@ -690,7 +785,7 @@
return firstEntry;
}
- private SplayedEntry<E> lastEntry(SplayedEntry<E> node) {
+ private static <E> SplayedEntry<E> lastEntry(SplayedEntry<E> node) {
SplayedEntry<E> lastEntry = node;
if (lastEntry != null) {
while (lastEntry.right != null) {
@@ -701,7 +796,7 @@
return lastEntry;
}
- private SplayedEntry<E> successor(SplayedEntry<E> node) {
+ private static <E> SplayedEntry<E> successor(SplayedEntry<E> node) {
if (node == null) {
return null;
} else if (node.right != null) {
@@ -724,7 +819,7 @@
}
}
- private SplayedEntry<E> predecessor(SplayedEntry<E> node) {
+ private static <E> SplayedEntry<E> predecessor(SplayedEntry<E> node) {
if (node == null) {
return null;
} else if (node.left != null) {
@@ -747,6 +842,17 @@
}
}
+ /**
+ * Unsigned comparison of two integer values
+ *
+ * @param lhs
+ * the left hand side value for comparison.
+ * @param rhs
+ * the right hand side value for comparison.
+ *
+ * @return a negative integer, zero, or a positive integer as the first argument is less than,
+ * equal to, or greater than the second.
+ */
private static int compare(int lhs, int rhs) {
return Integer.compareUnsigned(lhs, rhs);
}
@@ -760,10 +866,10 @@
// Base class iterator that can be used for the collections returned from the Map
private abstract class SplayMapIterator<T> implements Iterator<T> {
- private SplayedEntry<E> nextNode;
- private SplayedEntry<E> lastReturned;
+ protected SplayedEntry<E> nextNode;
+ protected SplayedEntry<E> lastReturned;
- private int expectedModCount;
+ protected int expectedModCount;
public SplayMapIterator(SplayedEntry<E> startAt) {
this.nextNode = startAt;
@@ -791,8 +897,6 @@
return lastReturned;
}
- // Unused as of now but can be used for NavigableMap amongst other things
- @SuppressWarnings("unused")
protected SplayedEntry<E> previousNode() {
final SplayedEntry<E> entry = nextNode;
@@ -849,6 +953,17 @@
}
}
+ final class ReverseSplayMapKeyIterator extends SplayMapIterator<UnsignedInteger> {
+ public ReverseSplayMapKeyIterator(SplayedEntry<E> startAt) {
+ super(startAt);
+ }
+
+ @Override
+ public UnsignedInteger next() {
+ return previousNode().getKey();
+ }
+ }
+
private class SplayMapValueIterator extends SplayMapIterator<E> {
public SplayMapValueIterator(SplayedEntry<E> startAt) {
@@ -897,7 +1012,7 @@
}
}
- private final class SplayMapKeySet extends AbstractSet<UnsignedInteger> {
+ protected class SplayMapKeySet extends AbstractSet<UnsignedInteger> implements NavigableSet<UnsignedInteger> {
@Override
public Iterator<UnsignedInteger> iterator() {
@@ -910,6 +1025,11 @@
}
@Override
+ public boolean isEmpty() {
+ return SplayMap.this.size == 0;
+ }
+
+ @Override
public boolean contains(Object o) {
return SplayMap.this.containsKey(o);
}
@@ -926,9 +1046,132 @@
}
@Override
+ public boolean retainAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ boolean modified = false;
+
+ for (SplayedEntry<E> e = firstEntry(root); e != null;) {
+ if (c.contains(e.getKey())) {
+ e = successor(e);
+ } else {
+ final SplayedEntry<E> target = e;
+ e = successor(e);
+
+ delete(target);
+ modified = true;
+ }
+ }
+
+ return modified;
+ }
+
+ @Override
+ public Object[] toArray() {
+ Object[] result = new Object[size()];
+ int i = 0;
+
+ for (SplayedEntry<E> e = firstEntry(root); e != null; e = successor(e), ++i) {
+ result[i] = e.getKey();
+ }
+
+ return result;
+ }
+
+ @Override
public void clear() {
SplayMap.this.clear();
}
+
+ @Override
+ public Comparator<? super UnsignedInteger> comparator() {
+ return SplayMap.COMPARATOR;
+ }
+
+ @Override
+ public UnsignedInteger first() {
+ return firstKey();
+ }
+
+ @Override
+ public UnsignedInteger last() {
+ return lastKey();
+ }
+
+ @Override
+ public UnsignedInteger lower(UnsignedInteger key) {
+ return lowerKey(key);
+ }
+
+ @Override
+ public UnsignedInteger floor(UnsignedInteger key) {
+ return floorKey(key);
+ }
+
+ @Override
+ public UnsignedInteger ceiling(UnsignedInteger key) {
+ return ceilingKey(key);
+ }
+
+ @Override
+ public UnsignedInteger higher(UnsignedInteger key) {
+ return higherKey(key);
+ }
+
+ @Override
+ public UnsignedInteger pollFirst() {
+ Map.Entry<UnsignedInteger, ?> first = pollFirstEntry();
+ return first == null ? null : first.getKey();
+ }
+
+ @Override
+ public UnsignedInteger pollLast() {
+ Map.Entry<UnsignedInteger, ?> first = pollLastEntry();
+ return first == null ? null : first.getKey();
+ }
+
+ @Override
+ public NavigableSet<UnsignedInteger> descendingSet() {
+ return descendingMap().navigableKeySet();
+ }
+
+ @Override
+ public Iterator<UnsignedInteger> descendingIterator() {
+ return descendingMap().keySet().iterator();
+ }
+
+ @Override
+ public NavigableSet<UnsignedInteger> subSet(UnsignedInteger fromElement, boolean fromInclusive, UnsignedInteger toElement, boolean toInclusive) {
+ return new AscendingSubMap<>(SplayMap.this,
+ false, fromElement.intValue(), fromInclusive,
+ false, toElement.intValue(), toInclusive).navigableKeySet();
+ }
+
+ @Override
+ public NavigableSet<UnsignedInteger> headSet(UnsignedInteger toElement, boolean inclusive) {
+ return new AscendingSubMap<>(SplayMap.this,
+ true, 0, true, false, toElement.intValue(), inclusive).navigableKeySet();
+ }
+
+ @Override
+ public NavigableSet<UnsignedInteger> tailSet(UnsignedInteger fromElement, boolean inclusive) {
+ return new AscendingSubMap<>(SplayMap.this,
+ false, fromElement.intValue(), inclusive, true, 0, true).navigableKeySet();
+ }
+
+ @Override
+ public SortedSet<UnsignedInteger> subSet(UnsignedInteger fromElement, UnsignedInteger toElement) {
+ return subSet(fromElement, true, toElement, true);
+ }
+
+ @Override
+ public SortedSet<UnsignedInteger> headSet(UnsignedInteger toElement) {
+ return headSet(toElement, false);
+ }
+
+ @Override
+ public SortedSet<UnsignedInteger> tailSet(UnsignedInteger fromElement) {
+ return tailSet(fromElement, false);
+ }
}
private final class SplayMapEntrySet extends AbstractSet<Entry<UnsignedInteger, E>> {
@@ -945,13 +1188,11 @@
@Override
public boolean contains(Object o) {
- if (!(o instanceof Map.Entry) || SplayMap.this.root == null) {
- return false;
- }
-
- for (SplayedEntry<E> e = firstEntry(root); e != null; e = successor(e)) {
- if (e.equals(o)) {
- return true;
+ if ((o instanceof Map.Entry) && SplayMap.this.root != null) {
+ for (SplayedEntry<E> e = firstEntry(root); e != null; e = successor(e)) {
+ if (e.equals(o)) {
+ return true;
+ }
}
}
@@ -1067,7 +1308,7 @@
* An immutable {@link Map} entry that can be used when exposing raw entry mappings
* via the {@link Map} API.
*/
- public class ImmutableSplayMapEntry implements Map.Entry<UnsignedInteger, E> {
+ public static class ImmutableSplayMapEntry<E> implements Map.Entry<UnsignedInteger, E> {
private final SplayedEntry<E> entry;
@@ -1104,8 +1345,8 @@
}
}
- protected ImmutableSplayMapEntry export(SplayedEntry<E> entry) {
- return entry == null ? null : new ImmutableSplayMapEntry(entry);
+ protected static <V> ImmutableSplayMapEntry<V> export(SplayedEntry<V> entry) {
+ return entry == null ? null : new ImmutableSplayMapEntry<>(entry);
}
//----- Unsigned Integer comparator for Navigable Maps
@@ -1118,6 +1359,10 @@
}
}
+ protected static Comparator<? super UnsignedInteger> reverseComparator() {
+ return REVERSE_COMPARATOR;
+ }
+
//----- Navigable and Sorted Map implementation methods
@Override
@@ -1136,17 +1381,17 @@
}
@Override
- public ImmutableSplayMapEntry firstEntry() {
+ public ImmutableSplayMapEntry<E> firstEntry() {
return export(firstEntry(root));
}
@Override
- public ImmutableSplayMapEntry lastEntry() {
+ public ImmutableSplayMapEntry<E> lastEntry() {
return export(lastEntry(root));
}
@Override
- public ImmutableSplayMapEntry pollFirstEntry() {
+ public ImmutableSplayMapEntry<E> pollFirstEntry() {
SplayedEntry<E> firstEntry = firstEntry(root);
if (firstEntry != null) {
delete(firstEntry);
@@ -1155,7 +1400,7 @@
}
@Override
- public ImmutableSplayMapEntry pollLastEntry() {
+ public ImmutableSplayMapEntry<E> pollLastEntry() {
SplayedEntry<E> lastEntry = lastEntry(root);
if (lastEntry != null) {
delete(lastEntry);
@@ -1164,23 +1409,37 @@
}
@Override
- public ImmutableSplayMapEntry lowerEntry(UnsignedInteger key) {
- return export(lowerEntry(key.intValue()));
+ public ImmutableSplayMapEntry<E> lowerEntry(UnsignedInteger key) {
+ return export(splayToLowerEntry(key.intValue()));
}
@Override
public UnsignedInteger lowerKey(UnsignedInteger key) {
- final SplayedEntry<E> result = lowerEntry(key.intValue());
+ final SplayedEntry<E> result = splayToLowerEntry(key.intValue());
return result == null ? null : result.getKey();
}
- private SplayedEntry<E> lowerEntry(int key) {
+ /**
+ * Splay to a key-value mapping associated with the greatest key strictly less than the given
+ * key, or null if there is no such key.
+ *
+ * @param key
+ * The key whose next lower entry match is being queried.
+ *
+ * @return the next lower entry or null if no keys lower than the given value.
+ */
+ private SplayedEntry<E> splayToLowerEntry(int key) {
root = splay(root, key);
while (root != null) {
if (compare(root.getIntKey(), key) >= 0) {
- root = predecessor(root);
+ SplayedEntry<E> pred = predecessor(root);
+ if (pred != null) {
+ root = splay(root, pred.key);
+ } else {
+ return null;
+ }
} else {
break;
}
@@ -1190,23 +1449,37 @@
}
@Override
- public ImmutableSplayMapEntry higherEntry(UnsignedInteger key) {
- return export(higherEntry(key.intValue()));
+ public ImmutableSplayMapEntry<E> higherEntry(UnsignedInteger key) {
+ return export(splayToHigherEntry(key.intValue()));
}
@Override
public UnsignedInteger higherKey(UnsignedInteger key) {
- final SplayedEntry<E> result = higherEntry(key.intValue());
+ final SplayedEntry<E> result = splayToHigherEntry(key.intValue());
return result == null ? null : result.getKey();
}
- private SplayedEntry<E> higherEntry(int key) {
+ /**
+ * Splay to a key-value mapping associated with the least key strictly greater than the given
+ * key, or null if there is no such key.
+ *
+ * @param key
+ * The key whose next higher entry match is being queried.
+ *
+ * @return the next highest entry or null if no keys higher than the given value.
+ */
+ private SplayedEntry<E> splayToHigherEntry(int key) {
root = splay(root, key);
while (root != null) {
if (compare(root.getIntKey(), key) <= 0) {
- root = successor(root);
+ SplayedEntry<E> succ = successor(root);
+ if (succ != null) {
+ root = splay(root, succ.key);
+ } else {
+ return null;
+ }
} else {
break;
}
@@ -1216,23 +1489,37 @@
}
@Override
- public ImmutableSplayMapEntry floorEntry(UnsignedInteger key) {
- return export(floorEntry(key.intValue()));
+ public ImmutableSplayMapEntry<E> floorEntry(UnsignedInteger key) {
+ return export(splayToFloorEntry(key.intValue()));
}
@Override
public UnsignedInteger floorKey(UnsignedInteger key) {
- final SplayedEntry<E> result = floorEntry(key.intValue());
+ final SplayedEntry<E> result = splayToFloorEntry(key.intValue());
return result == null ? null : result.getKey();
}
- private SplayedEntry<E> floorEntry(int key) {
+ /**
+ * Splay to 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.
+ *
+ * @param key
+ * The key whose floor entry match is being queried.
+ *
+ * @return the entry or next lowest entry or null if no keys less then or equal to the given value.
+ */
+ private SplayedEntry<E> splayToFloorEntry(int key) {
root = splay(root, key);
while (root != null) {
if (compare(root.getIntKey(), key) > 0) {
- root = predecessor(root);
+ SplayedEntry<E> pred = predecessor(root);
+ if (pred != null) {
+ root = splay(root, pred.key);
+ } else {
+ return null;
+ }
} else {
break;
}
@@ -1242,23 +1529,37 @@
}
@Override
- public ImmutableSplayMapEntry ceilingEntry(UnsignedInteger key) {
- return export(ceilingEntry(key.intValue()));
+ public ImmutableSplayMapEntry<E> ceilingEntry(UnsignedInteger key) {
+ return export(splayToCeilingEntry(key.intValue()));
}
@Override
public UnsignedInteger ceilingKey(UnsignedInteger key) {
- final SplayedEntry<E> result = ceilingEntry(key.intValue());
+ final SplayedEntry<E> result = splayToCeilingEntry(key.intValue());
return result == null ? null : result.getKey();
}
- private SplayedEntry<E> ceilingEntry(int key) {
+ /**
+ * Splay to 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.
+ *
+ * @param key
+ * The key whose ceiling entry match is being queried.
+ *
+ * @return the entry or next highest entry or null if no keys higher than or equal to the given value.
+ */
+ private SplayedEntry<E> splayToCeilingEntry(int key) {
root = splay(root, key);
while (root != null) {
if (compare(root.getIntKey(), key) < 0) {
- root = successor(root);
+ SplayedEntry<E> succ = successor(root);
+ if (succ != null) {
+ root = splay(root, succ.key);
+ } else {
+ return null;
+ }
} else {
break;
}
@@ -1269,55 +1570,1134 @@
@Override
public NavigableMap<UnsignedInteger, E> descendingMap() {
- // TODO Auto-generated method stub
- return null;
+ return (descendingMapView != null) ? descendingMapView :
+ (descendingMapView = new DescendingSubMap<>(this,
+ true, 0, true,
+ true, UnsignedInteger.MAX_VALUE.intValue(), true));
}
@Override
public NavigableSet<UnsignedInteger> navigableKeySet() {
- // TODO Auto-generated method stub
- return null;
+ if (keySet == null) {
+ keySet = new SplayMapKeySet();
+ }
+ return keySet;
}
@Override
public NavigableSet<UnsignedInteger> descendingKeySet() {
- // TODO Auto-generated method stub
- return null;
+ return descendingMap().navigableKeySet();
}
@Override
public NavigableMap<UnsignedInteger, E> subMap(UnsignedInteger fromKey, boolean fromInclusive, UnsignedInteger toKey, boolean toInclusive) {
- // TODO Auto-generated method stub
- return null;
+ return new AscendingSubMap<>(this, false, fromKey.intValue(), fromInclusive, false, toKey.intValue(), toInclusive);
}
@Override
public NavigableMap<UnsignedInteger, E> headMap(UnsignedInteger toKey, boolean inclusive) {
- // TODO Auto-generated method stub
- return null;
+ return new AscendingSubMap<>(this, true, 0, true, false, toKey.intValue(), inclusive);
}
@Override
public NavigableMap<UnsignedInteger, E> tailMap(UnsignedInteger fromKey, boolean inclusive) {
- // TODO Auto-generated method stub
- return null;
+ return new AscendingSubMap<>(this, false, fromKey.intValue(), inclusive, true, UnsignedInteger.MAX_VALUE.intValue(), true);
}
@Override
public SortedMap<UnsignedInteger, E> subMap(UnsignedInteger fromKey, UnsignedInteger toKey) {
- // TODO Auto-generated method stub
- return null;
+ return subMap(fromKey, true, toKey, false);
}
@Override
public SortedMap<UnsignedInteger, E> headMap(UnsignedInteger toKey) {
- // TODO Auto-generated method stub
- return null;
+ return headMap(toKey, false);
}
@Override
public SortedMap<UnsignedInteger, E> tailMap(UnsignedInteger fromKey) {
- // TODO Auto-generated method stub
+ return tailMap(fromKey, true);
+ }
+
+ /**
+ * Gets a key-value mapping associated with the given key or its successor.
+ * This method does not splay the tree so it will not bring the result to the root.
+ *
+ * @param key
+ * The key to search for in the mappings
+ *
+ * @return the entry that matches the search criteria or null if no valid match.
+ */
+ private SplayedEntry<E> getCeilingEntry(int key) {
+ SplayedEntry<E> result = this.root;
+
+ while (result != null) {
+ final int comparison = SplayMap.compare(key, result.key);
+ if (comparison < 0) {
+ // search key is less than current go left to get a smaller value
+ if (result.left != null) {
+ result = result.left;
+ } else {
+ return result; // nothing smaller exists
+ }
+ } else if (comparison > 0) {
+ // search key is greater than current go right to get a bigger one
+ // or go back up to the root of this branch
+ if (result.right != null) {
+ result = result.right;
+ } else {
+ SplayedEntry<E> parent = result.parent;
+ SplayedEntry<E> current = result;
+ while (parent != null && current == parent.right) {
+ current = parent;
+ parent = parent.parent;
+ }
+ return parent;
+ }
+ } else {
+ return result; // Found it.
+ }
+ }
+
return null;
}
+
+ /**
+ * Gets a key-value mapping associated with the given key or its predecessor.
+ * This method does not splay the tree so it will not bring the result to the root.
+ *
+ * @param key
+ * The key to search for in the mappings
+ *
+ * @return the entry that matches the search criteria or null if no valid match.
+ */
+ private SplayedEntry<E> getFloorEntry(int key) {
+ SplayedEntry<E> result = this.root;
+
+ while (result != null) {
+ final int comparison = SplayMap.compare(key, result.key);
+ if (comparison > 0) {
+ // search key is greater than current go right to get a bigger value
+ if (result.right != null) {
+ result = result.right;
+ } else {
+ return result; // nothing bigger exists
+ }
+ } else if (comparison < 0) {
+ // search key is less than current go left to get a smaller one
+ // or go back up to the root of this branch
+ if (result.left != null) {
+ result = result.left;
+ } else {
+ SplayedEntry<E> parent = result.parent;
+ SplayedEntry<E> current = result;
+ while (parent != null && current == parent.left) {
+ current = parent;
+ parent = parent.parent;
+ }
+ return parent;
+ }
+ } else {
+ return result; // Found it.
+ }
+ }
+
+ return null;
+ }
+
+ /**
+ * Gets a key-value mapping associated with the next entry higher than the given
+ * key or null if no entries exists with a higher key value. This method does not
+ * splay the tree so it will not bring the result to the root.
+ *
+ * @param key
+ * The key to search for in the mappings
+ *
+ * @return the entry that matches the search criteria or null if no valid match.
+ */
+ private SplayedEntry<E> getHigherEntry(int key) {
+ SplayedEntry<E> result = this.root;
+
+ while (result != null) {
+ final int comparison = SplayMap.compare(key, result.key);
+ if (comparison < 0) {
+ // search key is less than current go left to get a smaller value
+ if (result.left != null) {
+ result = result.left;
+ } else {
+ return result; // nothing smaller exists
+ }
+ } else {
+ // search key is greater than current go right to get a bigger one
+ // or go back up to the root of this branch
+ if (result.right != null) {
+ result = result.right;
+ } else {
+ SplayedEntry<E> parent = result.parent;
+ SplayedEntry<E> current = result;
+ while (parent != null && current == parent.right) {
+ current = parent;
+ parent = parent.parent;
+ }
+ return parent;
+ }
+ }
+ }
+
+ return null;
+ }
+
+ /**
+ * Gets a key-value mapping associated with next smallest entry below the given key
+ * or null if no smaller entries exist. This method does not splay the tree so it
+ * will not bring the result to the root.
+ *
+ * @param key
+ * The key to search for in the mappings
+ *
+ * @return the entry that matches the search criteria or null if no valid match.
+ */
+ private SplayedEntry<E> getLowerEntry(int key) {
+ SplayedEntry<E> result = this.root;
+
+ while (result != null) {
+ final int comparison = SplayMap.compare(key, result.key);
+ if (comparison > 0) {
+ // search key is greater than current go right to get a bigger value
+ if (result.right != null) {
+ result = result.right;
+ } else {
+ return result; // nothing bigger exists
+ }
+ } else {
+ // search key is less than current go left to get a smaller one
+ // or go back up to the root of this branch
+ if (result.left != null) {
+ result = result.left;
+ } else {
+ SplayedEntry<E> parent = result.parent;
+ SplayedEntry<E> current = result;
+ while (parent != null && current == parent.left) {
+ current = parent;
+ parent = parent.parent;
+ }
+ return parent;
+ }
+ }
+ }
+
+ return null;
+ }
+
+ protected static class NavigableSubMapKeySet extends AbstractSet<UnsignedInteger> implements NavigableSet<UnsignedInteger> {
+
+ private final NavigableSubMap<?> backingMap;
+
+ public NavigableSubMapKeySet(NavigableSubMap<?> backingMap) {
+ this.backingMap = backingMap;
+ }
+
+ @Override
+ public Iterator<UnsignedInteger> iterator() {
+ return backingMap.keyIterator();
+ }
+
+ @Override
+ public Iterator<UnsignedInteger> descendingIterator() {
+ return ((NavigableSubMap<?>)backingMap.descendingMap()).descendingKeyIterator();
+ }
+
+ @Override
+ public int size() {
+ return backingMap.size();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return backingMap.isEmpty();
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return backingMap.containsKey(o);
+ }
+
+ @Override
+ public boolean remove(Object target) {
+ int oldSize = backingMap.size();
+ backingMap.remove(target);
+ return oldSize != backingMap.size();
+ }
+
+ @Override
+ public void clear() {
+ backingMap.clear();
+ }
+
+ @Override
+ public Comparator<? super UnsignedInteger> comparator() {
+ return backingMap.comparator();
+ }
+
+ @Override
+ public UnsignedInteger first() {
+ return backingMap.firstKey();
+ }
+
+ @Override
+ public UnsignedInteger last() {
+ return backingMap.lastKey();
+ }
+
+ @Override
+ public UnsignedInteger lower(UnsignedInteger key) {
+ return backingMap.lowerKey(key);
+ }
+
+ @Override
+ public UnsignedInteger floor(UnsignedInteger key) {
+ return backingMap.floorKey(key);
+ }
+
+ @Override
+ public UnsignedInteger ceiling(UnsignedInteger key) {
+ return backingMap.ceilingKey(key);
+ }
+
+ @Override
+ public UnsignedInteger higher(UnsignedInteger key) {
+ return backingMap.higherKey(key);
+ }
+
+ @Override
+ public UnsignedInteger pollFirst() {
+ Map.Entry<UnsignedInteger, ?> first = backingMap.pollFirstEntry();
+ return first == null ? null : first.getKey();
+ }
+
+ @Override
+ public UnsignedInteger pollLast() {
+ Map.Entry<UnsignedInteger, ?> first = backingMap.pollLastEntry();
+ return first == null ? null : first.getKey();
+ }
+
+ @Override
+ public NavigableSet<UnsignedInteger> descendingSet() {
+ return backingMap.descendingMap().navigableKeySet();
+ }
+
+ @Override
+ public NavigableSet<UnsignedInteger> subSet(UnsignedInteger fromElement, boolean fromInclusive, UnsignedInteger toElement, boolean toInclusive) {
+ return backingMap.subMap(fromElement, fromInclusive, toElement, toInclusive).navigableKeySet();
+ }
+
+ @Override
+ public NavigableSet<UnsignedInteger> headSet(UnsignedInteger toElement, boolean inclusive) {
+ return backingMap.headMap(toElement, inclusive).navigableKeySet();
+ }
+
+ @Override
+ public NavigableSet<UnsignedInteger> tailSet(UnsignedInteger fromElement, boolean inclusive) {
+ return backingMap.tailMap(fromElement, inclusive).navigableKeySet();
+ }
+
+ @Override
+ public SortedSet<UnsignedInteger> subSet(UnsignedInteger fromElement, UnsignedInteger toElement) {
+ return subSet(fromElement, true, toElement, true);
+ }
+
+ @Override
+ public SortedSet<UnsignedInteger> headSet(UnsignedInteger toElement) {
+ return headSet(toElement, false);
+ }
+
+ @Override
+ public SortedSet<UnsignedInteger> tailSet(UnsignedInteger fromElement) {
+ return tailSet(fromElement, false);
+ }
+ }
+
+ /**
+ * Utility base class for the {@link SplayMap} that allows access to a sub region of the
+ * backing map.
+ * <p>
+ * If the from start directive is <code>true</code> then the map ignores the start key
+ * and the start key inclusive directive and assigns the start key as zero and the
+ * start key inclusive value to true.
+ * <p>
+ * If the to end directive is <code>true</code> then the map ignores the end key
+ * and the end key inclusive directive and assigns the end key to {@link UnsignedInteger#MAX_VALUE}
+ * and the end key inclusive flag to true.
+ *
+ * @param <E> The value type for this {@link NavigableSubMap}
+ */
+ private abstract static class NavigableSubMap<E> extends AbstractMap<UnsignedInteger, E> implements NavigableMap<UnsignedInteger, E> {
+
+ protected final SplayMap<E> backingMap;
+
+ final int startKey;
+ final int endKey;
+ final boolean fromStart;
+ final boolean toEnd;
+ final boolean startInclusive;
+ final boolean endInclusive;
+
+ private transient NavigableSubMapKeySet navigableSubMapKeySet;
+
+ NavigableSubMap(final SplayMap<E> map,
+ final boolean fromStart, final int start, final boolean startInclusive,
+ final boolean toEnd, final int end, final boolean endInclusive) {
+
+ if (SplayMap.compare(start, end) > 0) {
+ throw new IllegalArgumentException("The start key cannot be greater than the end key");
+ }
+
+ this.backingMap = map;
+ this.fromStart = fromStart;
+ this.toEnd = toEnd;
+ this.startKey = fromStart ? 0 : start;
+ this.endKey = toEnd ? UnsignedInteger.MAX_VALUE.intValue() : end;
+ this.startInclusive = fromStart ? true : startInclusive;
+ this.endInclusive = toEnd ? true : endInclusive;
+ }
+
+ //----- Basic Map implementation that defers to backing when possible
+
+ @Override
+ public boolean isEmpty() {
+ return (fromStart && toEnd) ? backingMap.size == 0 : entrySet().isEmpty();
+ }
+
+ @Override
+ public int size() {
+ return (fromStart && toEnd) ? backingMap.size : entrySet().size();
+ }
+
+ @Override
+ public boolean containsKey(Object key) {
+ Number numericKey = (Number) key;
+ return containsKey(numericKey.intValue());
+ }
+
+ public boolean containsKey(int key) {
+ return isInRange(key) && backingMap.containsKey(key);
+ }
+
+ @Override
+ public final E put(UnsignedInteger key, E value) {
+ return put(key.intValue(), value);
+ }
+
+ public final E put(int key, E value) {
+ if (!isInRange(key)) {
+ throw new IllegalArgumentException("The given key is out of range for this ranged sub-map");
+ }
+
+ return backingMap.put(key, value);
+ }
+
+ @Override
+ public final E get(Object key) {
+ Number numericKey = (Number) key;
+ return get(numericKey.intValue());
+ }
+
+ public final E get(int key) {
+ return !isInRange(key) ? null : backingMap.get(key);
+ }
+
+ @Override
+ public final E remove(Object key) {
+ Number numericKey = (Number) key;
+ return remove(numericKey.intValue());
+ }
+
+ public final E remove(int key) {
+ return !isInRange(key) ? null : backingMap.remove(key);
+ }
+
+ @Override
+ public final Map.Entry<UnsignedInteger, E> ceilingEntry(UnsignedInteger key) {
+ return SplayMap.export(getCeilingEntry(key.intValue()));
+ }
+
+ @Override
+ public final UnsignedInteger ceilingKey(UnsignedInteger key) {
+ SplayedEntry<E> result = getCeilingEntry(key.intValue());
+ return result == null ? null : result.getKey();
+ }
+
+ @Override
+ public final Map.Entry<UnsignedInteger, E> higherEntry(UnsignedInteger key) {
+ return SplayMap.export(getHigherEntry(key.intValue()));
+ }
+
+ @Override
+ public final UnsignedInteger higherKey(UnsignedInteger key) {
+ SplayedEntry<E> result = getHigherEntry(key.intValue());
+ return result == null ? null : result.getKey();
+ }
+
+ @Override
+ public final Map.Entry<UnsignedInteger, E> floorEntry(UnsignedInteger key) {
+ return SplayMap.export(getFloorEntry(key.intValue()));
+ }
+
+ @Override
+ public final UnsignedInteger floorKey(UnsignedInteger key) {
+ SplayedEntry<E> result = getFloorEntry(key.intValue());
+ return result == null ? null : result.getKey();
+ }
+
+ @Override
+ public final Map.Entry<UnsignedInteger, E> lowerEntry(UnsignedInteger key) {
+ return SplayMap.export(getLowerEntry(key.intValue()));
+ }
+
+ @Override
+ public final UnsignedInteger lowerKey(UnsignedInteger key) {
+ SplayedEntry<E> result = getLowerEntry(key.intValue());
+ return result == null ? null : result.getKey();
+ }
+
+ @Override
+ public final UnsignedInteger firstKey() {
+ SplayedEntry<E> result = getLowestEntry();
+ if (result != null) {
+ return result.getKey();
+ }
+
+ throw new NoSuchElementException();
+ }
+
+ @Override
+ public final UnsignedInteger lastKey() {
+ SplayedEntry<E> result = getHighestEntry();
+ if (result != null) {
+ return result.getKey();
+ }
+
+ throw new NoSuchElementException();
+ }
+
+ @Override
+ public final Map.Entry<UnsignedInteger, E> firstEntry() {
+ return SplayMap.export(getLowestEntry());
+ }
+
+ @Override
+ public final Map.Entry<UnsignedInteger, E> lastEntry() {
+ return SplayMap.export(getHighestEntry());
+ }
+
+ @Override
+ public final Map.Entry<UnsignedInteger, E> pollFirstEntry() {
+ SplayedEntry<E> result = getLowestEntry();
+ Map.Entry<UnsignedInteger, E> exported = SplayMap.export(result);
+ if (exported != null) {
+ backingMap.delete(result);
+ }
+
+ return exported;
+ }
+
+ @Override
+ public final Map.Entry<UnsignedInteger, E> pollLastEntry() {
+ SplayedEntry<E> result = getHighestEntry();
+ Map.Entry<UnsignedInteger, E> exported = SplayMap.export(result);
+ if (exported != null) {
+ backingMap.delete(result);
+ }
+
+ return exported;
+ }
+
+ @Override
+ public SortedMap<UnsignedInteger, E> subMap(UnsignedInteger fromKey, UnsignedInteger toKey) {
+ return subMap(fromKey, true, toKey, false);
+ }
+
+ @Override
+ public SortedMap<UnsignedInteger, E> headMap(UnsignedInteger toKey) {
+ return headMap(toKey, false);
+ }
+
+ @Override
+ public SortedMap<UnsignedInteger, E> tailMap(UnsignedInteger fromKey) {
+ return tailMap(fromKey, true);
+ }
+
+ @Override
+ public final Set<UnsignedInteger> keySet() {
+ return navigableKeySet();
+ }
+
+ @Override
+ public NavigableSet<UnsignedInteger> descendingKeySet() {
+ return descendingMap().navigableKeySet();
+ }
+
+ @Override
+ public final NavigableSet<UnsignedInteger> navigableKeySet() {
+ return (navigableSubMapKeySet != null) ?
+ navigableSubMapKeySet : (navigableSubMapKeySet = new NavigableSubMapKeySet(this));
+ }
+
+ //----- The abstract API that sub-classes will define
+
+ /**
+ * Returns an iterator appropriate to the sub map implementation
+ * which may be ascending or descending but must be the inverse of
+ * the direction of iterator returned from the {@link #descendingKeyIterator()}
+ * method.
+ *
+ * @return an iterator that operates over the keys in this sub map range.
+ */
+ abstract Iterator<UnsignedInteger> keyIterator();
+
+ /**
+ * Returns an iterator appropriate to the sub map implementation
+ * which may be ascending or descending but must be the inverse of
+ * the direction of iterator returned from the {@link #keyIterator()}
+ * method.
+ *
+ * @return an iterator that operates over the keys in this sub map range.
+ */
+ abstract Iterator<UnsignedInteger> descendingKeyIterator();
+
+ //----- Sub Map collection types
+
+ /**
+ * Specialized iterator for the sub-map type that iterators on a generic type
+ * but internally contains splayed entries from the splay map tree.
+ *
+ * @param <T>
+ */
+ protected abstract class NavigableSubMapIterator<T> implements Iterator<T> {
+ SplayedEntry<E> lastReturned;
+ SplayedEntry<E> next;
+ final int limitKey;
+ int expectedModCount;
+
+ NavigableSubMapIterator(SplayedEntry<E> start, SplayedEntry<E> limit) {
+ expectedModCount = backingMap.modCount;
+ lastReturned = null;
+ next = start;
+ limitKey = limit != null ? limit.key : UnsignedInteger.MAX_VALUE.intValue();
+ }
+
+ @Override
+ public abstract boolean hasNext();
+
+ @Override
+ public abstract T next();
+
+ @Override
+ public final void remove() {
+ if (lastReturned == null) {
+ throw new IllegalStateException();
+ }
+ if (backingMap.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+
+ backingMap.delete(lastReturned);
+ lastReturned = null;
+ expectedModCount = backingMap.modCount;
+ }
+
+ final boolean hasNextEntry() {
+ return next != null && SplayMap.compare(next.key, limitKey) <= 0;
+ }
+
+ final SplayedEntry<E> nextEntry() {
+ SplayedEntry<E> e = next;
+
+ if (e == null || SplayMap.compare(next.key, limitKey) > 0) {
+ throw new NoSuchElementException();
+ }
+ if (backingMap.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+
+ next = successor(e);
+ lastReturned = e;
+ return e;
+ }
+
+ final boolean hasPrevEntry() {
+ return next != null && SplayMap.compare(next.key, limitKey) >= 0;
+ }
+
+ final SplayedEntry<E> previousEntry() {
+ SplayedEntry<E> e = next;
+
+ if (e == null || SplayMap.compare(next.key, limitKey) < 0) {
+ throw new NoSuchElementException();
+ }
+ if (backingMap.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+
+ next = predecessor(e);
+ lastReturned = e;
+ return e;
+ }
+ }
+
+ final class NavigableSubMapEntryIterator extends NavigableSubMapIterator<Map.Entry<UnsignedInteger, E>> {
+ NavigableSubMapEntryIterator(SplayedEntry<E> first, SplayedEntry<E> fence) {
+ super(first, fence);
+ }
+
+ @Override
+ public boolean hasNext() {
+ return hasNextEntry();
+ }
+
+ @Override
+ public Map.Entry<UnsignedInteger, E> next() {
+ return nextEntry();
+ }
+ }
+
+ final class DescendingNavigableSubMapEntryIterator extends NavigableSubMapIterator<Map.Entry<UnsignedInteger, E>> {
+ DescendingNavigableSubMapEntryIterator(SplayedEntry<E> first, SplayedEntry<E> fence) {
+ super(first, fence);
+ }
+
+ @Override
+ public boolean hasNext() {
+ return hasPrevEntry();
+ }
+
+ @Override
+ public Map.Entry<UnsignedInteger, E> next() {
+ return previousEntry();
+ }
+ }
+
+ final class NavigableSubMapKeyIterator extends NavigableSubMapIterator<UnsignedInteger> {
+ NavigableSubMapKeyIterator(SplayedEntry<E> first, SplayedEntry<E> fence) {
+ super(first, fence);
+ }
+
+ @Override
+ public boolean hasNext() {
+ return hasNextEntry();
+ }
+
+ @Override
+ public UnsignedInteger next() {
+ return nextEntry().getKey();
+ }
+ }
+
+ final class DescendingNavigableSubMapKeyIterator extends NavigableSubMapIterator<UnsignedInteger> {
+ DescendingNavigableSubMapKeyIterator(SplayedEntry<E> first, SplayedEntry<E> fence) {
+ super(first, fence);
+ }
+
+ @Override
+ public boolean hasNext() {
+ return hasPrevEntry();
+ }
+
+ @Override
+ public UnsignedInteger next() {
+ return previousEntry().getKey();
+ }
+ }
+
+ protected abstract class NavigableSubMapEntrySet extends AbstractSet<Map.Entry<UnsignedInteger, E>> {
+ private transient int size = -1;
+ private transient int sizeModCount;
+
+ @Override
+ public int size() {
+ if ((!fromStart || !toEnd) && (size == -1 || sizeModCount != backingMap.modCount)) {
+ sizeModCount = backingMap.modCount;
+ size = 0;
+ Iterator<?> i = iterator();
+ while (i.hasNext()) {
+ size++;
+ i.next();
+ }
+
+ return size;
+ }
+
+ return backingMap.size;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ SplayedEntry<E> n = getLowestEntry();
+ return n == null || isToHigh(n.key);
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ if (o instanceof Map.Entry) {
+ Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
+ Number key = Number.class.cast(entry.getKey());
+
+ if (!isInRange(key.intValue())) {
+ return false;
+ }
+
+ SplayedEntry<E> node = backingMap.findEntry(key.intValue());
+
+ if (node != null) {
+ return Objects.equals(node.getValue(), entry.getValue());
+ }
+ }
+
+ return false;
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ if (o instanceof Map.Entry) {
+ Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
+ Number key = Number.class.cast(entry.getKey());
+
+ if (!isInRange(key.intValue())) {
+ return false;
+ }
+
+ SplayedEntry<E> node = backingMap.findEntry(key.intValue());
+
+ if (node != null) {
+ backingMap.delete(node);
+ return Objects.equals(node.getValue(), entry.getValue());
+ }
+ }
+
+ return false;
+ }
+ }
+
+ //----- Abstract access API which will be inverted based on sub map type
+
+ abstract SplayedEntry<E> getLowestEntry();
+
+ abstract SplayedEntry<E> getHighestEntry();
+
+ abstract SplayedEntry<E> getCeilingEntry(int key);
+
+ abstract SplayedEntry<E> getHigherEntry(int key);
+
+ abstract SplayedEntry<E> getFloorEntry(int key);
+
+ abstract SplayedEntry<E> getLowerEntry(int key);
+
+ //----- Internal API that aids this and other sub-classes
+
+ protected final SplayedEntry<E> lowestPossibleEntry() {
+ SplayedEntry<E> e =
+ startInclusive ? backingMap.getCeilingEntry(startKey) : backingMap.getHigherEntry(startKey);
+
+ return (e == null || isToHigh(e.key)) ? null : e;
+ }
+
+ protected final SplayedEntry<E> highestPossibleEntry() {
+ SplayedEntry<E> e =
+ endInclusive ? backingMap.getFloorEntry(endKey) : backingMap.getLowerEntry(endKey);
+
+ return (e == null || isToLow(e.key)) ? null : e;
+ }
+
+ protected final SplayedEntry<E> entryOrSuccessor(int key) {
+ if (isToLow(key)) {
+ return lowestPossibleEntry();
+ }
+ SplayedEntry<E> e = backingMap.getCeilingEntry(key);
+
+ return (e == null || isToHigh(e.key)) ? null : e;
+ }
+
+ protected final SplayedEntry<E> entrySuccessor(int key) {
+ if (isToLow(key)) {
+ return lowestPossibleEntry();
+ }
+ SplayedEntry<E> e = backingMap.getHigherEntry(key);
+
+ return (e == null || isToHigh(e.key)) ? null : e;
+ }
+
+ protected final SplayedEntry<E> entryOrPredecessor(int key) {
+ if (isToHigh(key)) {
+ return highestPossibleEntry();
+ }
+ SplayedEntry<E> e = backingMap.getFloorEntry(key);
+
+ return (e == null || isToLow(e.key)) ? null : e;
+ }
+
+ protected final SplayedEntry<E> entryPredecessor(int key) {
+ if (isToHigh(key)) {
+ return highestPossibleEntry();
+ }
+ SplayedEntry<E> e = backingMap.getLowerEntry(key);
+
+ return (e == null || isToLow(e.key)) ? null : e;
+ }
+
+ protected final void checkInRange(int fromKey, boolean fromInclusive, int toKey, boolean toInclusive) {
+ if (!isInRange(fromKey, fromInclusive)) {
+ throw new IllegalArgumentException("Given from key is out of range of this sub map view: " + fromKey);
+ }
+ if (!isInRange(toKey, toInclusive)) {
+ throw new IllegalArgumentException("Given to key is out of range of this sub map view: " + toKey);
+ }
+ }
+
+ protected final boolean isInRange(int key) {
+ return !isToLow(key) && !isToHigh(key);
+ }
+
+ final boolean isInCapturedRange(int key) {
+ return SplayMap.compare(key, startKey) >= 0 && SplayMap.compare(endKey, key) >= 0;
+ }
+
+ final boolean isInRange(int key, boolean inclusive) {
+ return inclusive ? isInRange(key) : isInCapturedRange(key);
+ }
+
+ protected final boolean isToLow(int key) {
+ int result = SplayMap.compare(key, startKey);
+ if (result < 0 || result == 0 && !startInclusive) {
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ protected final boolean isToHigh(int key) {
+ int result = SplayMap.compare(key, endKey);
+ if (result > 0 || result == 0 && !endInclusive) {
+ return true;
+ } else {
+ return false;
+ }
+ }
+ }
+
+ protected static final class AscendingSubMap<V> extends NavigableSubMap<V> {
+
+ AscendingSubMap(SplayMap<V> m,
+ boolean fromStart, int fromKey, boolean startInclusive,
+ boolean toEnd, int endKey, boolean endInclusive) {
+ super(m, fromStart, fromKey, startInclusive, toEnd, endKey, endInclusive);
+ }
+
+ private transient NavigableMap<UnsignedInteger, V> descendingMapView;
+ private transient NavigableSubMapEntrySet navigableEntrySet;
+
+ @Override
+ public Comparator<? super UnsignedInteger> comparator() {
+ return COMPARATOR;
+ }
+
+ @Override
+ public NavigableMap<UnsignedInteger, V> descendingMap() {
+ return descendingMapView != null ? descendingMapView :
+ (descendingMapView = new DescendingSubMap<>(backingMap,
+ fromStart, startKey, startInclusive, toEnd, endKey, endInclusive));
+ }
+
+ @Override
+ public NavigableMap<UnsignedInteger, V> subMap(UnsignedInteger fromKey, boolean fromInclusive,
+ UnsignedInteger toKey, boolean toInclusive) {
+ checkInRange(fromKey.intValue(), fromInclusive, toKey.compareTo(0), toInclusive);
+ return new AscendingSubMap<>(backingMap,
+ false, fromKey.intValue(), fromInclusive, false, toKey.intValue(), toInclusive);
+ }
+
+ @Override
+ public NavigableMap<UnsignedInteger, V> headMap(UnsignedInteger toKey, boolean inclusive) {
+ isInRange(toKey.intValue(), inclusive);
+ return new AscendingSubMap<>(backingMap,
+ fromStart, startKey, startInclusive, false, toKey.intValue(), inclusive);
+ }
+
+ @Override
+ public NavigableMap<UnsignedInteger, V> tailMap(UnsignedInteger fromKey, boolean inclusive) {
+ isInRange(fromKey.intValue(), inclusive);
+ return new AscendingSubMap<>(backingMap,
+ false, fromKey.intValue(), inclusive, toEnd, endKey, endInclusive);
+ }
+
+ @Override
+ public Set<Entry<UnsignedInteger, V>> entrySet() {
+ return navigableEntrySet != null ?
+ navigableEntrySet : (navigableEntrySet = new AscendingNavigableSubMapEntrySet());
+ }
+
+ @Override
+ Iterator<UnsignedInteger> keyIterator() {
+ return new NavigableSubMapKeyIterator(getLowestEntry(), getHighestEntry());
+ }
+
+ @Override
+ Iterator<UnsignedInteger> descendingKeyIterator() {
+ return new DescendingNavigableSubMapKeyIterator(getLowestEntry(), getHighestEntry());
+ }
+
+ @Override
+ SplayedEntry<V> getLowestEntry() {
+ return super.lowestPossibleEntry();
+ }
+
+ @Override
+ SplayedEntry<V> getHighestEntry() {
+ return super.highestPossibleEntry();
+ }
+
+ @Override
+ SplayedEntry<V> getCeilingEntry(int key) {
+ return super.entryOrSuccessor(key);
+ }
+
+ @Override
+ SplayedEntry<V> getHigherEntry(int key) {
+ return super.entrySuccessor(key);
+ }
+
+ @Override
+ SplayedEntry<V> getFloorEntry(int key) {
+ return super.entryOrPredecessor(key);
+ }
+
+ @Override
+ SplayedEntry<V> getLowerEntry(int key) {
+ return super.entryPredecessor(key);
+ }
+
+ private final class AscendingNavigableSubMapEntrySet extends NavigableSubMapEntrySet {
+
+ @Override
+ public Iterator<Entry<UnsignedInteger, V>> iterator() {
+ return new NavigableSubMapEntryIterator(lowestPossibleEntry(), highestPossibleEntry());
+ }
+ }
+ }
+
+ protected static final class DescendingSubMap<V> extends NavigableSubMap<V> {
+
+ DescendingSubMap(SplayMap<V> m,
+ boolean fromStart, int fromKey, boolean startInclusive,
+ boolean toEnd, int endKey, boolean endInclusive) {
+ super(m, fromStart, fromKey, startInclusive, toEnd, endKey, endInclusive);
+ }
+
+ private transient NavigableMap<UnsignedInteger, V> ascendingMapView;
+ private transient NavigableSubMapEntrySet navigableEntrySet;
+
+ @Override
+ public Comparator<? super UnsignedInteger> comparator() {
+ return REVERSE_COMPARATOR;
+ }
+
+ @Override
+ public NavigableMap<UnsignedInteger, V> descendingMap() {
+ return ascendingMapView != null ? ascendingMapView :
+ (ascendingMapView = new AscendingSubMap<>(backingMap,
+ fromStart, startKey, startInclusive, toEnd, endKey, endInclusive));
+ }
+
+ @Override
+ public NavigableMap<UnsignedInteger, V> subMap(UnsignedInteger fromKey, boolean fromInclusive,
+ UnsignedInteger toKey, boolean toInclusive) {
+ checkInRange(fromKey.intValue(), fromInclusive, toKey.intValue(), toInclusive);
+ return new DescendingSubMap<>(backingMap,
+ false, toKey.intValue(), toInclusive, false, fromKey.intValue(), fromInclusive);
+ }
+
+ @Override
+ public NavigableMap<UnsignedInteger, V> headMap(UnsignedInteger toKey, boolean inclusive) {
+ isInRange(toKey.intValue(), inclusive);
+ return new DescendingSubMap<>(backingMap,
+ false, toKey.intValue(), inclusive, toEnd, endKey, endInclusive);
+ }
+
+ @Override
+ public NavigableMap<UnsignedInteger, V> tailMap(UnsignedInteger fromKey, boolean inclusive) {
+ isInRange(fromKey.intValue(), inclusive);
+ return new DescendingSubMap<>(backingMap,
+ fromStart, startKey, startInclusive, false, fromKey.intValue(), inclusive);
+ }
+
+ @Override
+ public Set<Entry<UnsignedInteger, V>> entrySet() {
+ return navigableEntrySet != null ?
+ navigableEntrySet : (navigableEntrySet = new DescendingNavigableSubMapEntrySet());
+ }
+
+ @Override
+ Iterator<UnsignedInteger> keyIterator() {
+ return new DescendingNavigableSubMapKeyIterator(getHighestEntry(), getLowestEntry());
+ }
+
+ @Override
+ Iterator<UnsignedInteger> descendingKeyIterator() {
+ return new NavigableSubMapKeyIterator(getHighestEntry(), getLowestEntry());
+ }
+
+ @Override
+ SplayedEntry<V> getLowestEntry() {
+ return super.highestPossibleEntry();
+ }
+
+ @Override
+ SplayedEntry<V> getHighestEntry() {
+ return super.lowestPossibleEntry();
+ }
+
+ @Override
+ SplayedEntry<V> getCeilingEntry(int key) {
+ return super.entryPredecessor(key);
+ }
+
+ @Override
+ SplayedEntry<V> getHigherEntry(int key) {
+ return super.entryPredecessor(key);
+ }
+
+ @Override
+ SplayedEntry<V> getFloorEntry(int key) {
+ return super.entryOrSuccessor(key);
+ }
+
+ @Override
+ SplayedEntry<V> getLowerEntry(int key) {
+ return super.entryOrSuccessor(key);
+ }
+
+ @Override
+ public void forEach(BiConsumer<? super UnsignedInteger, ? super V> action) {
+ Objects.requireNonNull(action);
+ for (Map.Entry<UnsignedInteger, V> entry : entrySet()) {
+ UnsignedInteger k;
+ V v;
+ try {
+ k = entry.getKey();
+ v = entry.getValue();
+ } catch (IllegalStateException ise) {
+ // this usually means the entry is no longer in the map.
+ throw new ConcurrentModificationException(ise);
+ }
+ action.accept(k, v);
+ }
+ }
+
+ private final class DescendingNavigableSubMapEntrySet extends NavigableSubMapEntrySet {
+
+ @Override
+ public Iterator<Entry<UnsignedInteger, V>> iterator() {
+ return new DescendingNavigableSubMapEntryIterator(highestPossibleEntry(), lowestPossibleEntry());
+ }
+ }
+ }
}
diff --git a/protonj2/src/test/java/org/apache/qpid/protonj2/engine/impl/ProtonSenderTest.java b/protonj2/src/test/java/org/apache/qpid/protonj2/engine/impl/ProtonSenderTest.java
index 66d44bd..6f3cbcf 100644
--- a/protonj2/src/test/java/org/apache/qpid/protonj2/engine/impl/ProtonSenderTest.java
+++ b/protonj2/src/test/java/org/apache/qpid/protonj2/engine/impl/ProtonSenderTest.java
@@ -4158,6 +4158,75 @@
}
@Test
+ public void testSenderReportsDeliveryUpdatedOnDispositionForMultipleTransfersInsideTheRange() throws Exception {
+ final Engine engine = EngineFactory.PROTON.createNonSaslEngine();
+ engine.errorHandler(result -> failure = result.failureCause());
+ final ProtonTestConnector peer = createTestPeer(engine);
+ final byte[] payload = new byte[] {0, 1, 2, 3, 4};
+
+ peer.expectAMQPHeader().respondWithAMQPHeader();
+ peer.expectOpen().respond().withContainerId("driver");
+ peer.expectBegin().respond();
+ peer.expectAttach().respond();
+ peer.remoteFlow().withLinkCredit(10).queue();
+ for (int i = 0; i < 10; ++i) {
+ peer.expectTransfer().withDeliveryId(i)
+ .withDeliveryTag(new byte[] {(byte) i})
+ .withMore(false)
+ .withPayload(payload);
+ }
+ peer.remoteDisposition().withSettled(true)
+ .withRole(Role.RECEIVER.getValue())
+ .withState().accepted()
+ .withFirst(1)
+ .withLast(3).queue();
+
+ Connection connection = engine.start().open();
+ Session session = connection.session().open();
+ Sender sender = session.sender("test");
+
+ final AtomicInteger dispositionCounter = new AtomicInteger();
+
+ final ArrayList<OutgoingDelivery> deliveries = new ArrayList<>();
+
+ sender.deliveryStateUpdatedHandler(delivery -> {
+ if (delivery.isRemotelySettled()) {
+ dispositionCounter.incrementAndGet();
+ deliveries.add(delivery);
+ delivery.settle();
+ }
+ });
+
+ sender.open();
+
+ for (int i = 0; i < 10; ++i) {
+ OutgoingDelivery delivery = sender.next();
+ delivery.setTag(new byte[] { (byte) i });
+ delivery.writeBytes(ProtonByteBufferAllocator.DEFAULT.wrap(payload));
+ }
+
+ peer.waitForScriptToComplete();
+ peer.expectDetach().respond();
+
+ assertEquals(7, sender.unsettled().size());
+
+ sender.close();
+
+ assertEquals(3, deliveries.size(), "Not all deliveries received dispositions");
+
+ byte deliveryTag = 1;
+
+ for (OutgoingDelivery delivery : deliveries) {
+ assertEquals(deliveryTag++, delivery.getTag().tagBuffer().getByte(0), "Delivery not updated in correct order");
+ assertTrue(delivery.isRemotelySettled(), "Delivery should be marked as remotely settled");
+ }
+
+ peer.waitForScriptToComplete();
+
+ assertNull(failure);
+ }
+
+ @Test
public void testSenderReportsIsSendableAfterOpenedIfRemoteSendsFlowBeforeLocallyOpened() throws Exception {
Engine engine = EngineFactory.PROTON.createNonSaslEngine();
engine.errorHandler(result -> failure = result.failureCause());
diff --git a/protonj2/src/test/java/org/apache/qpid/protonj2/engine/util/LinkedSplayMapTest.java b/protonj2/src/test/java/org/apache/qpid/protonj2/engine/util/LinkedSplayMapTest.java
index 5e59d3e..04a563f 100644
--- a/protonj2/src/test/java/org/apache/qpid/protonj2/engine/util/LinkedSplayMapTest.java
+++ b/protonj2/src/test/java/org/apache/qpid/protonj2/engine/util/LinkedSplayMapTest.java
@@ -112,6 +112,35 @@
*/
@Override
@Test
+ public void testNavigableKeysIterationFollowsUnsignedOrderingExpectations() {
+ LinkedSplayMap<String> map = createMap();
+
+ final int[] inputValues = {3, 0, -1, 1, -2, 2};
+ final int[] expectedOrder = {3, 0, -1, 1, -2, 2};
+
+ for (int entry : inputValues) {
+ map.put(entry, "" + entry);
+ }
+
+ Collection<UnsignedInteger> keys = map.navigableKeySet();
+ Iterator<UnsignedInteger> iterator = keys.iterator();
+ assertNotNull(iterator);
+ assertTrue(iterator.hasNext());
+
+ int counter = 0;
+ while (iterator.hasNext()) {
+ assertEquals(UnsignedInteger.valueOf(expectedOrder[counter++]), iterator.next());
+ }
+
+ // Check that we really did iterate.
+ assertEquals(inputValues.length, counter);
+ }
+
+ /**
+ * Test differs from parent as order is insertion based.
+ */
+ @Override
+ @Test
public void testEntryIterationFollowsUnsignedOrderingExpectations() {
LinkedSplayMap<String> map = createMap();
diff --git a/protonj2/src/test/java/org/apache/qpid/protonj2/engine/util/SplayMapTest.java b/protonj2/src/test/java/org/apache/qpid/protonj2/engine/util/SplayMapTest.java
index edb11b3..d819257 100644
--- a/protonj2/src/test/java/org/apache/qpid/protonj2/engine/util/SplayMapTest.java
+++ b/protonj2/src/test/java/org/apache/qpid/protonj2/engine/util/SplayMapTest.java
@@ -18,21 +18,28 @@
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertNotEquals;
import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertSame;
+import static org.junit.jupiter.api.Assertions.assertThrows;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.junit.jupiter.api.Assertions.fail;
+import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
+import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;
+import java.util.SortedMap;
import org.apache.qpid.protonj2.logging.ProtonLogger;
import org.apache.qpid.protonj2.logging.ProtonLoggerFactory;
@@ -49,12 +56,22 @@
protected long seed;
protected Random random;
+ protected UnsignedInteger uintArray[] = new UnsignedInteger[1000];
+ protected String objArray[] = new String[1000];
+ protected SplayMap<String> testMap = new SplayMap<>();
@BeforeEach
public void setUp() {
seed = System.nanoTime();
random = new Random();
random.setSeed(seed);
+
+ testMap = new SplayMap<>();
+ for (int i = 0; i < objArray.length; i++) {
+ UnsignedInteger x = uintArray[i] = UnsignedInteger.valueOf(i);
+ String y = objArray[i] = UnsignedInteger.valueOf(i).toString();
+ testMap.put(x, y);
+ }
}
protected <E> SplayMap<E> createMap() {
@@ -123,6 +140,26 @@
}
@Test
+ public void testSizeWithSubMaps() {
+ assertEquals(1000, testMap.size(), "Returned incorrect size");
+ assertEquals(500, testMap.headMap(UnsignedInteger.valueOf(500)).size(), "Returned incorrect size");
+ assertEquals(0, testMap.headMap(UnsignedInteger.valueOf(0)).size(), "Returned incorrect size");
+ assertEquals(1, testMap.headMap(UnsignedInteger.valueOf(1)).size(), "Returned incorrect size");
+ assertEquals(501, testMap.headMap(UnsignedInteger.valueOf(501)).size(), "Returned incorrect size");
+ assertEquals(500, testMap.tailMap(UnsignedInteger.valueOf(500)).size(), "Returned incorrect size");
+ assertEquals(1000, testMap.tailMap(UnsignedInteger.valueOf(0)).size(), "Returned incorrect size");
+ assertEquals(500, testMap.tailMap(UnsignedInteger.valueOf(500)).size(), "Returned incorrect size");
+ assertEquals(100, testMap.subMap(UnsignedInteger.valueOf(500), UnsignedInteger.valueOf(600)).size(), "Returned incorrect size");
+
+ assertThrows(NullPointerException.class, () -> testMap.subMap(null, UnsignedInteger.valueOf(600)));
+ assertThrows(NullPointerException.class, () -> testMap.subMap(UnsignedInteger.valueOf(600), null));
+ assertThrows(NullPointerException.class, () -> testMap.subMap(null, null));
+ assertThrows(NullPointerException.class, () -> testMap.subMap(null, true, null, true));
+ assertThrows(NullPointerException.class, () -> testMap.headMap(null));
+ assertThrows(NullPointerException.class, () -> testMap.tailMap(null));
+ }
+
+ @Test
public void testInsert() {
SplayMap<String> map = createMap();
@@ -725,6 +762,27 @@
}
@Test
+ public void testKeysIterationRemoveContract() {
+ Set<UnsignedInteger> set = testMap.keySet();
+ Iterator<UnsignedInteger> iter = set.iterator();
+ iter.next();
+ iter.remove();
+
+ // No remove allowed again until next is called
+ assertThrows(IllegalStateException.class, () -> iter.remove());
+
+ iter.next();
+ iter.remove();
+
+ assertEquals(998, testMap.size());
+
+ iter.next();
+ assertNotNull(testMap.remove(999));
+
+ assertThrows(ConcurrentModificationException.class, () -> iter.remove());
+ }
+
+ @Test
public void testKeysIteration() {
SplayMap<String> map = createMap();
@@ -814,6 +872,194 @@
}
@Test
+ public void testKeySetRetainAllFromCollection() throws Exception {
+ final Collection<UnsignedInteger> collection = new ArrayList<>();
+ collection.add(UnsignedInteger.valueOf(200));
+
+ assertEquals(1000, testMap.size());
+
+ final Set<UnsignedInteger> keys = testMap.keySet();
+
+ keys.retainAll(collection);
+ assertEquals(1, testMap.size());
+ keys.removeAll(collection);
+ assertEquals(0, testMap.size());
+ testMap.put(1, "one");
+ assertEquals(1, testMap.size());
+ keys.clear();
+ assertEquals(0, testMap.size());
+ }
+
+ @Test
+ public void testNavigableKeySetReturned() {
+ SplayMap<String> map = createMap();
+
+ map.put(0, "zero");
+ map.put(1, "one");
+ map.put(2, "two");
+ map.put(3, "three");
+
+ Set<UnsignedInteger> keys = map.navigableKeySet();
+ assertNotNull(keys);
+ assertEquals(4, keys.size());
+ assertFalse(keys.isEmpty());
+ assertSame(keys, map.keySet());
+ }
+
+ @Test
+ public void testNavigableKeysIterationRemove() {
+ SplayMap<String> map = createMap();
+
+ final int[] intValues = {0, 1, 2, 3};
+
+ for (int entry : intValues) {
+ map.put(entry, "" + entry);
+ }
+
+ Collection<UnsignedInteger> keys = map.navigableKeySet();
+ Iterator<UnsignedInteger> iterator = keys.iterator();
+ assertNotNull(iterator);
+ assertTrue(iterator.hasNext());
+
+ int counter = 0;
+ while (iterator.hasNext()) {
+ assertEquals(UnsignedInteger.valueOf(intValues[counter++]), iterator.next());
+ }
+
+ // Check that we really did iterate.
+ assertEquals(intValues.length, counter);
+ }
+
+ @Test
+ public void testNavigableKeysIterationRemoveContract() {
+ Set<UnsignedInteger> set = testMap.navigableKeySet();
+ Iterator<UnsignedInteger> iter = set.iterator();
+ iter.next();
+ iter.remove();
+
+ // No remove allowed again until next is called
+ assertThrows(IllegalStateException.class, () -> iter.remove());
+
+ iter.next();
+ iter.remove();
+
+ assertEquals(998, testMap.size());
+
+ iter.next();
+ assertNotNull(testMap.remove(999));
+
+ assertThrows(ConcurrentModificationException.class, () -> iter.remove());
+ }
+
+ @Test
+ public void testNavigableKeysIteration() {
+ SplayMap<String> map = createMap();
+
+ final int[] intValues = {0, 1, 2, 3};
+
+ for (int entry : intValues) {
+ map.put(entry, "" + entry);
+ }
+
+ Collection<UnsignedInteger> keys = map.navigableKeySet();
+ Iterator<UnsignedInteger> iterator = keys.iterator();
+ assertNotNull(iterator);
+ assertTrue(iterator.hasNext());
+
+ int counter = 0;
+ while (iterator.hasNext()) {
+ assertEquals(UnsignedInteger.valueOf(intValues[counter++]), iterator.next());
+ iterator.remove();
+ }
+
+ // Check that we really did iterate.
+ assertEquals(intValues.length, counter);
+ assertTrue(map.isEmpty());
+ assertEquals(0, map.size());
+ }
+
+ @Test
+ public void testNavigableKeysIterationFollowsUnsignedOrderingExpectations() {
+ SplayMap<String> map = createMap();
+
+ final int[] inputValues = {3, 0, -1, 1, -2, 2};
+ final int[] expectedOrder = {0, 1, 2, 3, -2, -1};
+
+ for (int entry : inputValues) {
+ map.put(entry, "" + entry);
+ }
+
+ Collection<UnsignedInteger> keys = map.navigableKeySet();
+ Iterator<UnsignedInteger> iterator = keys.iterator();
+ assertNotNull(iterator);
+ assertTrue(iterator.hasNext());
+
+ int counter = 0;
+ while (iterator.hasNext()) {
+ assertEquals(UnsignedInteger.valueOf(expectedOrder[counter++]), iterator.next());
+ }
+
+ // Check that we really did iterate.
+ assertEquals(inputValues.length, counter);
+ }
+
+ @Test
+ public void testNavigableKeysIterationFailsWhenConcurrentlyModified() {
+ SplayMap<String> map = createMap();
+
+ final int[] inputValues = {3, 0, -1, 1, -2, 2};
+
+ for (int entry : inputValues) {
+ map.put(entry, "" + entry);
+ }
+
+ Collection<UnsignedInteger> keys = map.navigableKeySet();
+ Iterator<UnsignedInteger> iterator = keys.iterator();
+ assertNotNull(iterator);
+ assertTrue(iterator.hasNext());
+
+ map.remove(3);
+
+ try {
+ iterator.next();
+ fail("Should not iterate when modified outside of iterator");
+ } catch (ConcurrentModificationException cme) {}
+ }
+
+ @Test
+ public void testNavigableKeysIterationOnEmptyTree() {
+ SplayMap<String> map = createMap();
+ Collection<UnsignedInteger> keys = map.navigableKeySet();
+ Iterator<UnsignedInteger> iterator = keys.iterator();
+
+ assertFalse(iterator.hasNext());
+ try {
+ iterator.next();
+ fail("Should have thrown a NoSuchElementException");
+ } catch (NoSuchElementException nse) {
+ }
+ }
+
+ @Test
+ public void testNavigableKeySetRetainAllFromCollection() throws Exception {
+ final Collection<UnsignedInteger> collection = new ArrayList<>();
+ collection.add(UnsignedInteger.valueOf(200));
+
+ assertEquals(1000, testMap.size());
+
+ final Set<UnsignedInteger> keys = testMap.navigableKeySet();
+
+ keys.retainAll(collection);
+ assertEquals(1, testMap.size());
+ keys.removeAll(collection);
+ assertEquals(0, testMap.size());
+ testMap.put(1, "one");
+ assertEquals(1, testMap.size());
+ keys.clear();
+ assertEquals(0, testMap.size());
+ }
+
+ @Test
public void tesEntrySetReturned() {
SplayMap<String> map = createMap();
@@ -1040,6 +1286,10 @@
map.put(entry, "" + entry);
}
+ assertEquals(UnsignedInteger.valueOf(0), map.firstKey());
+ SortedMap<UnsignedInteger, String> descending = map.descendingMap();
+ assertEquals(UnsignedInteger.valueOf(-1), descending.firstKey());
+
for (int expected : expectedOrder) {
assertEquals(expected, map.pollFirstEntry().getPrimitiveKey());
}
@@ -1064,6 +1314,10 @@
map.put(entry, "" + entry);
}
+ assertEquals(UnsignedInteger.valueOf(-1), map.lastKey());
+ SortedMap<UnsignedInteger, String> descending = map.descendingMap();
+ assertEquals(UnsignedInteger.valueOf(0), descending.lastKey());
+
for (int expected : expectedOrder) {
assertEquals(expected, map.lastKey().intValue());
map.remove(expected);
@@ -1073,6 +1327,27 @@
}
@Test
+ public void testLastKeyAfterSubMap() {
+ SplayMap<String> tm = new SplayMap<String>();
+ tm.put(1, "VAL001");
+ tm.put(3, "VAL003");
+ tm.put(2, "VAL002");
+ SortedMap<UnsignedInteger, String> sm = tm;
+ UnsignedInteger firstKey = sm.firstKey();
+ UnsignedInteger lastKey = null;
+
+ for (int i = 1; i <= tm.size(); i++) {
+ try {
+ lastKey = sm.lastKey();
+ } catch (NoSuchElementException excep) {
+ assertTrue(sm.isEmpty());
+ fail("NoSuchElementException thrown when there are elements in the map");
+ }
+ sm = sm.subMap(firstKey, lastKey);
+ }
+ }
+
+ @Test
public void testLastEntryOnEmptyMap() {
SplayMap<String> map = createMap();
assertNull(map.lastEntry());
@@ -1139,6 +1414,28 @@
});
assertEquals(index.intValue(), inputValues.length);
+
+ NavigableMap<UnsignedInteger, String> descemding = map.descendingMap();
+
+ assertEquals(map.size(), descemding.size());
+
+ descemding.forEach((k, v) -> {
+ int value = index.decrement().intValue();
+ assertEquals(expectedOrder[value], k.intValue());
+ });
+
+ assertEquals(index.intValue(), 0);
+
+ NavigableMap<UnsignedInteger, String> ascending = descemding.descendingMap();
+
+ assertEquals(map.size(), ascending.size());
+
+ ascending.forEach((k, v) -> {
+ int value = index.getAndIncrement().intValue();
+ assertEquals(expectedOrder[value], k.intValue());
+ });
+
+ assertEquals(index.intValue(), expectedOrder.length);
}
@Test
@@ -1339,6 +1636,10 @@
assertEquals(UnsignedInteger.valueOf(2), map.floorEntry(UnsignedInteger.valueOf(2)).getKey());
assertEquals(UnsignedInteger.valueOf(1), map.floorEntry(UnsignedInteger.valueOf(1)).getKey());
assertEquals(UnsignedInteger.valueOf(0), map.floorEntry(UnsignedInteger.valueOf(0)).getKey());
+
+ map.remove(0);
+
+ assertNull(map.floorEntry(UnsignedInteger.valueOf(0)));
}
@Test
@@ -1360,6 +1661,10 @@
assertEquals(UnsignedInteger.valueOf(2), map.floorKey(UnsignedInteger.valueOf(2)));
assertEquals(UnsignedInteger.valueOf(1), map.floorKey(UnsignedInteger.valueOf(1)));
assertEquals(UnsignedInteger.valueOf(0), map.floorKey(UnsignedInteger.valueOf(0)));
+
+ map.remove(0);
+
+ assertNull(map.floorEntry(UnsignedInteger.valueOf(0)));
}
@Test
@@ -1381,6 +1686,10 @@
assertEquals(UnsignedInteger.valueOf(-2), map.ceilingEntry(UnsignedInteger.valueOf(-3)).getKey());
assertEquals(UnsignedInteger.valueOf(-2), map.ceilingEntry(UnsignedInteger.valueOf(-2)).getKey());
assertEquals(UnsignedInteger.valueOf(-1), map.ceilingEntry(UnsignedInteger.valueOf(-1)).getKey());
+
+ map.remove(-1);
+
+ assertNull(map.ceilingEntry(UnsignedInteger.valueOf(-1)));
}
@Test
@@ -1402,6 +1711,472 @@
assertEquals(UnsignedInteger.valueOf(-2), map.ceilingKey(UnsignedInteger.valueOf(-3)));
assertEquals(UnsignedInteger.valueOf(-2), map.ceilingKey(UnsignedInteger.valueOf(-2)));
assertEquals(UnsignedInteger.valueOf(-1), map.ceilingKey(UnsignedInteger.valueOf(-1)));
+
+ map.remove(-1);
+
+ assertNull(map.ceilingKey(UnsignedInteger.valueOf(-1)));
+ }
+
+ @Test
+ public void testHeadMapForBasicTestMap() {
+ Map<UnsignedInteger, String> head = testMap.headMap(UnsignedInteger.valueOf(99));
+ assertEquals(99, head.size(), "Returned map of incorrect size");
+ assertTrue(head.containsKey(UnsignedInteger.valueOf(0)));
+ assertTrue(head.containsValue("1"));
+ assertTrue(head.containsKey(UnsignedInteger.valueOf(10)));
+
+ SortedMap<UnsignedInteger, Integer> intMap;
+ SortedMap<UnsignedInteger, Integer> sub;
+
+ int size = 16;
+ intMap = new SplayMap<Integer>();
+ for (int i = 1; i <= size; i++) {
+ intMap.put(UnsignedInteger.valueOf(i), i);
+ }
+ sub = intMap.headMap(UnsignedInteger.valueOf(0));
+ assertEquals(sub.size(), 0, "size should be zero");
+ assertTrue(sub.isEmpty(), "The SubMap should be empty");
+ try {
+ sub.firstKey();
+ fail("java.util.NoSuchElementException should be thrown");
+ } catch (java.util.NoSuchElementException e) {
+ }
+
+ SplayMap<Integer> t = new SplayMap<Integer>();
+ try {
+ @SuppressWarnings("unused")
+ SortedMap<UnsignedInteger, Integer> th = t.headMap(null);
+ fail("Should throw a NullPointerException");
+ } catch (NullPointerException npe) {
+ // expected
+ }
+
+ try {
+ sub.lastKey();
+ fail("java.util.NoSuchElementException should be thrown");
+ } catch (java.util.NoSuchElementException e) {
+ }
+
+ size = 256;
+ intMap = new SplayMap<Integer>();
+ for (int i = 0; i < size; i++) {
+ intMap.put(UnsignedInteger.valueOf(i), i);
+ }
+ sub = intMap.headMap(UnsignedInteger.valueOf(0));
+ assertEquals(sub.size(), 0, "size should be zero");
+ assertTrue(sub.isEmpty(), "SubMap should be empty");
+ try {
+ sub.firstKey();
+ fail("java.util.NoSuchElementException should be thrown");
+ } catch (java.util.NoSuchElementException e) {
+ }
+
+ try {
+ sub.lastKey();
+ fail("java.util.NoSuchElementException should be thrown");
+ } catch (java.util.NoSuchElementException e) {
+ }
+ }
+
+ @Test
+ public void testSubMapTwoArgVariant() {
+ SortedMap<UnsignedInteger, String> subMap = testMap.subMap(uintArray[100], uintArray[109]);
+
+ assertEquals(9, subMap.size(), "SubMap returned is of incorrect size");
+ for (int counter = 100; counter < 109; counter++) {
+ assertTrue(subMap.get(uintArray[counter]).equals(objArray[counter]), "SubMap contains incorrect elements");
+ }
+
+ assertThrows(IllegalArgumentException.class, () -> testMap.subMap(uintArray[9], uintArray[1]));
+
+ SortedMap<UnsignedInteger, String> map = new SplayMap<String>();
+ map.put(UnsignedInteger.valueOf(1), "one");
+ map.put(UnsignedInteger.valueOf(2), "two");
+ map.put(UnsignedInteger.valueOf(3), "three");
+ assertEquals(UnsignedInteger.valueOf(3), map.lastKey());
+ SortedMap<UnsignedInteger, String> sub = map.subMap(UnsignedInteger.valueOf(1), UnsignedInteger.valueOf(3));
+ assertEquals(UnsignedInteger.valueOf(2), sub.lastKey());
+
+ SortedMap<UnsignedInteger, String> t = new SplayMap<String>();
+ assertThrows(NullPointerException.class, () -> t.subMap(null, UnsignedInteger.valueOf(1)));
+ }
+
+ @Test
+ public void testSubMapIterator() {
+ SplayMap<String> map = new SplayMap<String>();
+
+ UnsignedInteger[] keys = { UnsignedInteger.valueOf(1), UnsignedInteger.valueOf(2), UnsignedInteger.valueOf(3) };
+ String[] values = { "one", "two", "three" };
+ for (int i = 0; i < keys.length; i++) {
+ map.put(keys[i], values[i]);
+ }
+
+ assertEquals(3, map.size());
+
+ SortedMap<UnsignedInteger, String> subMap = map.subMap(UnsignedInteger.valueOf(0), UnsignedInteger.valueOf(4));
+ assertEquals(3, subMap.size());
+
+ Set<Map.Entry<UnsignedInteger, String>> entrySet = subMap.entrySet();
+ Iterator<Map.Entry<UnsignedInteger, String>> iter = entrySet.iterator();
+ int size = 0;
+ while (iter.hasNext()) {
+ Map.Entry<UnsignedInteger, String> entry = iter.next();
+ assertTrue(map.containsKey(entry.getKey()));
+ assertTrue(map.containsValue(entry.getValue()));
+ size++;
+ }
+ assertEquals(map.size(), size);
+
+ Set<UnsignedInteger> keySet = subMap.keySet();
+ Iterator<UnsignedInteger> keyIter = keySet.iterator();
+ size = 0;
+ while (keyIter.hasNext()) {
+ UnsignedInteger key = keyIter.next();
+ assertTrue(map.containsKey(key));
+ size++;
+ }
+ assertEquals(map.size(), size);
+ }
+
+ @Test
+ public void testTailMapWithSingleArgument() {
+ SortedMap<UnsignedInteger, String> tail = testMap.tailMap(uintArray[900]);
+ assertEquals(tail.size(), (uintArray.length - 900), "Returned map of incorrect size : " + tail.size());
+ for (int i = 900; i < objArray.length; i++) {
+ assertTrue(tail.containsValue(objArray[i]), "Map contains incorrect entries");
+ }
+
+ SortedMap<UnsignedInteger, Integer> intMap;
+
+ int size = 16;
+ intMap = new SplayMap<Integer>();
+
+ for (int i = 0; i < size; i++) {
+ intMap.put(UnsignedInteger.valueOf(i), i);
+ }
+
+ final SortedMap<UnsignedInteger, Integer> sub = intMap.tailMap(UnsignedInteger.valueOf(size));
+ assertEquals(sub.size(),0, "size should be zero");
+ assertTrue(sub.isEmpty(), "SubMap should be empty");
+
+ assertThrows(NoSuchElementException.class, () -> sub.firstKey());
+ assertThrows(NullPointerException.class, () -> new SplayMap<String>().tailMap(null));
+ assertThrows(NoSuchElementException.class, () -> sub.lastKey());
+
+ // Try with larger more complex tree structure.
+
+ size = 256;
+ intMap = new SplayMap<Integer>();
+ for (int i = 0; i < size; i++) {
+ intMap.put(UnsignedInteger.valueOf(i), i);
+ }
+ final SortedMap<UnsignedInteger, Integer> sub1 = intMap.tailMap(UnsignedInteger.valueOf(size));
+
+ assertThrows(NoSuchElementException.class, () -> sub1.firstKey());
+ assertThrows(NullPointerException.class, () -> new SplayMap<String>().tailMap(null));
+ assertThrows(NoSuchElementException.class, () -> sub1.lastKey());
+ }
+
+ @SuppressWarnings({ "unchecked", "rawtypes" })
+ @Test
+ public void testNavigableKeySetOperationInteractions() throws Exception {
+ UnsignedInteger testint9999 = UnsignedInteger.valueOf(9999);
+ UnsignedInteger testint10000 = UnsignedInteger.valueOf(10000);
+ UnsignedInteger testint100 = UnsignedInteger.valueOf(100);
+ UnsignedInteger testint0 = UnsignedInteger.valueOf(0);
+
+ final NavigableSet untypedSet = testMap.navigableKeySet();
+ final NavigableSet<UnsignedInteger> set = testMap.navigableKeySet();
+
+ assertFalse(set.contains(testint9999));
+ testMap.put(testint9999, testint9999.toString());
+ assertTrue(set.contains(testint9999));
+ testMap.remove(testint9999);
+ assertFalse(set.contains(testint9999));
+
+ assertThrows(UnsupportedOperationException.class, () -> untypedSet.add(new Object()));
+ assertThrows(UnsupportedOperationException.class, () -> untypedSet.add(null));
+ assertThrows(NullPointerException.class, () -> untypedSet.addAll(null));
+
+ final Collection collection = new ArrayList();
+ set.addAll(collection);
+ try {
+ collection.add(new Object());
+ set.addAll(collection);
+ fail("should throw UnsupportedOperationException");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ set.remove(testint100);
+ assertFalse(testMap.containsKey(testint100));
+ assertTrue(testMap.containsKey(testint0));
+
+ final Iterator iter = set.iterator();
+ iter.next();
+ iter.remove();
+ assertFalse(testMap.containsKey(testint0));
+ collection.add(UnsignedInteger.valueOf(2));
+ set.retainAll(collection);
+ assertEquals(1, testMap.size());
+ set.removeAll(collection);
+ assertEquals(0, testMap.size());
+ testMap.put(testint10000, testint10000.toString());
+ assertEquals(1, testMap.size());
+ set.clear();
+ assertEquals(0, testMap.size());
+ }
+
+ @Test
+ public void testEmptySubMap() throws Exception {
+ SplayMap<List<Integer>> tm = new SplayMap<>();
+ SortedMap<UnsignedInteger, List<Integer>> sm = tm.tailMap(UnsignedInteger.valueOf(1));
+ assertTrue(sm.values().size() == 0);
+
+ NavigableMap<UnsignedInteger, List<Integer>> sm1 = tm.descendingMap();
+ assertTrue(sm1.values().size() == 0);
+
+ NavigableMap<UnsignedInteger, List<Integer>> sm2 = sm1.tailMap(UnsignedInteger.valueOf(1), true);
+ assertTrue(sm2.values().size() == 0);
+ }
+
+ @Test
+ public void testValuesOneEntrySubMap() {
+ SplayMap<String> tm = new SplayMap<String>();
+ tm.put(1, "VAL001");
+ tm.put(3, "VAL003");
+ tm.put(2, "VAL002");
+
+ UnsignedInteger firstKey = tm.firstKey();
+ SortedMap<UnsignedInteger, String> subMap = tm.subMap(firstKey, firstKey);
+ Iterator<String> iter = subMap.values().iterator();
+ assertNotNull(iter);
+ }
+
+ @Test
+ public void testDescendingMapSubMap() throws Exception {
+ SplayMap<Object> tm = new SplayMap<>();
+ for (int i = 0; i < 10; ++i) {
+ tm.put(i, new Object());
+ }
+
+ NavigableMap<UnsignedInteger, Object> descMap = tm.descendingMap();
+ assertEquals(7, descMap.subMap(UnsignedInteger.valueOf(8), true, UnsignedInteger.valueOf(1), false).size());
+ assertEquals(4, descMap.headMap(UnsignedInteger.valueOf(6), true).size());
+ assertEquals(2, descMap.tailMap(UnsignedInteger.valueOf(2), false).size());
+
+ // sub map of sub map of descendingMap
+ NavigableMap<UnsignedInteger, Object> mapUIntObj = new SplayMap<Object>();
+ for (int i = 0; i < 10; ++i) {
+ mapUIntObj.put(UnsignedInteger.valueOf(i), new Object());
+ }
+ mapUIntObj = mapUIntObj.descendingMap();
+ NavigableMap<UnsignedInteger, Object> subMapUIntObj =
+ mapUIntObj.subMap(UnsignedInteger.valueOf(9), true, UnsignedInteger.valueOf(5), false);
+
+ assertEquals(4, subMapUIntObj.size());
+ subMapUIntObj = subMapUIntObj.subMap(UnsignedInteger.valueOf(9), true, UnsignedInteger.valueOf(5), false);
+ assertEquals(4, subMapUIntObj.size());
+ subMapUIntObj = subMapUIntObj.subMap(UnsignedInteger.valueOf(6), false, UnsignedInteger.valueOf(5), false);
+ assertEquals(0, subMapUIntObj.size());
+
+ subMapUIntObj = mapUIntObj.headMap(UnsignedInteger.valueOf(5), false);
+ assertEquals(4, subMapUIntObj.size());
+ subMapUIntObj = subMapUIntObj.headMap(UnsignedInteger.valueOf(5), false);
+ assertEquals(4, subMapUIntObj.size());
+ subMapUIntObj = subMapUIntObj.tailMap(UnsignedInteger.valueOf(5), false);
+ assertEquals(0, subMapUIntObj.size());
+
+ subMapUIntObj = mapUIntObj.tailMap(UnsignedInteger.valueOf(5), false);
+ assertEquals(5, subMapUIntObj.size());
+ subMapUIntObj = subMapUIntObj.tailMap(UnsignedInteger.valueOf(5), false);
+ assertEquals(5, subMapUIntObj.size());
+ subMapUIntObj = subMapUIntObj.headMap(UnsignedInteger.valueOf(5), false);
+ assertEquals(0, subMapUIntObj.size());
+ }
+
+ @Test
+ public void testEqualsJDKMapTypes() throws Exception {
+ // comparing SplayMap with different object types
+ Map<UnsignedInteger, String> m1 = new SplayMap<>();
+ Map<UnsignedInteger, String> m2 = new SplayMap<>();
+
+ m1.put(UnsignedInteger.valueOf(1), "val1");
+ m1.put(UnsignedInteger.valueOf(2), "val2");
+ m2.put(UnsignedInteger.valueOf(3), "val1");
+ m2.put(UnsignedInteger.valueOf(4), "val2");
+
+ assertNotEquals(m1, m2, "Maps should not be equal 1");
+ assertNotEquals(m2, m1, "Maps should not be equal 2");
+
+ // comparing SplayMap with HashMap with equal values
+ m1 = new SplayMap<>();
+ m2 = new HashMap<>();
+ m1.put(UnsignedInteger.valueOf(1), "val");
+ m2.put(UnsignedInteger.valueOf(2), "val");
+ assertNotEquals(m1, m2, "Maps should not be equal 3");
+ assertNotEquals(m2, m1, "Maps should not be equal 4");
+
+ // comparing SplayMap with differing objects inside values
+ m1 = new SplayMap<>();
+ m2 = new SplayMap<>();
+ m1.put(UnsignedInteger.valueOf(1), "val1");
+ m2.put(UnsignedInteger.valueOf(1), "val2");
+ assertNotEquals(m1, m2, "Maps should not be equal 5");
+ assertNotEquals(m2, m1, "Maps should not be equal 6");
+
+ // comparing SplayMap with same objects inside values
+ m1 = new SplayMap<>();
+ m2 = new SplayMap<>();
+ m1.put(UnsignedInteger.valueOf(1), "val1");
+ m2.put(UnsignedInteger.valueOf(1), "val1");
+ assertTrue(m1.equals(m2), "Maps should be equal 7");
+ assertTrue(m2.equals(m1), "Maps should be equal 7");
+ }
+
+ @Test
+ public void testEntrySetContains() throws Exception {
+ SplayMap<String> first = new SplayMap<>();
+ SplayMap<String> second = new SplayMap<>();
+
+ first.put(UnsignedInteger.valueOf(1), "one");
+ Object[] entry = first.entrySet().toArray();
+ assertFalse(second.entrySet().contains(entry[0]),
+ "Empty map should not contain anything from first map");
+
+ Map<UnsignedInteger, String> submap = second.subMap(UnsignedInteger.valueOf(0), UnsignedInteger.valueOf(1));
+ entry = first.entrySet().toArray();
+ assertFalse(submap.entrySet().contains(entry[0]),
+ "Empty SubMap should not contain the first map's entry");
+
+ second.put(UnsignedInteger.valueOf(1), "one");
+ assertTrue(second.entrySet().containsAll(first.entrySet()),
+ "entrySet().containsAll(...) should work with values");
+
+ first.clear();
+ first.put(UnsignedInteger.valueOf(1), "two");
+ entry = first.entrySet().toArray();
+ assertFalse(second.entrySet().contains(entry[0]),
+ "new valued entry should not equal old valued entry");
+ }
+
+ @Test
+ public void testValues() {
+ Collection<String> vals = testMap.values();
+ vals.iterator();
+ assertEquals(vals.size(), objArray.length, "Returned collection of incorrect size");
+ for (String element : objArray) {
+ assertTrue(vals.contains(element), "Collection contains incorrect elements");
+ }
+
+ assertEquals(1000, vals.size());
+ int j = 0;
+ for (Iterator<String> iter = vals.iterator(); iter.hasNext(); j++) {
+ String element = iter.next();
+ assertNotNull(element);
+ }
+ assertEquals(1000, j);
+
+ vals = testMap.descendingMap().values();
+ assertNotNull(vals.iterator());
+ assertEquals(vals.size(), objArray.length, "Returned collection of incorrect size");
+ for (String element : objArray) {
+ assertTrue(vals.contains(element), "Collection contains incorrect elements");
+ }
+ assertEquals(1000, vals.size());
+ j = 0;
+ for (Iterator<String> iter = vals.iterator(); iter.hasNext(); j++) {
+ String element = iter.next();
+ assertNotNull(element);
+ }
+ assertEquals(1000, j);
+
+ SplayMap<String> myMap = new SplayMap<String>();
+ for (int i = 0; i < 100; i++) {
+ myMap.put(uintArray[i], objArray[i]);
+ }
+ Collection<String> values = myMap.values();
+ values.remove(UnsignedInteger.ZERO.toString());
+ assertTrue(!myMap.containsKey(UnsignedInteger.ZERO), "Removing from the values collection should remove from the original map");
+ assertTrue(!myMap.containsValue(UnsignedInteger.ZERO.toString()), "Removing from the values collection should remove from the original map");
+ assertEquals(99, values.size());
+ j = 0;
+ for (Iterator<String> iter = values.iterator(); iter.hasNext(); j++) {
+ iter.next();
+ }
+ assertEquals(99, j);
+ }
+
+ @Test
+ public void testSubMapValuesSizeMetrics() {
+ SplayMap<String> myMap = new SplayMap<>();
+ for (int i = 0; i < 1000; i++) {
+ myMap.put(i, objArray[i]);
+ }
+
+ // Test for method values() in subMaps
+ Collection<String> vals = myMap.subMap(UnsignedInteger.valueOf(200), UnsignedInteger.valueOf(400)).values();
+ assertEquals(200, vals.size(), "Returned collection of incorrect size");
+ for (int i = 200; i < 400; i++) {
+ assertTrue(vals.contains(objArray[i]), "Collection contains incorrect elements" + i);
+ }
+ assertEquals(200, vals.toArray().length);
+ vals.remove(objArray[300]);
+ assertTrue(!myMap.containsValue(objArray[300]),
+ "Removing from the values collection should remove from the original map");
+ assertTrue(vals.size() == 199, "Returned collection of incorrect size");
+ assertEquals(199, vals.toArray().length);
+
+ myMap.put(300, objArray[300]);
+ // Test for method values() in subMaps
+ vals = myMap.headMap(UnsignedInteger.valueOf(400)).values();
+ assertEquals(vals.size(), 400, "Returned collection of incorrect size");
+ for (int i = 0; i < 400; i++) {
+ assertTrue(vals.contains(objArray[i]), "Collection contains incorrect elements " + i);
+ }
+ assertEquals(400,vals.toArray().length);
+ vals.remove(objArray[300]);
+ assertTrue(!myMap.containsValue(objArray[300]), "Removing from the values collection should remove from the original map");
+ assertEquals(vals.size(), 399, "Returned collection of incorrect size");
+ assertEquals(399, vals.toArray().length);
+
+ myMap.put(300, objArray[300]);
+ // Test for method values() in subMaps
+ vals = myMap.tailMap(UnsignedInteger.valueOf(400)).values();
+ assertEquals(vals.size(), 600, "Returned collection of incorrect size");
+ for (int i = 400; i < 1000; i++) {
+ assertTrue(vals.contains(objArray[i]), "Collection contains incorrect elements " + i);
+ }
+ assertEquals(600, vals.toArray().length);
+ vals.remove(objArray[600]);
+ assertTrue(!myMap.containsValue(objArray[600]), "Removing from the values collection should remove from the original map");
+ assertEquals(vals.size(), 599, "Returned collection of incorrect size");
+ assertEquals(599,vals.toArray().length);
+
+ myMap.put(600, objArray[600]);
+ // Test for method values() in subMaps
+ vals = myMap.descendingMap().headMap(UnsignedInteger.valueOf(400)).values();
+ assertEquals(vals.size(), 599, "Returned collection of incorrect size");
+ for (int i = 401; i < 1000; i++) {
+ assertTrue(vals.contains(objArray[i]), "Collection contains incorrect elements " + i);
+ }
+ assertEquals(599,vals.toArray().length);
+ vals.remove(objArray[600]);
+ assertTrue(!myMap.containsValue(objArray[600]), "Removing from the values collection should remove from the original map");
+ assertEquals(vals.size(), 598, "Returned collection of incorrect size");
+ assertEquals(598,vals.toArray().length);
+
+ myMap.put(600, objArray[600]);
+ // Test for method values() in subMaps
+ vals = myMap.descendingMap().tailMap(UnsignedInteger.valueOf(400)).values();
+ assertEquals(vals.size(), 401, "Returned collection of incorrect size");
+ for (int i = 0; i <= 400; i++) {
+ assertTrue(vals.contains(objArray[i]), "Collection contains incorrect elements " + i);
+ }
+ assertEquals(401, vals.toArray().length);
+ vals.remove(objArray[300]);
+ assertTrue(!myMap.containsValue(objArray[300]), "Removing from the values collection should remove from the original map");
+ assertEquals(vals.size(), 400, "Returned collection of incorrect size");
+ assertEquals(400,vals.toArray().length);
}
protected void dumpRandomDataSet(int iterations, boolean bounded) {
