Class IntTreePMap<V>

java.lang.Object

java.util.AbstractMap<Integer,V>

org.pcollections.AbstractUnmodifiableMap<Integer,V>

org.pcollections.IntTreePMap<V>

Type Parameters:

V -

All Implemented Interfaces:

Serializable, Map<Integer,V>, PMap<Integer,V>

public final class IntTreePMap<V>
extends AbstractUnmodifiableMap<Integer,V>
implements PMap<Integer,V>, Serializable

An efficient persistent map from integer keys to values. Null values are supported.

Iteration occurs in the integer order of the keys.

This implementation is thread-safe (assuming Java's AbstractMap and AbstractSet are thread-safe), although its iterators may not be.

The balanced tree is based on the Glasgow Haskell Compiler's Data.Map implementation, which in turn is based on "size balanced binary trees" as described by:

Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.

J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.

See Also:

• Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class AbstractMap

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

Nested classes/interfaces inherited from interface Map

Map.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field	Description
private static final IntTreePMap<Object>	EMPTY	/ STATIC FACTORY METHODS ////
private Set<Map.Entry<Integer,V>>	entrySet	/ REQUIRED METHODS FROM AbstractMap ////
private final IntTree<V>	root	/ PRIVATE CONSTRUCTORS ////
private static final long	serialVersionUID

Constructor Summary

Constructors

Modifier	Constructor	Description
private	IntTreePMap(IntTree<V> root)

Method Summary

Modifier and Type	Method	Description
boolean	containsKey(Object key)
static <V> IntTreePMap<V>	empty()
Set<Map.Entry<Integer,V>>	entrySet()
static <V> IntTreePMap<V>	from(Map<? extends Integer, ? extends V> map)
V	get(Object key)
IntTreePMap<V>	minus(Object key)
IntTreePMap<V>	minusAll(Collection<?> keys)
IntTreePMap<V>	minusRange(int start, int end)
IntTreePMap<V>	plus(Integer key, V value)	/ IMPLEMENTED METHODS OF PMap////
IntTreePMap<V>	plusAll(Map<? extends Integer, ? extends V> map)
static <V> IntTreePMap<V>	singleton(Integer key, V value)
int	size()	/ OVERRIDDEN METHODS FROM AbstractMap ////
(package private) IntTreePMap<V>	withKeysChangedAbove(int key, int delta)
(package private) IntTreePMap<V>	withKeysChangedBelow(int key, int delta)
private IntTreePMap<V>	withRoot(IntTree<V> root)

Methods inherited from class AbstractUnmodifiableMap

clear, compute, computeIfAbsent, computeIfPresent, merge, put, putAll, putIfAbsent, remove, replace, replaceAll

Methods inherited from class AbstractMap

clone, containsValue, equals, hashCode, isEmpty, keySet, toString, values

Methods inherited from class Object

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

Methods inherited from interface Map

compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, isEmpty, keySet, merge, putIfAbsent, remove, replace, replace, replaceAll, values

Methods inherited from interface PMap

clear, put, putAll, remove

Field Details

serialVersionUID

private static final long serialVersionUID

See Also:

• Constant Field Values

EMPTY

private static final IntTreePMap<Object> EMPTY

/ STATIC FACTORY METHODS ////

root

private final IntTree<V> root

/ PRIVATE CONSTRUCTORS ////

entrySet

private transient Set<Map.Entry<Integer,V>> entrySet

/ REQUIRED METHODS FROM AbstractMap ////

Constructor Details

IntTreePMap

private IntTreePMap(IntTree<V> root)

Method Details

empty

public static <V> IntTreePMap<V> empty()

Type Parameters:

V -

Returns:

an empty map

singleton

public static <V> IntTreePMap<V> singleton(Integer key,
 V value)

Type Parameters:

V -

Parameters:

key -

value -

Returns:

empty().plus(key, value)

from

public static <V> IntTreePMap<V> from(Map<? extends Integer, ? extends V> map)

Type Parameters:

V -

Parameters:

map -

Returns:

empty().plusAll(map)

withRoot

private IntTreePMap<V> withRoot(IntTree<V> root)

minusRange

public IntTreePMap<V> minusRange(int start,
 int end)

Parameters:

start -

end -

Returns:

this map but with all keys start≤k<end removed

withKeysChangedAbove

IntTreePMap<V> withKeysChangedAbove(int key,
 int delta)

withKeysChangedBelow

IntTreePMap<V> withKeysChangedBelow(int key,
 int delta)

entrySet

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

Specified by:

entrySet in interface Map<Integer,V>

Specified by:

entrySet in class AbstractMap<Integer,V>

size

public int size()

/ OVERRIDDEN METHODS FROM AbstractMap ////

Specified by:

size in interface Map<Integer,V>

Overrides:

size in class AbstractMap<Integer,V>

containsKey

public boolean containsKey(Object key)

Specified by:

containsKey in interface Map<Integer,V>

Overrides:

containsKey in class AbstractMap<Integer,V>

get

public V get(Object key)

Specified by:

get in interface Map<Integer,V>

Overrides:

get in class AbstractMap<Integer,V>

plus

public IntTreePMap<V> plus(Integer key,
 V value)

/ IMPLEMENTED METHODS OF PMap////

Specified by:

plus in interface PMap<Integer,V>

Parameters:

key -

value -

Returns:

a map with the mappings of this but with key mapped to value

minus

public IntTreePMap<V> minus(Object key)

Specified by:

minus in interface PMap<Integer,V>

Parameters:

key -

Returns:

a map with the mappings of this but with no value for key

plusAll

public IntTreePMap<V> plusAll(Map<? extends Integer, ? extends V> map)

Specified by:

plusAll in interface PMap<Integer,V>

Parameters:

map -

Returns:

this combined with map, with map's mappings used for any keys in both map and this

minusAll

public IntTreePMap<V> minusAll(Collection<?> keys)

Specified by:

minusAll in interface PMap<Integer,V>

Parameters:

keys -

Returns:

a map with the mappings of this but with no value for any element of keys