Package fj.data.fingertrees
Class Deep<V,A>
java.lang.Object
fj.data.fingertrees.FingerTree<V,A>
fj.data.fingertrees.Deep<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.
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate 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> Adds the given element to this tree as the first element.private static <V,
A> FingerTree <V, A> private static <V,
A> FingerTree <V, A> <B> B
Folds the tree to the left with the given function and the given initial element.<B> B
Folds the tree to the right with the given function and the given initial element.head()
The first element of this tree.FingerTree
<V, A> init()
The tree without the last element.last()
The last element of this tree.int
length()
<B> FingerTree
<V, B> Maps the given function across this tree, measuring with the given Measured instance.<B> B
Pattern matching on the tree.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.prefix()
Returns the first few elements of this tree.Folds the tree to the left with the given function.Folds the tree to the right with the given function.FingerTree
<V, A> Adds the given element to this tree as the last element.(package private) P3
<FingerTree<V, A>, A, FingerTree<V, A>> suffix()
Returns the last few elements of this tree.FingerTree
<V, A> tail()
The tree without the first element.toStream()
toString()
Methods inherited from class fj.data.fingertrees.FingerTree
empty, emptyIntAddition, emptyIntMax, filter, foldLeft, foldRight, headOption, isEmpty, measured, measured, mkTree, split, split1, uncons
-
Field Details
-
v
-
prefix
-
middle
-
suffix
-
-
Constructor Details
-
Deep
-
-
Method Details
-
prefix
Returns the first few elements of this tree.- Returns:
- the first few elements of this tree.
-
middle
Returns a finger tree of the inner nodes of this tree.- Returns:
- a finger tree of the inner nodes of this tree.
-
suffix
Returns the last few elements of this tree.- Returns:
- the last few elements of this tree.
-
foldRight
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
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
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
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
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
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
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
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
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
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
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
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
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
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
- Specified by:
split1
in classFingerTree<V,
A>
-
lookup
- 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, addDigits0A>> (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, append1A>> (Measured<V, A> m, FingerTree<V, Node<V, A>> xs, Node<V, A> a, FingerTree<V, Node<V, A>> ys) -
addDigits1
-
append2
private static <V,A> FingerTree<V,Node<V, append2A>> (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
-
append3
private static <V,A> FingerTree<V,Node<V, append3A>> (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
-
append4
private static <V,A> FingerTree<V,Node<V, append4A>> (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
-
toString
-
toStream
- Specified by:
toStream
in classFingerTree<V,
A>
-