- Type Parameters:
V
-
- All Implemented Interfaces:
Serializable
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 -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final int
private final long
private static final int
private static final long
private final int
private final V
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionchangeKeysAbove
(long key, int delta) Changes every key k>=key to k+delta.changeKeysBelow
(long key, int delta) Changes every key kinvalid input: '<'key to k+delta.(package private) boolean
containsKey
(long key) (package private) V
get
(long key) iterator()
private long
minKey()
minus
(long key) private static <V> IntTree
<V> rebalanced
(long key, V value, IntTree<V> left, IntTree<V> right) rebalanced
(IntTree<V> newLeft, IntTree<V> newRight) (package private) int
size()
withKey
(long newKey)
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
EMPTYNODE
-
key
private final long key -
value
-
left
-
right
-
size
private final int size -
OMEGA
private static final int OMEGA- See Also:
-
ALPHA
private static final int ALPHA- See Also:
-
-
Constructor Details
-
IntTree
private IntTree() -
IntTree
-
-
Method Details
-
withKey
-
iterator
-
size
int size() -
containsKey
boolean containsKey(long key) -
get
-
plus
-
minus
-
changeKeysAbove
Changes every key k>=key to k+delta.This method will create an _invalid_ tree if deltainvalid input: '<'0 and the distance between the smallest k>=key in this and the largest jinvalid input: '<'key in this is |delta| or less.
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
Changes every key kinvalid input: '<'key to k+delta.This 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() -
rebalanced
-
rebalanced
-