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.
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 -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionabstract FingerTree
<V, A> append
(FingerTree<V, A> t) Appends one finger tree to another.abstract FingerTree
<V, A> Adds the given element to this tree as the first element.static <V,
A> FingerTree <V, A> Creates an empty finger tree with elements of type A and node annotations of type V.static <A> FingerTree
<Integer, A> static <A> FingerTree
<Integer, P2<Integer, A>> Returns a finger tree which combines the integer node annotations with the maximum function.final <B> FingerTree
<V, A> abstract <B> B
Folds the tree to the left with the given function and the given initial element.final <B> B
abstract <B> B
Folds the tree to the right with the given function and the given initial element.final <B> B
abstract A
head()
The first element of this tree.abstract FingerTree
<V, A> init()
The tree without the last element.final boolean
isEmpty()
Indicates whether this tree is empty.abstract A
last()
The last element of this tree.abstract int
length()
abstract <B> FingerTree
<V, B> Maps the given function across this tree, measuring with the given Measured instance.abstract <B> B
Provides pattern matching on trees.abstract V
measure()
Returns the sum of this tree's annotations.measured()
static <V,
A> Measured <V, A> Constructs a Measured instance for the element type, given a monoid and a measuring function.static <V,
A> MakeTree <V, A> Returns a builder of trees and tree components that annotates them using the given Measured instance.abstract A
Folds the tree to the left with the given function.abstract A
Folds the tree to the right with the given function.abstract FingerTree
<V, A> Adds the given element to this tree as the last element.final P2
<FingerTree<V, A>, FingerTree<V, A>> Splits this tree into a pair of subtrees at the point where the given predicate, based on the measure, changes fromfalse
totrue
.final P3
<FingerTree<V, A>, A, FingerTree<V, A>> Likesplit
, but returns the element wherepred
first holds separately.(package private) abstract P3
<FingerTree<V, A>, A, FingerTree<V, A>> abstract FingerTree
<V, A> tail()
The tree without the first element.toStream()
final <B> B
Performs a reduction on this finger tree using the given arguments.
-
Field Details
-
m
-
-
Constructor Details
-
FingerTree
-
-
Method Details
-
foldRight
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
-
reduceRight
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
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
-
reduceLeft
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
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
-
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
-
match
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
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
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
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
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
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
-
uncons
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
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
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
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
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
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
Likesplit
, but returns the element wherepred
first holds separately. Throws an error if the tree is empty. -
split1
-
lookup
-
length
public abstract int length() -
emptyIntAddition
-
empty
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
Returns a finger tree which combines the integer node annotations with the maximum function. A priority queue with integer priorities. -
toStream
-