Module type Hash_queue.S_backend
include Core_kernel__.Hash_queue_intf.S1 with type 'key create_arg := 'key Hashtbl.Hashable.t with type 'key create_key := 'key
type 'key create_arg
type 'key create_key
type ('key, 'data) t
A hash-queue, where the values are of type
'data
.
val sexp_of_t : ('key -> Ppx_sexp_conv_lib.Sexp.t) -> ('data -> Ppx_sexp_conv_lib.Sexp.t) -> ('key, 'data) t -> Ppx_sexp_conv_lib.Sexp.t
include Container.S1_phantom_invariant with type ('data, 'key) t := ('key, 'data) t
val mem : ('a, _) t -> 'a -> equal:('a -> 'a -> bool) -> bool
Checks whether the provided element is there, using
equal
.
val length : (_, _) t -> int
val is_empty : (_, _) t -> bool
val iter : ('a, _) t -> f:('a -> unit) -> unit
val fold : ('a, _) t -> init:'accum -> f:('accum -> 'a -> 'accum) -> 'accum
fold t ~init ~f
returnsf (... f (f (f init e1) e2) e3 ...) en
, wheree1..en
are the elements oft
.
val fold_result : ('a, _) t -> init:'accum -> f:('accum -> 'a -> ('accum, 'e) Base.Result.t) -> ('accum, 'e) Base.Result.t
fold_result t ~init ~f
is a short-circuiting version offold
that runs in theResult
monad. Iff
returns anError _
, that value is returned without any additional invocations off
.
val fold_until : ('a, _) t -> init:'accum -> f:('accum -> 'a -> ('accum, 'final) Base__.Container_intf.Continue_or_stop.t) -> finish:('accum -> 'final) -> 'final
fold_until t ~init ~f ~finish
is a short-circuiting version offold
. Iff
returnsStop _
the computation ceases and results in that value. Iff
returnsContinue _
, the fold will proceed. Iff
never returnsStop _
, the final result is computed byfinish
.Example:
type maybe_negative = | Found_negative of int | All_nonnegative of { sum : int } (** [first_neg_or_sum list] returns the first negative number in [list], if any, otherwise returns the sum of the list. *) let first_neg_or_sum = List.fold_until ~init:0 ~f:(fun sum x -> if x < 0 then Stop (Found_negative x) else Continue (sum + x)) ~finish:(fun sum -> All_nonnegative { sum }) ;; let x = first_neg_or_sum [1; 2; 3; 4; 5] val x : maybe_negative = All_nonnegative {sum = 15} let y = first_neg_or_sum [1; 2; -3; 4; 5] val y : maybe_negative = Found_negative -3
val exists : ('a, _) t -> f:('a -> bool) -> bool
Returns
true
if and only if there exists an element for which the provided function evaluates totrue
. This is a short-circuiting operation.
val for_all : ('a, _) t -> f:('a -> bool) -> bool
Returns
true
if and only if the provided function evaluates totrue
for all elements. This is a short-circuiting operation.
val count : ('a, _) t -> f:('a -> bool) -> int
Returns the number of elements for which the provided function evaluates to true.
val sum : (module Base__.Container_intf.Summable with type t = 'sum) -> ('a, _) t -> f:('a -> 'sum) -> 'sum
Returns the sum of
f i
for alli
in the container.
val find : ('a, _) t -> f:('a -> bool) -> 'a option
Returns as an
option
the first element for whichf
evaluates to true.
val find_map : ('a, _) t -> f:('a -> 'b option) -> 'b option
Returns the first evaluation of
f
that returnsSome
, and returnsNone
if there is no such element.
val to_list : ('a, _) t -> 'a list
val to_array : ('a, _) t -> 'a array
val min_elt : ('a, _) t -> compare:('a -> 'a -> int) -> 'a option
Returns a min (resp max) element from the collection using the provided
compare
function. In case of a tie, the first element encountered while traversing the collection is returned. The implementation usesfold
so it has the same complexity asfold
. ReturnsNone
iff the collection is empty.
val max_elt : ('a, _) t -> compare:('a -> 'a -> int) -> 'a option
val invariant : ('key, 'data) t -> Core_kernel__.Import.unit
val create : ?growth_allowed:Core_kernel__.Import.bool -> ?size:Core_kernel__.Import.int -> 'key create_arg -> ('key create_key, 'data) t
create ()
returns an empty queue. The argumentsgrowth_allowed
andsize
are referring to the underlying hashtable.- parameter growth_allowed
defaults to true
- parameter size
initial size -- default to 16
val clear : ('key, 'data) t -> Core_kernel__.Import.unit
Clears the queue.
Finding elements
val mem : ('key, 'data) t -> 'key -> Core_kernel__.Import.bool
mem q k
returns true iff there is some (k, v) in the queue.
val lookup : ('key, 'data) t -> 'key -> 'data Core_kernel__.Import.option
lookup t k
returns the value of the key-value pair in the queue with key k, if there is one.
val lookup_exn : ('key, 'data) t -> 'key -> 'data
Adding, removing, and replacing elements
Note that even the non-*_exn
versions can raise, but only if there is an ongoing iteration.
val enqueue : ('key, 'data) t -> [ `back | `front ] -> 'key -> 'data -> [ `Ok | `Key_already_present ]
enqueue t back_or_front k v
adds the key-value pair (k, v) to the front or back of the queue, returning`Ok
if the pair was added, or`Key_already_present
if there is already a (k, v') in the queue.
val enqueue_exn : ('key, 'data) t -> [ `back | `front ] -> 'key -> 'data -> Core_kernel__.Import.unit
Like
enqueue
, but it raises in the`Key_already_present
case
val enqueue_back : ('key, 'data) t -> 'key -> 'data -> [ `Ok | `Key_already_present ]
See
enqueue
.enqueue_back t k v
is the same asenqueue t `back k v
val enqueue_back_exn : ('key, 'data) t -> 'key -> 'data -> Core_kernel__.Import.unit
See
enqueue_exn
.enqueue_back_exn t k v
is the same asenqueue_exn t `back k v
val enqueue_front : ('key, 'data) t -> 'key -> 'data -> [ `Ok | `Key_already_present ]
See
enqueue
.enqueue_front t k v
is the same asenqueue t `front k v
val enqueue_front_exn : ('key, 'data) t -> 'key -> 'data -> Core_kernel__.Import.unit
See
enqueue_exn
.enqueue_front_exn t k v
is the same asenqueue_exn t `front k v
val lookup_and_move_to_back : ('key, 'data) t -> 'key -> 'data Core_kernel__.Import.option
lookup_and_move_to_back
finds the key-value pair (k, v) and moves it to the back of the queue if it exists, otherwise returningNone
.The
_exn
versions of these functions raise if key-value pair does not exist.
val lookup_and_move_to_back_exn : ('key, 'data) t -> 'key -> 'data
Like
lookup_and_move_to_back
, but raises instead of returning an option
val lookup_and_move_to_front : ('key, 'data) t -> 'key -> 'data Core_kernel__.Import.option
Like
lookup_and_move_to_back
, but moves element to the front of the queue
val lookup_and_move_to_front_exn : ('key, 'data) t -> 'key -> 'data
Like
lookup_and_move_to_front
, but raises instead of returning an option
val first : ('key, 'data) t -> 'data Core_kernel__.Import.option
first t
returns the front element of the queue, without removing it.
val first_with_key : ('key, 'data) t -> ('key * 'data) Core_kernel__.Import.option
first_with_key t
returns the front element of the queue and its key, without removing it.
val keys : ('key, 'data) t -> 'key Core_kernel__.Import.list
keys t
returns the keys in the order of the queue.
val dequeue : ('key, 'data) t -> [ `back | `front ] -> 'data Core_kernel__.Import.option
dequeue t front_or_back
returns the front or back element of the queue.
val dequeue_exn : ('key, 'data) t -> [ `back | `front ] -> 'data
Like
dequeue
, but it raises if the queue is empty.
val dequeue_back : ('key, 'data) t -> 'data Core_kernel__.Import.option
dequeue_back t
returns the back element of the queue.
val dequeue_back_exn : ('key, 'data) t -> 'data
Like
dequeue_back
, but it raises if the queue is empty.
val dequeue_front : ('key, 'data) t -> 'data Core_kernel__.Import.option
dequeue_front t
returns the front element of the queue.
val dequeue_front_exn : ('key, 'data) t -> 'data
Like
dequeue_front
, but it raises if the queue is empty.
val dequeue_with_key : ('key, 'data) t -> [ `back | `front ] -> ('key * 'data) Core_kernel__.Import.option
dequeue_with_key t
returns the front or back element of the queue and its key.
val dequeue_with_key_exn : ('key, 'data) t -> [ `back | `front ] -> 'key * 'data
Like
dequeue_with_key
, but it raises if the queue is empty.
val dequeue_back_with_key : ('key, 'data) t -> ('key * 'data) Core_kernel__.Import.option
dequeue_back_with_key t
returns the back element of the queue and its key.
val dequeue_back_with_key_exn : ('key, 'data) t -> 'key * 'data
Like
dequeue_back_with_key
, but it raises if the queue is empty.
val dequeue_front_with_key : ('key, 'data) t -> ('key * 'data) Core_kernel__.Import.option
dequeue_front_with_key t
returns the front element of the queue and its key.
val dequeue_front_with_key_exn : ('key, 'data) t -> 'key * 'data
Like
dequeue_front_with_key
, but it raises if the queue is empty.
val dequeue_all : ('key, 'data) t -> f:('data -> Core_kernel__.Import.unit) -> Core_kernel__.Import.unit
dequeue_all t ~f
dequeues every element of the queue and appliesf
to each one. The dequeue order is from front to back.
val remove : ('key, 'data) t -> 'key -> [ `Ok | `No_such_key ]
remove q k
removes the key-value pair with keyk
from the queue.
val remove_exn : ('key, 'data) t -> 'key -> Core_kernel__.Import.unit
val replace : ('key, 'data) t -> 'key -> 'data -> [ `Ok | `No_such_key ]
replace q k v
changes the value of keyk
in the queue tov
.
val replace_exn : ('key, 'data) t -> 'key -> 'data -> Core_kernel__.Import.unit
val drop : ?n:Core_kernel__.Import.int -> ('key, 'data) t -> [ `back | `front ] -> Core_kernel__.Import.unit
drop ?n q back_or_front
dropsn
elements (default 1) from the back or front of the queue. If the queue has fewer thann
elements then it is cleared.
val drop_front : ?n:Core_kernel__.Import.int -> ('key, 'data) t -> Core_kernel__.Import.unit
Equivalent to
drop ?n q `front
.
val drop_back : ?n:Core_kernel__.Import.int -> ('key, 'data) t -> Core_kernel__.Import.unit
Equivalent to
drop ?n q `back
.
Iterating over elements
val iteri : ('key, 'data) t -> f:(key:'key -> data:'data -> Core_kernel__.Import.unit) -> Core_kernel__.Import.unit
iter t ~f
appliesf
to each key and element of the queue.
val foldi : ('key, 'data) t -> init:'b -> f:('b -> key:'key -> data:'data -> 'b) -> 'b
module type S = Core_kernel__.Hash_queue_intf.S0 with type ('key, 'data) hash_queue := ('key, 'data) t