Top Description Fields Constructors Methods
org.pcollections

public final Class IntTreePMap<V>

extends AbstractUnmodifiableMap<Integer, V>
implements PMap<Integer, V>, Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable, org.pcollections.PMap, java.util.Map
Static Imports
java.util.Objects.requireNonNull
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.

Author
harold

Field Summary

Modifier and TypeField and Description
private static final IntTreePMap<Object>
EMPTY

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

private final IntTree<V>
root

private static final long
serialVersionUID

Constructor Summary

AccessConstructor and Description
private
IntTreePMap(final IntTree<V> root)

Method Summary

Modifier and TypeMethod and Description
public boolean
containsKey(final Object
key whose presence in this map is to be tested
key)

Overrides java.util.AbstractMap.containsKey.

Implements java.util.Map.containsKey.

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

public static <V> IntTreePMap<V>

Returns:

an empty map
empty()

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

Implements abstract java.util.AbstractMap.entrySet.

Implements java.util.Map.entrySet.

Returns a Set view of the mappings contained in this map.

public static <V> IntTreePMap<V>

Returns:

empty().plusAll(map)
from(final Map<? extends Integer, ? extends V> map)

public V
get(final Object
the key whose associated value is to be returned
key)

Overrides java.util.AbstractMap.get.

Implements java.util.Map.get.

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

public IntTreePMap<V>
minus(final Object key)

Implements org.pcollections.PMap.minus.

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

Implements org.pcollections.PMap.minusAll.

public IntTreePMap<V>

Returns:

this map but with all keys start≤k<end removed
minusRange(final int start, final int end)

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

Implements org.pcollections.PMap.plus.

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

Implements org.pcollections.PMap.plusAll.

public static <V> IntTreePMap<V>

Returns:

empty().plus(key, value)
singleton(final Integer key, final V value)

public int
size()

Overrides java.util.AbstractMap.size.

Implements java.util.Map.size.

Returns the number of key-value mappings in this map.

pack-priv IntTreePMap<V>
withKeysChangedAbove(final int key, final int delta)

pack-priv IntTreePMap<V>
withKeysChangedBelow(final int key, final int delta)

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

Inherited from org.pcollections.AbstractUnmodifiableMap:
clearcomputecomputeIfAbsentcomputeIfPresentmergeputputAllputIfAbsentremovereplacereplaceAll

Field Detail

EMPTYback to summary
private static final IntTreePMap<Object> EMPTY
entrySetback to summary
private transient Set<Map.Entry<Integer, V>> entrySet
rootback to summary
private final IntTree<V> root
serialVersionUIDback to summary
private static final long serialVersionUID

Constructor Detail

IntTreePMapback to summary
private IntTreePMap(final IntTree<V> root)

Method Detail

containsKeyback to summary
public boolean containsKey(final Object key)

Overrides java.util.AbstractMap.containsKey.

Implements java.util.Map.containsKey.

Doc from java.util.Map.containsKey.

Returns true if this map contains a mapping for the specified key. More formally, returns true if and only if this map contains a mapping for a key k such that Objects.equals(key, k). (There can be at most one such mapping.)

Parameters
key:Object

key whose presence in this map is to be tested

Returns:boolean

true if this map contains a mapping for the specified key

Annotations
@Override
emptyback to summary
public static <V> IntTreePMap<V> empty()
Returns:IntTreePMap<V>

an empty map

Annotations
@SuppressWarnings:unchecked
entrySetback to summary
public Set<Map.Entry<Integer, V>> entrySet()

Implements abstract java.util.AbstractMap.entrySet.

Implements java.util.Map.entrySet.

Doc from java.util.Map.entrySet.

Returns a Set view of the mappings contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation, or through the setValue operation on a map entry returned by the iterator) the results of the iteration are undefined. 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.

Returns:Set<Map.Entry<Integer, V>>

a set view of the mappings contained in this map

Annotations
@Override
fromback to summary
public static <V> IntTreePMap<V> from(final Map<? extends Integer, ? extends V> map)
Returns:IntTreePMap<V>

empty().plusAll(map)

Annotations
@SuppressWarnings:unchecked
getback to summary
public V get(final Object key)

Overrides java.util.AbstractMap.get.

Implements java.util.Map.get.

Doc from java.util.Map.get.

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 Objects.equals(key, k), then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

If this map permits null values, then a return value of null does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to null. The containsKey operation may be used to distinguish these two cases.

Parameters
key:Object

the key whose associated value is to be returned

Returns:V

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

Annotations
@Override
minusback to summary
public IntTreePMap<V> minus(final Object key)

Implements org.pcollections.PMap.minus.

Returns:IntTreePMap<V>

Doc from org.pcollections.PMap.minus.

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

minusAllback to summary
public IntTreePMap<V> minusAll(final Collection<?> keys)

Implements org.pcollections.PMap.minusAll.

Returns:IntTreePMap<V>

Doc from org.pcollections.PMap.minusAll.

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

minusRangeback to summary
public IntTreePMap<V> minusRange(final int start, final int end)
Returns:IntTreePMap<V>

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

plusback to summary
public IntTreePMap<V> plus(final Integer key, final V value)

Implements org.pcollections.PMap.plus.

Returns:IntTreePMap<V>

Doc from org.pcollections.PMap.plus.

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

plusAllback to summary
public IntTreePMap<V> plusAll(final Map<? extends Integer, ? extends V> map)

Implements org.pcollections.PMap.plusAll.

Returns:IntTreePMap<V>

Doc from org.pcollections.PMap.plusAll.

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

singletonback to summary
public static <V> IntTreePMap<V> singleton(final Integer key, final V value)
Returns:IntTreePMap<V>

empty().plus(key, value)

sizeback to summary
public int size()

Overrides java.util.AbstractMap.size.

Implements java.util.Map.size.

Doc from java.util.Map.size.

Returns the number of key-value mappings in this map. If the map contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Returns:int

the number of key-value mappings in this map

Annotations
@Override
withKeysChangedAboveback to summary
pack-priv IntTreePMap<V> withKeysChangedAbove(final int key, final int delta)
withKeysChangedBelowback to summary
pack-priv IntTreePMap<V> withKeysChangedBelow(final int key, final int delta)
withRootback to summary
private IntTreePMap<V> withRoot(final IntTree<V> root)