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.

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.

Method Summary

Modifier and Type	Method and 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.
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.
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.
boolean	isEmpty() Indicates whether this tree is empty.
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.
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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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.

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.

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.

lookup

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