module Bunch:Collection of elements with fast union.`sig`

..`end`

A multi-set like collection of elements with a fast union operation that shares the unioned collections, and a filter operation that retains sharing.

`type ``'a`

t

Collection of elements.

`val size : ``'a t -> int`

`val empty : ``'a t`

`val is_empty : ``'a t -> bool`

Is a bunch empty?

`val singleton : ``'a -> 'a t`

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

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

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

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

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

Hosted by the