Class SortedMap<K,V>

java.lang.Object
io.lacuna.bifurcan.IMap.Mixin<K,V>
io.lacuna.bifurcan.ISortedMap.Mixin<K,V>
io.lacuna.bifurcan.SortedMap<K,V>
All Implemented Interfaces:
ICollection<IMap<K,V>,IEntry<K,V>>, IMap<K,V>, ISortedMap<K,V>, Iterable<IEntry<K,V>>, Function<K,V>
public class SortedMap<K,V> extends ISortedMap.Mixin<K,V>
A red-black tree based on Germane 2014.

  • Field Details

    • root

      public io.lacuna.bifurcan.nodes.SortedMapNodes.Node<K,V> root

  • Constructor Details

    • SortedMap

      public SortedMap()

    • SortedMap

      public SortedMap(Comparator<K> comparator)

  • Method Details

    • from

      public static <K, V> SortedMap<K,V> from(Map<K,V> m)

    • empty

      public static <K, V> SortedMap<K,V> empty()

    • comparator

      public Comparator<K> comparator()

    • inclusiveFloorIndex

      public OptionalLong inclusiveFloorIndex(K key)

    • ceilIndex

      public OptionalLong ceilIndex(K key)

    • update

      public SortedMap<K,V> update(K key, UnaryOperator<V> update)
      Parameters:
      update - a function which takes the existing value, or null if none exists, and returns an updated value.
      Returns:
      an updated map with update(value) under key.

    • put

      public SortedMap<K,V> put(K key, V value)
      Returns:
      an updated map with value stored under key

    • split

      public List<SortedMap<K,V>> split(int parts)
      Description copied from interface: ICollection
      Splits the collection into roughly even pieces, for parallel processing. Depending on the size and contents of the collection, this function may not return exactly parts subsets.
      Parameters:
      parts - the target number of pieces
      Returns:
      a list containing subsets of the collection.

    • put

      public SortedMap<K,V> put(K key, V value, BinaryOperator<V> merge)
      Parameters:
      merge - a function which will be invoked if there is a pre-existing value under key, with the current value as the first argument and new value as the second, to determine the combined result
      Returns:
      an updated map with value under key

    • remove

      public SortedMap<K,V> remove(K key)
      Returns:
      an updated map that does not contain key

    • get

      public V get(K key, V defaultValue)
      Returns:
      the value under key, or defaultValue if there is no such key

    • contains

      public boolean contains(K key)
      Returns:
      true if key is in the map, false otherwise

    • indexOf

      public OptionalLong indexOf(K key)
      Returns:
      the index of key within the collection, if it's present

    • mapValues

      public <U> SortedMap<K,U> mapValues(BiFunction<K,V,U> f)
      Type Parameters:
      U - the new type of the values
      Parameters:
      f - a function which transforms the values
      Returns:
      a transformed map which shares the same equality semantics

    • iterator

      public Iterator<IEntry<K,V>> iterator()

    • nth

      public IEntry<K,V> nth(long idx)
      Returns:
      the element at idx

    • size

      public long size()
      Returns:
      the number of elements in the collection

    • clone

      public SortedMap<K,V> clone()
      Specified by:
      clone in interface ICollection<K,V>
      Overrides:
      clone in class ISortedMap.Mixin<K,V>
      Returns:
      a cloned copy of the collection

    • isLinear

      public boolean isLinear()
      Returns:
      true, if the collection is linear

    • forked

      public SortedMap<K,V> forked()
      Description copied from interface: ICollection
      This returns a data structure which is forked, which is equivalent to Clojure's persistent data structures, also sometimes called functional or immutable. This is called "forked" because it means that multiple functions can make divergent changes to the data structure without affecting each other.

      If only a single function or scope uses the data structure, it can be left as a linear data structure, which can have significant performance benefits.

      If the data structure is already forked, it will simply return itself.

      Returns:
      a forked form of the data structure

    • linear

      public SortedMap<K,V> linear()
      Description copied from interface: ICollection
      This returns a data structure which is linear, or temporarily mutable. The term "linear", as used here, does not completely align with the formal definition of linear types as used in type theory. It is meant to describe the linear dataflow of the method calls, and as a converse to "forked" data structures.

      If ICollection.forked() is called on a linear collection, all references to that linear collection should be discarded.

      If the data structure is already linear, it will simply return itself.

      Returns:
      a linear form of this data structure

    • keyHash

      public ToLongFunction<K> keyHash()
      Returns:
      the hash function used by the map

    • keyEquality

      public BiPredicate<K,K> keyEquality()
      Returns:
      the key equality semantics used by the map