module BatFingerTree:sig..end
This module implements a generic finger tree datastructure as described here: Finger Trees: A Simple General-purpose Data Structure http://www.soi.city.ac.uk/~ross/papers/FingerTree.pdf
The finger tree itself is polymorphic over the measure and the measurement function (this is needed because sometimes the type of the measure depends on the type of the elements).
This module also contains an instantiation of a finger tree that implements a functional sequence with the following characteristics:
If you are trying to understand the signature at first, whenever you
see a type (something, _, _) wrap, just pretend it is simply
the type something (this is what the documentation does).
Complexities are given assuming that the monoid combination operation and the measurement functions are constant time and space.
None of the functions on finger trees can cause stack overflow: they use at worst a logarithmic amount of stack space.
type 'a monoid = {
|
zero : |
(* | The neutral element of the monoid. | *) |
|
combine : |
(* |
| *) |
}
The type of the element of a monoid.
exception Empty
An exception that is thrown by various operations when trying to get a non existing element.
module type S =sig..end
module Generic:sig..end
type 'a t
include BatFingerTree.S
val size : 'a t -> intsize t returns the number of elements in the sequence.
Unlike the generic size on finger trees, this one has complexity O(1).
val split_at : 'a t -> int -> 'a t * 'a tsplit_at is equivalent to List.split_at.
Invalid_argument when the index is out of bounds.
O(log(n)).val get : 'a t -> int -> 'aget t i returns the i-th element of t.
Invalid_argument when the index is out of bounds.
O(log(n)).val set : 'a t -> int -> 'a -> 'a tset t i v returns t where the i-th element is now v.
Invalid_argument when the index is out of bounds.
O(log(n)).val update : 'a t -> int -> ('a -> 'a) -> 'a tupdate t i f returns t where the i-th element is now f (get i t).
Invalid_argument when the index is out of bounds.
O(log(n)).