Class IntTree<V>

java.lang.Object
org.pcollections.IntTree<V>
Type Parameters:
V -
All Implemented Interfaces:
Serializable

class IntTree<V> extends Object implements 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.

  • Field Details

  • Constructor Details

    • IntTree

      private IntTree()
    • IntTree

      private IntTree(long key, V value, IntTree<V> left, IntTree<V> right)
  • Method Details

    • withKey

      private IntTree<V> withKey(long newKey)
    • iterator

      Iterator<Map.Entry<Integer,V>> iterator()
    • size

      int size()
    • containsKey

      boolean containsKey(long key)
    • get

      V get(long key)
    • plus

      IntTree<V> plus(long key, V value)
    • minus

      IntTree<V> minus(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 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

      IntTree<V> changeKeysBelow(long key, int delta)
      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

      private IntTree<V> rebalanced(IntTree<V> newLeft, IntTree<V> newRight)
    • rebalanced

      private static <V> IntTree<V> rebalanced(long key, V value, IntTree<V> left, IntTree<V> right)