Class FingerTree<V,A>

java.lang.Object
fj.data.fingertrees.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 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 Details

  • Constructor Details

  • Method Details

    • 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,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,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,Boolean> predicate)
      Like split, but returns the element where pred first holds separately. Throws an error if the tree is empty.

    • split1

      abstract P3<FingerTree<V,A>, A, FingerTree<V,A>> split1(F<V,Boolean> predicate, V acc)

    • lookup

      public abstract P2<Integer,A> lookup(F<V,Integer> o, int i)

    • length

      public abstract int length()

    • emptyIntAddition

      public static <A> FingerTree<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<Integer, P2<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()