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

      • 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

    • 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.

      • 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​(int key)

      • containsKey

        public boolean containsKey​(int key)

      • get

        public E get​(java.lang.Object key)
        Specified by:
        get 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>

      • 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)

      • replace

        public boolean replace​(int key,
                       E oldValue,
                       E newValue)

      • replace

        public E replace​(int key,
                 E value)

      • 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>