Module BatFingerTree Source 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:
amortized constant time addition and deletions at both ends constant time size operation logarithmic lookup, update or deletion of the element at a given index logarithmic splitting and concatenation 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.
Source 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.
An exception that is thrown by various operations when trying to get a non existing element.
include S
with type ('wrapped_type, 'a, 'm) wrap = 'wrapped_type and type ('a, 'm) fg = 'a t The type of finger trees containing elements of type 'a measured by 'm.
Source type ('wrapped_type, 'a, 'm) wrap = 'wrapped_type A type meant to avoid duplication of signatures.
For the generic finger tree, this type will be monoid:'m monoid -> measure:('a -> 'm) -> 'wrapped_type.
Once the finger tree has been specialized, the resulting module should be reexported in such a way that the type is now simply 'wrapped_type.
empty is the sequence with no elements.
singleton elt build the sequence containing elt as its sole element.
O(1).
cons t elt adds elt to the left of t.
O(1) amortized, O(log(n)) worst case.
snoc t elt adds elt to the right of t.
O(1) amortized, O(log(n)) worst case.
Source val front : (('a , 'm ) fg -> (('a , 'm ) fg 'a ) option'a , 'm ) wrap front t returns None when t is empty, or Some (tl, hd) when hd is the first element of the sequence and tl is the rest of the sequence.
O(1) amortized, O(log(n)) worst case.
front_exn t returns (tl, hd) when hd is the first element of the sequence and tl is the rest of the sequence.
O(1) amortized, O(log(n)) worst case.
Source val head : ('a , 'm ) fg -> 'a optionhead t returns None if t is empty, or Some hd otherwise, where hd is the first element of the sequence.
O(1).
head_exn t returns the first element of the sequence.
O(1).
Source val last : ('a , 'm ) fg -> 'a optionlast t returns None if t is empty, or Some hd otherwise, where hd is the last element of the sequence.
O(1).
last_exn t returns the last element of the sequence.
O(1).
tail t returns None when t is empty, or Some tl where tl is the sequence t where the first element has been removed.
O(1) amortized, O(log(n)) worst case.
tail_exn t returns the sequence t where the first element has been removed.
O(1) amortized, O(log(n)) worst case.
init t returns None if t is empty, or Some init where init is the sequence t where the last element has been removed.
O(1) amortized, O(log(n)) worst case.
init_exn t returns the sequence t where the last element has been removed.
O(1) amortized, O(log(n)) worst case.
Source val rear : (('a , 'm ) fg -> (('a , 'm ) fg 'a ) option'a , 'm ) wrap rear t returns None when t is empty, or Some (init, last) where last is the last element of the sequence and init is the rest of the sequence.
O(1) amortized, O(log(n)) worst case.
rear_exn t returns (init, last) when last is the last element of the sequence and init is the rest of the sequence.
O(1) amortized, O(log(n)) worst case.
Source val is_empty : ('a , 'm ) fg -> is_empty t returns true when the sequence has no elements.
O(1).
Source val fold_left : ('acc -> 'a -> 'acc ) -> 'acc -> ('a , 'm ) fg -> 'acc fold_left is equivalent to List.fold_left.
O(n).
Source val fold_right : ('acc -> 'a -> 'acc ) -> 'acc -> ('a , 'm ) fg -> 'acc fold_right is equivalent to List.fold_right.
O(n).
Source val iter : ('a -> -> ('a , 'm ) fg -> iter is equivalent to List.iter.
O(n).
Source val iter_right : ('a -> -> ('a , 'm ) fg -> iter_right is equivalent to List.iter o List.rev.
O(n).
Source val compare : ('a -> 'a -> -> ('a , 'm ) fg -> ('a , 'm ) fg -> compare cmp t1 t2 compares the two sequences lexicographically.
O(n).
Source val equal : ('a -> 'a -> -> ('a , 'm ) fg -> ('a , 'm ) fg -> equal eq t1 t2 returns true when the two sequences contain the the same elements.
O(n).
enum t builds an enumeration of the elements of t going from left to right.
O(1).
Forcing the whole enumeration takes O(n).
backwards t builds an enumeration of the elements of t going from right to left. Same complexity as enum
Source val to_list : ('a , 'm ) fg -> 'a listto_list t is equivalent to BatList.of_enum (enum t).
O(n).
Source val to_list_backwards : ('a , 'm ) fg -> 'a listto_list_backwards t is equivalent to BatList.of_enum (backwards t).
O(n).
of_enum e build the sequence containing the elements of e in the same order.
Its complexity is the complexity of forcing the enumeration.
of_backwards e is equivalent to reverse (of_enum e).
O(n).
of_list l is equivalent to of_enum (BatList.enum l).
O(n).
Source val of_list_backwards : ('a list-> ('a , 'm ) fg 'a , 'm ) wrap of_list_backwards l is equivalent to of_enum_backwards (BatList.enum l).
O(n).
Source val map : (('a -> 'b ) -> ('a , 'm ) fg -> ('b , 'm ) fg 'b , 'm ) wrap Source val map_right : (('a -> 'b ) -> ('a , 'm ) fg -> ('b , 'm ) fg 'b , 'm ) wrap map_right is equivalent to List.rev o List.map o List.rev.
O(n).
append is equivalent to List.append.
O(log(min(n,m))).
reverse t is equivalent to of_list (List.rev (to_list t)).
O(n).
size t returns the number of elements in the sequence.
Unlike the generic size on finger trees, this one has complexity O(1).
Source val split_at : 'a t -> int -> 'a t 'a t split_at is equivalent to List.split_at.
O(log(n)).
get t i returns the i-th element of t.
O(log(n)).
Source val set : 'a t -> int -> 'a -> 'a t set t i v returns t where the i-th element is now v.
O(log(n)).
Source 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).
O(log(n)).