|
Copyright 2008 - 2009 Tony Morris, Runar Bjarnason, Tom Adams, Brad Clow, Ricky Clarkson, Nick Partridge, Jason Zaugg This software is released under an open source BSD licence. |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectfj.data.fingertrees.FingerTree<V,A>
V
- The monoidal type with which to annotate nodes.A
- The type of the tree's elements.public abstract class FingerTree<V,A>
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.
Method Summary | ||
---|---|---|
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
|
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
|
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<Integer,A> |
lookup(F<V,Integer> o,
int i)
|
|
abstract
|
map(F<A,B> f,
Measured<V,B> m)
Maps the given function across this tree, measuring with the given Measured instance. |
|
abstract
|
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. |
|
protected Measured<V,A> |
measured()
|
|
static
|
measured(Monoid<V> monoid,
F<A,V> measure)
Constructs a Measured instance for the element type, given a monoid and a measuring function. |
|
static
|
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 |
---|
public abstract <B> B foldRight(F<A,F<B,B>> f, B z)
f
- A function with which to fold the tree.z
- An initial element to apply to the fold.
public abstract A reduceRight(F<A,F<A,A>> f)
f
- A function with which to fold the tree.
public abstract <B> B foldLeft(F<B,F<A,B>> f, B z)
f
- A function with which to fold the tree.z
- An initial element to apply to the fold.
public abstract A reduceLeft(F<A,F<A,A>> f)
f
- A function with which to fold the tree.
public abstract <B> FingerTree<V,B> map(F<A,B> f, Measured<V,B> m)
f
- A function to map across the values of this tree.m
- A measuring with which to annotate the tree.
public abstract V measure()
public boolean isEmpty()
protected Measured<V,A> measured()
public abstract <B> B match(F<Empty<V,A>,B> empty, F<Single<V,A>,B> single, F<Deep<V,A>,B> deep)
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.
public static <V,A> Measured<V,A> measured(Monoid<V> monoid, F<A,V> measure)
monoid
- A monoid for the measures.measure
- A function with which to measure element values.
public static <V,A> MakeTree<V,A> mkTree(Measured<V,A> m)
m
- A Measured instance with which to annotate trees, digits, and nodes.
public abstract FingerTree<V,A> cons(A a)
a
- The element to add to the front of this tree.
public abstract FingerTree<V,A> snoc(A a)
a
- The element to add to the end of this tree.
public abstract FingerTree<V,A> append(FingerTree<V,A> t)
t
- A finger tree to append to this one.
public abstract P2<Integer,A> lookup(F<V,Integer> o, int i)
|
Copyright 2008 - 2009 Tony Morris, Runar Bjarnason, Tom Adams, Brad Clow, Ricky Clarkson, Nick Partridge, Jason Zaugg This software is released under an open source BSD licence. |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |