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 and Inner Type Summary

Modifier and Type	Class and Description
private static class	IntTree.EntryIterator<V>

Field Summary

Modifier and Type	Field and Description
private static final int	ALPHA
pack-priv static final IntTree<Object>	EMPTYNODE
private final long	key
private final IntTree<V>	left
private static final int	OMEGA
private final IntTree<V>	right
private static final long	serialVersionUID
private final int	size
private final V	value

Constructor Summary

Access	Constructor and Description
private	IntTree()
private	IntTree(final long key, final V value, final IntTree<V> left, final IntTree<V> right)

Method Summary

Modifier and Type	Method and Description
pack-priv IntTree<V>	changeKeysAbove(final long key, final int delta) Changes every key k>=key to k+delta.
pack-priv IntTree<V>	changeKeysBelow(final long key, final int delta) Changes every key k<key to k+delta. 0 and the distance between the largest k<key in this and the smallest j>=key in this is delta or less.
pack-priv boolean	containsKey(final long key)
pack-priv V	get(final long key)
pack-priv Iterator<Map.Entry<Integer, V>>	iterator()
private long	minKey()
pack-priv IntTree<V>	minus(final long key)
pack-priv IntTree<V>	plus(final long key, final V value)
private IntTree<V>	rebalanced(final IntTree<V> newLeft, final IntTree<V> newRight)
private static <V> IntTree<V>	rebalanced(final long key, final V value, final IntTree<V> left, final IntTree<V> right)
pack-priv int	size()
private IntTree<V>	withKey(final long newKey)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

ALPHA	back to summary
private static final int ALPHA

EMPTYNODE	back to summary
pack-priv static final IntTree<Object> EMPTYNODE

key	back to summary
private final long key

left	back to summary
private final IntTree<V> left

OMEGA	back to summary
private static final int OMEGA

right	back to summary
private final IntTree<V> right

serialVersionUID	back to summary
private static final long serialVersionUID

size	back to summary
private final int size

value	back to summary
private final V value

Constructor Detail

IntTree	back to summary
private IntTree()

IntTree	back to summary
private IntTree(final long key, final V value, final IntTree<V> left, final IntTree<V> right)

Method Detail

changeKeysAbove	back to summary
pack-priv IntTree<V> changeKeysAbove(final long key, final 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 jIn 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.

changeKeysAbove

back to summary

pack-priv IntTree<V> changeKeysAbove(final long key, final 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 jIn 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	back to summary
pack-priv IntTree<V> changeKeysBelow(final long key, final 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.

changeKeysBelow

back to summary

pack-priv IntTree<V> changeKeysBelow(final long key, final 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.

containsKey	back to summary
pack-priv boolean containsKey(final long key)

get	back to summary
pack-priv V get(final long key)

iterator	back to summary
pack-priv Iterator<Map.Entry<Integer, V>> iterator()

minKey	back to summary
private long minKey()

minus	back to summary
pack-priv IntTree<V> minus(final long key)

plus	back to summary
pack-priv IntTree<V> plus(final long key, final V value)

rebalanced	back to summary
private IntTree<V> rebalanced(final IntTree<V> newLeft, final IntTree<V> newRight)

rebalanced	back to summary
private static <V> IntTree<V> rebalanced(final long key, final V value, final IntTree<V> left, final IntTree<V> right)

size	back to summary
pack-priv int size()

withKey	back to summary
private IntTree<V> withKey(final long newKey)

org.pcollections back to summary

private final Class IntTree.EntryIterator<V>

Class Inheritance

extends Object
implements Iterator<Map.Entry<Integer, V>>

java.lang.Object
org.pcollections.IntTree.EntryIterator

All Implemented Interfaces

java.util.Iterator

Field Summary

Modifier and Type	Field and Description
private int	key
private PStack<IntTree<V>>	stack

Constructor Summary

Access	Constructor and Description
pack-priv	EntryIterator(final IntTree<V> root)

Method Summary

Modifier and Type	Method and Description
private void	gotoMinOf(IntTree<V> node)
public boolean	hasNext() Implements java.util.Iterator.hasNext. Returns `true` if the iteration has more elements.
public Map.Entry<Integer, V>	next() Implements java.util.Iterator.next. Returns the next element in the iteration.
public void	remove() Overrides default java.util.Iterator.remove. Removes from the underlying collection the last element returned by this iterator (optional operation).

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

key	back to summary
private int key

stack	back to summary
private PStack<IntTree<V>> stack

Constructor Detail

EntryIterator	back to summary
pack-priv EntryIterator(final IntTree<V> root)

Method Detail

gotoMinOf	back to summary
private void gotoMinOf(IntTree<V> node)

hasNext back to summary

hasNext	back to summary
public boolean hasNext() Implements java.util.Iterator.hasNext. Doc from java.util.Iterator.hasNext. Returns `true` if the iteration has more elements. (In other words, returns `true` if `next` would return an element rather than throwing an exception.) Returns:boolean `true` if the iteration has more elements

public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

Returns:boolean: true if the iteration has more elements

next	back to summary
public Map.Entry<Integer, V> next() Implements java.util.Iterator.next. Doc from java.util.Iterator.next. Returns the next element in the iteration. Returns:Map.Entry<Integer, V> the next element in the iteration

back to summary

public Map.Entry<Integer, V> next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

Returns:Map.Entry<Integer, V>: the next element in the iteration

remove back to summary

remove	back to summary
public void remove() Overrides default java.util.Iterator.remove. Doc from java.util.Iterator.remove. Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to `next`. The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy. The behavior of an iterator is unspecified if this method is called after a call to the `forEachRemaining` method.

public void remove()

Overrides default java.util.Iterator.remove.

Doc from java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next.

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy.

The behavior of an iterator is unspecified if this method is called after a call to the forEachRemaining method.

pack-priv Class IntTree<V>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private final Class IntTree.EntryIterator<V>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail