Package fj.data.fingertrees
package fj.data.fingertrees
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.
Based on "Finger trees: a simple general-purpose data structure", by Ralf Hinze and Ross Paterson.
- Version:
- %build.number%
-
ClassesClassDescriptionDeep<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.Digit<V,A> A digit is a vector of 1-4 elements.Empty<V,A> The empty tree.FingerTree<V,A> Provides 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized O(1) time.Four<V,A> A four-element prefix or suffix of a finger tree.MakeTree<V,A> A builder of trees and tree components, supplied with a particular monoid and measuring function.Measured<V,A> Determines how the elements of a tree are measured and how measures are summed.Node<V,A> An inner node of the 2-3 tree.Node2<V,A> A two-element inner tree node.Node3<V,A> A three-element inner tree node.One<V,A> A single-element prefix or suffix of a finger tree.Single<V,A> A tree with a single element.Three<V,A> A three-element prefix or suffix of a finger tree.Two<V,A> A two-element prefix or suffix of a finger tree.