- java.lang.Object
-
- org.pcollections.IntTree<V>
-
- Type Parameters:
V
-
- All Implemented Interfaces:
java.io.Serializable
class IntTree<V> extends java.lang.Object implements java.io.Serializable
A non-public utility class for persistent balanced tree maps with integer keys.To allow for efficiently increasing all keys above a certain value or decreasing all keys below a certain value, the keys values are stored relative to their parent. This makes this map a good backing for fast insertion and removal of indices in a vector. Null values are supported.
This implementation is thread-safe except for its iterators.
Other than that, this 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
IntTree.EntryIterator<V>
-
Field Summary
Fields Modifier and Type Field Description private static int
ALPHA
(package private) static IntTree<java.lang.Object>
EMPTYNODE
private long
key
private IntTree<V>
left
private static int
OMEGA
private IntTree<V>
right
private static long
serialVersionUID
private int
size
private V
value
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) IntTree<V>
changeKeysAbove(long key, int delta)
Changes every key k>=key to k+delta.(package private) IntTree<V>
changeKeysBelow(long key, int delta)
Changes every key k(package private) boolean
containsKey(long key)
(package private) V
get(long key)
(package private) java.util.Iterator<java.util.Map.Entry<java.lang.Integer,V>>
iterator()
private long
minKey()
(package private) IntTree<V>
minus(long key)
(package private) IntTree<V>
plus(long key, V value)
private static <V> IntTree<V>
rebalanced(long key, V value, IntTree<V> left, IntTree<V> right)
private IntTree<V>
rebalanced(IntTree<V> newLeft, IntTree<V> newRight)
(package private) int
size()
private IntTree<V>
withKey(long newKey)
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
EMPTYNODE
static final IntTree<java.lang.Object> EMPTYNODE
-
key
private final long key
-
value
private final V value
-
size
private final int size
-
OMEGA
private static final int OMEGA
- See Also:
- Constant Field Values
-
ALPHA
private static final int ALPHA
- See Also:
- Constant Field Values
-
-
Method Detail
-
iterator
java.util.Iterator<java.util.Map.Entry<java.lang.Integer,V>> iterator()
-
size
int size()
-
containsKey
boolean containsKey(long key)
-
get
V get(long key)
-
changeKeysAbove
IntTree<V> changeKeysAbove(long key, int delta)
Changes every key k>=key to k+delta.This method will create an _invalid_ tree if delta<0 and the distance between the smallest k>=key in this and the largest j
In other words, this method must not result in any change in the order of the keys in this, since the tree structure is not being changed at all.
-
changeKeysBelow
IntTree<V> changeKeysBelow(long key, int delta)
Changes every key kThis method will create an _invalid_ tree if delta>0 and the distance between the largest k =key in this is delta or less. In other words, this method must not result in any overlap or change in the order of the keys in this, since the tree _structure_ is not being changed at all.
-
minKey
private long minKey()
-
-