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 Object

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static final class	FingerTree.Branch<T,S>
private static final 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) final ToSemigroup<? super T, S>	semigroup

Constructor Summary

Constructors

Modifier	Constructor	Description
private	FingerTree(ToSemigroup<? super T, S> semigroup)

Method Summary

Modifier and Type	Method	Description
FingerTree.NonEmptyFingerTree<T,S>	append(T data)
abstract 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, BiFunction<? super R, ? super T, ? extends R> reduction)
<R> R	foldBetween(R acc, BiFunction<? super R, ? super T, ? extends R> reduction, int startLeaf, int endLeaf)
<R> R	foldBetween(R acc, BiFunction<? super R, ? super T, ? extends R> reduction, ToIntFunction<? super S> metric, int startPosition, int endPosition, TetraFunction<? super R, ? super T, Integer, Integer, ? extends R> rangeReduction)
(package private) abstract <R> R	foldBetween0(R acc, BiFunction<? super R, ? super T, ? extends R> reduction, int startLeaf, int endLeaf)
(package private) abstract <R> R	foldBetween0(R acc, BiFunction<? super R, ? super T, ? extends R> reduction, ToIntFunction<? super S> metric, int startPosition, int endPosition, TetraFunction<? super R, ? super T, Integer, Integer, ? extends R> rangeReduction)
Tuple2<T,BiIndex>	get(ToIntFunction<? super S> metric, int index)
<E> E	get(ToIntFunction<? super S> metric, int index, BiFunction<? super T, 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)
Optional<S>	getSummaryBetween(int startLeaf, int endLeaf)
Optional<S>	getSummaryBetween(ToIntFunction<? super S> metric, int startPosition, int endPosition, TriFunction<? super T, Integer, Integer, ? extends S> subSummary)
(package private) abstract S	getSummaryBetween0(int startLeaf, int endLeaf)
(package private) abstract S	getSummaryBetween0(ToIntFunction<? super S> metric, int startPosition, int endPosition, TriFunction<? super T, Integer, Integer, ? extends S> subSummary)
abstract Optional<S>	getSummaryOpt()
FingerTree<T,S>	insertLeaf(int position, T data)
final boolean	isEmpty()
abstract FingerTree<T,S>	join(FingerTree<T,S> rightTree)
(package private) FingerTree.Leaf<T,S>	leaf(T data)
BiIndex	locate(BiFunction<? super S, Integer, Either<Integer,Integer>> navigate, int position)
BiIndex	locateProgressively(ToIntFunction<? super S> metric, int position)
BiIndex	locateRegressively(ToIntFunction<? super S> metric, int position)
(package private) final int	measure(ToIntFunction<? super S> metric)
static <T> FingerTree<T,Void>	mkTree(List<? extends T> items)
static <T,S> FingerTree<T,S>	mkTree(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)

Methods inherited from class Object

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

Field Details

semigroup

final ToSemigroup<? super T, S> semigroup

Constructor Details

FingerTree

private FingerTree(ToSemigroup<? super T, S> semigroup)

Method Details

empty

public static <T,S> FingerTree<T,S> empty(ToSemigroup<? super T, S> statisticsProvider)

mkTree

public static <T> FingerTree<T,Void> mkTree(List<? extends T> items)

mkTree

public static <T,S> FingerTree<T,S> mkTree(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 Optional<S> getSummaryOpt()

caseEmpty

public abstract Either<FingerTree<T,S>, FingerTree.NonEmptyFingerTree<T,S>> caseEmpty()

isEmpty

public final boolean isEmpty()

getSummary

public S getSummary(S whenEmpty)

getLeaf

public T getLeaf(int index)

getLeaf0

abstract T getLeaf0(int index)

get

public Tuple2<T,BiIndex> get(ToIntFunction<? super S> metric,
 int index)

get

public <E> E get(ToIntFunction<? super S> metric,
 int index,
 BiFunction<? super T, 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(BiFunction<? super S, Integer, Either<Integer,Integer>> navigate,
 int position)

locateProgressively

public BiIndex locateProgressively(ToIntFunction<? super S> metric,
 int position)

locateRegressively

public BiIndex locateRegressively(ToIntFunction<? super S> metric,
 int position)

fold

public abstract <R> R fold(R acc,
 BiFunction<? super R, ? super T, ? extends R> reduction)

foldBetween

public <R> R foldBetween(R acc,
 BiFunction<? super R, ? super T, ? extends R> reduction,
 int startLeaf,
 int endLeaf)

foldBetween0

abstract <R> R foldBetween0(R acc,
 BiFunction<? super R, ? super T, ? extends R> reduction,
 int startLeaf,
 int endLeaf)

foldBetween

public <R> R foldBetween(R acc,
 BiFunction<? super R, ? super T, ? extends R> reduction,
 ToIntFunction<? super S> metric,
 int startPosition,
 int endPosition,
 TetraFunction<? super R, ? super T, Integer, Integer, ? extends R> rangeReduction)

foldBetween0

abstract <R> R foldBetween0(R acc,
 BiFunction<? super R, ? super T, ? extends R> reduction,
 ToIntFunction<? super S> metric,
 int startPosition,
 int endPosition,
 TetraFunction<? super R, ? super T, Integer, Integer, ? extends R> rangeReduction)

getSummaryBetween

public Optional<S> getSummaryBetween(int startLeaf,
 int endLeaf)

getSummaryBetween0

abstract S getSummaryBetween0(int startLeaf,
 int endLeaf)

getSummaryBetween

public Optional<S> getSummaryBetween(ToIntFunction<? super S> metric,
 int startPosition,
 int endPosition,
 TriFunction<? super T, Integer, Integer, ? extends S> subSummary)

getSummaryBetween0

abstract S getSummaryBetween0(ToIntFunction<? super S> metric,
 int startPosition,
 int endPosition,
 TriFunction<? super T, Integer, 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 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. calling subList on the result of previous subList, 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(ToIntFunction<? super S> metric)