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

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.