Class IntTreePMap<V>

  • Type Parameters:
    V -
    All Implemented Interfaces:
    java.io.Serializable, java.util.Map<java.lang.Integer,​V>, PMap<java.lang.Integer,​V>

    public final class IntTreePMap<V>
    extends AbstractUnmodifiableMap<java.lang.Integer,​V>
    implements PMap<java.lang.Integer,​V>, java.io.Serializable
    An efficient persistent map from integer keys to values. Null values are supported.

    Iteration occurs in the integer order of the keys.

    This implementation is thread-safe (assuming Java's AbstractMap and AbstractSet are thread-safe), although its iterators may not be.

    The balanced 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.

    See Also:
    Serialized Form
    • Field Detail

      • EMPTY

        private static final IntTreePMap<java.lang.Object> EMPTY
      • entrySet

        private transient java.util.Set<java.util.Map.Entry<java.lang.Integer,​V>> entrySet
    • Constructor Detail

      • IntTreePMap

        private IntTreePMap​(IntTree<V> root)
    • Method Detail

      • empty

        public static <V> IntTreePMap<V> empty()
        Type Parameters:
        V -
        Returns:
        an empty map
      • singleton

        public static <V> IntTreePMap<V> singleton​(java.lang.Integer key,
                                                   V value)
        Type Parameters:
        V -
        Parameters:
        key -
        value -
        Returns:
        empty().plus(key, value)
      • from

        public static <V> IntTreePMap<V> from​(java.util.Map<? extends java.lang.Integer,​? extends V> map)
        Type Parameters:
        V -
        Parameters:
        map -
        Returns:
        empty().plusAll(map)
      • minusRange

        public IntTreePMap<V> minusRange​(int start,
                                         int end)
        Parameters:
        start -
        end -
        Returns:
        this map but with all keys start≤k<end removed
      • withKeysChangedAbove

        IntTreePMap<V> withKeysChangedAbove​(int key,
                                            int delta)
      • withKeysChangedBelow

        IntTreePMap<V> withKeysChangedBelow​(int key,
                                            int delta)
      • entrySet

        public java.util.Set<java.util.Map.Entry<java.lang.Integer,​V>> entrySet()
        Specified by:
        entrySet in interface java.util.Map<java.lang.Integer,​V>
        Specified by:
        entrySet in class java.util.AbstractMap<java.lang.Integer,​V>
      • size

        public int size()
        Specified by:
        size in interface java.util.Map<java.lang.Integer,​V>
        Overrides:
        size in class java.util.AbstractMap<java.lang.Integer,​V>
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<java.lang.Integer,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<java.lang.Integer,​V>
      • get

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<java.lang.Integer,​V>
        Overrides:
        get in class java.util.AbstractMap<java.lang.Integer,​V>
      • plus

        public IntTreePMap<V> plus​(java.lang.Integer key,
                                   V value)
        Specified by:
        plus in interface PMap<java.lang.Integer,​V>
        Returns:
        a map with the mappings of this but with key mapped to value
      • minus

        public IntTreePMap<V> minus​(java.lang.Object key)
        Specified by:
        minus in interface PMap<java.lang.Integer,​V>
        Returns:
        a map with the mappings of this but with no value for key
      • plusAll

        public IntTreePMap<V> plusAll​(java.util.Map<? extends java.lang.Integer,​? extends V> map)
        Specified by:
        plusAll in interface PMap<java.lang.Integer,​V>
        Returns:
        this combined with map, with map's mappings used for any keys in both map and this
      • minusAll

        public IntTreePMap<V> minusAll​(java.util.Collection<?> keys)
        Specified by:
        minusAll in interface PMap<java.lang.Integer,​V>
        Returns:
        a map with the mappings of this but with no value for any element of keys