Package fj.data.fingertrees
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.
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. SeeSeq
for an example. Based on "Finger trees: a simple general-purpose data structure", by Ralf Hinze and Ross Paterson.
-
-
Constructor Summary
Constructors Constructor Description FingerTree(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 fromfalse
totrue
.P3<FingerTree<V,A>,A,FingerTree<V,A>>
split1(F<V,java.lang.Boolean> predicate)
Likesplit
, but returns the element wherepred
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.
-
-
-
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.
-
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.
-
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.
-
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.
-
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 fromfalse
totrue
. 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 wherepred
first holds. Empty ifpred
never holds.
-
split1
public final P3<FingerTree<V,A>,A,FingerTree<V,A>> split1(F<V,java.lang.Boolean> predicate)
Likesplit
, but returns the element wherepred
first holds separately. Throws an error if the tree is empty.
-
split1
abstract P3<FingerTree<V,A>,A,FingerTree<V,A>> split1(F<V,java.lang.Boolean> predicate, V acc)
-
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 annotationsf
- 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.
-
-