%`55.5.0+dev0-2025-04-28/%Queue!tA;!a@|@A@A@O@B@@@6../../stdlib/queue.mlib,,b,6@@@@%Queue@@A@±%EmptyB##exnG@@@Afuufu@@A@B@&create@$unitg@@@@@%Queueh!t!a@C@@@@@@@1j2j@@0B@@#add@!a@C@@@@%Queuei!t@@@@@5j@@@@@@@@VmWm:@@UC@@$push@!a@C@@@@%Queuek!t@@@@@Zl@@@@@@@@{p|p@@zD@@$take@%Queuem!t!a@C@@@@@@@@@ss@@E@@(take_opt@%Queuen!t!a@C@@@@@@&optionL @@@@@@wLLwLl@@F@@#pop@%Queueo!t!a@C@@@@@@@@@|| @@G@@$peek@%Queuep!t!a@C@@@@@@@@@ - - - B@@H@@(peek_opt@%Queueq!t!a@C@@@@@@[ @@@@@@C  C  @@I@@#top@%Queuer!t!a@C@@@@@@@@@/H  0H  @@.J@@$drop@%Queues!t!a@C@@@@@@/t@@@@@@PK  QK  @@OK@@%clear@%Queueu!t!a@C@@@@@@Pv@@@@@@qP R RrP R j@@pL@@$copy@%Queuew!t!a@C@@@@@@%Queuex!t@@@@@@S  S  @@M@@(is_empty @%Queuey!t!a@C@@@@@@$boolz@@@@@@V  V  @@N@@&length!@%Queue{!t!a@C@@@@@@#int|@@@@@@Y : :Y : R@@O@@$iter"@@!a@C@@@}@@@@@@@@%Queue~!t@@@@@@@@@@@@@\   \  @@P@@$fold#@@#acc@C@@@@!a@C@@@@@@@@@ @@@ @%Queue!t@@@@@!@@ @@ @@ @:a O O;a O @@9Q@@(transfer$@%Queue!t!a@C@@@@@@@%Queue!t@@@@@G@@@@@@@@hfif:@@gR@@&to_seqd@%Queue!t!a@ C@@@@ @@ &Stdlib#Seq!t@@@ @@ @n$$n$A@@S@@'add_seqe@%Queue!t!a@ C@ @@@ @@ @&Stdlib#Seq!t@@@ @@ @@@ @@ @@ @tt@@T@@&of_seqf@&Stdlib#Seq!t!a@ C@ @@@ @@ %Queue!t@@@ @@ @xVVxVs@@U@@@3:First-in first-out queues.@ N This module implements queues (FIFOs), with in-place modification. See .Queue.examples(Examples@4 the example section@' below.@@@@@@@@@@@5unsynchronized_access :Unsynchronized accesses to queues are a programming error.@A6../../stdlib/queue.mli7Unsynchronized accesses@@ Unsynchronized accesses to a queue may lead to an invalid queue state. Thus, concurrent accesses to queues must be synchronized (for instance with a 'Mutex.t@@").@#'Queue.t3 /The type of queues containing elements of type "'a!.@@@@@@@@@@@@5O@@A@@0.@@+Queue.Empty3,Raised when *Queue.takeD@$ or *Queue.peekD@> is applied to an empty queue.@@@@@@@@@@@@@@@@=<@@,Queue.create3 $Return a new queue, initially empty.@@@@@@@@@@@@?@ A@@@@,)Queue.add3'add x q2 adds the element !x9 at the end of the queue !q!.@@@@@@@@@@@@<@=@"6@@@@(*Queue.push3$push2 is a synonym for #add!.@@@@@@@@@@@@2@:3@=,@@@@_3&take q 0 removes and returns the first element in queue !q/, or raises yG@7 if the queue is empty.@@@@@@@@@@@@-@Z.@@@@.Queue.take_opt3*take_opt q 0 removes and returns the first element in queue !q0, or returns $None7 if the queue is empty.@@@@$4.08@@@@@@@1@z2@@@@)Queue.pop3#pop2 is a synonym for $take!.@@@@@@@@@@@@&@'@@@@3&peek q $ returns the first element in queue !q 3, without removing it from the queue, or raises ΐG@7 if the queue is empty.@@@@@@@@@@@@'@(@@@@.Queue.peek_opt3*peek_opt q $ returns the first element in queue !q 4, without removing it from the queue, or returns $None7 if the queue is empty.@@@@$4.08@@@@@@@+@,@@@@)Queue.top3#top2 is a synonym for $peek!.@@@@@@@@@@@@"@#@@@@*Queue.drop3&drop q $ removes the first element in queue !q,, or raises $G@: if the queue is empty.@@@@#5.3@@@@@@@&@'@@@@+Queue.clear3 "Discard all elements from a queue.@@@@@@@@@@@@@@@@@*Queue.copy3 !Return a copy of the given queue.@@@@@@@@@@@@@%@@@@렕.Queue.is_empty3'Return $true> if the given queue is empty, %false+ otherwise.@@@@@@@@@@@@@@@@@@䠕,Queue.length3 )Return the number of elements in a queue.@@@@@@@@@@@@@O@@@@Ѡ*Queue.iter3(iter f q) applies !f< in turn to all elements of !q d, from the least recently entered to the most recently entered. The queue itself is unchanged.@@@@@@@@@@@@@m@p@@@@Ġ*Queue.fold3-fold f accu q2 is equivalent to 7List.fold_left f accu l+, where !l0 is the list of !q ,'s elements. The queue remains unchanged.@@@@@@@@@@@@@@@@@@@.Queue.transfer3.transfer q1 q2- adds all of "q1 ''s elements at the end of the queue "q2., then clears "q1 &. It is equivalent to the sequence %iter (fun x -> add x q2) q1; clear q1?, but runs in constant time.@@@@@@@@@@@@@@@@@@A@)Iterators@@,Queue.to_seq3 Iterate on the queue, in front-to-back order. The behavior is not specified if the queue is modified during the iteration.@@@@$4.07@@@@@@@@@@@@-Queue.add_seq3 9Add the elements from a sequence to the end of the queue.@@@@$4.07@@@@@@@@@@@@@,Queue.of_seq3?Create a queue from a sequence.@@@@$4.07@@@@@@@@@@@@zA(examplesm@@# B@-Basic Example@@9 A basic example: W # let q = Queue.create () val q : '_weak1 Queue.t = # Queue.push 1 q; Queue.push 2 q; Queue.push 3 q - : unit = () # Queue.length q - : int = 3 # Queue.pop q - : int = 1 # Queue.pop q - : int = 2 # Queue.pop q - : int = 3 # Queue.pop q Exception: Stdlib.Queue.Empty. @# B@6Search Through a Graph@@ For a more elaborate example, a classic algorithmic use of queues is to implement a BFS (breadth-first search) through a graph.@$ T type graph = { edges: (int, int list) Hashtbl.t } (* Search in graph [g] using BFS, starting from node [start]. It returns the first node that satisfies [p], or [None] if no node reachable from [start] satisfies [p]. *) let search_for ~(g:graph) ~(start:int) (p:int -> bool) : int option = let to_explore = Queue.create() in let explored = Hashtbl.create 16 in Queue.push start to_explore; let rec loop () = if Queue.is_empty to_explore then None else (* node to explore *) let node = Queue.pop to_explore in explore_node node and explore_node node = if not (Hashtbl.mem explored node) then ( if p node then Some node (* found *) else ( Hashtbl.add explored node (); let children = Hashtbl.find_opt g.edges node |> Option.value ~default:[] in List.iter (fun child -> Queue.push child to_explore) children; loop() ) ) else loop() in loop() (* a sample graph *) let my_graph: graph = let edges = List.to_seq [ 1, [2;3]; 2, [10; 11]; 3, [4;5]; 5, [100]; 11, [0; 20]; ] |> Hashtbl.of_seq in {edges} # search_for ~g:my_graph ~start:1 (fun x -> x = 30) - : int option = None # search_for ~g:my_graph ~start:1 (fun x -> x >= 15) - : int option = Some 20 # search_for ~g:my_graph ~start:1 (fun x -> x >= 50) - : int option = Some 100 @@@@@A#Seq@@@@@