Package fj.data

Class TreeMap<K,​V>

  • All Implemented Interfaces:
    java.lang.Iterable<P2<K,​V>>
    public final class TreeMap<K,​V>
extends java.lang.Object
implements java.lang.Iterable<P2<K,​V>>
    An immutable, in-memory map, backed by a red-black tree.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private Set<P2<K,​Option<V>>> tree  

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private TreeMap​(Set<P2<K,​Option<V>>> tree)  

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      static <K,​V>
      TreeMap<K,​V>      		 arrayTreeMap​(Ord<K> keyOrd, P2<K,​V>... ps)
      Constructs a tree map from the given elements.
      boolean contains​(K k)
      Determines if the given key value exists in this tree map.
      TreeMap<K,​V> delete​(K k)
      Deletes the entry in the tree map that corresponds to the given key.
      static <K,​V>
      TreeMap<K,​V>      		 empty​(Ord<K> keyOrd)
      Constructs an empty tree map.
      boolean equals​(java.lang.Object other)  
      static <K,​V>
      TreeMap<K,​V>      		 fromMutableMap​(Ord<K> ord, java.util.Map<K,​V> m)
      An immutable projection of the given mutable map.
      F<K,​Option<V>> get()
      Returns a first-class version of the get method for this TreeMap.
      Option<V> get​(K k)
      Returns a potential value that the given key maps to.
      int hashCode()  
      boolean isEmpty()
      Determines if this tree map has any entries.
      static <K,​V>
      TreeMap<K,​V>      		 iterableTreeMap​(Ord<K> keyOrd, java.lang.Iterable<P2<K,​V>> it)
      Constructs a tree map from the given elements.
      java.util.Iterator<P2<K,​V>> iterator()
      Returns an iterator for this map's key-value pairs.
      static <K,​V>
      TreeMap<K,​V>      		 iteratorTreeMap​(Ord<K> keyOrd, java.util.Iterator<P2<K,​V>> it)
      Constructs a tree map from the given elements.
      List<K> keys()
      Returns all keys in this tree map.
      <W> TreeMap<K,​W> map​(F<V,​W> f)
      Maps the given function across the values of this TreeMap.
      Option<P2<K,​V>> max()
      Returns the maximum (key, value) pair in the tree if the tree is not empty.
      Option<K> maxKey()
      Returns the maximum key in the tree if the tree is not empty.
      Option<P2<K,​V>> min()
      Returns the minimum (key, value) pair in the tree if the tree is not empty.
      Option<K> minKey()
      Returns the minimum key in the tree if the tree is not empty.
      private static <K,​V>
      Ord<P2<K,​V>>      		 ord​(Ord<K> keyOrd)  
      TreeMap<K,​V> set​(K k, V v)
      Inserts the given key and value association into the tree map.
      static <K,​V>
      TreeMap<K,​V>      		 setTreeMap​(Ord<K> ord, Set<P2<K,​Option<V>>> s)
      Constructs a TreeMap from the given set.
      int size()
      Returns the number of entries in this tree map.
      P3<Set<V>,​Option<V>,​Set<V>> split​(Ord<V> ord, K k)
      Splits this TreeMap at the given key.
      P3<TreeMap<K,​V>,​Option<V>,​TreeMap<K,​V>> splitLookup​(K k)
      Splits this TreeMap at the given key.
      List<P2<K,​V>> toList()  
      List<P2<K,​V>> toListReverse()  
      java.util.Map<K,​V> toMutableMap()
      A mutable map projection of this tree map.
      Stream<P2<K,​V>> toStream()  
      Stream<P2<K,​V>> toStreamReverse()  
      java.lang.String toString()  
      static <K,​V>
      TreeMap<K,​V>      		 treeMap​(Ord<K> keyOrd, P2<K,​V>... p2s)
      Constructs a tree map from the given elements.
      TreeMap<K,​V> union​(TreeMap<K,​V> t2)
      The expression t1.union(t2) takes the left-biased union of t1 and t2.
      TreeMap<K,​V> union​(java.lang.Iterable<P2<K,​V>> t2)
      The expression t1.union(t2) takes the left-biased union of t1 and t2.
      P2<java.lang.Boolean,​TreeMap<K,​V>> update​(K k, F<V,​V> f)
      Modifies the value for the given key, if present, by applying the given function to it.
      TreeMap<K,​V> update​(K k, F<V,​V> f, V v)
      Modifies the value for the given key, if present, by applying the given function to it, or inserts the given value if the key is not present.
      List<V> values()
      Returns all values in this tree map.

      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait

      • Methods inherited from interface java.lang.Iterable

        forEach, spliterator

    • Constructor Detail

    • Method Detail

      • ord

        private static <K,​V> Ord<P2<K,​V>> ord​(Ord<K> keyOrd)

      • empty

        public static <K,​V> TreeMap<K,​V> empty​(Ord<K> keyOrd)
        Constructs an empty tree map.
        Parameters:
        keyOrd - An order for the keys of the tree map.
        Returns:
        an empty TreeMap with the given key order.

      • equals

        public boolean equals​(java.lang.Object other)
        Overrides:
        equals in class java.lang.Object

      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • treeMap

        @SafeVarargs
public static <K,​V> TreeMap<K,​V> treeMap​(Ord<K> keyOrd,
                                                     P2<K,​V>... p2s)
        Constructs a tree map from the given elements.
        Parameters:
        keyOrd - An order for the keys of the tree map.
        p2s - The elements to construct the tree map with.
        Returns:
        a TreeMap with the given elements.

      • iterableTreeMap

        public static <K,​V> TreeMap<K,​V> iterableTreeMap​(Ord<K> keyOrd,
                                                             java.lang.Iterable<P2<K,​V>> it)
        Constructs a tree map from the given elements.
        Parameters:
        keyOrd - An order for the keys of the tree map.
        it - The elements to construct the tree map with.
        Returns:
        A TreeMap with the given elements.

      • iteratorTreeMap

        public static <K,​V> TreeMap<K,​V> iteratorTreeMap​(Ord<K> keyOrd,
                                                             java.util.Iterator<P2<K,​V>> it)
        Constructs a tree map from the given elements.
        Parameters:
        keyOrd - An order for the keys of the tree map.
        it - The elements to construct the tree map with.
        Returns:
        A TreeMap with the given elements.

      • arrayTreeMap

        @SafeVarargs
public static <K,​V> TreeMap<K,​V> arrayTreeMap​(Ord<K> keyOrd,
                                                          P2<K,​V>... ps)
        Constructs a tree map from the given elements.
        Parameters:
        keyOrd - An order for the keys of the tree map.
        ps - The elements to construct the tree map with.
        Returns:
        A TreeMap with the given elements.

      • get

        public Option<V> get​(K k)
        Returns a potential value that the given key maps to.
        Parameters:
        k - The key to look up in the tree map.
        Returns:
        A potential value for the given key.

      • set

        public TreeMap<K,​V> set​(K k,
                              V v)
        Inserts the given key and value association into the tree map. If the given key is already mapped to a value, the old value is replaced with the given one.
        Parameters:
        k - The key to insert.
        v - The value to insert.
        Returns:
        A new tree map with the given value mapped to the given key.

      • delete

        public TreeMap<K,​V> delete​(K k)
        Deletes the entry in the tree map that corresponds to the given key.
        Parameters:
        k - The key to delete from this tree map.
        Returns:
        A new tree map with the entry corresponding to the given key removed.

      • size

        public int size()
        Returns the number of entries in this tree map.
        Returns:
        The number of entries in this tree map.

      • isEmpty

        public boolean isEmpty()
        Determines if this tree map has any entries.
        Returns:
        true if this tree map has no entries, false otherwise.

      • values

        public List<V> values()
        Returns all values in this tree map.
        Returns:
        All values in this tree map.

      • keys

        public List<K> keys()
        Returns all keys in this tree map.
        Returns:
        All keys in this tree map.

      • contains

        public boolean contains​(K k)
        Determines if the given key value exists in this tree map.
        Parameters:
        k - The key value to look for in this tree map.
        Returns:
        true if this tree map contains the given key, false otherwise.

      • iterator

        public java.util.Iterator<P2<K,​V>> iterator()
        Returns an iterator for this map's key-value pairs. This method exists to permit the use in a for-each loop.
        Specified by:
        iterator in interface java.lang.Iterable<K>
        Returns:
        A iterator for this map's key-value pairs.

      • toMutableMap

        public java.util.Map<K,​V> toMutableMap()
        A mutable map projection of this tree map.
        Returns:
        A new mutable map isomorphic to this tree map.

      • toStreamReverse

        public Stream<P2<K,​V>> toStreamReverse()

      • toList

        public List<P2<K,​V>> toList()

      • toListReverse

        public List<P2<K,​V>> toListReverse()

      • fromMutableMap

        public static <K,​V> TreeMap<K,​V> fromMutableMap​(Ord<K> ord,
                                                            java.util.Map<K,​V> m)
        An immutable projection of the given mutable map.
        Parameters:
        ord - An order for the map's keys.
        m - A mutable map to project to an immutable one.
        Returns:
        A new immutable tree map isomorphic to the given mutable map.

      • get

        public F<K,​Option<V>> get()
        Returns a first-class version of the get method for this TreeMap.
        Returns:
        a functional representation of this TreeMap.

      • update

        public P2<java.lang.Boolean,​TreeMap<K,​V>> update​(K k,
                                                             F<V,​V> f)
        Modifies the value for the given key, if present, by applying the given function to it.
        Parameters:
        k - The key for the value to modify.
        f - A function with which to modify the value.
        Returns:
        A new tree map with the value for the given key transformed by the given function, paired with True if the map was modified, otherwise False.

      • update

        public TreeMap<K,​V> update​(K k,
                                 F<V,​V> f,
                                 V v)
        Modifies the value for the given key, if present, by applying the given function to it, or inserts the given value if the key is not present.
        Parameters:
        k - The key for the value to modify.
        f - A function with which to modify the value.
        v - A value to associate with the given key if the key is not already present.
        Returns:
        A new tree map with the value for the given key transformed by the given function.

      • split

        public P3<Set<V>,​Option<V>,​Set<V>> split​(Ord<V> ord,
                                                     K k)
        Splits this TreeMap at the given key. Returns a triple of:
        • A set containing all the values of this map associated with keys less than the given key.
        • An option of a value mapped to the given key, if it exists in this map, otherwise None.
        • A set containing all the values of this map associated with keys greater than the given key.
        Parameters:
        k - A key at which to split this map.
        Returns:
        Two sets and an optional value, where all elements in the first set are mapped to keys less than the given key in this map, all the elements in the second set are mapped to keys greater than the given key, and the optional value is the value associated with the given key if present, otherwise None.

      • setTreeMap

        public static <K,​V> TreeMap<K,​V> setTreeMap​(Ord<K> ord,
                                                        Set<P2<K,​Option<V>>> s)
        Constructs a TreeMap from the given set.
        Parameters:
        ord - An order for the keys of the tree map.
        s - The elements to construct the tree map with.
        Returns:
        a TreeMap with the given elements.

      • splitLookup

        public P3<TreeMap<K,​V>,​Option<V>,​TreeMap<K,​V>> splitLookup​(K k)
        Splits this TreeMap at the given key. Returns a triple of:
        • A tree map containing all the values of this map associated with keys less than the given key.
        • An option of a value mapped to the given key, if it exists in this map, otherwise None.
        • A tree map containing all the values of this map associated with keys greater than the given key.
        Parameters:
        k - A key at which to split this map.
        Returns:
        Two tree maps and an optional value, where all keys in the first tree map are mapped to keys less than the given key in this map, all the keys in the second tree map are mapped to keys greater than the given key, and the optional value is the value associated with the given key if present, otherwise None.

      • map

        public <W> TreeMap<K,​W> map​(F<V,​W> f)
        Maps the given function across the values of this TreeMap.
        Parameters:
        f - A function to apply to the values of this TreeMap.
        Returns:
        A new TreeMap with the values transformed by the given function.

      • min

        public Option<P2<K,​V>> min()
        Returns the minimum (key, value) pair in the tree if the tree is not empty.

      • minKey

        public Option<K> minKey()
        Returns the minimum key in the tree if the tree is not empty.

      • max

        public Option<P2<K,​V>> max()
        Returns the maximum (key, value) pair in the tree if the tree is not empty.

      • maxKey

        public Option<K> maxKey()
        Returns the maximum key in the tree if the tree is not empty.

      • union

        public TreeMap<K,​V> union​(TreeMap<K,​V> t2)
        The expression t1.union(t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered.
        Parameters:
        t2 - The other tree we wish to combine with this one
        Returns:
        The combined TreeMap

      • union

        public TreeMap<K,​V> union​(java.lang.Iterable<P2<K,​V>> t2)
        The expression t1.union(t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered.
        Parameters:
        t2 - The other list/set of pairs we wish to combine with this one
        Returns:
        The combined TreeMap