-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Pure priority search queues -- -- The psqueues package provides Priority Search Queues in three -- different flavors. -- -- -- -- Each of the three implementations provides the same API, so they can -- be used interchangeably. The benchmarks show how they perform relative -- to one another, and also compared to the other Priority Search Queue -- implementations on Hackage: PSQueue and -- fingertree-psqueue. -- -- -- -- Typical applications of Priority Search Queues include: -- -- @package psqueues @version 0.2.2.2 -- | An OrdPSQ uses the Ord instance of the key type to build -- a priority search queue. -- -- It is based on Ralf Hinze's work. -- -- -- -- http://citeseer.ist.psu.edu/hinze01simple.html -- -- This means it is similar to the PSQueue package but our -- benchmarks showed it perform quite a bit faster. module Data.OrdPSQ -- | A mapping from keys k to priorites p and values -- v. It is strict in keys, priorities and values. data OrdPSQ k p v -- | O(1) True if the queue is empty. null :: OrdPSQ k p v -> Bool -- | O(1) The number of elements in a queue. size :: OrdPSQ k p v -> Int -- | O(log n) Check if a key is present in the the queue. member :: Ord k => k -> OrdPSQ k p v -> Bool -- | O(log n) The priority and value of a given key, or -- Nothing if the key is not bound. lookup :: (Ord k) => k -> OrdPSQ k p v -> Maybe (p, v) -- | O(1) The element with the lowest priority. findMin :: OrdPSQ k p v -> Maybe (k, p, v) -- | O(1) The empty queue. empty :: OrdPSQ k p v -- | O(1) Build a queue with one element. singleton :: k -> p -> v -> OrdPSQ k p v -- | 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. insert :: (Ord k, Ord p) => k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v -- | 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. delete :: (Ord k, Ord p) => k -> OrdPSQ k p v -> OrdPSQ k p v -- | 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. deleteMin :: (Ord k, Ord p) => OrdPSQ k p v -> OrdPSQ k p v -- | O(log n) The expression alter f k queue alters the -- value x at k, or absence thereof. alter can -- be used to insert, delete, or update a value in a queue. It also -- allows you to calculate an additional value b. alter :: (Ord k, Ord p) => (Maybe (p, v) -> (b, Maybe (p, v))) -> k -> OrdPSQ k p v -> (b, OrdPSQ k p v) -- | O(log n) A variant of alter which works on the element -- with the minimum priority. Unlike alter, this variant also -- allows you to change the key of the element. alterMin :: (Ord k, Ord p) => (Maybe (k, p, v) -> (b, Maybe (k, p, v))) -> OrdPSQ k p v -> (b, OrdPSQ k p v) -- | 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. fromList :: (Ord k, Ord p) => [(k, p, v)] -> OrdPSQ k p v -- | O(n) Convert a queue to a list of (key, priority, value) -- tuples. The order of the list is not specified. toList :: OrdPSQ k p v -> [(k, p, v)] -- | O(n) Convert to an ascending list. toAscList :: OrdPSQ k p v -> [(k, p, v)] -- | O(n) Obtain the list of present keys in the queue. keys :: OrdPSQ k p v -> [k] -- | 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. insertView :: (Ord k, Ord p) => k -> p -> v -> OrdPSQ k p v -> (Maybe (p, v), OrdPSQ k p v) -- | 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. deleteView :: (Ord k, Ord p) => k -> OrdPSQ k p v -> Maybe (p, v, OrdPSQ k p v) -- | O(log n) Retrieve the binding with the least priority, and the -- rest of the queue stripped of that binding. minView :: (Ord k, Ord p) => OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v) -- | O(n) Modify every value in the queue. map :: forall k p v w. (k -> p -> v -> w) -> OrdPSQ k p v -> OrdPSQ k p w -- | O(n) Strict fold over every key, priority and value in the -- queue. The order in which the fold is performed is not specified. fold' :: (k -> p -> v -> a -> a) -> a -> OrdPSQ k p v -> a -- | O(n^2) Internal function to check if the OrdPSQ is -- valid, i.e. if all invariants hold. This should always be the case. valid :: (Ord k, Ord p) => OrdPSQ k p v -> Bool -- | IntPSQ fixes the key type to Int. It is generally much -- faster than an OrdPSQ. -- -- Many operations have a worst-case complexity of O(min(n,W)). This -- means that the operation can -- become linear in the number of -- elements with a maximum of W -- the number of bits in an Int (32 or -- 64). module Data.IntPSQ -- | 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. data IntPSQ p v -- | O(1) True if the queue is empty. null :: IntPSQ p v -> Bool -- | O(n) The number of elements stored in the queue. size :: IntPSQ p v -> Int -- | O(min(n,W)) Check if a key is present in the the queue. member :: Int -> IntPSQ p v -> Bool -- | O(min(n,W)) The priority and value of a given key, or -- Nothing if the key is not bound. lookup :: Int -> IntPSQ p v -> Maybe (p, v) -- | O(1) The element with the lowest priority. findMin :: Ord p => IntPSQ p v -> Maybe (Int, p, v) -- | O(1) The empty queue. empty :: IntPSQ p v -- | O(1) Build a queue with one element. singleton :: Ord p => Int -> p -> v -> IntPSQ p v -- | 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. insert :: Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v -- | 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. delete :: Ord p => Int -> IntPSQ p v -> IntPSQ p v -- | 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. deleteMin :: Ord p => IntPSQ p v -> IntPSQ p v -- | O(min(n,W)) The expression alter f k queue alters the -- value x at k, or absence thereof. alter can -- be used to insert, delete, or update a value in a queue. It also -- allows you to calculate an additional value b. alter :: Ord p => (Maybe (p, v) -> (b, Maybe (p, v))) -> Int -> IntPSQ p v -> (b, IntPSQ p v) -- | O(min(n,W)) A variant of alter which works on the -- element with the minimum priority. Unlike alter, this variant -- also allows you to change the key of the element. alterMin :: Ord p => (Maybe (Int, p, v) -> (b, Maybe (Int, p, v))) -> IntPSQ p v -> (b, IntPSQ p v) -- | 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. fromList :: Ord p => [(Int, p, v)] -> IntPSQ p v -- | O(n) Convert a queue to a list of (key, priority, value) -- tuples. The order of the list is not specified. toList :: IntPSQ p v -> [(Int, p, v)] -- | O(n) Obtain the list of present keys in the queue. keys :: IntPSQ p v -> [Int] -- | 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. insertView :: Ord p => Int -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v) -- | 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. deleteView :: Ord p => Int -> IntPSQ p v -> Maybe (p, v, IntPSQ p v) -- | O(min(n,W)) Retrieve the binding with the least priority, and -- the rest of the queue stripped of that binding. minView :: Ord p => IntPSQ p v -> Maybe (Int, p, v, IntPSQ p v) -- | O(n) Modify every value in the queue. map :: (Int -> p -> v -> w) -> IntPSQ p v -> IntPSQ p w -- | O(n) Strict fold over every key, priority and value in the -- queue. The order in which the fold is performed is not specified. fold' :: (Int -> p -> v -> a -> a) -> a -> IntPSQ p v -> a -- | O(n^2) Internal function to check if the IntPSQ is -- valid, i.e. if all invariants hold. This should always be the case. valid :: Ord p => IntPSQ p v -> Bool -- | A HashPSQ offers very similar performance to IntPSQ. -- In case of collisions, it uses an OrdPSQ locally to solve -- those. -- -- This means worst case complexity is usually given by O(min(n,W), -- log n), where W is the number of bits in an Int. -- This simplifies to O(min(n,W)) since log n is always -- smaller than W on current machines. module Data.HashPSQ -- | 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. data HashPSQ k p v -- | O(1) True if the queue is empty. null :: HashPSQ k p v -> Bool -- | O(n) The number of elements stored in the PSQ. size :: HashPSQ k p v -> Int -- | O(min(n,W)) Check if a key is present in the the queue. member :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Bool -- | O(min(n,W)) The priority and value of a given key, or -- Nothing if the key is not bound. lookup :: (Ord k, Hashable k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v) -- | O(1) The element with the lowest priority. findMin :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v) -- | O(1) The empty queue. empty :: HashPSQ k p v -- | O(1) Build a queue with one element. singleton :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -- | 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. insert :: (Ord k, Hashable k, Ord p) => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v -- | 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. delete :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> HashPSQ k p v -- | 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. deleteMin :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> HashPSQ k p v -- | O(min(n,W)) The expression alter f k queue alters the -- value x at k, or absence thereof. alter can -- be used to insert, delete, or update a value in a queue. It also -- allows you to calculate an additional value b. alter :: (Hashable k, Ord k, Ord p) => (Maybe (p, v) -> (b, Maybe (p, v))) -> k -> HashPSQ k p v -> (b, HashPSQ k p v) -- | O(min(n,W)) A variant of alter which works on the -- element with the minimum priority. Unlike alter, this variant -- also allows you to change the key of the element. alterMin :: (Hashable k, Ord k, Ord p) => (Maybe (k, p, v) -> (b, Maybe (k, p, v))) -> HashPSQ k p v -> (b, HashPSQ k p v) -- | 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. fromList :: (Hashable k, Ord k, Ord p) => [(k, p, v)] -> HashPSQ k p v -- | O(n) Convert a queue to a list of (key, priority, value) -- tuples. The order of the list is not specified. toList :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [(k, p, v)] -- | O(n) Obtain the list of present keys in the queue. keys :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [k] -- | 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. insertView :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v) -- | 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. deleteView :: forall k p v. (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v) -- | O(min(n,W)) Retrieve the binding with the least priority, and -- the rest of the queue stripped of that binding. minView :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v) -- | O(n) Modify every value in the queue. map :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w -- | O(n) Strict fold over every key, priority and value in the -- queue. The order in which the fold is performed is not specified. fold' :: (k -> p -> v -> a -> a) -> a -> HashPSQ k p v -> a -- | O(n^2) Internal function to check if the HashPSQ is -- valid, i.e. if all invariants hold. This should always be the case. valid :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Bool