Package fj.data.fingertrees
Class Deep<V,A>
- java.lang.Object
-
- fj.data.fingertrees.FingerTree<V,A>
-
- fj.data.fingertrees.Deep<V,A>
-
public final class Deep<V,A> extends FingerTree<V,A>
A finger tree with 1-4-digits on the left and right, and a finger tree of 2-3-nodes in the middle.
-
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private static <V,A>
FingerTree<V,Node<V,A>>addDigits0(Measured<V,A> m, FingerTree<V,Node<V,A>> m1, Digit<V,A> s1, Digit<V,A> p2, FingerTree<V,Node<V,A>> m2)
private static <V,A>
FingerTree<V,Node<V,Node<V,A>>>addDigits1(Measured<V,Node<V,A>> m, FingerTree<V,Node<V,Node<V,A>>> m1, Digit<V,Node<V,A>> x, Node<V,A> n, Digit<V,Node<V,A>> y, FingerTree<V,Node<V,Node<V,A>>> m2)
private static <V,A>
FingerTree<V,Node<V,Node<V,A>>>addDigits2(Measured<V,Node<V,A>> m, FingerTree<V,Node<V,Node<V,A>>> m1, Digit<V,Node<V,A>> suffix, Node<V,A> n1, Node<V,A> n2, Digit<V,Node<V,A>> prefix, FingerTree<V,Node<V,Node<V,A>>> m2)
private static <V,A>
FingerTree<V,Node<V,Node<V,A>>>addDigits3(Measured<V,Node<V,A>> m, FingerTree<V,Node<V,Node<V,A>>> m1, Digit<V,Node<V,A>> suffix, Node<V,A> n1, Node<V,A> n2, Node<V,A> n3, Digit<V,Node<V,A>> prefix, FingerTree<V,Node<V,Node<V,A>>> m2)
private static <V,A>
FingerTree<V,Node<V,Node<V,A>>>addDigits4(Measured<V,Node<V,A>> m, FingerTree<V,Node<V,Node<V,A>>> m1, Digit<V,Node<V,A>> suffix, Node<V,A> n1, Node<V,A> n2, Node<V,A> n3, Node<V,A> n4, Digit<V,Node<V,A>> prefix, FingerTree<V,Node<V,Node<V,A>>> m2)
FingerTree<V,A>
append(FingerTree<V,A> t)
Appends one finger tree to another.private static <V,A>
FingerTree<V,Node<V,A>>append1(Measured<V,A> m, FingerTree<V,Node<V,A>> xs, Node<V,A> a, FingerTree<V,Node<V,A>> ys)
private static <V,A>
FingerTree<V,Node<V,A>>append2(Measured<V,A> m, FingerTree<V,Node<V,A>> t1, Node<V,A> n1, Node<V,A> n2, FingerTree<V,Node<V,A>> t2)
private static <V,A>
FingerTree<V,Node<V,A>>append3(Measured<V,A> m, FingerTree<V,Node<V,A>> t1, Node<V,A> n1, Node<V,A> n2, Node<V,A> n3, FingerTree<V,Node<V,A>> t2)
private static <V,A>
FingerTree<V,Node<V,A>>append4(Measured<V,A> m, FingerTree<V,Node<V,A>> t1, Node<V,A> n1, Node<V,A> n2, Node<V,A> n3, Node<V,A> n4, FingerTree<V,Node<V,A>> t2)
FingerTree<V,A>
cons(A a)
Adds the given element to this tree as the first element.private static <V,A>
FingerTree<V,A>deepL(Measured<V,A> measured, Option<Digit<V,A>> lOpt, FingerTree<V,Node<V,A>> m, Digit<V,A> r)
private static <V,A>
FingerTree<V,A>deepR(Measured<V,A> measured, Option<Digit<V,A>> rOpt, FingerTree<V,Node<V,A>> m, Digit<V,A> l)
<B> B
foldLeft(F<B,F<A,B>> bff, B z)
Folds the tree to the left with the given function and the given initial element.<B> B
foldRight(F<A,F<B,B>> aff, B z)
Folds the tree to the right with the given function and the given initial element.A
head()
The first element of this tree.FingerTree<V,A>
init()
The tree without the last element.A
last()
The last element of this tree.int
length()
P2<java.lang.Integer,A>
lookup(F<V,java.lang.Integer> o, int i)
<B> FingerTree<V,B>
map(F<A,B> abf, Measured<V,B> m)
Maps the given function across this tree, measuring with the given Measured instance.<B> B
match(F<Empty<V,A>,B> empty, F<Single<V,A>,B> single, F<Deep<V,A>,B> deep)
Pattern matching on the tree.V
measure()
Returns the sum of the measurements of this tree's elements, according to the monoid.FingerTree<V,Node<V,A>>
middle()
Returns a finger tree of the inner nodes of this tree.Digit<V,A>
prefix()
Returns the first few elements of this tree.A
reduceLeft(F<A,F<A,A>> aff)
Folds the tree to the left with the given function.A
reduceRight(F<A,F<A,A>> aff)
Folds the tree to the right with the given function.FingerTree<V,A>
snoc(A a)
Adds the given element to this tree as the last element.(package private) P3<FingerTree<V,A>,A,FingerTree<V,A>>
split1(F<V,java.lang.Boolean> predicate, V acc)
Digit<V,A>
suffix()
Returns the last few elements of this tree.FingerTree<V,A>
tail()
The tree without the first element.Stream<A>
toStream()
java.lang.String
toString()
-
Methods inherited from class fj.data.fingertrees.FingerTree
empty, emptyIntAddition, emptyIntMax, filter, foldLeft, foldRight, headOption, isEmpty, measured, measured, mkTree, split, split1, uncons
-
-
-
-
Method Detail
-
prefix
public Digit<V,A> prefix()
Returns the first few elements of this tree.- Returns:
- the first few elements of this tree.
-
middle
public FingerTree<V,Node<V,A>> middle()
Returns a finger tree of the inner nodes of this tree.- Returns:
- a finger tree of the inner nodes of this tree.
-
suffix
public Digit<V,A> suffix()
Returns the last few elements of this tree.- Returns:
- the last few elements of this tree.
-
foldRight
public <B> B foldRight(F<A,F<B,B>> aff, B z)
Description copied from class:FingerTree
Folds the tree to the right with the given function and the given initial element.- Specified by:
foldRight
in classFingerTree<V,A>
- Parameters:
aff
- 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 A reduceRight(F<A,F<A,A>> aff)
Description copied from class:FingerTree
Folds the tree to the right with the given function.- Specified by:
reduceRight
in classFingerTree<V,A>
- Parameters:
aff
- 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 <B> B foldLeft(F<B,F<A,B>> bff, B z)
Description copied from class:FingerTree
Folds the tree to the left with the given function and the given initial element.- Specified by:
foldLeft
in classFingerTree<V,A>
- Parameters:
bff
- 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 A reduceLeft(F<A,F<A,A>> aff)
Description copied from class:FingerTree
Folds the tree to the left with the given function.- Specified by:
reduceLeft
in classFingerTree<V,A>
- Parameters:
aff
- 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 <B> FingerTree<V,B> map(F<A,B> abf, Measured<V,B> m)
Description copied from class:FingerTree
Maps the given function across this tree, measuring with the given Measured instance.- Specified by:
map
in classFingerTree<V,A>
- Parameters:
abf
- 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 V measure()
Returns the sum of the measurements of this tree's elements, according to the monoid.- Specified by:
measure
in classFingerTree<V,A>
- Returns:
- the sum of the measurements of this tree's elements, according to the monoid.
-
match
public <B> B match(F<Empty<V,A>,B> empty, F<Single<V,A>,B> single, F<Deep<V,A>,B> deep)
Pattern matching on the tree. Matches the function on the Deep tree.- Specified by:
match
in classFingerTree<V,A>
- 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.
-
cons
public FingerTree<V,A> cons(A a)
Description copied from class:FingerTree
Adds the given element to this tree as the first element.- Specified by:
cons
in classFingerTree<V,A>
- 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 FingerTree<V,A> snoc(A a)
Description copied from class:FingerTree
Adds the given element to this tree as the last element.- Specified by:
snoc
in classFingerTree<V,A>
- 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 A head()
Description copied from class:FingerTree
The first element of this tree. This is an O(1) operation.- Specified by:
head
in classFingerTree<V,A>
- Returns:
- The first element if this tree is nonempty, otherwise throws an error.
-
last
public A last()
Description copied from class:FingerTree
The last element of this tree. This is an O(1) operation.- Specified by:
last
in classFingerTree<V,A>
- Returns:
- The last element if this tree is nonempty, otherwise throws an error.
-
deepL
private static <V,A> FingerTree<V,A> deepL(Measured<V,A> measured, Option<Digit<V,A>> lOpt, FingerTree<V,Node<V,A>> m, Digit<V,A> r)
-
deepR
private static <V,A> FingerTree<V,A> deepR(Measured<V,A> measured, Option<Digit<V,A>> rOpt, FingerTree<V,Node<V,A>> m, Digit<V,A> l)
-
tail
public FingerTree<V,A> tail()
Description copied from class:FingerTree
The tree without the first element. This is an O(1) operation.- Specified by:
tail
in classFingerTree<V,A>
- Returns:
- The tree without the first element if this tree is nonempty, otherwise throws an error.
-
init
public FingerTree<V,A> init()
Description copied from class:FingerTree
The tree without the last element. This is an O(1) operation.- Specified by:
init
in classFingerTree<V,A>
- Returns:
- The tree without the last element if this tree is nonempty, otherwise throws an error.
-
append
public FingerTree<V,A> append(FingerTree<V,A> t)
Description copied from class:FingerTree
Appends one finger tree to another.- Specified by:
append
in classFingerTree<V,A>
- 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.
-
split1
P3<FingerTree<V,A>,A,FingerTree<V,A>> split1(F<V,java.lang.Boolean> predicate, V acc)
- Specified by:
split1
in classFingerTree<V,A>
-
lookup
public P2<java.lang.Integer,A> lookup(F<V,java.lang.Integer> o, int i)
- Specified by:
lookup
in classFingerTree<V,A>
-
length
public int length()
- Specified by:
length
in classFingerTree<V,A>
-
addDigits0
private static <V,A> FingerTree<V,Node<V,A>> addDigits0(Measured<V,A> m, FingerTree<V,Node<V,A>> m1, Digit<V,A> s1, Digit<V,A> p2, FingerTree<V,Node<V,A>> m2)
-
append1
private static <V,A> FingerTree<V,Node<V,A>> append1(Measured<V,A> m, FingerTree<V,Node<V,A>> xs, Node<V,A> a, FingerTree<V,Node<V,A>> ys)
-
addDigits1
private static <V,A> FingerTree<V,Node<V,Node<V,A>>> addDigits1(Measured<V,Node<V,A>> m, FingerTree<V,Node<V,Node<V,A>>> m1, Digit<V,Node<V,A>> x, Node<V,A> n, Digit<V,Node<V,A>> y, FingerTree<V,Node<V,Node<V,A>>> m2)
-
append2
private static <V,A> FingerTree<V,Node<V,A>> append2(Measured<V,A> m, FingerTree<V,Node<V,A>> t1, Node<V,A> n1, Node<V,A> n2, FingerTree<V,Node<V,A>> t2)
-
addDigits2
private static <V,A> FingerTree<V,Node<V,Node<V,A>>> addDigits2(Measured<V,Node<V,A>> m, FingerTree<V,Node<V,Node<V,A>>> m1, Digit<V,Node<V,A>> suffix, Node<V,A> n1, Node<V,A> n2, Digit<V,Node<V,A>> prefix, FingerTree<V,Node<V,Node<V,A>>> m2)
-
append3
private static <V,A> FingerTree<V,Node<V,A>> append3(Measured<V,A> m, FingerTree<V,Node<V,A>> t1, Node<V,A> n1, Node<V,A> n2, Node<V,A> n3, FingerTree<V,Node<V,A>> t2)
-
addDigits3
private static <V,A> FingerTree<V,Node<V,Node<V,A>>> addDigits3(Measured<V,Node<V,A>> m, FingerTree<V,Node<V,Node<V,A>>> m1, Digit<V,Node<V,A>> suffix, Node<V,A> n1, Node<V,A> n2, Node<V,A> n3, Digit<V,Node<V,A>> prefix, FingerTree<V,Node<V,Node<V,A>>> m2)
-
append4
private static <V,A> FingerTree<V,Node<V,A>> append4(Measured<V,A> m, FingerTree<V,Node<V,A>> t1, Node<V,A> n1, Node<V,A> n2, Node<V,A> n3, Node<V,A> n4, FingerTree<V,Node<V,A>> t2)
-
addDigits4
private static <V,A> FingerTree<V,Node<V,Node<V,A>>> addDigits4(Measured<V,Node<V,A>> m, FingerTree<V,Node<V,Node<V,A>>> m1, Digit<V,Node<V,A>> suffix, Node<V,A> n1, Node<V,A> n2, Node<V,A> n3, Node<V,A> n4, Digit<V,Node<V,A>> prefix, FingerTree<V,Node<V,Node<V,A>>> m2)
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-