- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- org.pcollections.AbstractUnmodifiableMap<java.lang.Integer,V>
-
- org.pcollections.IntTreePMap<V>
-
- Type Parameters:
V
-
- All Implemented Interfaces:
java.io.Serializable
,java.util.Map<java.lang.Integer,V>
,PMap<java.lang.Integer,V>
public final class IntTreePMap<V> extends AbstractUnmodifiableMap<java.lang.Integer,V> implements PMap<java.lang.Integer,V>, java.io.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
-
-
Field Summary
Fields Modifier and Type Field Description private static IntTreePMap<java.lang.Object>
EMPTY
private java.util.Set<java.util.Map.Entry<java.lang.Integer,V>>
entrySet
private IntTree<V>
root
private static long
serialVersionUID
-
Constructor Summary
Constructors Modifier Constructor Description private
IntTreePMap(IntTree<V> root)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
containsKey(java.lang.Object key)
static <V> IntTreePMap<V>
empty()
java.util.Set<java.util.Map.Entry<java.lang.Integer,V>>
entrySet()
static <V> IntTreePMap<V>
from(java.util.Map<? extends java.lang.Integer,? extends V> map)
V
get(java.lang.Object key)
IntTreePMap<V>
minus(java.lang.Object key)
IntTreePMap<V>
minusAll(java.util.Collection<?> keys)
IntTreePMap<V>
minusRange(int start, int end)
IntTreePMap<V>
plus(java.lang.Integer key, V value)
IntTreePMap<V>
plusAll(java.util.Map<? extends java.lang.Integer,? extends V> map)
static <V> IntTreePMap<V>
singleton(java.lang.Integer key, V value)
int
size()
(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 org.pcollections.AbstractUnmodifiableMap
clear, compute, computeIfAbsent, computeIfPresent, merge, put, putAll, putIfAbsent, remove, replace, replaceAll
-
Methods inherited from class java.util.AbstractMap
clone, containsValue, equals, hashCode, isEmpty, keySet, toString, values
-
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
-
EMPTY
private static final IntTreePMap<java.lang.Object> EMPTY
-
entrySet
private transient java.util.Set<java.util.Map.Entry<java.lang.Integer,V>> entrySet
-
-
Method Detail
-
empty
public static <V> IntTreePMap<V> empty()
- Type Parameters:
V
-- Returns:
- an empty map
-
singleton
public static <V> IntTreePMap<V> singleton(java.lang.Integer key, V value)
- Type Parameters:
V
-- Parameters:
key
-value
-- Returns:
- empty().plus(key, value)
-
from
public static <V> IntTreePMap<V> from(java.util.Map<? extends java.lang.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 java.util.Set<java.util.Map.Entry<java.lang.Integer,V>> entrySet()
-
size
public int size()
-
containsKey
public boolean containsKey(java.lang.Object key)
-
get
public V get(java.lang.Object key)
-
plus
public IntTreePMap<V> plus(java.lang.Integer key, V value)
-
minus
public IntTreePMap<V> minus(java.lang.Object key)
-
plusAll
public IntTreePMap<V> plusAll(java.util.Map<? extends java.lang.Integer,? extends V> map)
-
minusAll
public IntTreePMap<V> minusAll(java.util.Collection<?> keys)
-
-