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

Class SplayMap<E>

  • Type Parameters:
    E - The type stored in the map entries
    All Implemented Interfaces:
    java.util.Map<UnsignedInteger,​E>, java.util.NavigableMap<UnsignedInteger,​E>, java.util.SortedMap<UnsignedInteger,​E>
    Direct Known Subclasses:
    LinkedSplayMap
    public class SplayMap<E>
extends java.lang.Object
implements java.util.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.

    • Field Detail

      • COMPARATOR

        protected static final java.util.Comparator<UnsignedInteger> COMPARATOR

      • REVERSE_COMPARATOR

        protected static final java.util.Comparator<UnsignedInteger> REVERSE_COMPARATOR

      • 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

      • values

        protected java.util.Collection<E> values

      • entrySet

        protected java.util.Set<java.util.Map.Entry<UnsignedInteger,​E>> entrySet

      • descendingMapView

        protected java.util.NavigableMap<UnsignedInteger,​E> descendingMapView

    • Constructor Detail

      • SplayMap

        public SplayMap()

    • Method Detail

      • size

        public int size()
        Specified by:
        size in interface java.util.Map<UnsignedInteger,​E>

      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.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.

      • get

        public E get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<UnsignedInteger,​E>

      • getOrDefault

        public E getOrDefault​(java.lang.Object key,
                      E defaultValue)
        Specified by:
        getOrDefault in interface java.util.Map<UnsignedInteger,​E>

      • remove

        public E remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<UnsignedInteger,​E>

      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<UnsignedInteger,​E>

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<UnsignedInteger,​E>

      • putAll

        public void putAll​(java.util.Map<? extends UnsignedInteger,​? extends E> source)
        Specified by:
        putAll in interface java.util.Map<UnsignedInteger,​E>

      • containsValue

        public boolean containsValue​(java.lang.Object value)
        Specified by:
        containsValue in interface java.util.Map<UnsignedInteger,​E>

      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface java.util.Map<UnsignedInteger,​E>
        Overrides:
        hashCode in class java.lang.Object

      • equals

        public boolean equals​(java.lang.Object o)
        Specified by:
        equals in interface java.util.Map<UnsignedInteger,​E>
        Overrides:
        equals in class java.lang.Object

      • values

        public java.util.Collection<E> values()
        Specified by:
        values in interface java.util.Map<UnsignedInteger,​E>
        Specified by:
        values in interface java.util.SortedMap<UnsignedInteger,​E>

      • entrySet

        public java.util.Set<java.util.Map.Entry<UnsignedInteger,​E>> entrySet()
        Specified by:
        entrySet in interface java.util.Map<UnsignedInteger,​E>
        Specified by:
        entrySet in interface java.util.SortedMap<UnsignedInteger,​E>

      • forEach

        public void forEach​(java.util.function.BiConsumer<? super UnsignedInteger,​? super E> action)
        Specified by:
        forEach in interface java.util.Map<UnsignedInteger,​E>

      • forEach

        public void forEach​(java.util.function.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​(java.util.function.BiFunction<? super UnsignedInteger,​? super E,​? extends E> function)
        Specified by:
        replaceAll in interface java.util.Map<UnsignedInteger,​E>

      • remove

        public boolean remove​(java.lang.Object key,
                      java.lang.Object value)
        Specified by:
        remove in interface java.util.Map<UnsignedInteger,​E>

      • remove

        public boolean remove​(int key,
                      java.lang.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​(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​(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

      • reverseComparator

        protected static java.util.Comparator<? super UnsignedInteger> reverseComparator()

      • comparator

        public java.util.Comparator<? super UnsignedInteger> comparator()
        Specified by:
        comparator in interface java.util.SortedMap<UnsignedInteger,​E>

      • descendingMap

        public java.util.NavigableMap<UnsignedInteger,​E> descendingMap()
        Specified by:
        descendingMap in interface java.util.NavigableMap<UnsignedInteger,​E>

      • navigableKeySet

        public java.util.NavigableSet<UnsignedInteger> navigableKeySet()
        Specified by:
        navigableKeySet in interface java.util.NavigableMap<UnsignedInteger,​E>

      • descendingKeySet

        public java.util.NavigableSet<UnsignedInteger> descendingKeySet()
        Specified by:
        descendingKeySet in interface java.util.NavigableMap<UnsignedInteger,​E>