úÎēĻĐþF      !"#$%&'()*+,-./0123456789:;<=>?@ABCDESafe234TF Hughes's efficient sequence typeA mapping from keys k to priorites p and values v/. It is strict in keys, priorities and values.GE k p v binds the key k to the value v with priority p.O(1) True if the queue is empty.O(1)# The number of elements in a queue.O(log n), Check if a key is present in the the queue.O(log n)+ The priority and value of a given key, or H if the key is not bound.O(1)& The element with the lowest priority.O(1) The empty queue.O(1) Build a queue with one element.O(log n)ļ Insert a new key, priority and value into the queue. If the key is already present in the queue, the associated priority and value are replaced with the supplied priority and value. O(log n)„ Delete a key and its priority and value from the queue. When the key is not a member of the queue, the original queue is returned. O(log n)Ļ Delete the binding with the least priority, and return the rest of the queue stripped of that binding. In case the queue is empty, the empty queue is returned again. O(log n) The expression alter f k queue alters the value x at k, or absence thereof.  s can be used to insert, delete, or update a value in a queue. It also allows you to calculate an additional value b. O(log n) A variant of  ? which works on the element with the minimum priority. Unlike  A, this variant also allows you to change the key of the element.  O(n*log n)ŧ Build a queue from a list of (key, priority, value) tuples. If the list contains more than one priority and value for the same key, the last priority and value for the key is retained.O(n)e Convert a queue to a list of (key, priority, value) tuples. The order of the list is not specified.O(n). Obtain the list of present keys in the queue.O(n) Convert to an ascending list.O(log n)― Insert a new key, priority and value into the queue. If the key is already present in the queue, then the evicted priority and value can be found the first element of the returned tuple.O(log n)Ģ Delete a key and its priority and value from the queue. If the key was present, the associated priority and value are returned in addition to the updated queue.O(log n)c Retrieve the binding with the least priority, and the rest of the queue stripped of that binding.FReturn a list of elements ordered by key whose priorities are at most pt‚, and the rest of the queue stripped of these elements. The returned list of elements can be in any order: no guarantees there.O(n)! Modify every value in the queue.O(n)y Strict fold over every key, priority and value in the queue. The order in which the fold is performed is not specified.I·Take two pennants and returns a new pennant that is the union of the two with the precondition that the keys in the first tree are strictly smaller than the keys in the second tree.JiWhen priorities are equal, the tree with the lowest key wins. This is important to have a deterministic K, which requires on . pulling out the elements in the right order.LBalance factorO(n^2)# Internal function to check if the H is valid, i.e. if all invariants hold. This should always be the case.MFMNOPQRSTUVWXGY Z[IJL\]^_`abcdefghijklmnopqrstuvwxyz{|1NOPQRSTUWXGY [I]^_hijklmnoCFMNOPQRSTUVWXGY Z[IJL\]^_`abcdefghijklmnopqrstuvwxyz{|w5SafeT  :(c) Clark Gaebel 2012 (c) Johan Tibel 2012 BSD-stylelibraries@haskell.org provisionalportable TrustworthyB}0Return a word where only the highest bit is set.}~}}~Safe234 A priority search queue with Int keys and priorities of type p and values of type v.. It is strict in keys, priorities and values.EWe store masks as the index of the bit that determines the branching.O(1) True if the queue is empty.O(n), The number of elements stored in the queue. O(min(n,W)), Check if a key is present in the the queue. O(min(n,W))+ The priority and value of a given key, or H if the key is not bound.O(1)& The element with the lowest priority.O(1) The empty queue.O(1) Build a queue with one element.  O(min(n,W))ļ Insert a new key, priority and value into the queue. If the key is already present in the queue, the associated priority and value are replaced with the supplied priority and value.€OInternal function to insert a key that is *not* present in the priority queue.Link! O(min(n,W))„ Delete a key and its priority and value from the queue. When the key is not a member of the queue, the original queue is returned." O(min(n,W))Ļ Delete the binding with the least priority, and return the rest of the queue stripped of that binding. In case the queue is empty, the empty queue is returned again.# O(min(n,W)) The expression alter f k queue alters the value x at k, or absence thereof. #s can be used to insert, delete, or update a value in a queue. It also allows you to calculate an additional value b.$ O(min(n,W)) A variant of #? which works on the element with the minimum priority. Unlike #A, this variant also allows you to change the key of the element.‚Smart constructor for a ƒ, node whose left subtree could have become „.…Smart constructor for a ƒ- node whose right subtree could have become „.% O(n*min(n,W))ŧ Build a queue from a list of (key, priority, value) tuples. If the list contains more than one priority and value for the same key, the last priority and value for the key is retained.&O(n)e Convert a queue to a list of (key, priority, value) tuples. The order of the list is not specified.'O(n). Obtain the list of present keys in the queue.( O(min(n,W))― Insert a new key, priority and value into the queue. If the key is already present in the queue, then the evicted priority and value can be found the first element of the returned tuple.) O(min(n,W))Ģ Delete a key and its priority and value from the queue. If the key was present, the associated priority and value are returned in addition to the updated queue.* O(min(n,W))c Retrieve the binding with the least priority, and the rest of the queue stripped of that binding.+FReturn a list of elements ordered by key whose priorities are at most pt‚, and the rest of the queue stripped of these elements. The returned list of elements can be in any order: no guarantees there.,O(n)! Modify every value in the queue.-O(n)y Strict fold over every key, priority and value in the queue. The order in which the fold is performed is not specified.†-Internal function that merges two *disjoint* #s that share the same prefix mask.‡ėInternal function to insert a key with priority larger than the maximal priority in the heap. This is always the case when using the PSQ as the basis to implement a LRU cache, which associates a access-tick-number with every element.ˆ4This name is not chosen well anymore. This function:YEither inserts a value at a new key with a prio higher than the max of the entire PSQ.•Or, overrides the value at the key with a prio strictly higher than the original prio at that key (but not necessarily the max of the entire PSQ).‰(This can NOT be used to delete elements..O(n^2)# Internal function to check if the H is valid, i.e. if all invariants hold. This should always be the case.6Š‹Œƒ„Ž‘’“”• €!"#$‚…%&'()*+,-†‡–ˆ—‰.˜™š›œ'ƒ„Ž €!"#$%&'()*+,-‡–ˆ—‰.˜™š›1Š‹Œƒ„Ž‘’“”• €!"#$‚…%&'()*+,-†‡–ˆ—‰.˜™š›œNone234IT/*A priority search queue with keys of type k and priorities of type p and values of type v.. It is strict in keys, priorities and values.žSSmart constructor which takes care of placing the minimum element directly in the Ÿ.0O(1) True if the queue is empty.1O(n)* The number of elements stored in the PSQ.2 O(min(n,W)), Check if a key is present in the the queue.3 O(min(n,W))+ The priority and value of a given key, or H if the key is not bound.4O(1)& The element with the lowest priority.5O(1) The empty queue.6O(1) Build a queue with one element.7 O(min(n,W))ļ Insert a new key, priority and value into the queue. If the key is already present in the queue, the associated priority and value are replaced with the supplied priority and value.8 O(min(n,W))„ Delete a key and its priority and value from the queue. When the key is not a member of the queue, the original queue is returned.9 O(min(n,W))Ļ Delete the binding with the least priority, and return the rest of the queue stripped of that binding. In case the queue is empty, the empty queue is returned again.: O(min(n,W)) The expression alter f k queue alters the value x at k, or absence thereof. :s can be used to insert, delete, or update a value in a queue. It also allows you to calculate an additional value b.; O(min(n,W)) A variant of :? which works on the element with the minimum priority. Unlike :A, this variant also allows you to change the key of the element.< O(n*min(n,W))ŧ Build a queue from a list of (key, priority, value) tuples. If the list contains more than one priority and value for the same key, the last priority and value for the key is retained.=O(n)e Convert a queue to a list of (key, priority, value) tuples. The order of the list is not specified.>O(n). Obtain the list of present keys in the queue.? O(min(n,W))― Insert a new key, priority and value into the queue. If the key is already present in the queue, then the evicted priority and value can be found the first element of the returned tuple.@ O(min(n,W))Ģ Delete a key and its priority and value from the queue. If the key was present, the associated priority and value are returned in addition to the updated queue.A O(min(n,W))c Retrieve the binding with the least priority, and the rest of the queue stripped of that binding.BFReturn a list of elements ordered by key whose priorities are at most pt‚, and the rest of the queue stripped of these elements. The returned list of elements can be in any order: no guarantees there.CO(n)! Modify every value in the queue.DO(n)y Strict fold over every key, priority and value in the queue. The order in which the fold is performed is not specified.EO(n^2)# Internal function to check if the /H is valid, i.e. if all invariants hold. This should always be the case.#/ ŸĄžĒ0123456789:;<=>?@ABCDĢĪĨEĶ§ĻĐ/ ŸĄž0123456789:;<=>?@ABCDĢĪĨE!/ ŸĄžĒ0123456789:;<=>?@ABCDĢĪĨEĶ§ĻĐNone/0123456789:;<=>?@ABCDE/0123456789:;<=>?@ABCDESafe !"#$%&'()*+,-. !"#$%&'()*+,-.Š           !     "#$%&'()*+,"-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwOPxyz{|!}~hfuO€‚'psqueues-0.2.3.0-Imih248Jg2BE8bRnowLdpL Data.OrdPSQ Data.IntPSQ Data.HashPSQData.OrdPSQ.Internal Data.BitUtilData.IntPSQ.InternalData.HashPSQ.InternalOrdPSQnullsizememberlookupfindMinempty singletoninsertdelete deleteMinalteralterMinfromListtoListkeys toAscList insertView deleteViewminView atMostViewmapfold'validIntPSQHashPSQSequElembaseGHC.BaseNothingplaybeatsghc-prim GHC.Classes==omegaTourViewNullSinglePlayLTreeStartLLoserRLoserSizeVoidWinnerE secondBesttourViewsize'leftrightmaxKeylloserrloserlbalancerbalance lbalanceLeft lbalanceRight rbalanceLeft rbalanceRight lsingleLeft rsingleLeft lsingleRight rsingleRight ldoubleLeft ldoubleRight rdoubleLeft rdoubleRighthasDuplicateKeyshasMinHeapPropertyhasBinarySearchTreePropertyhasCorrectSizeAnnotations moduleError emptySequ singleSequ<> seqToList $fNFDataLTree $fEqOrdPSQ$fNFDataOrdPSQ $fNFDataElemhighestBitMaskshiftRLMaskunsafeInsertNewlink binShrinkLBinNil binShrinkRmergeunsafeInsertIncreasePriority unsafeInsertWithIncreasePriorityunsafeLookupIncreasePrioritySideLRTipKeyNat natFromInt intFromNatzeronomatchmaskW branchMask unsafeInsertIncreasePriorityView$unsafeInsertWithIncreasePriorityView hasBadNils validMask $fEqIntPSQ$fNFDataIntPSQmkBucketBucketBtoBucket validBucket $fEqHashPSQ$fNFDataBucket