Module BatFingerTree

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 instanciation 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 : 'a; (*
The neutral element of the monoid.
*)
   combine : 'a -> 'a -> 'a; (*
combine should be associative, and have zero as neutral element.
*)
}
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 -> int
size 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 t
split_at is equivalent to List.split_at.
Raises Invalid_argument when the index is out of bounds.

O(log(n)).

val get : 'a t -> int -> 'a
get t i returns the i-th element of t.
Raises Invalid_argument when the index is out of bounds.

O(log(n)).

val set : 'a t -> int -> 'a -> 'a t
set t i v returns t where the i-th element is now v.
Raises Invalid_argument when the index is out of bounds.

O(log(n)).

val update : 'a t -> int -> ('a -> 'a) -> 'a t
update t i f returns t where the i-th element is now f (get i t).
Raises Invalid_argument when the index is out of bounds.

O(log(n)).