module type S =sig
..end
type ('a, 'm)
fg
The type of finger trees containing elements of type 'a
measured by 'm
.
type ('wrapped_type, 'a, 'm)
wrap
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
.
val empty : ('a, 'm) fg
empty
is the sequence with no elements.
val singleton : 'a -> ('a, 'm) fg
singleton elt
build the sequence containing elt
as its sole
element.
O(1).
val cons : (('a, 'm) fg -> 'a -> ('a, 'm) fg, 'a, 'm)
wrap
cons t elt
adds elt
to the left of t
.
O(1) amortized, O(log(n)) worst case.
val snoc : (('a, 'm) fg -> 'a -> ('a, 'm) fg, 'a, 'm)
wrap
snoc t elt
adds elt
to the right of t
.
O(1) amortized, O(log(n)) worst case.
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.
val front_exn : (('a, 'm) fg -> ('a, 'm) fg * 'a, 'a, 'm)
wrap
front_exn t
returns (tl, hd)
when hd
is the first element
of the sequence and tl
is the rest of the sequence.
Empty
if t
is empty.
O(1) amortized, O(log(n)) worst case.val head : ('a, 'm) fg -> 'a option
head t
returns None
if t
is empty,
or Some hd
otherwise, where hd
is the first element
of the sequence.
O(1).
val head_exn : ('a, 'm) fg -> 'a
head_exn t
returns the first element of the sequence.
Empty
if t
is empty.
O(1).val last : ('a, 'm) fg -> 'a option
last t
returns None
if t
is empty,
or Some hd
otherwise, where hd
is the last element
of the sequence.
O(1).
val last_exn : ('a, 'm) fg -> 'a
last_exn t
returns the last element of the sequence.
Empty
if t
is empty.
O(1).val tail : (('a, 'm) fg -> ('a, 'm) fg option, 'a, 'm)
wrap
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.
val tail_exn : (('a, 'm) fg -> ('a, 'm) fg, 'a, 'm)
wrap
tail_exn t
returns the sequence t
where the first element
has been removed.
Empty
if t
is empty.
O(1) amortized, O(log(n)) worst case.val init : (('a, 'm) fg -> ('a, 'm) fg option, 'a, 'm)
wrap
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.
val init_exn : (('a, 'm) fg -> ('a, 'm) fg, 'a, 'm)
wrap
init_exn t
returns the sequence t
where the last element
has been removed.
Empty
if t
is empty.
O(1) amortized, O(log(n)) worst case.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.
val rear_exn : (('a, 'm) fg -> ('a, 'm) fg * 'a, 'a, 'm)
wrap
rear_exn t
returns (init, last)
when last
is the last element of
the sequence and init
is the rest of the sequence.
Empty
if t
is empty.
O(1) amortized, O(log(n)) worst case.val size : ('a, 'm) fg -> int
size t
returns the number of elements in the sequence.
If you want to know that a sequence is empty, it is much
better to use BatFingerTree.S.is_empty
.
O(n).
val is_empty : ('a, 'm) fg -> bool
is_empty t
returns true
when the sequence has no elements.
O(1).
val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> ('a, 'm) fg -> 'acc
fold_left
is equivalent to List.fold_left
.
O(n).
val fold_right : ('acc -> 'a -> 'acc) -> 'acc -> ('a, 'm) fg -> 'acc
fold_right
is equivalent to List.fold_right
.
O(n).
val iter : ('a -> unit) -> ('a, 'm) fg -> unit
iter
is equivalent to List.iter
.
O(n).
val iter_right : ('a -> unit) -> ('a, 'm) fg -> unit
iter_right
is equivalent to List.iter o List.rev
.
O(n).
val compare : ('a -> 'a -> int) ->
('a, 'm) fg -> ('a, 'm) fg -> int
compare cmp t1 t2
compares the two sequences lexicographically.
O(n).
val equal : ('a -> 'a -> bool) ->
('a, 'm) fg -> ('a, 'm) fg -> bool
equal eq t1 t2
returns true
when the two sequences contain the
the same elements.
O(n).
val enum : ('a, 'm) fg -> 'a BatEnum.t
enum t
builds an enumeration of the elements of t
going from
left to right.
O(1).
Forcing the whole enumeration takes O(n).
val backwards : ('a, 'm) fg -> 'a BatEnum.t
backwards t
builds an enumeration of the elements of t
going from
right to left.
Same complexity as BatFingerTree.S.enum
.
val to_list : ('a, 'm) fg -> 'a list
to_list t
is equivalent to BatList.of_enum (enum t)
.
O(n).
val to_list_backwards : ('a, 'm) fg -> 'a list
to_list_backwards t
is equivalent to BatList.of_enum (backwards t)
.
O(n).
val of_enum : ('a BatEnum.t -> ('a, 'm) fg, 'a, 'm) wrap
of_enum e
build the sequence containing the elements of e
in the same order.
Its complexity is the complexity of forcing the enumeration.
val of_backwards : ('a BatEnum.t -> ('a, 'm) fg, 'a, 'm) wrap
of_backwards e
is equivalent to reverse (of_enum e)
.
O(n).
val of_list : ('a list -> ('a, 'm) fg, 'a, 'm) wrap
of_list l
is equivalent to of_enum (BatList.enum l)
.
O(n).
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).
val map : (('a -> 'b) -> ('a, 'm) fg -> ('b, 'm) fg,
'b, 'm)
wrap
map
is equivalent to List.map
.
O(n).
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).
val append : (('a, 'm) fg ->
('a, 'm) fg -> ('a, 'm) fg, 'a, 'm)
wrap
append
is equivalent to List.append
.
O(log(min(n,m))).
val reverse : (('a, 'm) fg -> ('a, 'm) fg, 'a, 'm)
wrap
reverse t
is equivalent to of_list (List.rev (to_list t))
.
O(n).
val print : ?first:string ->
?last:string ->
?sep:string ->
('a, 'b) BatIO.printer -> (('a, 'c) fg, 'b) BatIO.printer