Google Git
Sign in
apache / qpid-protonj2 / 8e388844dba5030e1c988dcf3e252a8692d40f1d / . / protonj2 / src / main / java / org / apache / qpid / protonj2 / engine / util / SplayMap.java
blob: 7cffd2919972a5c31f8f91632019b514dd610232 [file] [log] [blame]
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.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;
import java.util.Map;
import java.util.NavigableMap;
import java.util.NavigableSet;
import java.util.NoSuchElementException;
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;
import org.apache.qpid.protonj2.types.UnsignedInteger;
/**
* Map class that is implemented using a Splay Tree and uses primitive integers as the keys
* for the specified value type.
*
* The splay tree is a specialized form of a binary search tree that is self balancing and
* provides faster access in general to frequently used items. The splay tree serves well
* as an LRU cache of sorts where 80 percent of the accessed elements comes from 20 percent
* of the overall load in the {@link Map}. The best case access time is generally O(long n)
* however it can be Theta(n) in a very worst case scenario.
*
* @param <E> The type stored in the map entries
*/
public class SplayMap<E> implements NavigableMap<UnsignedInteger, E> {
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);
/**
* Root node which can be null if the tree has no elements (size == 0)
*/
protected SplayedEntry<E> root;
/**
* Current size of the splayed map tree.
*/
protected int size;
protected int modCount;
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 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}.
*
* @return the value stored for the given key if found or null if not in the {@link Map}.
*/
public E get(int key) {
if (root == null) {
return null;
} else if (root.key == key) {
return root.value;
} else {
root = splay(root, key);
if (root.key == key) {
return root.value;
} else {
return null;
}
}
}
/**
* 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.
*
* 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 and or insert in the {@link SplayMap}.
* @param value
* the value to assign to the entry accessed via the given key.
*
* @return the previous value stored for the given key if found or null if not in the {@link Map}.
*/
public E put(int key, E value) {
E oldValue = null;
if (root == null) {
root = entryPool.poll(SplayMap::createEntry).initialize(key, value);
} else {
root = splay(root, key);
if (root.key == key) {
oldValue = root.value;
root.value = value;
} else {
final SplayedEntry<E> node = entryPool.poll(SplayMap::createEntry).initialize(key, value);
if (compare(key, root.key) < 0) {
shiftRootRightOf(node);
} else {
shiftRootLeftOf(node);
}
}
}
if (oldValue == null) {
entryAdded(root);
size++;
}
modCount++;
return oldValue;
}
/**
* 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.
*
* 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 and or insert in the {@link SplayMap}.
* @param value
* the value to assign to the entry accessed via the given key.
*
* @return the previous value associated with the given key or null if none was present.
*/
public E putIfAbsent(int key, E value) {
if (root == null) {
root = entryPool.poll(SplayMap::createEntry).initialize(key, value);
} else {
root = splay(root, key);
if (root.key == key) {
return root.value;
} else {
final SplayedEntry<E> node = entryPool.poll(SplayMap::createEntry).initialize(key, value);
if (compare(key, root.key) < 0) {
shiftRootRightOf(node);
} else {
shiftRootLeftOf(node);
}
}
}
entryAdded(root);
size++;
modCount++;
return null;
}
private void shiftRootRightOf(SplayedEntry<E> newRoot) {
newRoot.right = root;
newRoot.left = root.left;
if (newRoot.left != null) {
newRoot.left.parent = newRoot;
}
root.left = null;
root.parent = newRoot;
root = newRoot;
}
private void shiftRootLeftOf(SplayedEntry<E> newRoot) {
newRoot.left = root;
newRoot.right = root.right;
if (newRoot.right != null) {
newRoot.right.parent = newRoot;
}
root.right = null;
root.parent = newRoot;
root = newRoot;
}
/**
* Removes the mapping for the {@link UnsignedInteger} key from this map if it is present
* and returns the value to which this map previously associated the key, or null if the
* map contained no mapping for the key.
*
* @param key
* The {@link UnsignedInteger} key whose value will be removed from the {@link SplayMap}.
*
* @return the value that was removed if one was present in the {@link Map}.
*/
public E remove(UnsignedInteger key) {
return remove(key.intValue());
}
/**
* Removes the mapping for the primitive <code>int</code> key from this map if it is present
* and returns the value to which this map previously associated the key, or null if the
* map contained no mapping for the key. The integer value is treated as an unsigned int
* internally.
*
* @param key
* The {@link UnsignedInteger} key whose value will be removed from the {@link SplayMap}.
*
* @return the value that was removed if one was present in the {@link Map}.
*/
public E remove(int key) {
if (root == null) {
return null;
}
root = splay(root, key);
if (root.key != key) {
return null;
}
final E removed = root.value;
// We splayed on the key and matched it so the root
// will now be the node matching that key.
delete(root);
return removed;
}
/**
* Searches the map using the given primitive integer key value which will be treated
* internally as an unsigned value when comparing against keys in the mapping.
*
* @param key
* The key which will be searched for in this mapping.
*
* @return <code>true</code> if the key mapping is found within this {@link Map}.
*/
public boolean containsKey(int key) {
if (root == null) {
return false;
}
root = splay(root, key);
if (root.key == key) {
return true;
}
return false;
}
//----- Map interface implementation
@Override
public E put(UnsignedInteger key, E value) {
return put(key.intValue(), value);
}
@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());
}
@Override
public boolean containsKey(Object key) {
Number numericKey = (Number) key;
return containsKey(numericKey.intValue());
}
@Override
public void clear() {
root = null;
size = 0;
}
@Override
public void putAll(Map<? extends UnsignedInteger, ? extends E> source) {
for (Entry<? extends UnsignedInteger, ? extends E> entry : source.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
@Override
public boolean containsValue(Object value) {
for (SplayedEntry<E> entry = firstEntry(root); entry != null; entry = successor(entry)) {
if (entry.valueEquals(value)) {
return true;
}
}
return false;
}
@Override
public int hashCode() {
int hash = 0;
for (SplayedEntry<E> entry = firstEntry(root); entry != null; entry = successor(entry)) {
hash += entry.hashCode();
}
return hash;
}
@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() {
return navigableKeySet();
}
@Override
public Collection<E> values() {
if (values == null) {
values = new SplayMapValues();
}
return values;
}
@Override
public Set<Entry<UnsignedInteger, E>> entrySet() {
if (entrySet == null) {
entrySet = new SplayMapEntrySet();
}
return entrySet;
}
@Override
public void forEach(BiConsumer<? super UnsignedInteger, ? super E> action) {
Objects.requireNonNull(action);
for (SplayedEntry<E> entry = firstEntry(root); entry != null; entry = successor(entry)) {
action.accept(entry.getKey(), entry.getValue());
}
}
/**
* A specialized forEach implementation that accepts a {@link Consumer} function that will
* be called for each value in the {@link SplayMap}. This method can save overhead as it does not
* need to box the primitive key values into an object for the call to the provided function.
* Unless otherwise specified by the implementing class, actions are performed in the order of entry
* set iteration (if an iteration order is specified.)
*
* @param action
* The action to be performed for each of the values in the {@link SplayMap}.
*/
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
for (SplayedEntry<E> entry = firstEntry(root); entry != null; entry = successor(entry)) {
action.accept(entry.getValue());
}
}
@Override
public void replaceAll(BiFunction<? super UnsignedInteger, ? super E, ? extends E> function) {
Objects.requireNonNull(function, "The replacement function parameter cannot be null");
final int initialModCount = modCount;
for (SplayedEntry<E> entry = firstEntry(root); entry != null; entry = successor(entry)) {
entry.value = function.apply(entry.getKey(), entry.value);
}
if (modCount != initialModCount) {
throw new ConcurrentModificationException();
}
}
@Override
public boolean remove(Object key, Object value) {
Number numericKey = (Number) key;
return remove(numericKey.intValue(), value);
}
/**
* Removes the entry for the specified primitive int (treated as unsigned) key only if it is
* currently mapped to the specified value in the {@link Map}.
*
* @param key
* The key whose value will be removed if matched.
* @param value
* The value that must be contained in the mapping for the remove to be performed.
*
* @return <code>true</code> if an entry was removed from the {@link Map}
*/
public boolean remove(int key, Object value) {
root = splay(root, key);
if (root == null || root.key != key || !Objects.equals(root.value, value)) {
return false;
} else {
delete(root);
return true;
}
}
@Override
public boolean replace(UnsignedInteger key, E oldValue, E newValue) {
return replace(key.intValue(), oldValue, newValue);
}
/**
* Replaces the entry for the specified primitive int (treated as unsigned) key only if it is
* currently mapped to the specified value in the {@link Map} with the new value provided.
*
* @param key
* The key whose value will be removed if matched.
* @param oldValue
* The old value that must be contained in the mapping for the replace to be performed.
* @param newValue
* The value that will replace the old value mapped to the given key if one existed..
*
* @return <code>true</code> if an entry was replaced in the {@link Map}
*/
public boolean replace(int key, E oldValue, E newValue) {
root = splay(root, key);
if (root == null || root.key != key || !Objects.equals(root.value, oldValue)) {
return false;
} else {
root.setValue(newValue);
return true;
}
}
@Override
public E replace(UnsignedInteger key, E value) {
return replace(key.intValue(), value);
}
/**
* Replaces the entry for the specified primitive int (treated as unsigned) key only if it is
* currently mapped to the a value in the {@link Map} with the new value provided.
*
* @param key
* The key whose value will be removed if matched.
* @param value
* The value that will replace the old value mapped to the given key if one existed..
*
* @return <code>true</code> if an entry was replaced in the {@link Map}
*/
public E replace(int key, E value) {
root = splay(root, key);
if (root == null || root.key != key || root.value == null) {
return null;
} else {
return root.setValue(value);
}
}
//----- Extension points
protected void entryAdded(SplayedEntry<E> newEntry) {
// Nothing to do in the base class implementation.
}
protected void entryDeleted(SplayedEntry<E> deletedEntry) {
// Nothing to do in the base class implementation.
}
//----- Internal Implementation
/*
* Rotations of tree elements form the basis of search and balance operations
* within the tree during put, get and remove type operations.
*
* y x
* / \ Zig (Right Rotation) / \
* x T3 – - – - – - – - - -> T1 y
* / \ < - - - - - - - - - / \
* T1 T2 Zag (Left Rotation) T2 T3
*
*/
private static <E> SplayedEntry<E> rightRotate(SplayedEntry<E> node) {
SplayedEntry<E> rotated = node.left;
node.left = rotated.right;
rotated.right = node;
// Reset the parent values for adjusted nodes.
rotated.parent = node.parent;
node.parent = rotated;
if (node.left != null) {
node.left.parent = node;
}
return rotated;
}
private static <E> SplayedEntry<E> leftRotate(SplayedEntry<E> node) {
SplayedEntry<E> rotated = node.right;
node.right = rotated.left;
rotated.left = node;
// Reset the parent values for adjusted nodes.
rotated.parent = node.parent;
node.parent = rotated;
if (node.right != null) {
node.right.parent = node;
}
return rotated;
}
/*
* The requested key if present is brought to the root of the tree. If it is not
* present then the last accessed element (nearest match) will be brought to the root
* 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 static <E> SplayedEntry<E> splay(SplayedEntry<E> root, int key) {
if (root == null || root.key == key) {
return root;
}
SplayedEntry<E> lessThanKeyRoot = null;
SplayedEntry<E> lessThanKeyNode = null;
SplayedEntry<E> greaterThanKeyRoot = null;
SplayedEntry<E> greaterThanKeyNode = null;
while (true) {
if (compare(key, root.key) < 0) {
// Entry must be to the left of the current node so we bring that up
// and then work from there to see if we can find the key
if (root.left != null && compare(key, root.left.key) < 0) {
root = rightRotate(root);
}
// Is there nowhere else to go, if so we are done.
if (root.left == null) {
break;
}
// Haven't found it yet but we now know the current element is greater
// than the element we are looking for so it goes to the right tree.
if (greaterThanKeyRoot == null) {
greaterThanKeyRoot = greaterThanKeyNode = root;
} else {
greaterThanKeyNode.left = root;
greaterThanKeyNode.left.parent = greaterThanKeyNode;
greaterThanKeyNode = root;
}
root = root.left;
root.parent = null;
} else if (compare(key, root.key) > 0) {
// Entry must be to the right of the current node so we bring that up
// and then work from there to see if we can find the key
if (root.right != null && compare(key, root.right.key) > 0) {
root = leftRotate(root);
}
// Is there nowhere else to go, if so we are done.
if (root.right == null) {
break;
}
// Haven't found it yet but we now know the current element is less
// than the element we are looking for so it goes to the left tree.
if (lessThanKeyRoot == null) {
lessThanKeyRoot = lessThanKeyNode = root;
} else {
lessThanKeyNode.right = root;
lessThanKeyNode.right.parent = lessThanKeyNode;
lessThanKeyNode = root;
}
root = root.right;
root.parent = null;
} else {
break; // Found it
}
}
// Reassemble the tree from the left, right and middle the assembled nodes in the
// left and right should have their last element either nulled out or linked to the
// remaining items middle tree
if (lessThanKeyRoot == null) {
lessThanKeyRoot = root.left;
} else {
lessThanKeyNode.right = root.left;
if (lessThanKeyNode.right != null) {
lessThanKeyNode.right.parent = lessThanKeyNode;
}
}
if (greaterThanKeyRoot == null) {
greaterThanKeyRoot = root.right;
} else {
greaterThanKeyNode.left = root.right;
if (greaterThanKeyNode.left != null) {
greaterThanKeyNode.left.parent = greaterThanKeyNode;
}
}
// The found or last accessed element is now rooted to the splayed
// left and right trees and returned as the new tree.
root.left = lessThanKeyRoot;
if (root.left != null) {
root.left.parent = root;
}
root.right = greaterThanKeyRoot;
if (root.right != null) {
root.right.parent = root;
}
return root;
}
protected void delete(SplayedEntry<E> node) {
final SplayedEntry<E> grandparent = node.parent;
SplayedEntry<E> replacement = node.right;
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) {
replacement.parent = grandparent;
}
if (grandparent != null) {
if (grandparent.left == node) {
grandparent.left = replacement;
} else {
grandparent.right = replacement;
}
} else {
root = replacement;
}
// Clear node before moving to cache
node.left = node.right = node.parent = null;
entryPool.offer(node);
entryDeleted(node);
size--;
modCount++;
}
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) {
firstEntry = firstEntry.left;
}
}
return firstEntry;
}
private static <E> SplayedEntry<E> lastEntry(SplayedEntry<E> node) {
SplayedEntry<E> lastEntry = node;
if (lastEntry != null) {
while (lastEntry.right != null) {
lastEntry = lastEntry.right;
}
}
return lastEntry;
}
private static <E> SplayedEntry<E> successor(SplayedEntry<E> node) {
if (node == null) {
return null;
} else if (node.right != null) {
// Walk to bottom of tree from this node's right child.
SplayedEntry<E> result = node.right;
while (result.left != null) {
result = result.left;
}
return result;
} else {
SplayedEntry<E> parent = node.parent;
SplayedEntry<E> child = node;
while (parent != null && child == parent.right) {
child = parent;
parent = parent.parent;
}
return parent;
}
}
private static <E> SplayedEntry<E> predecessor(SplayedEntry<E> node) {
if (node == null) {
return null;
} else if (node.left != null) {
// Walk to bottom of tree from this node's left child.
SplayedEntry<E> result = node.left;
while (result.right != null) {
result = result.right;
}
return result;
} else {
SplayedEntry<E> parent = node.parent;
SplayedEntry<E> child = node;
while (parent != null && child == parent.left) {
child = parent;
parent = parent.parent;
}
return parent;
}
}
/**
* 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);
}
private static <E> SplayedEntry<E> createEntry() {
return new SplayedEntry<>();
}
//----- Map Iterator implementation for EntrySet, KeySet and Values collections
// Base class iterator that can be used for the collections returned from the Map
private abstract class SplayMapIterator<T> implements Iterator<T> {
protected SplayedEntry<E> nextNode;
protected SplayedEntry<E> lastReturned;
protected int expectedModCount;
public SplayMapIterator(SplayedEntry<E> startAt) {
this.nextNode = startAt;
this.expectedModCount = SplayMap.this.modCount;
}
@Override
public boolean hasNext() {
return nextNode != null;
}
protected SplayedEntry<E> nextNode() {
final SplayedEntry<E> entry = nextNode;
if (nextNode == null) {
throw new NoSuchElementException();
}
if (expectedModCount != SplayMap.this.modCount) {
throw new ConcurrentModificationException();
}
nextNode = successor(nextNode);
lastReturned = entry;
return lastReturned;
}
protected SplayedEntry<E> previousNode() {
final SplayedEntry<E> entry = nextNode;
if (nextNode == null) {
throw new NoSuchElementException();
}
if (expectedModCount != SplayMap.this.modCount) {
throw new ConcurrentModificationException();
}
nextNode = predecessor(nextNode);
lastReturned = entry;
return lastReturned;
}
@Override
public void remove() {
if (lastReturned == null) {
throw new IllegalStateException();
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
delete(lastReturned);
expectedModCount = modCount;
lastReturned = null;
}
}
private class SplayMapEntryIterator extends SplayMapIterator<Entry<UnsignedInteger, E>> {
public SplayMapEntryIterator(SplayedEntry<E> startAt) {
super(startAt);
}
@Override
public Entry<UnsignedInteger, E> next() {
return nextNode();
}
}
private class SplayMapKeyIterator extends SplayMapIterator<UnsignedInteger> {
public SplayMapKeyIterator(SplayedEntry<E> startAt) {
super(startAt);
}
@Override
public UnsignedInteger next() {
return nextNode().getKey();
}
}
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) {
super(startAt);
}
@Override
public E next() {
return nextNode().getValue();
}
}
//----- Splay Map Collection types
private final class SplayMapValues extends AbstractCollection<E> {
@Override
public Iterator<E> iterator() {
return new SplayMapValueIterator(firstEntry(root));
}
@Override
public int size() {
return SplayMap.this.size;
}
@Override
public boolean contains(Object o) {
return SplayMap.this.containsValue(o);
}
@Override
public boolean remove(Object target) {
for (SplayedEntry<E> e = firstEntry(root); e != null; e = successor(e)) {
if (e.valueEquals(target)) {
delete(e);
return true;
}
}
return false;
}
@Override
public void clear() {
SplayMap.this.clear();
}
}
protected class SplayMapKeySet extends AbstractSet<UnsignedInteger> implements NavigableSet<UnsignedInteger> {
@Override
public Iterator<UnsignedInteger> iterator() {
return new SplayMapKeyIterator(firstEntry(root));
}
@Override
public int size() {
return SplayMap.this.size;
}
@Override
public boolean isEmpty() {
return SplayMap.this.size == 0;
}
@Override
public boolean contains(Object o) {
return SplayMap.this.containsKey(o);
}
@Override
public boolean remove(Object target) {
for (SplayedEntry<E> e = firstEntry(root); e != null; e = successor(e)) {
if (e.keyEquals(target)) {
delete(e);
return true;
}
}
return false;
}
@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>> {
@Override
public Iterator<Entry<UnsignedInteger, E>> iterator() {
return new SplayMapEntryIterator(firstEntry(root));
}
@Override
public int size() {
return SplayMap.this.size;
}
@Override
public boolean contains(Object o) {
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;
}
}
}
return false;
}
@Override
public boolean remove(Object target) {
if (!(target instanceof Entry)) {
throw new IllegalArgumentException("value provided is not an Entry type.");
}
for (SplayedEntry<E> e = firstEntry(root); e != null; e = successor(e)) {
if (e.equals(target)) {
delete(e);
return true;
}
}
return false;
}
@Override
public void clear() {
SplayMap.this.clear();
}
}
//----- Map Entry node for the Splay Map
protected static final class SplayedEntry<E> implements Map.Entry<UnsignedInteger, E>{
SplayedEntry<E> left;
SplayedEntry<E> right;
SplayedEntry<E> parent;
int key;
E value;
// Insertion order chain used by LinkedSplayMap
SplayedEntry<E> linkNext;
SplayedEntry<E> linkPrev;
public SplayedEntry() {
initialize(key, value);
}
public SplayedEntry<E> initialize(int key, E value) {
this.key = key;
this.value = value;
// Node is circular list to start.
this.linkNext = this;
this.linkPrev = this;
return this;
}
public int getIntKey() {
return key;
}
@Override
public UnsignedInteger getKey() {
return UnsignedInteger.valueOf(key);
}
@Override
public E getValue() {
return value;
}
@Override
public E setValue(E value) {
E oldValue = this.value;
this.value = value;
return oldValue;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return keyEquals(e.getKey()) && valueEquals(e.getValue());
}
@Override
public int hashCode() {
return key ^ (value == null ? 0 : value.hashCode());
}
@Override
public String toString() {
return "Node:{" + key + "," + value + "}";
}
boolean keyEquals(Object other) {
if (!(other instanceof Number)) {
return false;
}
return key == ((Number) other).intValue();
}
boolean valueEquals(Object other) {
return value != null ? value.equals(other) : other == null;
}
}
/**
* An immutable {@link Map} entry that can be used when exposing raw entry mappings
* via the {@link Map} API.
*/
public static class ImmutableSplayMapEntry<E> implements Map.Entry<UnsignedInteger, E> {
private final SplayedEntry<E> entry;
/**
* Create a new immutable {@link Map} entry.
*
* @param entry
* The inner {@link Map} entry that is wrapped.
*/
public ImmutableSplayMapEntry(SplayedEntry<E> entry) {
this.entry = entry;
}
@Override
public UnsignedInteger getKey() {
return entry.getKey();
}
/**
* @return the primitive integer view of the unsigned key.
*/
public int getPrimitiveKey() {
return entry.getIntKey();
}
@Override
public E getValue() {
return entry.getValue();
}
@Override
public E setValue(E value) {
throw new UnsupportedOperationException();
}
}
protected static <V> ImmutableSplayMapEntry<V> export(SplayedEntry<V> entry) {
return entry == null ? null : new ImmutableSplayMapEntry<>(entry);
}
//----- Unsigned Integer comparator for Navigable Maps
private static final class UnsignedComparator implements Comparator<UnsignedInteger> {
@Override
public int compare(UnsignedInteger uint1, UnsignedInteger uint2) {
return uint1.compareTo(uint2);
}
}
protected static Comparator<? super UnsignedInteger> reverseComparator() {
return REVERSE_COMPARATOR;
}
//----- Navigable and Sorted Map implementation methods
@Override
public Comparator<? super UnsignedInteger> comparator() {
return COMPARATOR;
}
@Override
public UnsignedInteger firstKey() {
return isEmpty() ? null : firstEntry(root).getKey();
}
@Override
public UnsignedInteger lastKey() {
return isEmpty() ? null : lastEntry(root).getKey();
}
@Override
public ImmutableSplayMapEntry<E> firstEntry() {
return export(firstEntry(root));
}
@Override
public ImmutableSplayMapEntry<E> lastEntry() {
return export(lastEntry(root));
}
@Override
public ImmutableSplayMapEntry<E> pollFirstEntry() {
SplayedEntry<E> firstEntry = firstEntry(root);
if (firstEntry != null) {
delete(firstEntry);
}
return export(firstEntry);
}
@Override
public ImmutableSplayMapEntry<E> pollLastEntry() {
SplayedEntry<E> lastEntry = lastEntry(root);
if (lastEntry != null) {
delete(lastEntry);
}
return export(lastEntry);
}
@Override
public ImmutableSplayMapEntry<E> lowerEntry(UnsignedInteger key) {
return export(splayToLowerEntry(key.intValue()));
}
@Override
public UnsignedInteger lowerKey(UnsignedInteger key) {
final SplayedEntry<E> result = splayToLowerEntry(key.intValue());
return result == null ? null : result.getKey();
}
/**
* 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) {
SplayedEntry<E> pred = predecessor(root);
if (pred != null) {
root = splay(root, pred.key);
} else {
return null;
}
} else {
break;
}
}
return root;
}
@Override
public ImmutableSplayMapEntry<E> higherEntry(UnsignedInteger key) {
return export(splayToHigherEntry(key.intValue()));
}
@Override
public UnsignedInteger higherKey(UnsignedInteger key) {
final SplayedEntry<E> result = splayToHigherEntry(key.intValue());
return result == null ? null : result.getKey();
}
/**
* 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) {
SplayedEntry<E> succ = successor(root);
if (succ != null) {
root = splay(root, succ.key);
} else {
return null;
}
} else {
break;
}
}
return root;
}
@Override
public ImmutableSplayMapEntry<E> floorEntry(UnsignedInteger key) {
return export(splayToFloorEntry(key.intValue()));
}
@Override
public UnsignedInteger floorKey(UnsignedInteger key) {
final SplayedEntry<E> result = splayToFloorEntry(key.intValue());
return result == null ? null : result.getKey();
}
/**
* 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) {
SplayedEntry<E> pred = predecessor(root);
if (pred != null) {
root = splay(root, pred.key);
} else {
return null;
}
} else {
break;
}
}
return root;
}
@Override
public ImmutableSplayMapEntry<E> ceilingEntry(UnsignedInteger key) {
return export(splayToCeilingEntry(key.intValue()));
}
@Override
public UnsignedInteger ceilingKey(UnsignedInteger key) {
final SplayedEntry<E> result = splayToCeilingEntry(key.intValue());
return result == null ? null : result.getKey();
}
/**
* 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) {
SplayedEntry<E> succ = successor(root);
if (succ != null) {
root = splay(root, succ.key);
} else {
return null;
}
} else {
break;
}
}
return root;
}
@Override
public NavigableMap<UnsignedInteger, E> descendingMap() {
return (descendingMapView != null) ? descendingMapView :
(descendingMapView = new DescendingSubMap<>(this,
true, 0, true,
true, UnsignedInteger.MAX_VALUE.intValue(), true));
}
@Override
public NavigableSet<UnsignedInteger> navigableKeySet() {
if (keySet == null) {
keySet = new SplayMapKeySet();
}
return keySet;
}
@Override
public NavigableSet<UnsignedInteger> descendingKeySet() {
return descendingMap().navigableKeySet();
}
@Override
public NavigableMap<UnsignedInteger, E> subMap(UnsignedInteger fromKey, boolean fromInclusive, UnsignedInteger toKey, boolean toInclusive) {
return new AscendingSubMap<>(this, false, fromKey.intValue(), fromInclusive, false, toKey.intValue(), toInclusive);
}
@Override
public NavigableMap<UnsignedInteger, E> headMap(UnsignedInteger toKey, boolean inclusive) {
return new AscendingSubMap<>(this, true, 0, true, false, toKey.intValue(), inclusive);
}
@Override
public NavigableMap<UnsignedInteger, E> tailMap(UnsignedInteger fromKey, boolean inclusive) {
return new AscendingSubMap<>(this, false, fromKey.intValue(), inclusive, true, UnsignedInteger.MAX_VALUE.intValue(), true);
}
@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);
}
/**
* 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());
}
}
}
}