Package org.apache.qpid.protonj2.engine.util

Class SplayMap<E>

java.lang.Object

org.apache.qpid.protonj2.engine.util.SplayMap<E>

Type Parameters:

E - The type stored in the map entries

All Implemented Interfaces:

Map<UnsignedInteger,E>, NavigableMap<UnsignedInteger,E>, SortedMap<UnsignedInteger,E>

Direct Known Subclasses:

LinkedSplayMap

public class SplayMap<E>
extends Object
implements NavigableMap<UnsignedInteger,E>

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 Map. The best case access time is generally O(long n) however it can be Theta(n) in a very worst case scenario.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static final class	SplayMap.AscendingSubMap<V>
protected static final class	SplayMap.DescendingSubMap<V>
static class	SplayMap.ImmutableSplayMapEntry<E>	An immutable Map entry that can be used when exposing raw entry mappings via the Map API.
protected static class	SplayMap.NavigableSubMapKeySet
protected static final class	SplayMap.SplayedEntry<E>
protected class	SplayMap.SplayMapKeySet

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field	Description
protected static final Comparator<UnsignedInteger>	COMPARATOR
protected final int	DEFAULT_ENTRY_POOL_SIZE
protected NavigableMap<UnsignedInteger,E>	descendingMapView
protected int	entriesInExistence
protected final RingQueue<SplayMap.SplayedEntry<E>>	entryPool
protected Set<Map.Entry<UnsignedInteger,E>>	entrySet
protected NavigableSet<UnsignedInteger>	keySet
protected int	modCount
protected static final Comparator<UnsignedInteger>	REVERSE_COMPARATOR
protected SplayMap.SplayedEntry<E>	root	Root node which can be null if the tree has no elements (size == 0)
protected int	size	Current size of the splayed map tree.
protected Collection<E>	values

Constructor Summary

Constructors

Constructor	Description
SplayMap()

Method Summary

Modifier and Type	Method	Description
SplayMap.ImmutableSplayMapEntry<E>	ceilingEntry(UnsignedInteger key)
UnsignedInteger	ceilingKey(UnsignedInteger key)
void	clear()
Comparator<? super UnsignedInteger>	comparator()
boolean	containsKey(int key)	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.
boolean	containsKey(Object key)
boolean	containsValue(Object value)
protected void	delete(SplayMap.SplayedEntry<E> node)
NavigableSet<UnsignedInteger>	descendingKeySet()
NavigableMap<UnsignedInteger,E>	descendingMap()
protected void	entryAdded(SplayMap.SplayedEntry<E> newEntry)
protected void	entryDeleted(SplayMap.SplayedEntry<E> deletedEntry)
Set<Map.Entry<UnsignedInteger,E>>	entrySet()
boolean	equals(Object o)
protected static <V> SplayMap.ImmutableSplayMapEntry<V>	export(SplayMap.SplayedEntry<V> entry)
SplayMap.ImmutableSplayMapEntry<E>	firstEntry()
UnsignedInteger	firstKey()
SplayMap.ImmutableSplayMapEntry<E>	floorEntry(UnsignedInteger key)
UnsignedInteger	floorKey(UnsignedInteger key)
void	forEach(BiConsumer<? super UnsignedInteger,? super E> action)
void	forEach(Consumer<? super E> action)	A specialized forEach implementation that accepts a Consumer function that will be called for each value in the SplayMap.
E	get(int key)	Gets the value of the element stored in the Map with the key (treated as an unsigned integer for comparison.
E	get(Object key)
E	getOrDefault(int key, E defaultValue)	Gets the value of the element stored in the Map with the key (treated as an unsigned integer for comparison.
E	getOrDefault(Object key, E defaultValue)
int	hashCode()
SortedMap<UnsignedInteger,E>	headMap(UnsignedInteger toKey)
NavigableMap<UnsignedInteger,E>	headMap(UnsignedInteger toKey, boolean inclusive)
SplayMap.ImmutableSplayMapEntry<E>	higherEntry(UnsignedInteger key)
UnsignedInteger	higherKey(UnsignedInteger key)
boolean	isEmpty()
Set<UnsignedInteger>	keySet()
SplayMap.ImmutableSplayMapEntry<E>	lastEntry()
UnsignedInteger	lastKey()
SplayMap.ImmutableSplayMapEntry<E>	lowerEntry(UnsignedInteger key)
UnsignedInteger	lowerKey(UnsignedInteger key)
NavigableSet<UnsignedInteger>	navigableKeySet()
SplayMap.ImmutableSplayMapEntry<E>	pollFirstEntry()
SplayMap.ImmutableSplayMapEntry<E>	pollLastEntry()
E	put(int key, E value)	Puts the value into the in the Map at the entry specified by the given key (treated as an unsigned integer for comparison.
E	put(UnsignedInteger key, E value)
void	putAll(Map<? extends UnsignedInteger,? extends E> source)
E	putIfAbsent(int key, E 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.
E	putIfAbsent(UnsignedInteger key, E value)
E	remove(int key)	Removes the mapping for the primitive int 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.
boolean	remove(int key, Object 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 Map.
E	remove(Object key)
boolean	remove(Object key, Object value)
E	remove(UnsignedInteger key)	Removes the mapping for the 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.
E	replace(int key, E 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 Map with the new value provided.
boolean	replace(int key, E oldValue, E 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 Map with the new value provided.
E	replace(UnsignedInteger key, E value)
boolean	replace(UnsignedInteger key, E oldValue, E newValue)
void	replaceAll(BiFunction<? super UnsignedInteger,? super E,? extends E> function)
protected static Comparator<? super UnsignedInteger>	reverseComparator()
int	size()
NavigableMap<UnsignedInteger,E>	subMap(UnsignedInteger fromKey, boolean fromInclusive, UnsignedInteger toKey, boolean toInclusive)
SortedMap<UnsignedInteger,E>	subMap(UnsignedInteger fromKey, UnsignedInteger toKey)
SortedMap<UnsignedInteger,E>	tailMap(UnsignedInteger fromKey)
NavigableMap<UnsignedInteger,E>	tailMap(UnsignedInteger fromKey, boolean inclusive)
Collection<E>	values()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, merge

Field Details

COMPARATOR

protected static final Comparator<UnsignedInteger> COMPARATOR

REVERSE_COMPARATOR

protected static final Comparator<UnsignedInteger> REVERSE_COMPARATOR

DEFAULT_ENTRY_POOL_SIZE

protected final int DEFAULT_ENTRY_POOL_SIZE

See Also:

• Constant Field Values

entryPool

protected final RingQueue<SplayMap.SplayedEntry<E>> entryPool

entriesInExistence

protected int entriesInExistence

root

protected SplayMap.SplayedEntry<E> root

Root node which can be null if the tree has no elements (size == 0)

size

protected int size

Current size of the splayed map tree.

modCount

protected int modCount

keySet

protected NavigableSet<UnsignedInteger> keySet

values

protected Collection<E> values

entrySet

protected Set<Map.Entry<UnsignedInteger,E>> entrySet

descendingMapView

protected NavigableMap<UnsignedInteger,E> descendingMapView

Constructor Details

SplayMap

public SplayMap()

Method Details

size

public int size()

Specified by:

size in interface Map<UnsignedInteger,E>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Map<UnsignedInteger,E>

get

public E get(int key)

Gets the value of the element stored in the 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 Map. For entries at the root of the tree that match the given search key the method returns immediately without modifying the Map.

Parameters:

key - the integer key value to search for in the SplayMap.

Returns:

the value stored for the given key if found or null if not in the Map.

getOrDefault

public E getOrDefault(int key,
 E defaultValue)

Gets the value of the element stored in the 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 Map. For entries at the root of the tree that match the given search key the method returns immediately without modifying the Map.

Parameters:

key - the integer key value to search for in the SplayMap.

defaultValue - the default value to return if the key is not stored in this Map.

Returns:

the value stored for the given key if found the default value if not in the Map.

put

public E put(int key,
 E value)

Puts the value into the in the 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 Map. For entries at the root of the tree that match the given search key the method returns immediately without modifying the Map.

Parameters:

key - the integer key value to search for and or insert in the SplayMap.

value - the value to assign to the entry accessed via the given key.

Returns:

the previous value stored for the given key if found or null if not in the Map.

putIfAbsent

public E putIfAbsent(int key,
 E 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. 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 Map. For entries at the root of the tree that match the given search key the method returns immediately without modifying the Map.

Parameters:

key - the integer key value to search for and or insert in the SplayMap.

value - the value to assign to the entry accessed via the given key.

Returns:

the previous value associated with the given key or null if none was present.

remove

public E remove(UnsignedInteger key)

Removes the mapping for the 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.

Parameters:

key - The UnsignedInteger key whose value will be removed from the SplayMap.

Returns:

the value that was removed if one was present in the Map.

remove

public E remove(int key)

Removes the mapping for the primitive int 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.

Parameters:

key - The UnsignedInteger key whose value will be removed from the SplayMap.

Returns:

the value that was removed if one was present in the Map.

containsKey

public boolean containsKey(int key)

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.

Parameters:

key - The key which will be searched for in this mapping.

Returns:

true if the key mapping is found within this Map.

put

public E put(UnsignedInteger key,
 E value)

Specified by:

put in interface Map<UnsignedInteger,E>

putIfAbsent

public E putIfAbsent(UnsignedInteger key,
 E value)

Specified by:

putIfAbsent in interface Map<UnsignedInteger,E>

get

public E get(Object key)

Specified by:

get in interface Map<UnsignedInteger,E>

getOrDefault

public E getOrDefault(Object key,
 E defaultValue)

Specified by:

getOrDefault in interface Map<UnsignedInteger,E>

remove

public E remove(Object key)

Specified by:

remove in interface Map<UnsignedInteger,E>

containsKey

public boolean containsKey(Object key)

Specified by:

containsKey in interface Map<UnsignedInteger,E>

clear

public void clear()

Specified by:

clear in interface Map<UnsignedInteger,E>

putAll

public void putAll(Map<? extends UnsignedInteger,? extends E> source)

Specified by:

putAll in interface Map<UnsignedInteger,E>

containsValue

public boolean containsValue(Object value)

Specified by:

containsValue in interface Map<UnsignedInteger,E>

hashCode

public int hashCode()

Specified by:

hashCode in interface Map<UnsignedInteger,E>

Overrides:

hashCode in class Object

equals

public boolean equals(Object o)

Specified by:

equals in interface Map<UnsignedInteger,E>

Overrides:

equals in class Object

keySet

public Set<UnsignedInteger> keySet()

Specified by:

keySet in interface Map<UnsignedInteger,E>

Specified by:

keySet in interface SortedMap<UnsignedInteger,E>

values

public Collection<E> values()

Specified by:

values in interface Map<UnsignedInteger,E>

Specified by:

values in interface SortedMap<UnsignedInteger,E>

entrySet

public Set<Map.Entry<UnsignedInteger,E>> entrySet()

Specified by:

entrySet in interface Map<UnsignedInteger,E>

Specified by:

entrySet in interface SortedMap<UnsignedInteger,E>

forEach

public void forEach(BiConsumer<? super UnsignedInteger,? super E> action)

Specified by:

forEach in interface Map<UnsignedInteger,E>

forEach

public void forEach(Consumer<? super E> action)

A specialized forEach implementation that accepts a Consumer function that will be called for each value in the 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.)

Parameters:

action - The action to be performed for each of the values in the SplayMap.

replaceAll

public void replaceAll(BiFunction<? super UnsignedInteger,? super E,? extends E> function)

Specified by:

replaceAll in interface Map<UnsignedInteger,E>

remove

public boolean remove(Object key,
 Object value)

Specified by:

remove in interface Map<UnsignedInteger,E>

remove

public boolean remove(int key,
 Object 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 Map.

Parameters:

key - The key whose value will be removed if matched.

value - The value that must be contained in the mapping for the remove to be performed.

Returns:

true if an entry was removed from the Map

replace

public boolean replace(UnsignedInteger key,
 E oldValue,
 E newValue)

Specified by:

replace in interface Map<UnsignedInteger,E>

replace

public boolean replace(int key,
 E oldValue,
 E 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 Map with the new value provided.

Parameters:

key - The key whose value will be removed if matched.

oldValue - The old value that must be contained in the mapping for the replace to be performed.

newValue - The value that will replace the old value mapped to the given key if one existed..

Returns:

true if an entry was replaced in the Map

replace

public E replace(UnsignedInteger key,
 E value)

Specified by:

replace in interface Map<UnsignedInteger,E>

replace

public E replace(int key,
 E 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 Map with the new value provided.

Parameters:

key - The key whose value will be removed if matched.

value - The value that will replace the old value mapped to the given key if one existed..

Returns:

true if an entry was replaced in the Map

entryAdded

protected void entryAdded(SplayMap.SplayedEntry<E> newEntry)

entryDeleted

protected void entryDeleted(SplayMap.SplayedEntry<E> deletedEntry)

delete

protected void delete(SplayMap.SplayedEntry<E> node)

export

protected static <V>
SplayMap.ImmutableSplayMapEntry<V> export(SplayMap.SplayedEntry<V> entry)

reverseComparator

protected static Comparator<? super UnsignedInteger> reverseComparator()

comparator

public Comparator<? super UnsignedInteger> comparator()

Specified by:

comparator in interface SortedMap<UnsignedInteger,E>

firstKey

public UnsignedInteger firstKey()

Specified by:

firstKey in interface SortedMap<UnsignedInteger,E>

lastKey

public UnsignedInteger lastKey()

Specified by:

lastKey in interface SortedMap<UnsignedInteger,E>

firstEntry

public SplayMap.ImmutableSplayMapEntry<E> firstEntry()

Specified by:

firstEntry in interface NavigableMap<UnsignedInteger,E>

lastEntry

public SplayMap.ImmutableSplayMapEntry<E> lastEntry()

Specified by:

lastEntry in interface NavigableMap<UnsignedInteger,E>

pollFirstEntry

public SplayMap.ImmutableSplayMapEntry<E> pollFirstEntry()

Specified by:

pollFirstEntry in interface NavigableMap<UnsignedInteger,E>

pollLastEntry

public SplayMap.ImmutableSplayMapEntry<E> pollLastEntry()

Specified by:

pollLastEntry in interface NavigableMap<UnsignedInteger,E>

lowerEntry

public SplayMap.ImmutableSplayMapEntry<E> lowerEntry(UnsignedInteger key)

Specified by:

lowerEntry in interface NavigableMap<UnsignedInteger,E>

lowerKey

public UnsignedInteger lowerKey(UnsignedInteger key)

Specified by:

lowerKey in interface NavigableMap<UnsignedInteger,E>

higherEntry

public SplayMap.ImmutableSplayMapEntry<E> higherEntry(UnsignedInteger key)

Specified by:

higherEntry in interface NavigableMap<UnsignedInteger,E>

higherKey

public UnsignedInteger higherKey(UnsignedInteger key)

Specified by:

higherKey in interface NavigableMap<UnsignedInteger,E>

floorEntry

public SplayMap.ImmutableSplayMapEntry<E> floorEntry(UnsignedInteger key)

Specified by:

floorEntry in interface NavigableMap<UnsignedInteger,E>

floorKey

public UnsignedInteger floorKey(UnsignedInteger key)

Specified by:

floorKey in interface NavigableMap<UnsignedInteger,E>

ceilingEntry

public SplayMap.ImmutableSplayMapEntry<E> ceilingEntry(UnsignedInteger key)

Specified by:

ceilingEntry in interface NavigableMap<UnsignedInteger,E>

ceilingKey

public UnsignedInteger ceilingKey(UnsignedInteger key)

Specified by:

ceilingKey in interface NavigableMap<UnsignedInteger,E>

descendingMap

public NavigableMap<UnsignedInteger,E> descendingMap()

Specified by:

descendingMap in interface NavigableMap<UnsignedInteger,E>

navigableKeySet

public NavigableSet<UnsignedInteger> navigableKeySet()

Specified by:

navigableKeySet in interface NavigableMap<UnsignedInteger,E>

descendingKeySet

public NavigableSet<UnsignedInteger> descendingKeySet()

Specified by:

descendingKeySet in interface NavigableMap<UnsignedInteger,E>

subMap

public NavigableMap<UnsignedInteger,E> subMap(UnsignedInteger fromKey,
 boolean fromInclusive,
 UnsignedInteger toKey,
 boolean toInclusive)

Specified by:

subMap in interface NavigableMap<UnsignedInteger,E>

headMap

public NavigableMap<UnsignedInteger,E> headMap(UnsignedInteger toKey,
 boolean inclusive)

Specified by:

headMap in interface NavigableMap<UnsignedInteger,E>

tailMap

public NavigableMap<UnsignedInteger,E> tailMap(UnsignedInteger fromKey,
 boolean inclusive)

Specified by:

tailMap in interface NavigableMap<UnsignedInteger,E>

subMap

public SortedMap<UnsignedInteger,E> subMap(UnsignedInteger fromKey,
 UnsignedInteger toKey)

Specified by:

subMap in interface NavigableMap<UnsignedInteger,E>

Specified by:

subMap in interface SortedMap<UnsignedInteger,E>

headMap

public SortedMap<UnsignedInteger,E> headMap(UnsignedInteger toKey)

Specified by:

headMap in interface NavigableMap<UnsignedInteger,E>

Specified by:

headMap in interface SortedMap<UnsignedInteger,E>

tailMap

public SortedMap<UnsignedInteger,E> tailMap(UnsignedInteger fromKey)

Specified by:

tailMap in interface NavigableMap<UnsignedInteger,E>

Specified by:

tailMap in interface SortedMap<UnsignedInteger,E>