# Module Bag

    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.

It is an error to modify a bag (`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 filter_inplace : 'a t -> f:('a -> bool) -> unit

`filter_inplace t ~f` removes all the elements from `t` that don't satisfy `f`.

    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 elts : 'a t -> 'a Elt.t list

    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.
`filter_inplace t ~f` removes all the elements from `t` that don't satisfy `f`.
`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.