net.sf.beanlib.util.concurrent
Class ConcurrentSkipListMap<K,V>

java.lang.Object
  net.sf.beanlib.util.AbstractMap<K,V>
      net.sf.beanlib.util.concurrent.ConcurrentSkipListMap<K,V>

Type Parameters:

K - the type of keys maintained by this map

V - the type of mapped values

All Implemented Interfaces:

Serializable, Cloneable, ConcurrentMap<K,V>, Map<K,V>, SortedMap<K,V>, ConcurrentNavigableMap<K,V>, NavigableMap<K,V>

public class ConcurrentSkipListMap<K,V>
extends AbstractMap<K,V>
implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable

A scalable concurrent ConcurrentNavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map 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.

This class is a member of the Java Collections Framework.

Since:

1.6

Author:

Doug Lea

See Also:

Serialized Form

Nested Class Summary

(package private) static class	ConcurrentSkipListMap.ComparableUsingComparator<K> Represents a key with a comparator as a Comparable.
(package private) class	ConcurrentSkipListMap.EntryIterator
(package private) static class	ConcurrentSkipListMap.EntrySet<K1,V1>
(package private) static class	ConcurrentSkipListMap.HeadIndex<K,V> Nodes heading each level keep track of their level.
(package private) static class	ConcurrentSkipListMap.Index<K,V> Index nodes represent the levels of the skip list.
(package private) class	ConcurrentSkipListMap.Iter<T> Base of iterator classes:
(package private) class	ConcurrentSkipListMap.KeyIterator
(package private) static class	ConcurrentSkipListMap.KeySet<E>
(package private) static class	ConcurrentSkipListMap.Node<K,V> Nodes hold keys and values, and are singly linked in sorted order, possibly with some intervening marker nodes.
(package private) static class	ConcurrentSkipListMap.SubMap<K,V> Submaps returned by ConcurrentSkipListMap submap operations represent a subrange of mappings of their underlying maps.
(package private) class	ConcurrentSkipListMap.ValueIterator
(package private) static class	ConcurrentSkipListMap.Values<E>

Nested classes/interfaces inherited from class net.sf.beanlib.util.AbstractMap

AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>

Field Summary

private static Object	BASE_HEADER Special value used to identify base-level header
private Comparator<? super K>	comparator The comparator used to maintain order in this map, or null if using natural ordering.
private ConcurrentNavigableMap<K,V>	descendingMap Lazily initialized descending key set
private ConcurrentSkipListMap.EntrySet	entrySet Lazily initialized entry set
private static int	EQ
private static int	GT
private ConcurrentSkipListMap.HeadIndex<K,V>	head The topmost head index of the skiplist.
private static AtomicReferenceFieldUpdater<ConcurrentSkipListMap,ConcurrentSkipListMap.HeadIndex>	headUpdater Updater for casHead
private ConcurrentSkipListMap.KeySet	keySet Lazily initialized key set
private static int	LT
private int	randomSeed Seed for simple random number generator.
private static Random	seedGenerator Generates the initial random seed for the cheaper per-instance random number generators used in randomLevel.
private static long	serialVersionUID
private ConcurrentSkipListMap.Values	values Lazily initialized values collection

Constructor Summary

ConcurrentSkipListMap()
Constructs a new, empty map, sorted according to the natural ordering of the keys.

ConcurrentSkipListMap(Comparator<? super K> comparator)
Constructs a new, empty map, sorted according to the specified comparator.

ConcurrentSkipListMap(Map<? extends K,? extends V> m)
Constructs a new map containing the same mappings as the given map, sorted according to the natural ordering of the keys.

ConcurrentSkipListMap(SortedMap<K,? extends V> m)
Constructs a new map containing the same mappings and using the same ordering as the specified sorted map.

Method Summary

private void	addIndex(ConcurrentSkipListMap.Index<K,V> idx, ConcurrentSkipListMap.HeadIndex<K,V> h, int indexLevel) Adds given index nodes from given level down to 1.
private void	buildFromSorted(SortedMap<K,? extends V> map) Streamlined bulk insertion to initialize from elements of given sorted map.
private boolean	casHead(ConcurrentSkipListMap.HeadIndex<K,V> cmp, ConcurrentSkipListMap.HeadIndex<K,V> val) compareAndSet head node
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.
K	ceilingKey(K key) Returns the least key greater than or equal to the given key, or null if there is no such key.
void	clear() Removes all of the mappings from this map.
private void	clearIndexToFirst() Clears out index nodes associated with deleted first entry.
ConcurrentSkipListMap<K,V>	clone() Returns a shallow copy of this ConcurrentSkipListMap instance.
private Comparable<? super K>	comparable(Object key) If using comparator, return a ComparableUsingComparator, else cast key as Comparable, which may cause ClassCastException, which is propagated back to caller.
Comparator<? super K>	comparator()
(package private) int	compare(K k1, K k2) Compares using comparator or natural ordering.
boolean	containsKey(Object key) Returns true if this map contains a mapping for the specified key.
boolean	containsValue(Object value) Returns true if this map maps one or more keys to the specified value.
NavigableSet<K>	descendingKeySet() Returns a reverse order NavigableSet view of the keys contained in this map.
ConcurrentNavigableMap<K,V>	descendingMap() Returns a reverse order view of the mappings contained in this map.
private V	doGet(Object okey) Specialized variant of findNode to perform Map.get.
private V	doPut(K kkey, V value, boolean onlyIfAbsent) Main insertion method.
(package private) V	doRemove(Object okey, Object value) Main deletion method.
(package private) Map.Entry<K,V>	doRemoveFirstEntry() Removes first entry; returns its snapshot.
(package private) Map.Entry<K,V>	doRemoveLastEntry() Removes last entry; returns its snapshot.
(package private) Iterator<Map.Entry<K,V>>	entryIterator()
Set<Map.Entry<K,V>>	entrySet() Returns a Set view of the mappings contained in this map.
boolean	equals(Object o) Compares the specified object with this map for equality.
(package private) ConcurrentSkipListMap.Node<K,V>	findFirst() Specialized variant of findNode to get first valid node.
(package private) ConcurrentSkipListMap.Node<K,V>	findLast() Specialized version of find to get last valid node.
(package private) ConcurrentSkipListMap.Node<K,V>	findNear(K kkey, int rel) Utility for ceiling, floor, lower, higher methods.
private ConcurrentSkipListMap.Node<K,V>	findNode(Comparable<? super K> key) Returns node holding key or null if no such, clearing out any deleted nodes seen along the way.
private ConcurrentSkipListMap.Node<K,V>	findPredecessor(Comparable<? super K> key) Returns a base-level node with key strictly less than given key, or the base-level header if there is no such node.
private ConcurrentSkipListMap.Node<K,V>	findPredecessorOfLast() Specialized variant of findPredecessor to get predecessor of last valid node.
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.
K	firstKey()
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 key.
K	floorKey(K key) Returns the greatest key less than or equal to the given key, or null if there is no such key.
V	get(Object key) Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
(package private) AbstractMap.SimpleImmutableEntry<K,V>	getNear(K key, int rel) Returns SimpleImmutableEntry for results of findNear.
private V	getUsingFindNode(Comparable<? super K> key) Performs map.get via findNode.
ConcurrentNavigableMap<K,V>	headMap(K toKey)
ConcurrentNavigableMap<K,V>	headMap(K toKey, boolean inclusive) Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.
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 key.
K	higherKey(K key) Returns the least key strictly greater than the given key, or null if there is no such key.
(package private) boolean	inHalfOpenRange(K key, K least, K fence) Returns true if given key greater than or equal to least and strictly less than fence, bypassing either test if least or fence are null.
(package private) void	initialize() Initializes or resets state.
(package private) boolean	inOpenRange(K key, K least, K fence) Returns true if given key greater than or equal to least and less or equal to fence.
private void	insertIndex(ConcurrentSkipListMap.Node<K,V> z, int level) Creates and adds index nodes for the given node.
boolean	isEmpty() Returns true if this map contains no key-value mappings.
(package private) Iterator<K>	keyIterator()
NavigableSet<K>	keySet() Returns a NavigableSet view of the keys contained in this map.
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.
K	lastKey()
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 key.
K	lowerKey(K key) Returns the greatest key strictly less than the given key, or null if there is no such key.
NavigableSet<K>	navigableKeySet() Returns a NavigableSet view of the keys contained in this map.
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.
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.
V	put(K key, V value) Associates the specified value with the specified key in this map.
V	putIfAbsent(K key, V value)
private int	randomLevel() Returns a random level for inserting a new node.
private void	readObject(ObjectInputStream s) Reconstitute the map from a stream.
V	remove(Object key) Removes the mapping for the specified key from this map if present.
boolean	remove(Object key, Object value)
V	replace(K key, V value)
boolean	replace(K key, V oldValue, V newValue)
int	size() Returns the number of key-value mappings in this map.
ConcurrentNavigableMap<K,V>	subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) Returns a view of the portion of this map whose keys range from fromKey to toKey.
ConcurrentNavigableMap<K,V>	subMap(K fromKey, K toKey)
ConcurrentNavigableMap<K,V>	tailMap(K fromKey)
ConcurrentNavigableMap<K,V>	tailMap(K fromKey, boolean inclusive) Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.
(package private) static <E> List<E>	toList(Collection<E> c)
private void	tryReduceLevel() Possibly reduce head level if it has no nodes.
(package private) Iterator<V>	valueIterator()
Collection<V>	values() Returns a Collection view of the values contained in this map.
private void	writeObject(ObjectOutputStream s) Save the state of this map to a stream.

Methods inherited from class net.sf.beanlib.util.AbstractMap

hashCode, putAll, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

seedGenerator

private static final Random seedGenerator

Generates the initial random seed for the cheaper per-instance random number generators used in randomLevel.

BASE_HEADER

private static final Object BASE_HEADER

Special value used to identify base-level header

head

private transient volatile ConcurrentSkipListMap.HeadIndex<K,V> head

The topmost head index of the skiplist.

comparator

private final Comparator<? super K> comparator

The comparator used to maintain order in this map, or null if using natural ordering.

randomSeed

private transient int randomSeed

Seed for simple random number generator. Not volatile since it doesn't matter too much if different threads don't see updates.

keySet

private transient ConcurrentSkipListMap.KeySet keySet

Lazily initialized key set

entrySet

private transient ConcurrentSkipListMap.EntrySet entrySet

Lazily initialized entry set

values

private transient ConcurrentSkipListMap.Values values

Lazily initialized values collection

descendingMap

private transient ConcurrentNavigableMap<K,V> descendingMap

Lazily initialized descending key set

headUpdater

private static final AtomicReferenceFieldUpdater<ConcurrentSkipListMap,ConcurrentSkipListMap.HeadIndex> headUpdater

Updater for casHead

EQ

private static final int EQ

See Also:

Constant Field Values

LT

private static final int LT

See Also:

Constant Field Values

GT

private static final int GT

See Also:

Constant Field Values

Constructor Detail

ConcurrentSkipListMap

public ConcurrentSkipListMap()

Constructs a new, empty map, sorted according to the natural ordering of the keys.

ConcurrentSkipListMap

public ConcurrentSkipListMap(Comparator<? super K> comparator)

Constructs a new, empty map, sorted according to the specified comparator.

Parameters:

comparator - the comparator that will be used to order this map. If null, the natural ordering of the keys will be used.

ConcurrentSkipListMap

public ConcurrentSkipListMap(Map<? extends K,? extends V> m)

Constructs a new map containing the same mappings as the given map, sorted according to the natural ordering of the keys.

Parameters:

m - the map whose mappings are to be placed in this map

Throws:

ClassCastException - if the keys in m are not Comparable, or are not mutually comparable

NullPointerException - if the specified map or any of its keys or values are null

ConcurrentSkipListMap

public ConcurrentSkipListMap(SortedMap<K,? extends V> m)

Constructs a new map containing the same mappings and using the same ordering as the specified sorted map.

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:

NullPointerException - if the specified sorted map or any of its keys or values are null

Method Detail

initialize

final void initialize()

Initializes or resets state. Needed by constructors, clone, clear, readObject. and ConcurrentSkipListSet.clone. (Note that comparator must be separately initialized.)

casHead

private boolean casHead(ConcurrentSkipListMap.HeadIndex<K,V> cmp,
                        ConcurrentSkipListMap.HeadIndex<K,V> val)

compareAndSet head node

comparable

private Comparable<? super K> comparable(Object key)
                                  throws ClassCastException

If using comparator, return a ComparableUsingComparator, else cast key as Comparable, which may cause ClassCastException, which is propagated back to caller.

Throws:

ClassCastException

compare

int compare(K k1,
            K k2)
      throws ClassCastException

Compares using comparator or natural ordering. Used when the ComparableUsingComparator approach doesn't apply.

Throws:

ClassCastException

inHalfOpenRange

boolean inHalfOpenRange(K key,
                        K least,
                        K fence)

Returns true if given key greater than or equal to least and strictly less than fence, bypassing either test if least or fence are null. Needed mainly in submap operations.

inOpenRange

boolean inOpenRange(K key,
                    K least,
                    K fence)

Returns 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(Comparable<? super K> key)

Returns 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(Comparable<? super K> key)

Returns 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 findFirst, and findLast and their variants. 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(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(Comparable<? super K> key)

Performs 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()

Returns a random level for inserting a new node. Hardwired to k=1, p=0.5, max 31 (see above and Pugh's "Skip List Cookbook", sec 3.4). This uses the simplest of the generators described in George Marsaglia's "Xorshift RNGs" paper. This is not a high-quality generator but is acceptable here.

insertIndex

private void insertIndex(ConcurrentSkipListMap.Node<K,V> z,
                         int level)

Creates and adds index nodes for the 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)

Adds 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

final V doRemove(Object okey,
                 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.

findFirst

ConcurrentSkipListMap.Node<K,V> findFirst()

Specialized variant of findNode to get first valid node.

Returns:

first node or null if empty

doRemoveFirstEntry

Map.Entry<K,V> doRemoveFirstEntry()

Removes first entry; returns its snapshot.

Returns:

null if empty, else snapshot of first entry

clearIndexToFirst

private void clearIndexToFirst()

Clears out index nodes associated with deleted first entry.

findLast

ConcurrentSkipListMap.Node<K,V> findLast()

Specialized version of find to get last valid node.

Returns:

last node or null if empty

findPredecessorOfLast

private ConcurrentSkipListMap.Node<K,V> findPredecessorOfLast()

Specialized variant of findPredecessor to get predecessor of last valid node. Needed when removing the last entry. 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

doRemoveLastEntry

Map.Entry<K,V> doRemoveLastEntry()

Removes last entry; returns its snapshot. Specialized variant of doRemove.

Returns:

null if empty, else snapshot of last entry

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

AbstractMap.SimpleImmutableEntry<K,V> getNear(K key,
                                              int rel)

Returns SimpleImmutableEntry for results of findNear.

Parameters:

key - the key

rel - the relation -- OR'ed combination of EQ, LT, GT

Returns:

Entry fitting relation, or null if no such

clone

public ConcurrentSkipListMap<K,V> clone()

Returns a shallow copy of this ConcurrentSkipListMap instance. (The keys and values themselves are not cloned.)

Overrides:

clone in class AbstractMap<K,V>

Returns:

a shallow copy of this map

buildFromSorted

private void buildFromSorted(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(ObjectOutputStream s)
                  throws IOException

Save the state of this map to a stream.

Throws:

IOException

readObject

private void readObject(ObjectInputStream s)
                 throws IOException,
                        ClassNotFoundException

Reconstitute the map from a stream.

Throws:

IOException

ClassNotFoundException

containsKey

public boolean containsKey(Object key)

Returns true if this map contains a mapping for the specified key.

Specified by:

containsKey in interface Map<K,V>

Overrides:

containsKey in class 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:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

get

public V get(Object key)

Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

More formally, if this map contains a mapping from a key k to a value v such that key compares equal to k according to the map's ordering, then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

Specified by:

get in interface Map<K,V>

Overrides:

get in class AbstractMap<K,V>

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified 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 the key, the old value is replaced.

Specified by:

put in interface Map<K,V>

Overrides:

put in class 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:

the previous value associated with the specified key, or null if there was no mapping for the key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key or value is null

remove

public V remove(Object key)

Removes the mapping for the specified key from this map if present.

Specified by:

remove in interface Map<K,V>

Overrides:

remove in class AbstractMap<K,V>

Parameters:

key - key for which mapping should be removed

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

containsValue

public boolean containsValue(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 Map<K,V>

Overrides:

containsValue in class 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:

NullPointerException - if the specified value is null

size

public int size()

Returns the number of key-value mappings 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 Map<K,V>

Overrides:

size in class 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 Map<K,V>

Overrides:

isEmpty in class AbstractMap<K,V>

Returns:

true if this map contains no key-value mappings

clear

public void clear()

Removes all of the mappings from this map.

Specified by:

clear in interface Map<K,V>

Overrides:

clear in class AbstractMap<K,V>

keySet

public NavigableSet<K> keySet()

Returns a NavigableSet view of the keys contained in this map. The set's iterator returns the keys in ascending 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 the 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.

This method is equivalent to method navigableKeySet.

Specified by:

keySet in interface Map<K,V>

Specified by:

keySet in interface ConcurrentNavigableMap<K,V>

Overrides:

keySet in class AbstractMap<K,V>

Returns:

a navigable set view of the keys in this map

navigableKeySet

public NavigableSet<K> navigableKeySet()

Description copied from interface: ConcurrentNavigableMap

Returns a NavigableSet view of the keys contained in this map. The set's iterator returns the keys in ascending 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 the 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:

navigableKeySet in interface ConcurrentNavigableMap<K,V>

Specified by:

navigableKeySet in interface NavigableMap<K,V>

Returns:

a navigable set view of the keys in this map

values

public Collection<V> values()

Returns a Collection view of the values contained in this map. The collection's iterator returns the values in ascending order of the corresponding keys. 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.

Specified by:

values in interface Map<K,V>

Overrides:

values in class AbstractMap<K,V>

entrySet

public Set<Map.Entry<K,V>> entrySet()

Returns a Set view of the mappings contained in this map. The set's iterator returns the entries in ascending key 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 the 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.

The Map.Entry elements returned by iterator.next() do not support the setValue operation.

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in class AbstractMap<K,V>

Returns:

a set view of the mappings contained in this map, sorted in ascending key order

descendingMap

public ConcurrentNavigableMap<K,V> descendingMap()

Description copied from interface: ConcurrentNavigableMap

Returns a reverse order view of the mappings contained in this map. The descending map is backed by this map, so changes to the map are reflected in the descending map, and vice-versa.

The returned map has an ordering equivalent to Collections.reverseOrder(comparator()). The expression m.descendingMap().descendingMap() returns a view of m essentially equivalent to m.

Specified by:

descendingMap in interface ConcurrentNavigableMap<K,V>

Specified by:

descendingMap in interface NavigableMap<K,V>

Returns:

a reverse order view of this map

descendingKeySet

public NavigableSet<K> descendingKeySet()

Description copied from interface: ConcurrentNavigableMap

Returns a reverse order NavigableSet view of the keys contained in this map. The set's iterator returns the keys 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 the 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 ConcurrentNavigableMap<K,V>

Specified by:

descendingKeySet in interface NavigableMap<K,V>

Returns:

a reverse order navigable set view of the keys in this map

equals

public boolean equals(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 m1 and m2 represent the same mappings if m1.entrySet().equals(m2.entrySet()). This operation may return misleading results if either map is concurrently modified during execution of this method.

Specified by:

equals in interface Map<K,V>

Overrides:

equals in class 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

putIfAbsent

public V putIfAbsent(K key,
                     V value)

Specified by:

putIfAbsent in interface ConcurrentMap<K,V>

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key or value is null

remove

public boolean remove(Object key,
                      Object value)

Specified by:

remove in interface ConcurrentMap<K,V>

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

replace

public boolean replace(K key,
                       V oldValue,
                       V newValue)

Specified by:

replace in interface ConcurrentMap<K,V>

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if any of the arguments are null

replace

public V replace(K key,
                 V value)

Specified by:

replace in interface ConcurrentMap<K,V>

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key or value is null

comparator

public Comparator<? super K> comparator()

Specified by:

comparator in interface SortedMap<K,V>

firstKey

public K firstKey()

Specified by:

firstKey in interface SortedMap<K,V>

Throws:

NoSuchElementException

lastKey

public K lastKey()

Specified by:

lastKey in interface SortedMap<K,V>

Throws:

NoSuchElementException

subMap

public ConcurrentNavigableMap<K,V> subMap(K fromKey,
                                          boolean fromInclusive,
                                          K toKey,
                                          boolean toInclusive)

Description copied from interface: NavigableMap

Returns a view of the portion of this map whose keys range from fromKey to toKey. If fromKey and toKey are equal, the returned map is empty unless fromExclusive and toExclusive are both true. The returned map is backed by this map, so changes in the returned map are reflected in this map, and vice-versa. The returned map supports all optional map operations that this map supports.

The returned map will throw an IllegalArgumentException on an attempt to insert a key outside of its range, or to construct a submap either of whose endpoints lie outside its range.

Specified by:

subMap in interface ConcurrentNavigableMap<K,V>

Specified by:

subMap in interface NavigableMap<K,V>

Parameters:

fromKey - low endpoint of the keys in the returned map

fromInclusive - true if the low endpoint is to be included in the returned view

toKey - high endpoint of the keys in the returned map

toInclusive - true if the high endpoint is to be included in the returned view

Returns:

a view of the portion of this map whose keys range from fromKey to toKey

Throws:

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). Implementations may, but are not required to, throw this exception if fromKey or toKey cannot be compared to keys currently in the map.

NullPointerException - if fromKey or toKey is null

IllegalArgumentException - if fromKey is greater than toKey; or if this map itself has a restricted range, and fromKey or toKey lies outside the bounds of the range

headMap

public ConcurrentNavigableMap<K,V> headMap(K toKey,
                                           boolean inclusive)

Description copied from interface: NavigableMap

Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey. The returned map is backed by this map, so changes in the returned map are reflected in this map, and vice-versa. The returned map supports all optional map operations that this map supports.

The returned map will throw an IllegalArgumentException on an attempt to insert a key outside its range.

Specified by:

headMap in interface ConcurrentNavigableMap<K,V>

Specified by:

headMap in interface NavigableMap<K,V>

Parameters:

toKey - high endpoint of the keys in the returned map

inclusive - true if the high endpoint is to be included in the returned view

Returns:

a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey

Throws:

ClassCastException - if toKey is not compatible with this map's comparator (or, if the map has no comparator, if toKey does not implement Comparable). Implementations may, but are not required to, throw this exception if toKey cannot be compared to keys currently in the map.

NullPointerException - if toKey is null

IllegalArgumentException - if this map itself has a restricted range, and toKey lies outside the bounds of the range

tailMap

public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
                                           boolean inclusive)

Description copied from interface: NavigableMap

Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey. The returned map is backed by this map, so changes in the returned map are reflected in this map, and vice-versa. The returned map supports all optional map operations that this map supports.

The returned map will throw an IllegalArgumentException on an attempt to insert a key outside its range.

Specified by:

tailMap in interface ConcurrentNavigableMap<K,V>

Specified by:

tailMap in interface NavigableMap<K,V>

Parameters:

fromKey - low endpoint of the keys in the returned map

inclusive - true if the low endpoint is to be included in the returned view

Returns:

a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey

Throws:

ClassCastException - if fromKey is not compatible with this map's comparator (or, if the map has no comparator, if fromKey does not implement Comparable). Implementations may, but are not required to, throw this exception if fromKey cannot be compared to keys currently in the map.

NullPointerException - if fromKey is null

IllegalArgumentException - if this map itself has a restricted range, and fromKey lies outside the bounds of the range

subMap

public ConcurrentNavigableMap<K,V> subMap(K fromKey,
                                          K toKey)

Description copied from interface: NavigableMap

Equivalent to subMap(fromKey, true, toKey, false).

Specified by:

subMap in interface SortedMap<K,V>

Specified by:

subMap in interface ConcurrentNavigableMap<K,V>

Specified by:

subMap in interface NavigableMap<K,V>

Throws:

ClassCastException

NullPointerException - if fromKey or toKey is null

IllegalArgumentException

headMap

public ConcurrentNavigableMap<K,V> headMap(K toKey)

Description copied from interface: NavigableMap

Equivalent to headMap(toKey, false).

Specified by:

headMap in interface SortedMap<K,V>

Specified by:

headMap in interface ConcurrentNavigableMap<K,V>

Specified by:

headMap in interface NavigableMap<K,V>

Throws:

ClassCastException

NullPointerException - if toKey is null

IllegalArgumentException

tailMap

public ConcurrentNavigableMap<K,V> tailMap(K fromKey)

Description copied from interface: NavigableMap

Equivalent to tailMap(fromKey, true).

Specified by:

tailMap in interface SortedMap<K,V>

Specified by:

tailMap in interface ConcurrentNavigableMap<K,V>

Specified by:

tailMap in interface NavigableMap<K,V>

Throws:

ClassCastException

NullPointerException - if fromKey is null

IllegalArgumentException

lowerEntry

public 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 key. 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 the greatest key less than key, or null if there is no such key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

lowerKey

public K lowerKey(K key)

Description copied from interface: NavigableMap

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 key, or null if there is no such key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

floorEntry

public 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 key. 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 with the greatest key less than or equal to key, or null if there is no such key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

floorKey

public K floorKey(K key)

Description copied from interface: NavigableMap

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 greatest key less than or equal to key, or null if there is no such key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

ceilingEntry

public 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 with the least key greater than or equal to key, or null if there is no such key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

ceilingKey

public K ceilingKey(K key)

Description copied from interface: NavigableMap

Returns the 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 least key greater than or equal to key, or null if there is no such key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

higherEntry

public 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 key. 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 the least key greater than key, or null if there is no such key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

higherKey

public K higherKey(K key)

Description copied from interface: NavigableMap

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 key, or null if there is no such key

Throws:

ClassCastException - if the specified key cannot be compared with the keys currently in the map

NullPointerException - if the specified key is null

firstEntry

public 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 the least key, or null if this map is empty

lastEntry

public 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 the greatest key, or null if this map is empty

pollFirstEntry

public 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 this map is empty

pollLastEntry

public 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 this map is empty

keyIterator

Iterator<K> keyIterator()

valueIterator

Iterator<V> valueIterator()

entryIterator

Iterator<Map.Entry<K,V>> entryIterator()

toList

static final <E> List<E> toList(Collection<E> c)