Caml1999I037B 11w.Stdlib__Pqueue+OrderedType!t;@@@A@@@@@*pqueue.mliiAEiAK@@@@@@A@'compare@@@@@@@@#intA@@@@@@@@lnrln@@-A@@@@g!! w s x@1B@@#Min!t;@@@A@@@@@0  1  @@@@BC@A@#elt;@@@A@@@@@:B 4 8;B 4 @@@@@LD@A@&create@$unitF@@@"@@@@@@OE r vPE r @@aE@@&length@@@@H@@@@@@aH  bH  @@sF@@(is_empty@!@@@$boolE@@@@@@uK  "vK  9@@G@@#add@5@@@@R@@@D@@@@@@@@N  N  @@H@@(add_iter@M@@@@@@@@@_@@@@@@!x@i@@@@@@@@ o@@@@@@@@@@Q  Q  2@@I@@'min_elt@x@@@&optionLG@@@@@@@@@U  U  @@J@@+get_min_elt@@@@Y@@@@@@YIMYIf@@K@@'pop_min@@@@)n@@@@@@@@@^^;@@ L@@*remove_min@@@@@@@@@@ b b@@M@@%clear@@@@@@@@@@faefay@@-N@@$copy@@@@@@@@@@,i-i@@>O@@(of_array@%arrayJ@@@@@@@@@@@@DnTXEnTt@@VP@@'of_list@$listK@@@@@@@@@@@@\r]r @@nQ@@'of_iter@@@@@@)@@@@@@!x@3@@@@@@@@ 3@@@@@@@@vv@@R@@.iter_unordered@@ @@@L@@@@@@L@@@U@@@@@@@@@@S@@.fold_unordered@@#acc@@,@@@ @@@@@ @m@@@@@@@@@@!@@T@@@@z  _d@U@@Ӡ'MakeMin@!Eڑ;@@@A@@@@@@@@@A@@@@@\@@@]@@^@@@@ @@@_@@@`@@a@@@@@@@b@@@c@@d@(@@@"@@@e@A!t@@@f@@@g@@h@@i@<@@@6@@@j@@@@@@k@@@l@@m@@q|@@@n@@o@@p@{@@@r@@s@@t@@u@]@w@v@W@@@vu65@@@w@@@x@@y@n@p@o@h@@@zDC@@@{@@|@{@l@k@u@@@}jTS@@@~@@@@@@@g@f@@@@e@@@@@@@a@`@@@@_@@@@@@@[@Z@@@@@@@@@@@V@U@T@@@@@@@@@@@@@O@N@M@@@@@@@@@@@@@H@G@@@@@@G@@@@@@F@C@@@@@@@@@@@@@@@@@?@>@@@@@>@@@@@@@@@=@@@@@@@@@9@8@@7@@@@@@@@@@ @ @@@@@@@@@@@2@@@@X@@@#Max!t;@@@A@@@@@imis@@@@Y@A@#elt;@@@A@@@@@ tx t@@@@Z@A@&create@@@@  @@@@@@@@/[@@&length@@@@@@@@@@/0@@A\@@(is_empty@!@@@@@@@@@AB@@S]@@#add@3@@@@N@@@@@@@@@@@YZ@@k^@@(add_iter@K@@@@@@@@@+@@@@@@!x@"5@@@@@ @@!@ ;@@@#@@$@@%@@&@0@@_@@'max_elt@v@@@'̠E@@@(@@@)@@*@151Q@@`@@+get_max_elt@@@@+W@@@,@@-@RVRo@@a@@'pop_max@@@@.l@@@/@@@0@@1@ptp@@b@@*remove_max@@@@2@@@3@@4@@@c@@%clear@@@@5@@@6@@7@@@d@@$copy@@@@8@@@9@@:@@@e@@(of_array@ʠ@@@;@@@<@@@=@@>@  @@f@@'of_list@Ƞ@@@?@@@@@@@A@@B@"#@@4g@@'of_iter@@@@@@C@@@D@@E@!x@I@@@F@@G@@H@ +@@@J@@K@@L@G!HV@@Yh@@.iter_unordered@@@@@M@@@N@@O@D@@@P@@@Q@@R@@S@dW[eW@@vi@@.fold_unordered@@#acc@X@&@@@T @@U@@V@ @e@@@W@@Y@@Z@@[@@@j@@@@QQ@k@@Ӡ'MakeMax@!EƑ;@@@A@@@@@&>@@@@A@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@(@~@}@"@@@@@!t@@@~@@@@@@@@<@z@y@6@@@@@@@@@y@@@@@@x@u@@@@@@@@t@@@@@@@@@@]@p@o@W@@@n65@@@@@@@@@n@k@j@h@@@DC@@@@@@{@g@f@u@@@eTS@@@@@@@@@@b@a@@@@`@@@@@@@\@[@@@@Z@@@@@@@V@U@@@@@@@@@@@Q@P@O@@@@@@@@@@@@@L@K@J@@@@@@@@@@@@@G@F@@@@@@F@@@@@@E@B@@@@@@@@@@@@@@@@@>@=@@@@@=@@@@@@@@@<@@@@@@@@@8@7@@6@ @@@@@@@@@ @ @@@@@ @@ @@ @@1@@@@n@@@/OrderedPolyType!t;!a@@A@A@G@B@@@ ; ? ; H@@@@o@A@'compare@!a@@@@@ !b@@@@@@@@@@@@ w { w @@p@@@@    @q@@'MinPoly!t;!a@U@A@A@G@B@@@ !H!L !H!U@@@@r@A@#elt;!a@V@A@A@G@B@@@!V!Z!V!e@@@@-s@A@&create@@@@W.!a@X@@@Y@@Z@3!f!j4!f!@@Et@@&length@!a@[@@@\1@@@]@@^@J!!K!!@@\u@@(is_empty@+!a@_@@@`@@@a@@b@a!!b!!@@sv@@#add@B!a@d@@@c@i @@@e6@@@f@@g@@h@!!!!@@w@@(add_iter@`!a@j@@@i@@@"@@@kW@@@l@@m@!x@qa@@@n@@o@@p@ g@@@r@@s@@t@@u@!!!")@@x@@'min_elt@!a@w@@@vQ @@@x@@@y@@z@"*"."*"P@@y@@+get_min_elt@!a@|@@@{i@@@}@@~@"Q"U"Q"t@@z@@'pop_min@Ġ!a@@@@0 @@@@@@@@@"u"y"u"@@{@@*remove_min@!a@@@@@@@@@@""""@@(|@@%clear@!a@@@@@@@@@@-"".""@@?}@@$copy@!a@@@@@@@@@@D""E""@@V~@@(of_array@ݠ!a@@@@@@@2 @@@@@@`""a"#@@r@@'of_list@!a@@@@@@@N @@@@@@|##}##?@@@@@'of_iter@@@!a@@@@N@@@@@@!x@X@@@@@@@@ y@@@@@@@@#@#D#@#@@A@@.iter_unordered@@>!a@@@@w@@@@@@@@@@@@@@@@@####@@B@@.fold_unordered@@#acc@@g!a@@@@@@@@@@ @@@@@@@@@@###$@@C@@@@!,!,$$@D@@Ӡ+MakeMinPoly@!EG;@@A@A@@@ $k$m $k$@@@@A@@@@@@@@@@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@.@@@(@@@@@K!t @@@@@@@@@@@E@@@?@ @@@@@@ @@@ @@@ @@ @@@@@ @@@@@@@@@@@@@@@i@@@c@@@@<; @@@@@@@@@}@@@w@@@@ML@@@@@@@@@@@@@`_ @@@ @@@!@@"@@@@@#@@@$@@@%@@&@@@@@'@@@(@@@)@@*@@@@@,@@@+@@@-@@.@@@@@1@@@/@@@0Р@@@2@@3@@@@@6@@@4@@@5@@@7@@8@@~@}@@@ }@@@@@9z@@@:@@;@y@?v@@@<@@=@@>@@@@A@@B@@C@@r@q@@ߠq@G@@@Dn@@@E@@F@ @@@Hm@@@I@@J@@K@-@i@h@@g@Q@e@O@@@L @@M@@N@ @6 @@@P@@R@@S@@T@F@_@@@ O$@$@F@ `G@@@'MaxPoly!t;!a@@A@A@G@B@@@ f%!%% g%!%.@@@@ xH@A@#elt;!a@@A@A@G@B@@@ w%/%3 x%/%>@@@@ I@A@&create @ =@@@.!a@@@@@@@ %?%C %?%[@@ J@@&length @!a@@@@ @@@@@@ %\%` %\%w@@ K@@(is_empty @+!a@@@@ J@@@@@@ %x%| %x%@@ L@@#add @B!a@@@@@i @@@ @@@@@@@@ %% %%@@ M@@(add_iter @`!a@@@@@@@"@@@ @@@@@@!x@ @@@@@@@@  @@@@@@@@@@ %% %&@@ N@@'max_elt@!a@@@@ YQ @@@@@@@@@ (&& )&&*@@ :O@@+get_max_elt@!a@@@@i@@@@@@ ?&+&/ @&+&N@@ QP@@'pop_max@Ġ!a@@@@  @@@@@@@@@ [&O&S \&O&u@@ mQ@@*remove_max@!a@@@@ )@@@@@@ r&v&z s&v&@@ R@@%clear@!a@@@@ @@@@@@@ && &&@@ S@@$copy@!a@@@@@@@@@@ && &&@@ T@@(of_array@ tݠ!a@@@@@@@2 @@@@@@ && &&@@ U@@'of_list@ x!a@@@@@@@N @@@@@@  &&  &'@@ V@@'of_iter@@@!a@@@@ @@@@@@!x@ @@@@@@@@ y@@@@@@@@  ''  ''Y@@ W@@.iter_unordered@@>!a@@@@ @@@@@@@@@ @@@@@@@@ & 'Z'^ ' 'Z'@@ 8X@@.fold_unordered@@#acc@@g!a@@@@@@@@@@ @@@@@@@@@@ I '' J ''@@ [Y@@@@ M%% N ''@ _Z@@Ӡ+MakeMaxPoly@!E\;@4@A@A@@@ d(C(E e(C(g@@@@A@@@@@5@6@@@7@@8@@@@ @9@@@:@@@;@@<@ @@@@=@@@>@@@?@@@@.@@@(@B@@@A@J!t @@@C@@@D@@E@@F@E@@@?@H@@@G@@@ @@@I@@@J@@K@@O@@@L@@M@@N@@@@P@@Q@@R@@S@i@@@c@U@@@T<; @@@V@@@W@@X@}@@ @w@Z@@@YML@@@[@@\@@@!@@^@@@]`_ @@@_@@@`@@a@@@"@@b@@@c@@@d@@e@@@#@@f@@@g@@@h@@i@@@$@@k@@@j@@@l@@m@@@%@@p@@@n@@@oР@@@q@@r@@@&@@u@@@s@@@t@@@v@@w@@}@|'@@@ |@@@@xy@@@y@@z@x@~u@@@{@@|@@}@@@@@@@@@@q@p(@@ߠp@@@@m@@@@@@ @@@l@@@@@@@@-@h@g)@@f@@d@@@@ @@@@@ @6 @@@@@@@@@@F@^@@@ ((F@ ]@@@@l:..Stdlib__Pqueue0> ? .*Y8&Stdlib0Lku]8_٠8CamlinternalFormatBasics0%FU(Q/Tu@@@Caml1999T037$C.Stdlib__Pqueue*ocaml.text&_none_@@A / Priority queues. The {!Pqueue} module implements a data structure of priority queues, given a totally ordered type for elements. This is a mutable data structure. Both min- and max-priority queues are provided. The implementation uses a heap stored in a dynamic array, and is therefore reasonably efficient: accessing the minimum (resp. maximum) element takes constant time, and insertion and removal take time logarithmic in the size of the priority queue. Note that [of_array] runs in linear time (and thus must be preferred to repeated insertions with [add]). It is fine to have several elements with the same priority. Nothing is guaranteed regarding the order in which they will be popped. However, it is guaranteed that the element returned by [min_elt] (or [get_min_elt]) is the one that is removed from the priority queue by [pop_min] (or [remove_min]). This is important in many algorithms, (e.g. when peeking at several priority queues and then selecting one to remove from). @since 5.4 *pqueue.mliOe@@@@@@3@@@@@@#intA;@@@A@@@@@:@A@$charB;@@A@@@@@>@A@&stringQ;@@ A@@@@@B@@@%bytesC;@@ A@@@@@F@@@%floatD;@@A@@@@@J@@@$boolE;@@%falsec@@T@$trued@@Z@@@A@@@@@[@A@$unitF;@@"()e@@e@@@A@@@@@f@A@ #exnG;@@@A@@@@@j@@@#effH;@@O@A@A@@@@@@s@@@,continuationI;@@Q@@P@B@A@nY@@@@@@@@@%arrayJ;@@R@A@A@@@@@@@@@ $listK;@@S@A"[]f@@@"::g@@@T@@@ @@A@Y@@@@@@@@&optionL;@@V@A$Noneh@@@$Somei@@@@@A@Y@@@@@@@@)nativeintM;@@A@@@@@@@@%int32N;@@A@@@@@@@@%int64O;@@A@@@@@@@@&lazy_tP;@@X@AJA@Y@@@@@@@@5extension_constructorR;@@A@@@@@@@@*floatarrayS;@@A@@@@@@@@&iarrayT;@@Y@A[A@Y@@@@@@@@*atomic_locU;@@Z@AdA@@@@@@@@@.Assert_failure`#@@@@@J@@@@@@@@[@@A=ocaml.warn_on_literal_pattern @ @0Division_by_zero]#@@@A  @+End_of_file\#$@@@A@'FailureY#,@'@@A!$$@0Invalid_argumentX#5@0@@A*$-#-@-Match_failureV#>@@=@9@;@@a@@A;5>4>@)Not_foundZ#O@@@AC=F<F@-Out_of_memoryW#W@@@AKENDN@.Stack_overflow^#_@@@ASMVLV@.Sys_blocked_io_#g@@@A[U^T^@)Sys_error[#o@j@@Ad^g]g@:Undefined_recursive_modulea#x@@w@s@u@@h@@Auoxnx@:Continuation_already_takenb#@@@A}wv@&Stdlib@Ax+OrderedTypeBg!-g!8@B@БA+!tAiAJiAK@@;@@@A@@@@@iAE@)ocaml.doc7 The type of elements. jLPjLl@@@@@@@@@@@@@A@@@@@@@@3@@A#@'comparelnvln}@б@г7!tlnln@@ @@@3@B<@A@@б@гH!tlnln@@ @@@@@г#intlnln@@ @@@@@@@@!@@@'@@$* @@@lnr@^  A total ordering function to compare elements. This is a two-argument function [f] such that [f e1 e2] is zero if the elements [e1] and [e2] are equal, [f e1 e2] is strictly negative if [e1] is smaller than [e2], and [f e1 e2] is strictly positive if [e1] is greater than [e2]. The generic structural comparison function {!Stdlib.compare} is a suitable ordering function for element types such as [int] or [string]. mv U r@@@@@@@A@@@n@@@@@@C@A@["@@3@H]$@A3@@Ah;=w s x@@) < Input signature of the functors {!MakeMin} and {!MakeMax}. &x y y'x y @@@@@@@)g!!@'@#Min'E3z  4z  @LU@БML {1:pqueue Min-priority queues} I}  J}  @@@@@@3HGGHHHHH@GA@d@@:9@99@@@9@9@6@AA+!tCg  h  @@;@@A@@@@@k  @א> The type of priority queues. x@  y@  2@@@@@@@@@C@@@A@@@@@@@@;@A+#eltDB 4 =B 4 @@@;@@A@@@@@B 4 8@ & The type of priority queue elements. C A EC A p@@@@@@@@@D@@@A@@@@@@@@3@eNH@A!@&createE r zE r @б@гr$unitE r E r @@ @@@3@@:@A@@гm!tE r E r @@ @@@@@@@@@@@E r v @K / Return a new priority queue, initially empty. F  F  @@@@@@@E@@@[@@@@@@1&lengthH  H  @б@г!tH  H  @@ @@@3@J_8@A@@г#intH  H  @@ @@@@@@@@@@@(H   @ 4 Return the number of elements in a priority queue. 5I  6I  @@@@@@@NF@@@I@@@@@@1(is_emptyLK  &MK  .@б@г!tWK  0XK  1@@ @@@3YXXYYYYY@J_8@A@@г$$boolfK  5gK  9@@ @@@@@@@@@@@qK  " @ݐ G [is_empty q] is [true] iff [q] is empty, that is, iff [length q = 0]. ~L : >L : @@@@@@@G@@@@@@@@@1#addN  N  @б@г9!tN  N  @@ @@@3@J_8@A@@б@г!#eltN  N  @@ @@@@@гk$unitN  N  @@ @@@@@@@@!@@@'@@$* @@@N  @8 ; [add q x] adds the element [x] in the priority queue [q]. O  O  @@@@@@@H@@@H퐠@@@@@@C(add_iterQ  Q  @б@г!tQ  Q  @@ @@@3@\q8@A@@б@б@б@г#eltQ  Q  @@ @@@@@гʠ$unitQ  Q  @@ @@@"@@@@@%@@б@А!x@E@01Q  2Q  @@г砐$unit:Q  ;Q  #@@ @@@?@@@@@B@@@"@@EFQ   @@б@А!x!LMQ  (NQ  *@@г$unitVQ  .WQ  2@@ @@@[@@@3@@^@@@@@abQ   @@@h@@ek@@@hQ  @Ԑ c [add_iter q iter x] adds each element of [x] to the end of [q]. This is [iter (add q) x]. uR 3 7vS { @@@@@@@I@@"@@@@@@@'min_eltU  U  @б@г0!tU  U  @@ @@@3@8@A@@г&optionU  U  @г #eltU  U  @@ @@@@@@@@@ @@@$@@!'@@@U  @, | [min_elt q] is an element of [q] with minimal priority or [None] if the queue is empty. The queue is not modified. V  WG@@@@@@@J@@*@<ᐠ@@@@@@@+get_min_eltYIQYI\@б@г!tYI^YI_@@ @@@3@Yn8@A@@гn#eltYIcYIf@@ @@@@@@@@@@@ YIM @u [get_min_elt q] returns an element of [q] with minimal priority, or raises {!Stdlib.Invalid_argument} if the queue is empty. The queue is not modified. Zgk\@@@@@@@/K@@@*@@@@@@1'pop_min-^#.^*@б@гѠ!t8^,9^-@@ @@@3:99:::::@J_8@A@@г&optionG^5H^;@г#eltQ^1R^4@@ @@@@@@@@@ @@@$@@!'@@@a^@͐ [pop_min q] removes and returns an element in queue [q] with minimal priority, or returns [None] if the queue is empty. n_<@o`@@@@@@@L@@*@@@@@@@@*remove_minbb@б@г)!tbb@@ @@@3@Yn8@A@@гL$unitbb@@ @@@@@@@@@@@b @ p [remove_min q] removes an element in queue [q] with minimal priority. It does nothing if [q] is empty. cd*_@@@@@@@M@@@&ː@@@@@@1%clear faifan@б@гr!tfapfaq@@ @@@3@J_8@A@@г$unitfaufay@@ @@@@@@@@@@@fae @_ * [clear q] removes all elements from [q]. gz~gz@@@@@@@N@@@o@@@@@@1$copy!ii@б@г!t"i#i@@ @@@3$##$$$$$@J_8@A@@гʠ!t1i2i@@ @@@@@@@@@@@<i @ B [copy q] is a new priority queue with the same elements [q] has. IjJj@@@@@@@bO@@@]@@@@@@1kj 8 {1:conversions Conversions from other data structures} glhlR@@@@@@3feefffff@CX1@A(of_array"snT\tnTd@б@г%array~nTjnTo@г#eltnTfnTi@@ @@@$@@@@@@) @@г3!tnTsnTt@@ @@@6@@@@@9@@@nTX @ n [of_array a] returns a new priority queue containing the elements of array [a]. Runs in linear time. ouyp@@@@@@@P@@@!Ɛ@@@@@@X'of_list#rr@б@гP$listrr@гN#eltrr@@ @@@3@{vB@A@@@ @@@ @@г!tr r @@ @@@@@@@@@@@r @i l [of_list l] returns a new priority queue containing the elements of list [l]. Runs in linear time.  s  tM@@@@@@@#Q@@@y@@@@@@6'of_iter$!v"v@б@б@б@г#elt0v1v@@ @@@321122222@Sr<@A@@г점$unit?v@v@@ @@@@@@@@@@б@А!x@E@SvTv@@г $unit\v]v@@ @@@,@@@@@/@@@"@@2hv @@б@А!x!9ovpv@@г!txvyv@@ @@@H@@@3@@K@@@@@Nv @@@v@󐠠 Q [of_iter iter x] returns a new priority queue containing the elements of [x], obtained from [iter]. For example, [of_iter Seq.iter s] returns a new priority queue containing all the elements of the sequence [s] (provided it is finite). Runs in linear time (excluding the time spent in [iter]). w~@@@@@@@R@@@@@@@@@n  {1:iteration Iteration} The order in which the elements of a priority queue are traversed is unspecified. It is a programming error to mutate a priority queue (by adding or removing elements) during an iteration of the queue. Such an error may be detected and signaled by the backing dynamic array implementation, but this is not guaranteed. p@@@@@@3@1@A.iter_unordered%@б@б@г;#elt@@ @@@@@г$unit@@ @@@)@@@@@,@@б@г!t@@ @@@;@@г$unit@@ @@@H@@@@@K@@@$@@N @@@@r [iter_unordered f q] applies [f] to all elements in [q]. The order in which the elements are passed to [f] is unspecified. The behavior is not specified if the priority queue is modified by [f] during the iteration. @@@@@@@,S@@@'@@@@@@n.fold_unordered&*+@б@б@А#acc@E@354455555@6@A;<@@б@г#eltFG@@ @@@@@А#accPQ @@@ !@@@@@$@@@@б@А#acc*%^_@@б@г!tij@@ @@@6@@А#acc?:st!@@@ D@@?@@@G@@B@@@(@@E~ @@@@퐠 2 [fold_unordered f accu q] is [(f (... (f (f accu x1) x2) ...) xn)] where [x1,x2,...,xn] are the elements of [q]. The order in which the elements are passed to [f] is unspecified. The behavior is not specified if the priority queue is modified by [f] during the iteration. "&6]@@@@@@@T@@@@@@@@@e@<6A@A@@@_8@@E@%@@R@2 @@}@J@@8@@B@@3@D@A'3@y@A{  _d@@3ؐ - Output signature of the functor {!MakeMin}. eee@@@@@@@z  @3@@A@'MakeMinLF@X@@Т!E(G@Р{+OrderedType@3@A@ztA@R+@ @@}D@$@T@4 @@p@P)@ @{@[%@@j @@@]\@\\@@@\@\@Y@A76@@УР#Min : ;@3 : 9 9 : : : : :@BT@M@R YV@W@A  @@#elt K L@+à@;@@@Ak!t@@@@@@@ Z [@@@@ sW@@@Aг !E f g@ j@@@/@@@@ ;H;@@@A@@@@@:@@@A@<@@@@@@@@@@@=@ @@@t@@@@@@dV@G>@@@@7@@@@@@&'@ ?@"@@@@Q@@@@@@@@@@@9@@@5@@@@@@g@@@@@@@@@@@@@@@@@z@@@@@@@@@@YcU@FA@U@@@64@@@@@@@@@j@B@f@@@B@@@@@@w@C@s@@@R@@@@@@@@@@|D@@@@l@@@@@@\N@?E@@@@/@@@@@@@F@@@@@@@@@@@G@@@@@@@@@@@@@|@mH@i@@@@@@@@@@@@C5@&I@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@J@@@@@@@@@@@@@@@@@@@@@@l^@OK@@H@)@@@N@@@@@P@@@@U@@@@@@@@@K@3        @@A1@@ w Functor building an implementation of the min-priority queue structure given a totally ordered type for elements.   O@@@@@@@ B@C@#Max_K Q] Q`@ k@БA+!tMI ir is@@;@@ 'A@@@@@ im@@@@ Y@@@A@@@3        @@֐͑UTA@QP@FE@<;@21@! @@@@@@@@@@@po@@ PXW@WW@@@W@W@T@A69@A+#eltNJ t} t@@;@@ jA@@@@@ tx@@@@ Z@@@A@@@3        @DOI@A@&createO  @б@г  $unit  @@ @@@3        @'!@A@@гn!t $ %@@ @@@@@@@@@@@ / @@ G[@@ @@&lengthP : ;@б@г!t E F@@ @@@3 G F F G G G G G@1F@A@@г '#int T U@@ @@@@@@@@@@@ _ @@ w\@@ @@(is_emptyQ j k@б@г!t u v@@ @@@3 w v v w w w w w@1F@A@@г B$bool  @@ @@@@@@@@@@@  @@ ]@@ @@#addR  @б@г!t  @@ @@@3        @1F@A@@б@г#elt  @@ @@@@@г p$unit  @@ @@@@@@@@!@@@'@@$* @@@ @@ ^@@@@*(add_iterS  @б@г1!t  @@ @@@3        @CX@A@@б@б@б@г#elt   @@ @@@@@г $unit  @@ @@@"@@@@@%@@б@А!x@K@0  @@г Ӡ$unit & '!@@ @@@?@@@@@B@@@"@@E 2 @@б@А!x!L 9& :(@@г $unit B, C0@@ @@@[@@@3@@^@@@@@a N @@@h@@ek@@@ T@@ l_@@@@k'max_eltT _19 `1@@б@г!t j1B k1C@@ @@@3 l k k l l l l l@@A@@г ؠ&option y1K z1Q@г#elt 1G 1J@@ @@@@@@@@@ @@@$@@!'@@@ 15@@ `@@@@'+get_max_eltU RZ Re@б@г!t Rg Rh@@ @@@ 3        @@U@A@@г#elt Rl Ro@@ @@@ @@@@@ @@@ RV @@ a@@ @@'pop_maxV px p@б@г#!t p p@@ @@@ 3        @1F@A@@г G&option p p@г#elt p p@@ @@@ @@@@@@ @@@$@@!'@@@ pt@@ b@@@@'*remove_maxW  @б@гb!t  @@ @@@3        @@U@A@@г Ԡ$unit ' (@@ @@@@@@@@@@@ 2 @@ Jc@@ @@%clearX = >@б@г!t H I@@ @@@3 J I I J J J J J@1F@A@@г $unit W X@@ @@@@@@@@@@@ b @@ zd@@ @@$copyY m n@б@г !t x y@@ @@@3 z y y z z z z z@1F@A@@гѠ!t  @@ @@@@@@@@@@@  @@ e@@ @@(of_arrayZ  @б@г .%array  @г#elt  @@ @@@3        @;P)@A@@@ @@@ @@г!t  @@ @@@@@@@@@@@  @@ f@@ @@'of_list[   @б@г c$list  @г#elt  @@ @@@3        @@_)@A@@@ @@@! @@гO!t@@ @@@"@@@@@#@@@ @@(g@@ @@'of_iter\%,@б@б@б@г1#elt*0+3@@ @@@$3,++,,,,,@:Y#@A@@г 栐$unit97:;@@ @@@%@@@@@&@@б@А!x@/K@'M@NB@@г$unitVFWJ@@ @@@(,@@@@@)/@@@"@@*2b/ @@б@А!x!9iOjQ@@г!trUsV@@ @@@+H@@@3@@,K@@@@@-N~. @@@!@@h@@@@U.iter_unordered]W_Wm@б@б@г#eltWpWs@@ @@@03@p!@A@@гU$unitWwW{@@ @@@1@@@@@2@@б@г!tWW@@ @@@3!@@гt$unitWW@@ @@@4.@@@@@51@@@$@@64Wo @@@W[@@i@@@@;.fold_unordered^@б@б@А#acc@@K@73@Ri@A@@б@г#elt@@ @@@8@@А#acc@@@ !@@9@@@$@@:@@б@А#acc*%@@б@гj!t !@@ @@@;6@@А#acc?:*+@@@ D@@<?@@@G@@=B@@@(@@>E5 @@@8@@Pj@@@@L@A@JDA@;@ @@x@q@@@O@H!@@@@K@D@@)@@3\[[\\\\\@q+@A'3_^^_____@@Adcee@@ v - Output signature of the functor {!MakeMax}. st@@@@@@@vQQ@3tssttttt@@A@'MakeMaxL @n@@Т!E`M@Р+OrderedType"@3@A@A@y@rK@D@@\@U@@@@X@Q*@#@@A@:@@@/]\@\\@@@\@\@Y&@A76@@УР2#Max&)@3@BT@M@Rl@W@A  @@#elt47@+@;@@@Ak!t@@@F@@@@/>@@@@m@@@Aг !E;<@=@@@/@@@@\sN;@@@A@@@@@:@@@@WA@t@ @@@+@@@*@@)@@@u@ @@@(@@@'@@&@@@v@@@@%@@@$@@#@&@@w@"@@@"@Q@@@!@@@ @@@@@9@x@tx@5@@@@@@g@@@[@@@@@@KC@@@@@@@@P,@@@@@@@@@@Y@@y@U@@@4@@@@@@@@@j@@z@f@@@B@@@ @@ @w@@{@s@@@ R@@@ @@@ @@@@@|@@@@@@@@@@@r@n}@@@@^@@@@@@@N@J~@@@@@@@@@@@*@&@"@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@x@t@@@@@e@@@@@@@@@N@@@@@@@@@:@6@@/@)@@@5@@@@@7@@@@<@@@@@@@@@@K@3%$$%%%%%@@A1@@: w Functor building an implementation of the max-priority queue structure given a totally ordered type for elements. 7??8@@@@@@@:B@C@ON S {1 Polymorphic priority queues} The following, more complex functors create polymorphic queues of type ['a t], just like other polymorphic containers (lists, arrays...). They require a notion of "polymorphic elements" ['a elt] that can be compared without depending on the values of ['a]. One usage scenario is when the user wants to pass priorities separately from the value stored in the queue. This is done by using pairs [priority * 'a] as elements. {[ module Prio : OrderedType = ... module PrioQueue = Pqueue.MakeMinPoly(struct type 'a t = Prio.t * 'a let compare (p1, _) (p2, _) = Prio.compare p1 p2 end) (* for example, we now have: *) PrioQueue.add: 'a PrioQueue.t -> Prio.t * 'a -> unit PrioQueue.min_elt: 'a PrioQueue.t -> (Prio.t * 'a) option ]} KL  @@@@@@3JIIJJJJJ@@ɐHGA@DC@98@/.@%$@@@@@@@@@@@xw@cb@@ᐠKJ@JJ@@@J@J@G@A6/OrderedPolyTypeP  #  2@q@БA+!tO ; G ; H@А!a@-3@V;@@,@A@A@G@B@@@ ; ?@ # The polymorphic type of elements.  I M I u@@@@@@@@@o@@A ; D ; F@@BA@;#@A0A@G@B@@@@@ @@A@/Ԑ@@@@@@@3@@A%8@'compare w  w @б@гL!t w  w @А!a@:P@03@]1@A w  w @@@ @@@2 @@б@гj!t w  w @А!b@3@:A@g@@=<@<<@@@<@<@9";@@=@A@A@G@B@@@!H!L&@@@@r@@A!H!Q!H!S@@@;&@AA@G@B@@@ @@@@@A@ @@3@$@A 0@A+#eltR!V!b!V!e@А!a@B3@;K;@@A@A@A@G@B@@@!V!Z@@@@s@@A!V!_!V!a@@@;@A?A@G@B@@@ @@@@@A@ @@3@@A @&create!f!n!f!t@б@г$unit!f!v!f!z@@ @@@E3@.> @A@@г|!t!f!!f!@А!a@KS@F!f!}!f!@@@ @@@H@@@"@@I%@@@!f!j@@'t@@@@%&length!!!!@б@г!t%!!&!!@А!a@RS@L3-,,-----@DY%@A3!!4!!@@@ @@@N @@г#intA!!B!!@@ @@@O@@@@@P@@@L!! @@du@@ @@(is_emptyW!!X!!@б@г砐!tb!!c!!@А!a@YS@S3jiijjjjj@>Y%@Ap!!q!!@@@ @@@U @@г<$bool~!!!!@@ @@@V@@@@@W@@@!! @@v@@ @@#add!!!!@б@г$!t!!!!@А!a@cS@Z3@>Y%@A!!!!@@@ @@@\ @@б@г#elt!!!!@А!a!!!!@@@$@@@^  @@г$unit!!!!@@ @@@_-@@@@@`0@@@.@@a31 @@@!!@@w@@@@9(add_iter!!!!@б@г{!t!!!!@А!a@tS@d3@Xs%@A!!!!@@@ @@@f @@б@б@б@гc#elt!"!"@А!a"!! !!@@@(@@@h$ @@гڠ$unit-!".!" @@ @@@i1@@@@@j4@@б@А!x@vS@k?A!"B!"@@г$unitJ!"K!"@@ @@@lN@@@@@mQ@@@"@@nTV!! @@б@А!x![]!"^!"!@@г$unitf!"%g!")@@ @@@oj@@@3@@pm@@@@@qpr!! @@@o@@rtr@@@x!!@@x@@@@z'min_elt"*"2"*"9@б@г!t"*">"*"?@А!a@S@w3@%@A"*";"*"=@@@ @@@y @@г &option"*"J"*"P@г#elt"*"F"*"I@А!a&!"*"C"*"E@@@,@@@{( @@@@@@}- @@@+@@~0.@@@"*"."@@y@@$@@6+get_min_elt"Q"Y"Q"d@б@гg!t"Q"i"Q"j@А!a@S@3@Up%@A"Q"f"Q"h@@@ @@@ @@гI#elt"Q"q"Q"t@А!a"Q"n"Q"p@@@"@@@ @@@@@!@@@"Q"U@@)z@@@@''pop_min"u"}"u"@б@г!t'"u"("u"@А!a@S@3/../////@Fa%@A5"u"6"u"@@@ @@@ @@г&optionC"u"D"u"@г#eltM"u"N"u"@А!a&!T"u"U"u"@@@,@@@( @@@@@@- @@@+@@0.@@@e"u"y"@@}{@@$@@6*remove_minp""q""@б@г!t{""|""@А!a@S@3@Up%@A""""@@@ @@@ @@гD$unit""""@@ @@@@@@@@@@@"" @@|@@ @@%clear""""@б@г=!t""""@А!a@S@3@>Y%@A""""@@@ @@@ @@г$unit""""@@ @@@@@@@@@@@"" @@}@@ @@$copy""""@б@гz!t""""@А!a@S@3@>Y%@A""""@@@ @@@ @@г!t""""@А!a""""@@@"@@@ @@@@@!@@@$""@@<~@@@@'(of_array/""0"#@б@г%array:"# ;"#@г#eltD"# E"# @А!a@S@3LKKLLLLL@Pk/@AR"#S"#@@@ @@@ @@@&@@@ #@@гꠐ!te"#f"#@А!a!l"#m"#@@@'@@@# @@@@@&$@@@x""@@@@@@,'of_list#####*@б@г $list##3##7@г㠐#elt##/##2@А!a@S@3@Uz/@A##,##.@@@ @@@ @@@&@@@ #@@г>!t##>##?@А!a!##;##=@@@'@@@# @@@@@&$@@@##@@@@@@@,'of_iter#@#H#@#O@б@б@б@г1#elt#@#V#@#Y@А!a@S@3@Ot)@A#@#S#@#U@@@ @@@ @@г$unit#@#]#@#a@@ @@@@@@@@@@б@А!x@S@$#@#f#@#h@@г̠$unit#@#l #@#p@@ @@@3@@@@@6@@@"@@9+#@#R @@б@А!x!@2#@#u3#@#w@@г!t;#@#~<#@#@А!aUPB#@#{C#@#}@@@[@@@W @@@;@@Z@@@&@@]O#@#Q@@@R#@#D@@jA@@@@d.iter_unordered]##^##@б@б@г#eltj##k##@А!a@S@3rqqrrrrr@'@Ax##y##@@@ @@@ @@г3$unit####@@ @@@@@@@@@@б@г!t####@А!a.)####@@@4@@@0 @@гZ$unit####@@ @@@=@@@@@@@@@,@@C## @@@##@@B@@@@J.fold_unordered####@б@б@А#acc@S@3@a~@A####@@б@г.#elt####@А!a@S@####@@@ @@@ @@А#acc)$####@@@ .@@)@@@1@@,*@@б@А#acc72## ##@@б@г!t####@А!a0D####@@@6@@@K @@А#accTO%##&#$@@@ Y@@T@@@\@@W%@@@0@@Z0## @@@3##@@KC@@@@a@A@kA@c/@(@@d@]@|@u9@2@@q@j.@'@@@@)@@3WVVWWWWW@+@A'3ZYYZZZZZ@@A_!B!D`$$@@q 1 Output signature of the functor {!MakeMinPoly}. n$$o$$>@@@@@@@q!,!,@3onnooooo@@A@+MakeMinPolyT~$@$G$@$R@G@@Т!EU$@$T$@$U@Р /OrderedPolyType$@$X$@$g@3@1&A@A@@Y@R@@3@,@@L@E@ @@A@:@k@d@@@*]\@\\@@@\@\@Y\@A76@@УРh'MinPoly$k$m$k$t@3@BT@M@RE@W@A  @@/#elt$k$$k$@+7А!a@V@$k$$k$@@7@; @A@Ay!tV@@@@G@B@@@$k$z$k$@@@@F@@@Aг!E$k$$k$@$k$@@А!aE$k$$k$@@@$H@@@@V;@A@A@~}@@T!@@@@A@P@L@@@ 7@@@ @@ @@%@!@ @@@ @@@ @@ @@@@@@@ @@@ @@ @)@@@%@@@ @a@@@ @@@ @@ @@ @>@@@:q@@@ @@@y|@@@ S@@@ @@ @C;@@@ @@ @@ @H$@@@ @@ @@ @@ @`@ @ @\@@@ 8@@@ @@@ @@ @s@@@o@@@ H@@@ @@ @@@@~@@@ vZ@@@ @@@ @@ @@U@Q@C@@@ 5@@@ @@ @@%@!@@@@ @@@ @@ @@@@@@@ @@@ @@ @@@@@@@ @@@  @@@ @@ @@}@y@ue@@@ @@@ ՠj@@@ @@ @@<@8@@@+@@@ @@@ @@ @ @@@ @@ @@ @9@@@ @@ @@ @@@@@3@@@ @@@ @@ @@@@ @@@ @@ @@ @@@~@@w@Nd@@@ ~@@ @@ @@"l@@@ @@ @@ @@ @0@"@@0@93UTTUUUUU@@AZ$@$SU@@k n Functor building an implementation of min-priority queues given a totally ordered type for the elements. h$$i$%@@@@@@@k$@$@f@g@'MaxPolyYu%%v%%@Z@БA+!tW%!%-%!%.@А!a@ 3@@wvA@rq@fe@[Z@PO@=<@@  @@@@@@@@@xw@@$]\@\\@@@\@\@YCB;@@ @A@A@G@B@@@%!%%F@@@@H@@A%!%*%!%,@@ @;F@A@A@G@B@@@ @@@@@A@ @@3@D@A P@A+#eltX%/%;%/%>@А!a@ 3@[k;@@ @A@A@G@B@@@%/%3@@@@ I@@A%/%8%/%:@@ :@;@AiA@G@B@@@ @@@@@A@ @@3@@A @&create %?%G%?%M@б@г$unit%?%O%?%S@@ @@@ 3@.> @A@@г!t!%?%Z"%?%[@А!a@ Y@ -%?%W.%?%Y@@@ @@@ @@@"@@ %@@@9%?%C@@QJ@@@@%&lengthàD%\%dE%\%j@б@гʠ!tO%\%oP%\%p@А!a@ Y@ 3WVVWWWWW@DY%@A]%\%l^%\%n@@@ @@@  @@г>#intk%\%tl%\%w@@ @@@ @@@@@ @@@v%\%` @@K@@ @@(is_emptyĠ%x%%x%@б@г!t%x%%x%@А!a@ Y@ 3@>Y%@A%x%%x%@@@ @@@  @@гf$bool%x%%x%@@ @@@ @@@@@ @@@%x%| @@L@@ @@#addŠ%%%%@б@гD!t%%%%@А!a@ Y@ 3@>Y%@A%%%%@@@ @@@  @@б@г#elt%%%%@А!a%%%%@@@$@@@   @@г$unit%%%%@@ @@@ -@@@@@ 0@@@.@@ 31 @@@ %%@@"M@@@@9(add_iterƠ%%%%@б@г!t %%!%%@А!a@ Y@ 3(''(((((@Xs%@A.%%/%%@@@ @@@  @@б@б@б@гc#eltB%%C%%@А!a"I%%J%%@@@(@@@ $ @@г$unitW%%X%%@@ @@@ 1@@@@@ 4@@б@А!x@ Y@ ?k%%l%%@@г!$unitt%%u%%@@ @@@ N@@@@@ Q@@@"@@ T%% @@б@А!x![%%%%@@г=$unit%%%&@@ @@@ j@@@3@@ m@@@@@ p%% @@@o@@ tr@@@%%@@N@@@@z'max_eltǠ&& &&@б@г3!t&&&&@А!a@ Y@ 3@%@A&&&&@@@ @@@  @@г3&option&&$&&*@г#elt&& &&#@А!a&!&&&&@@@,@@@ ( @@@@@@ - @@@+@@ 0.@@@&&"@@O@@$@@6+get_max_eltȠ&+&3&+&>@б@г!t &+&C &+&D@А!a@ $Y@ 3@Up%@A&+&@&+&B@@@ @@@  @@гI#elt(&+&K)&+&N@А!a/&+&H0&+&J@@@"@@@ ! @@@@@ "!@@@;&+&/@@SP@@@@''pop_maxɠF&O&WG&O&^@б@г̠!tQ&O&cR&O&d@А!a@ .Y@ %3YXXYYYYY@Fa%@A_&O&``&O&b@@@ @@@ ' @@г̠&optionm&O&on&O&u@г#eltw&O&kx&O&n@А!a&!~&O&h&O&j@@@,@@@ )( @@@@@@ +- @@@+@@ ,0.@@@&O&S"@@Q@@$@@6*remove_maxʠ&v&~&v&@б@г !t&v&&v&@А!a@ 5Y@ /3@Up%@A&v&&v&@@@ @@@ 1 @@гn$unit&v&&v&@@ @@@ 2@@@@@ 3@@@&v&z @@R@@ @@%clearˠ&&&&@б@г]!t&&&&@А!a@ Y%@A&&&&@@@ @@@ 8 @@г$unit&&&&@@ @@@ 9@@@@@ :@@@ && @@!S@@ @@$copy̠&&&&@б@г!t&& &&@А!a@ DY@ =3'&&'''''@>Y%@A-&&.&&@@@ @@@ ? @@г!t;&&<&&@А!aB&&C&&@@@"@@@ A @@@@@ B!@@@N&&@@fT@@@@'(of_array͠Y&&Z&&@б@гꠐ%arrayd&&e&&@г#eltn&&o&&@А!a@ NY@ E3vuuvvvvv@Pk/@A|&&}&&@@@ @@@ G @@@&@@@ I #@@г !t&&&&@А!a!&&&&@@@'@@@ K# @@@@@ L&$@@@&&@@U@@@@,'of_listΠ && &'@б@г4$list &'  &'@г㠐#elt &'  &' @А!a@ XY@ O3@Uz/@A &' &'@@@ @@@ Q @@@&@@@ S #@@г^!t &' &'@А!a! &' &'@@@'@@@ U# @@@@@ V&$@@@ &&@@V@@@@,'of_iterϠ ''" '')@б@б@б@г1#elt ''0 ''3@А!a@ gY@ Y3@Ot)@A ''- ''/@@@ @@@ [ @@г٠$unit, ''7- '';@@ @@@ \@@@@@ ]@@б@А!x@ iY@ ^$@ ''@A ''B@@г$unitI ''FJ ''J@@ @@@ _3@@@@@ `6@@@"@@ a9U '', @@б@А!x!@\ ''O] ''Q@@гࠐ!te ''Xf ''Y@А!aUPl ''Um ''W@@@[@@@ cW @@@;@@ dZ@@@&@@ e]y ''+@@@| ''@@W@@@@d.iter_unorderedР 'Z'b 'Z'p@б@б@г#elt 'Z'v 'Z'y@А!a@ uY@ j3@'@A 'Z's 'Z'u@@@ @@@ l @@г]$unit 'Z'} 'Z'@@ @@@ m@@@@@ n@@б@г=!t 'Z' 'Z'@А!a.) 'Z' 'Z'@@@4@@@ p0 @@г$unit 'Z' 'Z'@@ @@@ q=@@@@@ r@@@@,@@ sC 'Z'r @@@ 'Z'^@@X@@@@J.fold_unorderedѠ '' ''@б@б@А#acc@ Y@ v3@a~@A  ''  ''@@б@г.#elt  ''  ''@А!a@ Y@ w  ''  ''@@@ @@@ y @@А#acc)$ $ '' % ''@@@ .@@ z)@@@1@@ {,*@@б@А#acc72 2 '' 3 ''@@б@г!t = '' > ''@А!a0D D '' E ''@@@6@@@ }K @@А#accTO O '' P ''@@@ Y@@ ~T@@@\@@ W%@@@0@@ Z Z '' @@@ ] ''@@ uY@@@@a@A@kA@c/@(@@d@]@|@u9@2@@q@j.@'@@@@)@@3        @+@A'3        @@A %%  ''@@ 1 Output signature of the functor {!MakeMaxPoly}.  '' '(@@@@@@@ %%@3        @ @A@+MakeMaxPolyZ (( ((*@ ]@@Т!E[ ((, ((-@Р5/OrderedPolyType ((0 ((?@3        @1QFA@A@@Y@R@@3@,@@L@E@ @@A@:@k@d@@@T]\@\\@@@\@\@Y|@A76@@УР'MaxPoly (C(E (C(L@3        @BT@M@R![@W@A  @@/#elt!(C(Z!(C(]@+7А!a@ \@ !(C(W!(C(Y@@a@; @A@Ay!t\@ @@@ G@B@@@!/(C(R!0(C(g@@@@!H\@@@Aг!E!;(C(d!<(C(e@!?(C(f@@А!aE!F(C(a!G(C(c@@@$H@@@@\;@A@A@~}@@T!@@@@A@P@L@@@ t7@@@ s@@ r@@%@!@ @@@ q@@@ p@@ o@@@@@@@ n@@@ m@@ l@)@@@%@@@ k@a@@@ j@@@ i@@ h@@ g@>@@@:q@@@ f@@@y|@@@ eS@@@ d@@ c@C;@@@ b@@ a@@ `@H$@@@ _@@ ^@@ ]@@ \@`@ @ @\@@@ [8@@@ Z@@@ Y@@ X@s@@@o@@@ WH@@@ V@@ U@@@@~@@@ TvZ@@@ S@@@ R@@ Q@@U@Q@C@@@ P5@@@ O@@ N@@%@!@@@@ M@@@ L@@ K@@@@@@@ J@@@ I@@ H@@@@@@@ G@@@ F @@@ E@@ D@@}@y@ue@@@ C@@@ Bՠj@@@ A@@ @@@<@8@@@+@@@ ?@@@ >@@ =@ @@@ <@@ ;@@ :@9@@@ 9@@ 8@@ 7@@@@@3@@@ 6@@@ 5@@ 4@@@@ 3@@@ 2@@ 1@@ 0@@@~@@w@Nd@@@ /~@@ .@@ -@@"l@@@ ,@@ +@@ *@@ )@0@"@@0@93""~"~"""""@@A"((+U@@ " n Functor building an implementation of max-priority queues given a totally ordered type for the elements. "(h(h"((@@@@@@@"((f@g@@!  G s!@ ny j@@@@E1@*@3p$@@'aM#@H U  AD@ :@^J 4@@E2A@@;!&54@44@@@4@4@1@@@3""""""""@$@A@}|@qp@fe@[Z@HG@('@@  @@@@@@@@@@3ZD@A@ H************************************************************************"A@@"A@L@ H "BMM"BM@ H OCaml "C"C@ H #D#D3@ I Jean-Christophe Filliâtre # E44# E4@ H #F#F@ H Copyright 2023 CNRS #G#G@ H #H#Hh@ H All rights reserved. This file is distributed under the terms of #"Iii##Ii@ H the GNU Lesser General Public License version 2.1, with the #(J#)J@ H special exception on linking described in the file LICENSE. #.K#/KO@ H #4LPP#5LP@ H************************************************************************#:M#;M@ 0* Priority queues. The {!Pqueue} module implements a data structure of priority queues, given a totally ordered type for elements. This is a mutable data structure. Both min- and max-priority queues are provided. The implementation uses a heap stored in a dynamic array, and is therefore reasonably efficient: accessing the minimum (resp. maximum) element takes constant time, and insertion and removal take time logarithmic in the size of the priority queue. Note that [of_array] runs in linear time (and thus must be preferred to repeated insertions with [add]). It is fine to have several elements with the same priority. Nothing is guaranteed regarding the order in which they will be popped. However, it is guaranteed that the element returned by [min_elt] (or [get_min_elt]) is the one that is removed from the priority queue by [pop_min] (or [remove_min]). This is important in many algorithms, (e.g. when peeking at several priority queues and then selecting one to remove from). @since 5.4 #@8* The type of elements. ! * A total ordering function to compare elements. This is a two-argument function [f] such that [f e1 e2] is zero if the elements [e1] and [e2] are equal, [f e1 e2] is strictly negative if [e1] is smaller than [e2], and [f e1 e2] is strictly positive if [e1] is greater than [e2]. The generic structural comparison function {!Stdlib.compare} is a suitable ordering function for element types such as [int] or [string]. !G =* Input signature of the functors {!MakeMin} and {!MakeMax}. !# !* {1:pqueue Min-priority queues} !?* The type of priority queues.  נ '* The type of priority queue elements.  0* Return a new priority queue, initially empty.  i 5* Return the number of elements in a priority queue.  # H* [is_empty q] is [true] iff [q] is empty, that is, iff [length q = 0]. ݠ <* [add q x] adds the element [x] in the priority queue [q].  d* [add_iter q iter x] adds each element of [x] to the end of [q]. This is [iter (add q) x]. 젠 }* [min_elt q] is an element of [q] with minimal priority or [None] if the queue is empty. The queue is not modified.  * [get_min_elt q] returns an element of [q] with minimal priority, or raises {!Stdlib.Invalid_argument} if the queue is empty. The queue is not modified. Q * [pop_min q] removes and returns an element in queue [q] with minimal priority, or returns [None] if the queue is empty.  q* [remove_min q] removes an element in queue [q] with minimal priority. It does nothing if [q] is empty.  +* [clear q] removes all elements from [q]. p C* [copy q] is a new priority queue with the same elements [q] has. * 9* {1:conversions Conversions from other data structures}  o* [of_array a] returns a new priority queue containing the elements of array [a]. Runs in linear time. Ǡ m* [of_list l] returns a new priority queue containing the elements of list [l]. Runs in linear time. r R* [of_iter iter x] returns a new priority queue containing the elements of [x], obtained from [iter]. For example, [of_iter Seq.iter s] returns a new priority queue containing all the elements of the sequence [s] (provided it is finite). Runs in linear time (excluding the time spent in [iter]). 렠 * {1:iteration Iteration} The order in which the elements of a priority queue are traversed is unspecified. It is a programming error to mutate a priority queue (by adding or removing elements) during an iteration of the queue. Such an error may be detected and signaled by the backing dynamic array implementation, but this is not guaranteed. Р * [iter_unordered f q] applies [f] to all elements in [q]. The order in which the elements are passed to [f] is unspecified. The behavior is not specified if the priority queue is modified by [f] during the iteration. r 3* [fold_unordered f accu q] is [(f (... (f (f accu x1) x2) ...) xn)] where [x1,x2,...,xn] are the elements of [q]. The order in which the elements are passed to [f] is unspecified. The behavior is not specified if the priority queue is modified by [f] during the iteration.  .* Output signature of the functor {!MakeMin}.  x* Functor building an implementation of the min-priority queue structure given a totally ordered type for elements.  .* Output signature of the functor {!MakeMax}.  x* Functor building an implementation of the max-priority queue structure given a totally ordered type for elements. ] T* {1 Polymorphic priority queues} The following, more complex functors create polymorphic queues of type ['a t], just like other polymorphic containers (lists, arrays...). They require a notion of "polymorphic elements" ['a elt] that can be compared without depending on the values of ['a]. One usage scenario is when the user wants to pass priorities separately from the value stored in the queue. This is done by using pairs [priority * 'a] as elements. {[ module Prio : OrderedType = ... module PrioQueue = Pqueue.MakeMinPoly(struct type 'a t = Prio.t * 'a let compare (p1, _) (p2, _) = Prio.compare p1 p2 end) (* for example, we now have: *) PrioQueue.add: 'a PrioQueue.t -> Prio.t * 'a -> unit PrioQueue.min_elt: 'a PrioQueue.t -> (Prio.t * 'a) option ]} L $* The polymorphic type of elements. ᠠ 5* [compare] is a total order on values of type {!t}. f E* Input signature of the functors {!MakeMinPoly} and {!MakeMaxPoly}. B 2* Output signature of the functor {!MakeMinPoly}.  5 o* Functor building an implementation of min-priority queues given a totally ordered type for the elements.  > 2* Output signature of the functor {!MakeMaxPoly}.  o* Functor building an implementation of max-priority queues given a totally ordered type for the elements. @?)../ocamlc0-strict-sequence(-absname"-w5+a-4-9-41-42-44-45-48"-g+-warn-error"+A*-bin-annot)-nostdlib*-principal"-o2stdlib__Pqueue.cmi"-c## D/builds/workspace/precheck/flambda/false/label/ocaml-linux-32/stdlib @@0(B>wK3########@#@@8CamlinternalFormatBasics0%FU(Q/Tu&Stdlib0Lku]8_٠#0> ? .*Y8@0> ? .*Y8AZ^@@U°y +@6  P@@q@v~"@"\@  &@5nِ@@;@  "@$P@!"D@,u@@@@ } <@ 5 `/O@  C}go@:@ڐ@Z@02<@I  @  9@i@ G@!!@""@ڰɐL@ՐH@7B@ 8Wp@ET@@ N j x Ȱ7p@@:@@  @@ڐ\@^  @@,M@ !!@Ր% ِE@ @@@zʰ@l!!@"D"L@@.g@@@{@0qQ}@@@!L!@ְ@@@P@@