Caml1999I037 S-Stdlib__Queue!t;!a@@A@A@O@B@@@)queue.mlibb@@@@@@A@ %Empty##exnG@@@A&_none_@@A@ A@B@&create@$unitF@@@@@/!a@@@@@@@*j+j@@&Stdlib0t0VoS%{<F:8CamlinternalFormatBasics0|.e1R$|o@Y"@5unsynchronized_access :Unsynchronized accesses to queues are a programming error.@A@Caml1999T037_ k50 C-Stdlib__Queue*ocaml.text&_none_@@A First-in first-out queues. This module implements queues (FIFOs), with in-place modification. See {{!examples} the example section} below. )queue.mliP77T@@@@@@3@@@@@@#intA;@@#intA@@@@@;@A@$charB;@@$charA@@@@@A@A@&stringQ;@@&stringA@@@@@G@@@%bytesC;@@%bytesA@@@@@M@@@%floatD;@@%floatA@@@@@S@@@$boolE;@@%falsec@@]@$trued@@c@@@A@@@@@d@A@$unitF;@@"()e@@n@@@A@@@@@o@A@ #exnG;@@@A@@@@@s@@@#effH;@@O@A@A@@@@@@|@@@,continuationI;@@Q@@P@B,continuationA@nY@@@@@@@@@%arrayJ;@@R@A%arrayA@@@@@@@@@ $listK;@@S@A"[]f@@@"::g@@@T@@@ @@A@Y@@@@@@@@&optionL;@@V@A$Noneh@@@$Somei@@@@@A@Y@@@@@@@@)nativeintM;@@)nativeintA@@@@@@@@%int32N;@@%int32A@@@@@@@@%int64O;@@%int64A@@@@@@@@&lazy_tP;@@X@A&lazy_tA@Y@@@@@@@@ 5extension_constructorR;@@5extension_constructorA@@@@@@@@*floatarrayS;@@*floatarrayA@@@@@@@@&iarrayT;@@Y@A&iarrayA@Y@@@@@@@@ *atomic_locU;@@Z@A*atomic_locA@@@@@@ @@@ .Assert_failure`#@@@@@J@@@@@@@@[@@A!=ocaml.warn_on_literal_pattern%@&@0Division_by_zero]#@@@A+ . .@+End_of_file\#$@@@A366@'FailureY#,@'@@A<??@0Invalid_argumentX#5@0@@AE$H#H@-Match_failureV#>@@=@9@;@@a@@AV5Y4Y@)Not_foundZ#O@@@A^=a<a@-Out_of_memoryW#W@@@AfEiDi@.Stack_overflow^#_@@@AnMqLq@.Sys_blocked_io_#g@@@AvUyTy@)Sys_error[#o@j@@A^]@:Undefined_recursive_modulea#x@@w@s@u@@h@@Aon@:Continuation_already_takenb#@@@Awv@&Stdlib@A= {b Unsynchronized accesses} VV@@@@@@%alertXX@5unsynchronized_accessXX@@@@@ :Unsynchronized accesses to queues are a programming error.YYT@@YYU@@@@@@@@@@XZVW@ʰ@ 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}). \YY`  @@@@@@A+!tAbb@А!a@|3@;@@{@A@A@G@B@@@b@)ocaml.doc 6 The type of queues containing elements of type ['a].  c cU@@@@@@@@@$@@@Abb@@B@@;%@A@A@O@B@@@@@ @@A@'@@@@@@@':@%EmptyB,fXb-fXg@#.@@@A1fXX@5 J Raised when {!Queue.take} or {!Queue.peek} is applied to an empty queue. >ghh?gh@@@@@@@WA@@@@FS@@@@@@@3KJJKKKKK@Jl>@A $@&createYjZj@б@г$unitdjej@@ @@@3feefffff@C=@A@@г!tsjtj@А!a@C@jj@@@ @@@@@@$@@ @@!'@@@j@ & Return a new queue, initially empty. kk@@@@@@@B@@*@@@@@@@@#addmm@б@А!a@C@3@Uj4@Am m @@б@г㠐!tmm@А!amm@@@@@@ @@г$unitmm@@ @@@(@@@@@@@- @@@7@@ @@20@@@m@ = [add x q] adds the element [x] at the end of the queue [q]. nn`@@@@@@@C@@"@@@@@@@Q$pushpbfpbj@б@А!a@C@3@fw4@A%pbm&pbo@@б@гH!t0pbv1pbw@А!a7pbs8pbu@@@@@@ @@г預$unitEpb{Fpb@@ @@@(@@@@@@@- @@@7@@ @@20@@@Wpbb@[ [push] is a synonym for [add]. dqeq@@@@@@@}D@@"@kx@@@@@@Q$take{s|s@б@г!tss@А!a@C@3@p>@Ass@@@ @@@ @@А!a ss@@@@@@@@@@s @ k [take q] removes and returns the first element in queue [q], or raises {!Empty} if the queue is empty. tu-@@@@@@@E@@@ɐ@@@@@@3(take_optw/3w/;@б@г!tw/Aw/B@А!a@C@3@Rm>@Aw/>w/@@@@ @@@ @@гG&optionw/Iw/O@А!aw/Fw/H@@@"@@@ @@@@@ @@#!@@@w//@ } [take_opt q] removes and returns the first element in queue [q], or returns [None] if the queue is empty. @since 4.08 xPPz@@@@@@@.F@@%@)@@@@@@B#pop,|-|@б@гO!t7|8|@А!a@C@3?>>?????@a|>@AE|F|@@@ @@@ @@А!a P|Q|@@@@@@@@@@Y| @] [pop] is a synonym for [take]. f}g} @@@@@@@G@@@mz@@@@@@3$peek}  ~  @б@г!t    @А!a@C@3@Rm>@A    @@@ @@@ @@А!a   #  %@@@@@@@@@@   @ [peek q] returns the first element in queue [q], without removing it from the queue, or raises {!Empty} if the queue is empty. @ & &A l @@@@@@@H@@@ː@@@@@@3(peek_optC  C  @б@г!tC  C  @А!a@C@3@Rm>@AC  C  @@@ @@@ @@гI&optionC  C  @А!aC  C  @@@"@@@ @@@@@ @@#!@@@ C  @ [peek_opt q] returns the first element in queue [q], without removing it from the queue, or returns [None] if the queue is empty. @since 4.08 D  F Z k@@@@@@@0I@@%@+@@@@@@B#top.H m q/H m t@б@гQ!t9H m z:H m {@А!a@C@3A@@AAAAA@a|>@AGH m wHH m y@@@ @@@ @@А!a RH m SH m @@@@@@@@@@[H m m @_ [top] is a synonym for [peek]. hI  iI  @@@@@@@J@@@o|@@@@@@3$dropK  K  @б@г!tK  K  @А!a@C@3@Rm>@AK  K  @@@ @@@ @@гJ$unitK  K  @@ @@@@@@@@@@ @@@K   @ m [drop q] removes the first element in queue [q], or raises {!Empty} if the queue is empty. @since 5.3 L  N # 3@@@@@@@K@@@Ԑ@@@@@@:%clearP 5 9P 5 >@б@г!tP 5 DP 5 E@А!a@C@3@Yt>@AP 5 AP 5 C@@@ @@@ @@г$unitP 5 IP 5 M@@ @@@@@@@@@@ @@@ P 5 5 @ $ Discard all elements from a queue. Q N NQ N w@@@@@@@1L@@@,@@@@@@:$copy/S y }0S y @б@гR!t:S y ;S y @А!a@C@3BAABBBBB@Yt>@AHS y IS y @@@ @@@ @@гn!tVS y WS y @А!a]S y ^S y @@@"@@@ @@@@@ @@#!@@@kS y y@o # Return a copy of the given queue. xT  yT  @@@@@@@M@@%@@@@@@@B(is_empty V  V  @б@г!tV  V  @А!a@C@3@a|>@AV  V  @@@ @@@ @@гk$boolV  V  @@ @@@@@@@@@@ @@@V   @ǐ ? Return [true] if the given queue is empty, [false] otherwise. W  W  @@@@@@@N@@@䐠@@@@@@:&length!Y  !Y  '@б@г !tY  -Y  .@А!a@C@3@Yt>@AY  *Y  ,@@@ @@@ @@г᠐#intY  2Y  5@@ @@@@@@@@@@ @@@Y   @ + Return the number of elements in a queue. (Z 6 6)Z 6 f@@@@@@@AO@@@/<@@@@@@:$iter"?\ h l@\ h p@б@б@А!a@C@3JIIJJJJJ@Ql6@AP\ h tQ\ h v@@г$unitY\ h zZ\ h ~@@ @@@@@@@@@@ @@б@г!tm\ h n\ h @А!a+&t\ h u\ h @@@1@@@- @@г&$unit\ h \ h @@ @@@:@@@@@@@? @@@2@@ @@D\ h s@@@\ h h@ [iter f q] applies [f] in turn to all elements of [q], from the least recently entered to the most recently entered. The queue itself is unchanged. ]  _  0@@@@@@@P@@#@@@@@@@d$fold#a 2 6a 2 :@б@б@А#acc@C@3@{6@Aa 2 >a 2 B@@б@А!a@C@a 2 Fa 2 H@@А#acca 2 La 2 P@@@@@!@@ @@@&@@ @@! @@б@А#acc,'a 2 Ua 2 Y@@б@г!ta 2 `a 2 a@А!a/9a 2 ]a 2 _@@@5@@@@ @@А#accID a 2 e a 2 i@@@@@P@@ K@@@U@@  @@ P) @@@8@@  @@ Ua 2 =@@@ a 2 2@$ [fold f accu q] is equivalent to [List.fold_left f accu l], where [l] is the list of [q]'s elements. The queue remains unchanged. -b j j.d  @@@@@@@FQ@@$@4A@@@@@@u(transfer$Df  Ef @б@гg!tOf  Pf  @А!a@C@3WVVWWWWW@>@A]f  ^f  @@@ @@@ @@б@г!tmf nf @А!atf uf @@@$@@@  @@г&$unitf f @@ @@@-@@@@@@@2 @@@2@@ @@75@@@f  @ [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. gj@@@@@@@R@@"@@@@@@@V/ {1 Iterators} ll@@@@@@3@h1@A&to_seqdn n@б@г!tnn@А!a@ C@ nn@@@ @@@ '@@г^#Seq!tnn"@ n#n$@@А!a#> n n@@@)@@@ E@@@'@@  @@ J*@@@ n@ Iterate on the queue, in front-to-back order. The behavior is not specified if the queue is modified during the iteration. @since 4.07  o%% r@@@@@@@ 4S@@&@" /@@@@@@i'add_seqe 2t 3t@б@гU!t =t >t@А!a@ C@ 3 E D D E E E E E@>@A Kt Lt@@@ @@@  @@б@г#Seq!t _t `t@  ct dt@@А!a'" kt lt@@@-@@@ )@@г $unit yt zt@@ @@@ 6@@@@@ @@ ; @@@;@@  @@ @>@@@ t@ K Add the elements from a sequence to the end of the queue. @since 4.07  u v%7@@@@@@@ T@@"@ @@@@@@_&of_seqf x9= x9C@б@г(#Seq!t x9I x9L@  x9M x9N@@А!a@ C@ 3        @G@A x9F x9H@@@  @@@  @@г!t x9U x9V@А!a x9R x9T@@@"@@@  @@@@@  @@ #!@@@ x99@ 1 Create a queue from a sequence. @since 4.07  yWW z{@@@@@@@ U@@%@ @@@@@@B # "  {1:examples Examples} {2 Basic Example} A basic example: {[ # 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. ]} {2 Search 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. {[ 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 ]}  | 5:@@@@@@3        @Tx1@A@AA@B@@~;@@@i+@ @@m/@@@j4@@@`*@ @)@ @?@@]@@3 L K K L L L L L@.@A@ H************************************************************************ TA@@ UA@L@ H  ZBMM [BM@ H OCaml  `C aC@ H  fD gD3@ H Xavier Leroy, projet Cristal, INRIA Rocquencourt  lE44 mE4@ H  rF sF@ H Copyright 1996 Institut National de Recherche en Informatique et  xG yG@ H en Automatique.  ~H Hg@ H  Ihh Ih@ H All rights reserved. This file is distributed under the terms of  J J@ H the GNU Lesser General Public License version 2.1, with the  K KN@ H special exception on linking described in the file LICENSE.  LOO LO@ H  M M@ H************************************************************************ N N5@ * First-in first-out queues. This module implements queues (FIFOs), with in-place modification. See {{!examples} the example section} below.  >* {b Unsynchronized 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}). Ѡ 7* The type of queues containing elements of type ['a].  K* Raised when {!Queue.take} or {!Queue.peek} is applied to an empty queue. v '* Return a new queue, initially empty.  >* [add x q] adds the element [x] at the end of the queue [q].  !* [push] is a synonym for [add]. Y l* [take q] removes and returns the first element in queue [q], or raises {!Empty} if the queue is empty.  ~* [take_opt q] removes and returns the first element in queue [q], or returns [None] if the queue is empty. @since 4.08  !* [pop] is a synonym for [take]. ` * [peek q] returns the first element in queue [q], without removing it from the queue, or raises {!Empty} if the queue is empty.  * [peek_opt q] returns the first element in queue [q], without removing it from the queue, or returns [None] if the queue is empty. @since 4.08  !* [top] is a synonym for [peek]. g n* [drop q] removes the first element in queue [q], or raises {!Empty} if the queue is empty. @since 5.3  %* Discard all elements from a queue.  $* Return a copy of the given queue. ` @* Return [true] if the given queue is empty, [false] otherwise.  ,* Return the number of elements in a queue.  * [iter f q] applies [f] in turn to all elements of [q], from the least recently entered to the most recently entered. The queue itself is unchanged. ? * [fold f accu q] is equivalent to [List.fold_left f accu l], where [l] is the list of [q]'s elements. The queue remains unchanged.  * [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. F0* {1 Iterators} + * Iterate on the queue, in front-to-back order. The behavior is not specified if the queue is modified during the iteration. @since 4.07 Ҡ L* Add the elements from a sequence to the end of the queue. @since 4.07 X 2* Create a queue from a sequence. @since 4.07  * {1:examples Examples} {2 Basic Example} A basic example: {[ # 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. ]} {2 Search 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. {[ 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 ]} @?)../ocamlc0-strict-sequence(-absname"-w5+a-4-9-41-42-44-45-48"-g+-warn-error"+A*-bin-annot)-nostdlib*-principal"-o1stdlib__Queue.cmi"-c   Z/home/teraram/ci/builds/workspace/parallel-build/flambda/true/label/ocaml-manycores/stdlib @@0Jvo8yWuU3        @ @@8CamlinternalFormatBasics0|.e1R$|o&Stdlib0t0VoS%{<F:.Stdlib__Either0HD ?|> 308.9Nrk]+Stdlib__Seq0?72#[O@08.9Nrk]AVC@@zN_ |ѐ'@ q@#l 2 ]@@@D@0@@.@)@@  +@@P@@P@@