module Bag:`sig`

..`end`

Imperative set-like data structure.

Primary differences from a simple set:

- It doesn't require anything (hashable, comparable) of elements in the bag.
- Duplicates are allowed.
- Addition and removal are constant time.

`add`

, `remove`

, `remove_one`

, ...) during iteration
(`fold`

, `iter`

, ...).module Elt:`sig`

..`end`

`type ``'a`

t

`include Container.S1`

`val invariant : ``'a t -> unit`

`val create : ``unit -> 'a t`

`create ()`

returns an empty bag.`val add : ``'a t -> 'a -> 'a Elt.t`

`add t v`

adds `v`

to the bag `t`

, returning an element that can
later be removed from the bag. `add`

runs in constant time.`val remove : ``'a t -> 'a Elt.t -> unit`

`remove t elt`

removes `elt`

from the bag `t`

, raising an exception if `elt`

is not in the bag. `remove`

runs in constant time.`val choose : ``'a t -> 'a Elt.t option`

`choose t`

returns some element in the bag.`val remove_one : ``'a t -> 'a option`

`remove_one t`

removes some element from the bag, and returns its value.
`remove_one`

runs in constant time.`val clear : ``'a t -> unit`

`clear t`

removes all elements from the bag. `clear`

runs in O(1) time.`val fold_elt : ``'a t -> init:'b -> f:('b -> 'a Elt.t -> 'b) -> 'b`

`fold_elt t ~init ~f`

is the same as fold, except `f`

is called with the
`'a Elt.t`

's from the bag instead of the contained `'a`

values.
Note that like other iteration functions, it is an error to mutate `t`

inside the
fold. If you'd like to call `remove`

on any of the `'a Elt.t`

's, accumulate them here
and do so after `fold_elt`

returns.

`val iter_elt : ``'a t -> f:('a Elt.t -> unit) -> unit`

`val find_elt : ``'a t -> f:('a -> bool) -> 'a Elt.t option`

`find_elt t ~f`

looks at elements in the bag one-by-one until it finds one
`elt`

such that `f (Elt.value elt)`

, in which case it returns `Some elt`

.
If there is no element satisfying `f`

, then `find_elt`

returns `None`

.`val until_empty : ``'a t -> ('a -> unit) -> unit`

`until_empty t f`

repeatedly removes a value `v`

from `t`

and runs `f v`

,
continuing until `t`

is empty. Running `f`

may add elements to `t`

if it
wants.`val transfer : ``src:'a t -> dst:'a t -> unit`

`transfer ~src ~dst`

moves all of the elements from `src`

to `dst`

in constant
time.`val of_list : ``'a list -> 'a t`

`val unchecked_iter : ``'a t -> f:('a -> unit) -> unit`

`unchecked_iter t ~f`

behaves like `iter t ~f`

except that `f`

is allowed to modify
`t`

. Elements added by `f`

may or may not be visited, elements removed by `f`

that
have not been visited will not be visited. It is an (undetected) error to delete the
current element.`val t_of_sexp : ``(Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t`

`val sexp_of_t : ``('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t`

`create ()`

returns an empty bag.`add t v`

adds `v`

to the bag `t`

, returning an element that can
later be removed from the bag. `add`

runs in constant time.`remove t elt`

removes `elt`

from the bag `t`

, raising an exception if `elt`

is not in the bag. `remove`

runs in constant time.`choose t`

returns some element in the bag.`remove_one t`

removes some element from the bag, and returns its value.
`remove_one`

runs in constant time.`clear t`

removes all elements from the bag. `clear`

runs in O(1) time.`fold_elt t ~init ~f`

is the same as fold, except `f`

is called with the
`'a Elt.t`

's from the bag instead of the contained `'a`

values.
Note that like other iteration functions, it is an error to mutate `t`

inside the
fold. If you'd like to call `remove`

on any of the `'a Elt.t`

's, accumulate them here
and do so after `fold_elt`

returns.

`find_elt t ~f`

looks at elements in the bag one-by-one until it finds one
`elt`

such that `f (Elt.value elt)`

, in which case it returns `Some elt`

.
If there is no element satisfying `f`

, then `find_elt`

returns `None`

.

`until_empty t f`

repeatedly removes a value `v`

from `t`

and runs `f v`

,
continuing until `t`

is empty. Running `f`

may add elements to `t`

if it
wants.

`transfer ~src ~dst`

moves all of the elements from `src`

to `dst`

in constant
time.

`unchecked_iter t ~f`

behaves like `iter t ~f`

except that `f`

is allowed to modify
`t`

. Elements added by `f`

may or may not be visited, elements removed by `f`

that
have not been visited will not be visited. It is an (undetected) error to delete the
current element.