Module Bunch

module Bunch: sig .. end

type 'a t 

Collection of elements.

val size : 'a t -> int

Number of elements in a bunch.

• Takes constant time
• Ensure size Bunch.empty = 0

val empty : 'a t

An empty bunch.

• Ensure Bunch.size empty = 0

val is_empty : 'a t -> bool

Is a bunch empty?

val singleton : 'a -> 'a t

A singleton bunch.

• Ensure Bunch.size (singleton x) = 1

val couple : 'a -> 'a -> 'a t

A bunch with the two elements provided.

• Ensure Bunch.size (couple x y) = 2

val imbalance : 'a t -> int

The worst imbalance in the internal tree representation of a bunch. Optimally balanced representations have a an imbalance of 0. A completely unbalanced representation will have an imbalance within 1 of the size of the bunch.

• Takes time linear in the size of the bunch.
• Ensure imbalance b >= 0

val add : 'a -> 'a t -> 'a t

Add an element to a bunch.

• Takes constant time.
• Ensure Bunch.imbalance b <= Bunch.imbalance (add x b) <= Bunch.imbalance b + 1
• Ensure Bunch.size (add x b) = 1 + Bunch.size b

val add_balanced : 'a -> 'a t -> 'a t

Add an element to a bunch.

• Takes time logarithmic in the bunch size for balanced bunches.
• Takes time linear in the bunch size for imbalanced bunches.
• Ensure Bunch.imbalance (add_balanced x b) <= Bunch.imbalance <= Bunch.imbalance (add_balanced x b) + 1
• Ensure Bunch.size (add_balanced x b) = 1 + Bunch.size b

val join : 'a t -> 'a t -> 'a t

The constant time union of two bunches.

• Takes constant time.
• Ensure Bunch.imbalance (join b c) = max (max (abs (size b - size c), Bunch.imbalance b), Bunch.imbalance c)
• Ensure Bunch.size (join a b) = Bunch.size a + Bunch.size b

val iter : ('a -> unit) -> 'a t -> unit

iter f b evaluates f on all the elements of b.

• Takes time linear in the size of the b

val iter_const : ('a -> 'b -> unit) -> 'a -> 'b t -> unit

iter_const f c b is Bunch.iter (f c) b, only faster since applying closures is slow.

val filter : ('a -> bool) -> 'a t -> 'a t

filter p b is a bunch containing all elements of b that satisfy predicate b.

Not tail-recursive, but sharing preserving.

• Takes time linear in the size of the bunch.

• Causes allocation and collection in proportion to the number of nodes filtered and the shape of the internal tree representation. More balanced trees cause less allocation.

val filter_const : ('a -> 'b -> bool) -> 'a -> 'b t -> 'b t

filter_const p c b is Bunch.filter (p c) b, only faster since applying closures is slow.

val partition : ('a -> bool) -> 'a t -> 'a t * 'a t

partition p b is a pair of bunches (b1, b2) such that b1 contains all elements of b that satisfy predicate b, and b2 contains the rest.

Not tail-recursive, but sharing preserving.

• Takes time linear in the size of the bunch.

val partition_const : ('a -> 'b -> bool) -> 'a -> 'b t -> 'b t * 'b t

partition_const p c b is Bunch.partition (p c) b, only faster since applying closures is slow.

val fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

fold f a b folds f over every element of b using a as an initial value.

• Takes time linear in the size of the bunch.

val map : ('a -> 'b) -> 'a t -> 'b t

map f a maps every element of a using f.

• Not tail recursive.
• Takes time linear in the size of the bunch.

val exists : ('a -> bool) -> 'a t -> bool

exists p b is true if p x holds for any x in b.

• Takes time linear in the size of the bunch.

val for_all : ('a -> bool) -> 'a t -> bool

for_all p b is true if p x holds for every x in b.

• Takes time linear in the size of the bunch.

val of_list : 'a list -> 'a t

A bunch with all the elements in the list.

• Not tail recursive.
• Takes time linear in the size of the list.

val to_list : 'a t -> 'a list

A list of all elements in the bunch.

• Not tail recursive.
• Takes time linear in the size of the bunch.