#hp55.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@@@@@@@/j0j@@.B@@#add@!a@C@@%Queuei!t@@@1j@@@@@@@@PmQm:@@OC@@$push@!a@C@@%Queuek!t@@@Rl@@@@@@@@qprp@@pD@@$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@@@@U @@@@@@C  C  @@I@@#top@%Queuer!t!a@C@@@@@@@H  H  @@J@@$drop@%Queues!t!a@C@@@@t@@@@@@8K  9K  @@7K@@%clear@%Queueu!t!a@C@@@@8v@@@@@@WP R RXP R j@@VL@@$copy@%Queuew!t!a@C@@@@%Queuex!t@@@@@@zS  {S  @@yM@@(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 @@ Q@@(transfer$@%Queue!t!a@'C@@@@ @%Queue!t@@@"@@@#@@$@@%@4f5f:@@3R@@&to_seqd@%Queue!t!a@ RC@(@@@*&Stdlib#Seq!t@@@ O@@ P@Yn$$Zn$A@@XS@@'add_seqe@%Queue!t!a@ \C@ S@@@ U@&Stdlib#Seq!t@@@ Wf@@@ X@@ Y@@ Z@tt@@T@@&of_seqf@&Stdlib#Seq!t!a@ dC@ ]@@@ _%Queue!t@@@ a@@ b@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!.@@@@@@@@@@@@O@@A@@@@+Queue.Empty3,Raised when *Queue.takeD@$ or *Queue.peekD@> is applied to an empty queue.@@@@@@@@@@@@@@@@@@,Queue.create3 $Return a new queue, initially empty.@@@@@@@@@@@@@ @@@@)Queue.add3'add x q2 adds the element !x9 at the end of the queue !q!.@@@@@@@@@@@@@@"@@@@*Queue.push3$push2 is a synonym for #add!.@@@@@@@@@@@@@:@=@@@@정_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@@@@@@@@z@@@@)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@@@@@