Package org.reactfx.util
Class FingerTree<T,S>
- java.lang.Object
-
- org.reactfx.util.FingerTree<T,S>
-
- Direct Known Subclasses:
FingerTree.Empty
,FingerTree.NonEmptyFingerTree
public abstract class FingerTree<T,S> extends java.lang.Object
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
FingerTree.Branch<T,S>
private static class
FingerTree.Empty<T,S>
private static class
FingerTree.Leaf<T,S>
static class
FingerTree.NonEmptyFingerTree<T,S>
-
Field Summary
Fields Modifier and Type Field Description (package private) ToSemigroup<? super T,S>
semigroup
-
Constructor Summary
Constructors Modifier Constructor Description private
FingerTree(ToSemigroup<? super T,S> semigroup)
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description FingerTree.NonEmptyFingerTree<T,S>
append(T data)
abstract java.util.List<T>
asList()
Returns a list view of this tree.private static <T,S>
FingerTree.Branch<T,S>branch(FingerTree.NonEmptyFingerTree<T,S> left, FingerTree.NonEmptyFingerTree<T,S> right)
private static <T,S>
FingerTree.Branch<T,S>branch(FingerTree.NonEmptyFingerTree<T,S> left, FingerTree.NonEmptyFingerTree<T,S> middle, FingerTree.NonEmptyFingerTree<T,S> right)
private static <T,S>
FingerTree.Branch<T,S>branch(LL.Cons<FingerTree.NonEmptyFingerTree<T,S>> children)
abstract Either<FingerTree<T,S>,FingerTree.NonEmptyFingerTree<T,S>>
caseEmpty()
private static <T,S>
FingerTree<T,S>concat(LL.Cons<? extends FingerTree<T,S>> nodes)
(package private) FingerTree.Empty<T,S>
empty()
static <T,S>
FingerTree<T,S>empty(ToSemigroup<? super T,S> statisticsProvider)
abstract <R> R
fold(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction)
<R> R
foldBetween(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction, int startLeaf, int endLeaf)
<R> R
foldBetween(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction, java.util.function.ToIntFunction<? super S> metric, int startPosition, int endPosition, TetraFunction<? super R,? super T,java.lang.Integer,java.lang.Integer,? extends R> rangeReduction)
(package private) abstract <R> R
foldBetween0(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction, int startLeaf, int endLeaf)
(package private) abstract <R> R
foldBetween0(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction, java.util.function.ToIntFunction<? super S> metric, int startPosition, int endPosition, TetraFunction<? super R,? super T,java.lang.Integer,java.lang.Integer,? extends R> rangeReduction)
Tuple2<T,BiIndex>
get(java.util.function.ToIntFunction<? super S> metric, int index)
<E> E
get(java.util.function.ToIntFunction<? super S> metric, int index, java.util.function.BiFunction<? super T,java.lang.Integer,? extends E> leafAccessor)
(package private) abstract T
getData()
abstract int
getDepth()
T
getLeaf(int index)
(package private) abstract T
getLeaf0(int index)
abstract int
getLeafCount()
S
getSummary(S whenEmpty)
java.util.Optional<S>
getSummaryBetween(int startLeaf, int endLeaf)
java.util.Optional<S>
getSummaryBetween(java.util.function.ToIntFunction<? super S> metric, int startPosition, int endPosition, TriFunction<? super T,java.lang.Integer,java.lang.Integer,? extends S> subSummary)
(package private) abstract S
getSummaryBetween0(int startLeaf, int endLeaf)
(package private) abstract S
getSummaryBetween0(java.util.function.ToIntFunction<? super S> metric, int startPosition, int endPosition, TriFunction<? super T,java.lang.Integer,java.lang.Integer,? extends S> subSummary)
abstract java.util.Optional<S>
getSummaryOpt()
FingerTree<T,S>
insertLeaf(int position, T data)
boolean
isEmpty()
abstract FingerTree<T,S>
join(FingerTree<T,S> rightTree)
(package private) FingerTree.Leaf<T,S>
leaf(T data)
BiIndex
locate(java.util.function.BiFunction<? super S,java.lang.Integer,Either<java.lang.Integer,java.lang.Integer>> navigate, int position)
BiIndex
locateProgressively(java.util.function.ToIntFunction<? super S> metric, int position)
BiIndex
locateRegressively(java.util.function.ToIntFunction<? super S> metric, int position)
(package private) int
measure(java.util.function.ToIntFunction<? super S> metric)
static <T> FingerTree<T,java.lang.Void>
mkTree(java.util.List<? extends T> items)
static <T,S>
FingerTree<T,S>mkTree(java.util.List<? extends T> items, ToSemigroup<? super T,S> summaryProvider)
FingerTree.NonEmptyFingerTree<T,S>
prepend(T data)
FingerTree<T,S>
removeLeafs(int fromLeaf, int toLeaf)
Tuple2<FingerTree<T,S>,FingerTree<T,S>>
split(int beforeLeaf)
(package private) abstract Tuple2<FingerTree<T,S>,FingerTree<T,S>>
split0(int beforeLeaf)
FingerTree.NonEmptyFingerTree<T,S>
updateLeaf(int index, T data)
(package private) abstract FingerTree.NonEmptyFingerTree<T,S>
updateLeaf0(int index, T data)
-
-
-
Field Detail
-
semigroup
final ToSemigroup<? super T,S> semigroup
-
-
Constructor Detail
-
FingerTree
private FingerTree(ToSemigroup<? super T,S> semigroup)
-
-
Method Detail
-
empty
public static <T,S> FingerTree<T,S> empty(ToSemigroup<? super T,S> statisticsProvider)
-
mkTree
public static <T> FingerTree<T,java.lang.Void> mkTree(java.util.List<? extends T> items)
-
mkTree
public static <T,S> FingerTree<T,S> mkTree(java.util.List<? extends T> items, ToSemigroup<? super T,S> summaryProvider)
-
branch
private static <T,S> FingerTree.Branch<T,S> branch(FingerTree.NonEmptyFingerTree<T,S> left, FingerTree.NonEmptyFingerTree<T,S> right)
-
branch
private static <T,S> FingerTree.Branch<T,S> branch(FingerTree.NonEmptyFingerTree<T,S> left, FingerTree.NonEmptyFingerTree<T,S> middle, FingerTree.NonEmptyFingerTree<T,S> right)
-
branch
private static <T,S> FingerTree.Branch<T,S> branch(LL.Cons<FingerTree.NonEmptyFingerTree<T,S>> children)
-
concat
private static <T,S> FingerTree<T,S> concat(LL.Cons<? extends FingerTree<T,S>> nodes)
-
getDepth
public abstract int getDepth()
-
getLeafCount
public abstract int getLeafCount()
-
getSummaryOpt
public abstract java.util.Optional<S> getSummaryOpt()
-
caseEmpty
public abstract Either<FingerTree<T,S>,FingerTree.NonEmptyFingerTree<T,S>> caseEmpty()
-
isEmpty
public final boolean isEmpty()
-
getLeaf
public T getLeaf(int index)
-
getLeaf0
abstract T getLeaf0(int index)
-
get
public <E> E get(java.util.function.ToIntFunction<? super S> metric, int index, java.util.function.BiFunction<? super T,java.lang.Integer,? extends E> leafAccessor)
-
updateLeaf
public FingerTree.NonEmptyFingerTree<T,S> updateLeaf(int index, T data)
-
updateLeaf0
abstract FingerTree.NonEmptyFingerTree<T,S> updateLeaf0(int index, T data)
-
locate
public BiIndex locate(java.util.function.BiFunction<? super S,java.lang.Integer,Either<java.lang.Integer,java.lang.Integer>> navigate, int position)
-
locateProgressively
public BiIndex locateProgressively(java.util.function.ToIntFunction<? super S> metric, int position)
-
locateRegressively
public BiIndex locateRegressively(java.util.function.ToIntFunction<? super S> metric, int position)
-
fold
public abstract <R> R fold(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction)
-
foldBetween
public <R> R foldBetween(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction, int startLeaf, int endLeaf)
-
foldBetween0
abstract <R> R foldBetween0(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction, int startLeaf, int endLeaf)
-
foldBetween
public <R> R foldBetween(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction, java.util.function.ToIntFunction<? super S> metric, int startPosition, int endPosition, TetraFunction<? super R,? super T,java.lang.Integer,java.lang.Integer,? extends R> rangeReduction)
-
foldBetween0
abstract <R> R foldBetween0(R acc, java.util.function.BiFunction<? super R,? super T,? extends R> reduction, java.util.function.ToIntFunction<? super S> metric, int startPosition, int endPosition, TetraFunction<? super R,? super T,java.lang.Integer,java.lang.Integer,? extends R> rangeReduction)
-
getSummaryBetween
public java.util.Optional<S> getSummaryBetween(int startLeaf, int endLeaf)
-
getSummaryBetween0
abstract S getSummaryBetween0(int startLeaf, int endLeaf)
-
getSummaryBetween
public java.util.Optional<S> getSummaryBetween(java.util.function.ToIntFunction<? super S> metric, int startPosition, int endPosition, TriFunction<? super T,java.lang.Integer,java.lang.Integer,? extends S> subSummary)
-
getSummaryBetween0
abstract S getSummaryBetween0(java.util.function.ToIntFunction<? super S> metric, int startPosition, int endPosition, TriFunction<? super T,java.lang.Integer,java.lang.Integer,? extends S> subSummary)
-
split
public Tuple2<FingerTree<T,S>,FingerTree<T,S>> split(int beforeLeaf)
-
split0
abstract Tuple2<FingerTree<T,S>,FingerTree<T,S>> split0(int beforeLeaf)
-
removeLeafs
public FingerTree<T,S> removeLeafs(int fromLeaf, int toLeaf)
-
insertLeaf
public FingerTree<T,S> insertLeaf(int position, T data)
-
join
public abstract FingerTree<T,S> join(FingerTree<T,S> rightTree)
-
append
public FingerTree.NonEmptyFingerTree<T,S> append(T data)
-
prepend
public FingerTree.NonEmptyFingerTree<T,S> prepend(T data)
-
asList
public abstract java.util.List<T> asList()
Returns a list view of this tree. Complexity of operations on the returned list:size()
: O(1);get
: O(log(n));- iteration: O(n) in either direction, with O(log(n)) total allocations;
subList
: O(log(n));- iterative
subList
, i.e. callingsubList
on the result of previoussubList
, up to n times: O(n).
-
getData
abstract T getData()
-
empty
FingerTree.Empty<T,S> empty()
-
leaf
FingerTree.Leaf<T,S> leaf(T data)
-
measure
final int measure(java.util.function.ToIntFunction<? super S> metric)
-
-