Module BatFingerTree.Generic

include S with type ('wrapped_type, 'a, 'm) wrap = monoid:'m monoid -> measure:('a -> 'm) -> 'wrapped_type
type ('a, 'm) fg

The type of finger trees containing elements of type 'a measured by 'm.

type ('wrapped_type, 'a, 'm) wrap = monoid:'m monoid -> measure:('a -> 'm) -> '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.

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

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

  • raises 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.

  • raises 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.

  • raises 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.

  • raises 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.

  • raises 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.

  • raises Empty

    if t is empty.

    O(1) amortized, O(log(n)) worst case.

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

Conversions
Conversions to other structures
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 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).

Conversions from other structures
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).

Combining/reorganizing
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).

Boilerplate code
val print : ?first:string -> ?last:string -> ?sep:string -> ('a, 'b) BatIO.printer -> (('a, _) fg, 'b) BatIO.printer
val lookup : (('m -> bool) -> ('a, 'm) fg -> 'a, 'a, 'm) wrap

lookup p t, when p is monotonic, returns the first element of the sequence for which the measure of its predecessors in the sequence (itself included) satisfies p.

  • raises Empty

    is there is no such element.

    O(log(n)).

    When p is not monotonic, take a look at the code or at the paper cited above and see if you understand something (lookup is a specialized version of splitTree that returns the element without building the left and right tree).

val measure : (('a, 'm) fg -> 'm, 'a, 'm) wrap

measure m gives the measure of the whole tree, whose meaning depends on the measure chosen.

O(1).

val split : (('m -> bool) -> ('a, 'm) fg -> ('a, 'm) fg * ('a, 'm) fg, 'a, 'm) wrap

split p t, when p is monotonic, returns (t1, t2) where t1 is the longest prefix of t whose measure does not satisfies p, and t2 is the rest of t.

  • raises Empty

    is there is no such element

    O(log(n)).

    When p is not monotonic, take a look at the code or at the paper cited above and see if you understand something.