Class ConcurrentSkipListMap<K,​V>

  • Type Parameters:
    K - the type of keys maintained by this map
    V - the type of mapped values
    All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.util.concurrent.ConcurrentMap<K,​V>, java.util.Map<K,​V>, java.util.SortedMap<K,​V>, ConcurrentNavigableMap<K,​V>, NavigableMap<K,​V>

    public class ConcurrentSkipListMap<K,​V>
    extends java.util.AbstractMap<K,​V>
    implements ConcurrentNavigableMap<K,​V>, java.lang.Cloneable, java.io.Serializable
    A scalable ConcurrentNavigableMap implementation. This class maintains a map in ascending key order, sorted according to the natural order for the key's class (see Comparable), or by the Comparator provided at creation time, depending on which constructor is used.

    This class implements a concurrent variant of SkipLists providing expected average log(n) time cost for the containsKey, get, put and remove operations and their variants. Insertion, removal, update, and access operations safely execute concurrently by multiple threads. Iterators are weakly consistent, returning elements reflecting the state of the map at some point at or since the creation of the iterator. They do not throw ConcurrentModificationException, and may proceed concurrently with other operations. Ascending key ordered views and their iterators are faster than descending ones.

    All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method. (Note however that it is possible to change mappings in the associated map using put, putIfAbsent, or replace, depending on exactly which effect you need.)

    Beware that, unlike in most collections, the size method is not a constant-time operation. Because of the asynchronous nature of these maps, determining the current number of elements requires a traversal of the elements. Additionally, the bulk operations putAll, equals, and clear are not guaranteed to be performed atomically. For example, an iterator operating concurrently with a putAll operation might view only some of the added elements.

    This class and its views and iterators implement all of the optional methods of the Map and Iterator interfaces. Like most other concurrent collections, this class does not permit the use of null keys or values because some null return values cannot be reliably distinguished from the absence of elements.

    See Also:
    Serialized Form
    • Constructor Detail

      • ConcurrentSkipListMap

        public ConcurrentSkipListMap()
        Constructs a new empty map, sorted according to the keys' natural order.
      • ConcurrentSkipListMap

        public ConcurrentSkipListMap​(java.util.Comparator<? super K> c)
        Constructs a new empty map, sorted according to the given comparator.
        Parameters:
        c - the comparator that will be used to sort this map. A null value indicates that the keys' natural ordering should be used.
      • ConcurrentSkipListMap

        public ConcurrentSkipListMap​(java.util.Map<? extends K,​? extends V> m)
        Constructs a new map containing the same mappings as the given map, sorted according to the keys' natural order.
        Parameters:
        m - the map whose mappings are to be placed in this map.
        Throws:
        java.lang.ClassCastException - if the keys in m are not Comparable, or are not mutually comparable.
        java.lang.NullPointerException - if the specified map is null.
      • ConcurrentSkipListMap

        public ConcurrentSkipListMap​(java.util.SortedMap<K,​? extends V> m)
        Constructs a new map containing the same mappings as the given SortedMap, sorted according to the same ordering.
        Parameters:
        m - the sorted map whose mappings are to be placed in this map, and whose comparator is to be used to sort this map.
        Throws:
        java.lang.NullPointerException - if the specified sorted map is null.
    • Method Detail

      • initialize

        final void initialize()
        Initialize or reset state. Needed by constructors, clone, clear, readObject. and ConcurrentSkipListSet.clone. (Note that comparator must be separately initialized.)
      • comparable

        private java.lang.Comparable<K> comparable​(java.lang.Object key)
                                            throws java.lang.ClassCastException
        If using comparator, return a ComparableUsingComparator, else cast key as Comparator, which may cause ClassCastException, which is propagated back to caller.
        Throws:
        java.lang.ClassCastException
      • compare

        int compare​(K k1,
                    K k2)
             throws java.lang.ClassCastException
        Compare using comparator or natural ordering. Used when the ComparableUsingComparator approach doesn't apply.
        Throws:
        java.lang.ClassCastException
      • inHalfOpenRange

        boolean inHalfOpenRange​(K key,
                                K least,
                                K fence)
        Return true if given key greater than or equal to least and strictly less than fence, bypassing either test if least or fence oare null. Needed mainly in submap operations.
      • inOpenRange

        boolean inOpenRange​(K key,
                            K least,
                            K fence)
        Return true if given key greater than or equal to least and less or equal to fence. Needed mainly in submap operations.
      • findPredecessor

        private ConcurrentSkipListMap.Node<K,​V> findPredecessor​(java.lang.Comparable<K> key)
        Return a base-level node with key strictly less than given key, or the base-level header if there is no such node. Also unlinks indexes to deleted nodes found along the way. Callers rely on this side-effect of clearing indices to deleted nodes.
        Parameters:
        key - the key
        Returns:
        a predecessor of key
      • findNode

        private ConcurrentSkipListMap.Node<K,​V> findNode​(java.lang.Comparable<K> key)
        Return node holding key or null if no such, clearing out any deleted nodes seen along the way. Repeatedly traverses at base-level looking for key starting at predecessor returned from findPredecessor, processing base-level deletions as encountered. Some callers rely on this side-effect of clearing deleted nodes. Restarts occur, at traversal step centered on node n, if: (1) After reading n's next field, n is no longer assumed predecessor b's current successor, which means that we don't have a consistent 3-node snapshot and so cannot unlink any subsequent deleted nodes encountered. (2) n's value field is null, indicating n is deleted, in which case we help out an ongoing structural deletion before retrying. Even though there are cases where such unlinking doesn't require restart, they aren't sorted out here because doing so would not usually outweigh cost of restarting. (3) n is a marker or n's predecessor's value field is null, indicating (among other possibilities) that findPredecessor returned a deleted node. We can't unlink the node because we don't know its predecessor, so rely on another call to findPredecessor to notice and return some earlier predecessor, which it will do. This check is only strictly needed at beginning of loop, (and the b.value check isn't strictly needed at all) but is done each iteration to help avoid contention with other threads by callers that will fail to be able to change links, and so will retry anyway. The traversal loops in doPut, doRemove, and findNear all include the same three kinds of checks. And specialized versions appear in doRemoveFirst, doRemoveLast, findFirst, and findLast. They can't easily share code because each uses the reads of fields held in locals occurring in the orders they were performed.
        Parameters:
        key - the key
        Returns:
        node holding key, or null if no such.
      • doGet

        private V doGet​(java.lang.Object okey)
        Specialized variant of findNode to perform Map.get. Does a weak traversal, not bothering to fix any deleted index nodes, returning early if it happens to see key in index, and passing over any deleted base nodes, falling back to getUsingFindNode only if it would otherwise return value from an ongoing deletion. Also uses "bound" to eliminate need for some comparisons (see Pugh Cookbook). Also folds uses of null checks and node-skipping because markers have null keys.
        Parameters:
        okey - the key
        Returns:
        the value, or null if absent
      • getUsingFindNode

        private V getUsingFindNode​(java.lang.Comparable<K> key)
        Perform map.get via findNode. Used as a backup if doGet encounters an in-progress deletion.
        Parameters:
        key - the key
        Returns:
        the value, or null if absent
      • doPut

        private V doPut​(K kkey,
                        V value,
                        boolean onlyIfAbsent)
        Main insertion method. Adds element if not present, or replaces value if present and onlyIfAbsent is false.
        Parameters:
        kkey - the key
        value - the value that must be associated with key
        onlyIfAbsent - if should not insert if already present
        Returns:
        the old value, or null if newly inserted
      • randomLevel

        private int randomLevel()
        Return a random level for inserting a new node. Hardwired to k=1, p=0.5, max 31. This uses a cheap pseudo-random function that according to http://home1.gte.net/deleyd/random/random4.html was used in Turbo Pascal. It seems the fastest usable one here. The low bits are apparently not very random (the original used only upper 16 bits) so we traverse from highest bit down (i.e., test sign), thus hardly ever use lower bits.
      • insertIndex

        private void insertIndex​(ConcurrentSkipListMap.Node<K,​V> z,
                                 int level)
        Create and add index nodes for given node.
        Parameters:
        z - the node
        level - the level of the index
      • addIndex

        private void addIndex​(ConcurrentSkipListMap.Index<K,​V> idx,
                              ConcurrentSkipListMap.HeadIndex<K,​V> h,
                              int indexLevel)
        Add given index nodes from given level down to 1.
        Parameters:
        idx - the topmost index node being inserted
        h - the value of head to use to insert. This must be snapshotted by callers to provide correct insertion level
        indexLevel - the level of the index
      • doRemove

        private V doRemove​(java.lang.Object okey,
                           java.lang.Object value)
        Main deletion method. Locates node, nulls value, appends a deletion marker, unlinks predecessor, removes associated index nodes, and possibly reduces head index level. Index nodes are cleared out simply by calling findPredecessor. which unlinks indexes to deleted nodes found along path to key, which will include the indexes to this node. This is done unconditionally. We can't check beforehand whether there are index nodes because it might be the case that some or all indexes hadn't been inserted yet for this node during initial search for it, and we'd like to ensure lack of garbage retention, so must call to be sure.
        Parameters:
        okey - the key
        value - if non-null, the value that must be associated with key
        Returns:
        the node, or null if not found
      • tryReduceLevel

        private void tryReduceLevel()
        Possibly reduce head level if it has no nodes. This method can (rarely) make mistakes, in which case levels can disappear even though they are about to contain index nodes. This impacts performance, not correctness. To minimize mistakes as well as to reduce hysteresis, the level is reduced by one only if the topmost three levels look empty. Also, if the removed level looks non-empty after CAS, we try to change it back quick before anyone notices our mistake! (This trick works pretty well because this method will practically never make mistakes unless current thread stalls immediately before first CAS, in which case it is very unlikely to stall again immediately afterwards, so will recover.) We put up with all this rather than just let levels grow because otherwise, even a small map that has undergone a large number of insertions and removals will have a lot of levels, slowing down access more than would an occasional unwanted reduction.
      • removep

        boolean removep​(java.lang.Object key)
        Version of remove with boolean return. Needed by view classes
      • findFirst

        ConcurrentSkipListMap.Node<K,​V> findFirst()
        Specialized variant of findNode to get first valid node
        Returns:
        first node or null if empty
      • doRemoveFirst

        java.lang.Object doRemoveFirst​(boolean keyOnly)
        Remove first entry; return either its key or a snapshot.
        Parameters:
        keyOnly - if true return key, else return SnapshotEntry (This is a little ugly, but avoids code duplication.)
        Returns:
        null if empty, first key if keyOnly true, else key,value entry
      • clearIndexToFirst

        private void clearIndexToFirst()
        Clear out index nodes associated with deleted first entry. Needed by doRemoveFirst
      • pollFirstKey

        K pollFirstKey()
        Remove first entry; return key or null if empty.
      • findLast

        ConcurrentSkipListMap.Node<K,​V> findLast()
        Specialized version of find to get last valid node
        Returns:
        last node or null if empty
      • doRemoveLast

        java.lang.Object doRemoveLast​(boolean keyOnly)
        Specialized version of doRemove for last entry.
        Parameters:
        keyOnly - if true return key, else return SnapshotEntry
        Returns:
        null if empty, last key if keyOnly true, else key,value entry
      • findPredecessorOfLast

        private ConcurrentSkipListMap.Node<K,​V> findPredecessorOfLast()
        Specialized variant of findPredecessor to get predecessor of last valid node. Needed by doRemoveLast. It is possible that all successors of returned node will have been deleted upon return, in which case this method can be retried.
        Returns:
        likely predecessor of last node.
      • pollLastKey

        K pollLastKey()
        Remove last entry; return key or null if empty.
      • findNear

        ConcurrentSkipListMap.Node<K,​V> findNear​(K kkey,
                                                       int rel)
        Utility for ceiling, floor, lower, higher methods.
        Parameters:
        kkey - the key
        rel - the relation -- OR'ed combination of EQ, LT, GT
        Returns:
        nearest node fitting relation, or null if no such
      • getNear

        ConcurrentSkipListMap.SnapshotEntry<K,​V> getNear​(K kkey,
                                                               int rel)
        Return SnapshotEntry for results of findNear.
        Parameters:
        kkey - the key
        rel - the relation -- OR'ed combination of EQ, LT, GT
        Returns:
        Entry fitting relation, or null if no such
      • getNear

        java.lang.Object getNear​(K kkey,
                                 int rel,
                                 K least,
                                 K fence,
                                 boolean keyOnly)
        Return SnapshotEntry or key for results of findNear ofter screening to ensure result is in given range. Needed by submaps.
        Parameters:
        kkey - the key
        rel - the relation -- OR'ed combination of EQ, LT, GT
        least - minimum allowed key value
        fence - key greater than maximum allowed key value
        keyOnly - if true return key, else return SnapshotEntry
        Returns:
        Key or Entry fitting relation, or null if no such
      • removeFirstEntryOfSubrange

        java.lang.Object removeFirstEntryOfSubrange​(K least,
                                                    K fence,
                                                    boolean keyOnly)
        Find and remove least element of subrange.
        Parameters:
        least - minimum allowed key value
        fence - key greater than maximum allowed key value
        keyOnly - if true return key, else return SnapshotEntry
        Returns:
        least Key or Entry, or null if no such
      • removeLastEntryOfSubrange

        java.lang.Object removeLastEntryOfSubrange​(K least,
                                                   K fence,
                                                   boolean keyOnly)
        Find and remove greatest element of subrange.
        Parameters:
        least - minimum allowed key value
        fence - key greater than maximum allowed key value
        keyOnly - if true return key, else return SnapshotEntry
        Returns:
        least Key or Entry, or null if no such
      • clone

        public java.lang.Object clone()
        Returns a shallow copy of this Map instance. (The keys and values themselves are not cloned.)
        Overrides:
        clone in class java.util.AbstractMap<K,​V>
        Returns:
        a shallow copy of this Map.
      • buildFromSorted

        private void buildFromSorted​(java.util.SortedMap<K,​? extends V> map)
        Streamlined bulk insertion to initialize from elements of given sorted map. Call only from constructor or clone method.
      • writeObject

        private void writeObject​(java.io.ObjectOutputStream s)
                          throws java.io.IOException
        Save the state of the Map instance to a stream.
        Throws:
        java.io.IOException
      • readObject

        private void readObject​(java.io.ObjectInputStream s)
                         throws java.io.IOException,
                                java.lang.ClassNotFoundException
        Reconstitute the Map instance from a stream.
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Returns true if this map contains a mapping for the specified key.
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K,​V>
        Parameters:
        key - key whose presence in this map is to be tested.
        Returns:
        true if this map contains a mapping for the specified key.
        Throws:
        java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if the key is null.
      • get

        public V get​(java.lang.Object key)
        Returns the value to which this map maps the specified key. Returns null if the map contains no mapping for this key.
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>
        Parameters:
        key - key whose associated value is to be returned.
        Returns:
        the value to which this map maps the specified key, or null if the map contains no mapping for the key.
        Throws:
        java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if the key is null.
      • put

        public V put​(K key,
                     V value)
        Associates the specified value with the specified key in this map. If the map previously contained a mapping for this key, the old value is replaced.
        Specified by:
        put in interface java.util.Map<K,​V>
        Overrides:
        put in class java.util.AbstractMap<K,​V>
        Parameters:
        key - key with which the specified value is to be associated.
        value - value to be associated with the specified key.
        Returns:
        previous value associated with specified key, or null if there was no mapping for key.
        Throws:
        java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if the key or value are null.
      • remove

        public V remove​(java.lang.Object key)
        Removes the mapping for this key from this Map if present.
        Specified by:
        remove in interface java.util.Map<K,​V>
        Overrides:
        remove in class java.util.AbstractMap<K,​V>
        Parameters:
        key - key for which mapping should be removed
        Returns:
        previous value associated with specified key, or null if there was no mapping for key.
        Throws:
        java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if the key is null.
      • containsValue

        public boolean containsValue​(java.lang.Object value)
        Returns true if this map maps one or more keys to the specified value. This operation requires time linear in the Map size.
        Specified by:
        containsValue in interface java.util.Map<K,​V>
        Overrides:
        containsValue in class java.util.AbstractMap<K,​V>
        Parameters:
        value - value whose presence in this Map is to be tested.
        Returns:
        true if a mapping to value exists; false otherwise.
        Throws:
        java.lang.NullPointerException - if the value is null.
      • size

        public int size()
        Returns the number of elements in this map. If this map contains more than Integer.MAX_VALUE elements, it returns Integer.MAX_VALUE.

        Beware that, unlike in most collections, this method is NOT a constant-time operation. Because of the asynchronous nature of these maps, determining the current number of elements requires traversing them all to count them. Additionally, it is possible for the size to change during execution of this method, in which case the returned result will be inaccurate. Thus, this method is typically not very useful in concurrent applications.

        Specified by:
        size in interface java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>
        Returns:
        the number of elements in this map.
      • isEmpty

        public boolean isEmpty()
        Returns true if this map contains no key-value mappings.
        Specified by:
        isEmpty in interface java.util.Map<K,​V>
        Overrides:
        isEmpty in class java.util.AbstractMap<K,​V>
        Returns:
        true if this map contains no key-value mappings.
      • clear

        public void clear()
        Removes all mappings from this map.
        Specified by:
        clear in interface java.util.Map<K,​V>
        Overrides:
        clear in class java.util.AbstractMap<K,​V>
      • keySet

        public java.util.Set<K> keySet()
        Returns a set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations. The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.
        Specified by:
        keySet in interface java.util.Map<K,​V>
        Specified by:
        keySet in interface java.util.SortedMap<K,​V>
        Overrides:
        keySet in class java.util.AbstractMap<K,​V>
        Returns:
        a set view of the keys contained in this map.
      • descendingKeySet

        public java.util.Set<K> descendingKeySet()
        Returns a set view of the keys contained in this map in descending order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations. The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.
        Specified by:
        descendingKeySet in interface NavigableMap<K,​V>
        Returns:
        a set view of the keys contained in this map.
      • values

        public java.util.Collection<V> values()
        Returns a collection view of the values contained in this map. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations. The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.
        Specified by:
        values in interface java.util.Map<K,​V>
        Specified by:
        values in interface java.util.SortedMap<K,​V>
        Overrides:
        values in class java.util.AbstractMap<K,​V>
        Returns:
        a collection view of the values contained in this map.
      • entrySet

        public java.util.Set<java.util.Map.Entry<K,​V>> entrySet()
        Returns a collection view of the mappings contained in this map. Each element in the returned collection is a Map.Entry. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations. The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction. The Map.Entry elements returned by iterator.next() do not support the setValue operation.
        Specified by:
        entrySet in interface java.util.Map<K,​V>
        Specified by:
        entrySet in interface java.util.SortedMap<K,​V>
        Specified by:
        entrySet in class java.util.AbstractMap<K,​V>
        Returns:
        a collection view of the mappings contained in this map.
      • descendingEntrySet

        public java.util.Set<java.util.Map.Entry<K,​V>> descendingEntrySet()
        Returns a collection view of the mappings contained in this map, in descending order. Each element in the returned collection is a Map.Entry. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations. The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction. The Map.Entry elements returned by iterator.next() do not support the setValue operation.
        Specified by:
        descendingEntrySet in interface NavigableMap<K,​V>
        Returns:
        a collection view of the mappings contained in this map.
      • equals

        public boolean equals​(java.lang.Object o)
        Compares the specified object with this map for equality. Returns true if the given object is also a map and the two maps represent the same mappings. More formally, two maps t1 and t2 represent the same mappings if t1.keySet().equals(t2.keySet()) and for every key k in t1.keySet(), (t1.get(k)==null ? t2.get(k)==null : t1.get(k).equals(t2.get(k))) . This operation may return misleading results if either map is concurrently modified during execution of this method.
        Specified by:
        equals in interface java.util.Map<K,​V>
        Overrides:
        equals in class java.util.AbstractMap<K,​V>
        Parameters:
        o - object to be compared for equality with this map.
        Returns:
        true if the specified object is equal to this map.
      • containsAllMappings

        static <K,​V> boolean containsAllMappings​(java.util.Map<K,​V> a,
                                                       java.util.Map<K,​V> b)
        Helper for equals -- check for containment, avoiding nulls.
      • putIfAbsent

        public V putIfAbsent​(K key,
                             V value)
        If the specified key is not already associated with a value, associate it with the given value. This is equivalent to
           if (!map.containsKey(key))
              return map.put(key, value);
           else
              return map.get(key);
         
        except that the action is performed atomically.
        Specified by:
        putIfAbsent in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        putIfAbsent in interface java.util.Map<K,​V>
        Parameters:
        key - key with which the specified value is to be associated.
        value - value to be associated with the specified key.
        Returns:
        previous value associated with specified key, or null if there was no mapping for key.
        Throws:
        java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if the key or value are null.
      • remove

        public boolean remove​(java.lang.Object key,
                              java.lang.Object value)
        Remove entry for key only if currently mapped to given value. Acts as
          if ((map.containsKey(key) && map.get(key).equals(value)) {
             map.remove(key);
             return true;
         } else return false;
         
        except that the action is performed atomically.
        Specified by:
        remove in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        remove in interface java.util.Map<K,​V>
        Parameters:
        key - key with which the specified value is associated.
        value - value associated with the specified key.
        Returns:
        true if the value was removed, false otherwise
        Throws:
        java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if the key or value are null.
      • replace

        public boolean replace​(K key,
                               V oldValue,
                               V newValue)
        Replace entry for key only if currently mapped to given value. Acts as
          if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
             map.put(key, newValue);
             return true;
         } else return false;
         
        except that the action is performed atomically.
        Specified by:
        replace in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        replace in interface java.util.Map<K,​V>
        Parameters:
        key - key with which the specified value is associated.
        oldValue - value expected to be associated with the specified key.
        newValue - value to be associated with the specified key.
        Returns:
        true if the value was replaced
        Throws:
        java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if key, oldValue or newValue are null.
      • replace

        public V replace​(K key,
                         V value)
        Replace entry for key only if currently mapped to some value. Acts as
          if ((map.containsKey(key)) {
             return map.put(key, value);
         } else return null;
         
        except that the action is performed atomically.
        Specified by:
        replace in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        replace in interface java.util.Map<K,​V>
        Parameters:
        key - key with which the specified value is associated.
        value - value to be associated with the specified key.
        Returns:
        previous value associated with specified key, or null if there was no mapping for key.
        Throws:
        java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if the key or value are null.
      • comparator

        public java.util.Comparator<? super K> comparator()
        Returns the comparator used to order this map, or null if this map uses its keys' natural order.
        Specified by:
        comparator in interface java.util.SortedMap<K,​V>
        Returns:
        the comparator associated with this map, or null if it uses its keys' natural sort method.
      • firstKey

        public K firstKey()
        Returns the first (lowest) key currently in this map.
        Specified by:
        firstKey in interface java.util.SortedMap<K,​V>
        Returns:
        the first (lowest) key currently in this map.
        Throws:
        java.util.NoSuchElementException - Map is empty.
      • lastKey

        public K lastKey()
        Returns the last (highest) key currently in this map.
        Specified by:
        lastKey in interface java.util.SortedMap<K,​V>
        Returns:
        the last (highest) key currently in this map.
        Throws:
        java.util.NoSuchElementException - Map is empty.
      • subMap

        public ConcurrentNavigableMap<K,​V> subMap​(K fromKey,
                                                        K toKey)
        Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive. (If fromKey and toKey are equal, the returned sorted map is empty.) The returned sorted map is backed by this map, so changes in the returned sorted map are reflected in this map, and vice-versa.
        Specified by:
        subMap in interface ConcurrentNavigableMap<K,​V>
        Specified by:
        subMap in interface NavigableMap<K,​V>
        Specified by:
        subMap in interface java.util.SortedMap<K,​V>
        Parameters:
        fromKey - low endpoint (inclusive) of the subMap.
        toKey - high endpoint (exclusive) of the subMap.
        Returns:
        a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
        Throws:
        java.lang.ClassCastException - if fromKey and toKey cannot be compared to one another using this map's comparator (or, if the map has no comparator, using natural ordering).
        java.lang.IllegalArgumentException - if fromKey is greater than toKey.
        java.lang.NullPointerException - if fromKey or toKey is null.
      • headMap

        public ConcurrentNavigableMap<K,​V> headMap​(K toKey)
        Returns a view of the portion of this map whose keys are strictly less than toKey. The returned sorted map is backed by this map, so changes in the returned sorted map are reflected in this map, and vice-versa.
        Specified by:
        headMap in interface ConcurrentNavigableMap<K,​V>
        Specified by:
        headMap in interface NavigableMap<K,​V>
        Specified by:
        headMap in interface java.util.SortedMap<K,​V>
        Parameters:
        toKey - high endpoint (exclusive) of the headMap.
        Returns:
        a view of the portion of this map whose keys are strictly less than toKey.
        Throws:
        java.lang.ClassCastException - if toKey is not compatible with this map's comparator (or, if the map has no comparator, if toKey does not implement Comparable).
        java.lang.NullPointerException - if toKey is null.
      • tailMap

        public ConcurrentNavigableMap<K,​V> tailMap​(K fromKey)
        Returns a view of the portion of this map whose keys are greater than or equal to fromKey. The returned sorted map is backed by this map, so changes in the returned sorted map are reflected in this map, and vice-versa.
        Specified by:
        tailMap in interface ConcurrentNavigableMap<K,​V>
        Specified by:
        tailMap in interface NavigableMap<K,​V>
        Specified by:
        tailMap in interface java.util.SortedMap<K,​V>
        Parameters:
        fromKey - low endpoint (inclusive) of the tailMap.
        Returns:
        a view of the portion of this map whose keys are greater than or equal to fromKey.
        Throws:
        java.lang.ClassCastException - if fromKey is not compatible with this map's comparator (or, if the map has no comparator, if fromKey does not implement Comparable).
        java.lang.NullPointerException - if fromKey is null.
      • ceilingEntry

        public java.util.Map.Entry<K,​V> ceilingEntry​(K key)
        Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such entry. The returned entry does not support the Entry.setValue method.
        Specified by:
        ceilingEntry in interface NavigableMap<K,​V>
        Parameters:
        key - the key.
        Returns:
        an Entry associated with ceiling of given key, or null if there is no such Entry.
        Throws:
        java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if key is null.
      • ceilingKey

        public K ceilingKey​(K key)
        Returns least key greater than or equal to the given key, or null if there is no such key.
        Specified by:
        ceilingKey in interface NavigableMap<K,​V>
        Parameters:
        key - the key.
        Returns:
        the ceiling key, or null if there is no such key.
        Throws:
        java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if key is null.
      • lowerEntry

        public java.util.Map.Entry<K,​V> lowerEntry​(K key)
        Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such entry. The returned entry does not support the Entry.setValue method.
        Specified by:
        lowerEntry in interface NavigableMap<K,​V>
        Parameters:
        key - the key.
        Returns:
        an Entry with greatest key less than the given key, or null if there is no such Entry.
        Throws:
        java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if key is null.
      • lowerKey

        public K lowerKey​(K key)
        Returns the greatest key strictly less than the given key, or null if there is no such key.
        Specified by:
        lowerKey in interface NavigableMap<K,​V>
        Parameters:
        key - the key.
        Returns:
        the greatest key less than the given key, or null if there is no such key.
        Throws:
        java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if key is null.
      • floorEntry

        public java.util.Map.Entry<K,​V> floorEntry​(K key)
        Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such entry. The returned entry does not support the Entry.setValue method.
        Specified by:
        floorEntry in interface NavigableMap<K,​V>
        Parameters:
        key - the key.
        Returns:
        an Entry associated with floor of given key, or null if there is no such Entry.
        Throws:
        java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if key is null.
      • floorKey

        public K floorKey​(K key)
        Returns the greatest key less than or equal to the given key, or null if there is no such key.
        Specified by:
        floorKey in interface NavigableMap<K,​V>
        Parameters:
        key - the key.
        Returns:
        the floor of given key, or null if there is no such key.
        Throws:
        java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if key is null.
      • higherEntry

        public java.util.Map.Entry<K,​V> higherEntry​(K key)
        Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such entry. The returned entry does not support the Entry.setValue method.
        Specified by:
        higherEntry in interface NavigableMap<K,​V>
        Parameters:
        key - the key.
        Returns:
        an Entry with least key greater than the given key, or null if there is no such Entry.
        Throws:
        java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if key is null.
      • higherKey

        public K higherKey​(K key)
        Returns the least key strictly greater than the given key, or null if there is no such key.
        Specified by:
        higherKey in interface NavigableMap<K,​V>
        Parameters:
        key - the key.
        Returns:
        the least key greater than the given key, or null if there is no such key.
        Throws:
        java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.
        java.lang.NullPointerException - if key is null.
      • firstEntry

        public java.util.Map.Entry<K,​V> firstEntry()
        Returns a key-value mapping associated with the least key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method.
        Specified by:
        firstEntry in interface NavigableMap<K,​V>
        Returns:
        an Entry with least key, or null if the map is empty.
      • lastEntry

        public java.util.Map.Entry<K,​V> lastEntry()
        Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method.
        Specified by:
        lastEntry in interface NavigableMap<K,​V>
        Returns:
        an Entry with greatest key, or null if the map is empty.
      • pollFirstEntry

        public java.util.Map.Entry<K,​V> pollFirstEntry()
        Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method.
        Specified by:
        pollFirstEntry in interface NavigableMap<K,​V>
        Returns:
        the removed first entry of this map, or null if the map is empty.
      • pollLastEntry

        public java.util.Map.Entry<K,​V> pollLastEntry()
        Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method.
        Specified by:
        pollLastEntry in interface NavigableMap<K,​V>
        Returns:
        the removed last entry of this map, or null if the map is empty.
      • keyIterator

        java.util.Iterator<K> keyIterator()
      • descendingKeyIterator

        java.util.Iterator<K> descendingKeyIterator()