Class FingerTree<V,​A>

  • Type Parameters:
    V - The monoidal type with which to annotate nodes.
    A - The type of the tree's elements.
    Direct Known Subclasses:
    Deep, Empty, Single

    public abstract class FingerTree<V,​A>
    extends java.lang.Object
    Provides 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized O(1) time. Concatenation and splitting time is O(log n) in the size of the smaller piece. A general purpose data structure that can serve as a sequence, priority queue, search tree, priority search queue and more.

    This class serves as a datastructure construction kit, rather than a datastructure in its own right. By supplying a monoid, a measurement function, insertion, deletion, and so forth, any purely functional datastructure can be emulated. See Seq for an example.

    Based on "Finger trees: a simple general-purpose data structure", by Ralf Hinze and Ross Paterson.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private Measured<V,​A> m  
    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      abstract FingerTree<V,​A> append​(FingerTree<V,​A> t)
      Appends one finger tree to another.
      abstract FingerTree<V,​A> cons​(A a)
      Adds the given element to this tree as the first element.
      static <V,​A>
      FingerTree<V,​A>
      empty​(Monoid<V> m, F<A,​V> f)
      Creates an empty finger tree with elements of type A and node annotations of type V.
      static <A> FingerTree<java.lang.Integer,​A> emptyIntAddition()  
      static <A> FingerTree<java.lang.Integer,​P2<java.lang.Integer,​A>> emptyIntMax()
      Returns a finger tree which combines the integer node annotations with the maximum function.
      <B> FingerTree<V,​A> filter​(F<A,​java.lang.Boolean> f)  
      abstract <B> B foldLeft​(F<B,​F<A,​B>> f, B z)
      Folds the tree to the left with the given function and the given initial element.
      <B> B foldLeft​(F2<B,​A,​B> f, B z)  
      abstract <B> B foldRight​(F<A,​F<B,​B>> f, B z)
      Folds the tree to the right with the given function and the given initial element.
      <B> B foldRight​(F2<A,​B,​B> f, B z)  
      abstract A head()
      The first element of this tree.
      Option<A> headOption()  
      abstract FingerTree<V,​A> init()
      The tree without the last element.
      boolean isEmpty()
      Indicates whether this tree is empty.
      abstract A last()
      The last element of this tree.
      abstract int length()  
      abstract P2<java.lang.Integer,​A> lookup​(F<V,​java.lang.Integer> o, int i)  
      abstract <B> FingerTree<V,​B> map​(F<A,​B> f, Measured<V,​B> m)
      Maps the given function across this tree, measuring with the given Measured instance.
      abstract <B> B match​(F<Empty<V,​A>,​B> empty, F<Single<V,​A>,​B> single, F<Deep<V,​A>,​B> deep)
      Provides pattern matching on trees.
      abstract V measure()
      Returns the sum of this tree's annotations.
      Measured<V,​A> measured()  
      static <V,​A>
      Measured<V,​A>
      measured​(Monoid<V> monoid, F<A,​V> measure)
      Constructs a Measured instance for the element type, given a monoid and a measuring function.
      static <V,​A>
      MakeTree<V,​A>
      mkTree​(Measured<V,​A> m)
      Returns a builder of trees and tree components that annotates them using the given Measured instance.
      abstract A reduceLeft​(F<A,​F<A,​A>> f)
      Folds the tree to the left with the given function.
      abstract A reduceRight​(F<A,​F<A,​A>> f)
      Folds the tree to the right with the given function.
      abstract FingerTree<V,​A> snoc​(A a)
      Adds the given element to this tree as the last element.
      P2<FingerTree<V,​A>,​FingerTree<V,​A>> split​(F<V,​java.lang.Boolean> predicate)
      Splits this tree into a pair of subtrees at the point where the given predicate, based on the measure, changes from false to true.
      P3<FingerTree<V,​A>,​A,​FingerTree<V,​A>> split1​(F<V,​java.lang.Boolean> predicate)
      Like split, but returns the element where pred first holds separately.
      (package private) abstract P3<FingerTree<V,​A>,​A,​FingerTree<V,​A>> split1​(F<V,​java.lang.Boolean> predicate, V acc)  
      abstract FingerTree<V,​A> tail()
      The tree without the first element.
      abstract Stream<A> toStream()  
      <B> B uncons​(B nil, F2<A,​FingerTree<V,​A>,​B> cons)
      Performs a reduction on this finger tree using the given arguments.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

    • Method Detail

      • foldRight

        public abstract <B> B foldRight​(F<A,​F<B,​B>> f,
                                        B z)
        Folds the tree to the right with the given function and the given initial element.
        Parameters:
        f - A function with which to fold the tree.
        z - An initial element to apply to the fold.
        Returns:
        A reduction of this tree by applying the given function, associating to the right.
      • foldRight

        public final <B> B foldRight​(F2<A,​B,​B> f,
                                     B z)
      • reduceRight

        public abstract A reduceRight​(F<A,​F<A,​A>> f)
        Folds the tree to the right with the given function.
        Parameters:
        f - A function with which to fold the tree.
        Returns:
        A reduction of this tree by applying the given function, associating to the right.
      • foldLeft

        public abstract <B> B foldLeft​(F<B,​F<A,​B>> f,
                                       B z)
        Folds the tree to the left with the given function and the given initial element.
        Parameters:
        f - A function with which to fold the tree.
        z - An initial element to apply to the fold.
        Returns:
        A reduction of this tree by applying the given function, associating to the left.
      • foldLeft

        public final <B> B foldLeft​(F2<B,​A,​B> f,
                                    B z)
      • reduceLeft

        public abstract A reduceLeft​(F<A,​F<A,​A>> f)
        Folds the tree to the left with the given function.
        Parameters:
        f - A function with which to fold the tree.
        Returns:
        A reduction of this tree by applying the given function, associating to the right.
      • map

        public abstract <B> FingerTree<V,​B> map​(F<A,​B> f,
                                                      Measured<V,​B> m)
        Maps the given function across this tree, measuring with the given Measured instance.
        Parameters:
        f - A function to map across the values of this tree.
        m - A measuring with which to annotate the tree.
        Returns:
        A new tree with the same structure as this tree, with each element transformed by the given function, and nodes annotated according to the given measuring.
      • filter

        public final <B> FingerTree<V,​A> filter​(F<A,​java.lang.Boolean> f)
      • measure

        public abstract V measure()
        Returns the sum of this tree's annotations.
        Returns:
        the sum of this tree's annotations.
      • isEmpty

        public final boolean isEmpty()
        Indicates whether this tree is empty.
        Returns:
        true if this tree is the empty tree, otherwise false.
      • measured

        public final Measured<V,​A> measured()
      • match

        public abstract <B> B match​(F<Empty<V,​A>,​B> empty,
                                    F<Single<V,​A>,​B> single,
                                    F<Deep<V,​A>,​B> deep)
        Provides pattern matching on trees. This is the Church encoding of the FingerTree datatype.
        Parameters:
        empty - The function to apply to this empty tree.
        single - A function to apply if this tree contains a single element.
        deep - A function to apply if this tree contains more than one element.
        Returns:
        The result of the function that matches this tree structurally, applied to this tree.
      • measured

        public static <V,​A> Measured<V,​A> measured​(Monoid<V> monoid,
                                                               F<A,​V> measure)
        Constructs a Measured instance for the element type, given a monoid and a measuring function.
        Parameters:
        monoid - A monoid for the measures.
        measure - A function with which to measure element values.
        Returns:
        A Measured instance for the given element type, that uses the given monoid and measuring function.
      • mkTree

        public static <V,​A> MakeTree<V,​A> mkTree​(Measured<V,​A> m)
        Returns a builder of trees and tree components that annotates them using the given Measured instance.
        Parameters:
        m - A Measured instance with which to annotate trees, digits, and nodes.
        Returns:
        A builder of trees and tree components that annotates them using the given Measured instance.
      • cons

        public abstract FingerTree<V,​A> cons​(A a)
        Adds the given element to this tree as the first element.
        Parameters:
        a - The element to add to the front of this tree.
        Returns:
        A new tree with the given element at the front.
      • snoc

        public abstract FingerTree<V,​A> snoc​(A a)
        Adds the given element to this tree as the last element.
        Parameters:
        a - The element to add to the end of this tree.
        Returns:
        A new tree with the given element at the end.
      • head

        public abstract A head()
        The first element of this tree. This is an O(1) operation.
        Returns:
        The first element if this tree is nonempty, otherwise throws an error.
      • headOption

        public final Option<A> headOption()
      • uncons

        public final <B> B uncons​(B nil,
                                  F2<A,​FingerTree<V,​A>,​B> cons)
        Performs a reduction on this finger tree using the given arguments.
        Parameters:
        nil - The value to return if this finger tree is empty.
        cons - The function to apply to the head and tail of this finger tree if it is not empty.
        Returns:
        A reduction on this finger tree.
      • last

        public abstract A last()
        The last element of this tree. This is an O(1) operation.
        Returns:
        The last element if this tree is nonempty, otherwise throws an error.
      • tail

        public abstract FingerTree<V,​A> tail()
        The tree without the first element. This is an O(1) operation.
        Returns:
        The tree without the first element if this tree is nonempty, otherwise throws an error.
      • init

        public abstract FingerTree<V,​A> init()
        The tree without the last element. This is an O(1) operation.
        Returns:
        The tree without the last element if this tree is nonempty, otherwise throws an error.
      • append

        public abstract FingerTree<V,​A> append​(FingerTree<V,​A> t)
        Appends one finger tree to another.
        Parameters:
        t - A finger tree to append to this one.
        Returns:
        A new finger tree which is a concatenation of this tree and the given tree.
      • split

        public final P2<FingerTree<V,​A>,​FingerTree<V,​A>> split​(F<V,​java.lang.Boolean> predicate)
        Splits this tree into a pair of subtrees at the point where the given predicate, based on the measure, changes from false to true. This is a O(log(n)) operation.
        Returns:
        Pair: the subtree containing elements before the point where pred first holds and the subtree containing element at and after the point where pred first holds. Empty if pred never holds.
      • split1

        public final P3<FingerTree<V,​A>,​A,​FingerTree<V,​A>> split1​(F<V,​java.lang.Boolean> predicate)
        Like split, but returns the element where pred first holds separately. Throws an error if the tree is empty.
      • lookup

        public abstract P2<java.lang.Integer,​A> lookup​(F<V,​java.lang.Integer> o,
                                                             int i)
      • length

        public abstract int length()
      • emptyIntAddition

        public static <A> FingerTree<java.lang.Integer,​A> emptyIntAddition()
      • empty

        public static <V,​A> FingerTree<V,​A> empty​(Monoid<V> m,
                                                              F<A,​V> f)
        Creates an empty finger tree with elements of type A and node annotations of type V.
        Parameters:
        m - A monoid to combine node annotations
        f - Function to convert node element to annotation.
        Returns:
        An empty finger tree.
      • emptyIntMax

        public static <A> FingerTree<java.lang.Integer,​P2<java.lang.Integer,​A>> emptyIntMax()
        Returns a finger tree which combines the integer node annotations with the maximum function. A priority queue with integer priorities.
      • toStream

        public abstract Stream<A> toStream()