Class 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.

    • Constructor Detail

      • IntTree

        private IntTree()
      • IntTree

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

      • withKey

        private IntTree<V> withKey​(long newKey)
      • 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)
      • plus

        IntTree<V> plus​(long key,
                        V value)
      • 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 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

        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()
      • rebalanced

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