module Bag: Bag
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.