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:

- amortized constant time addition and deletions at both ends
- contant time size operation
- logarithmic lookup, update or deletion of the element at a given index
- logarithmic splitting and concatenation

`(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 : ` |
`(*` | `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`

.`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`

.`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`

.`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)`

.`Invalid_argument`

when the index is out of bounds.
O(log(n)).