-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Priority Search Queue -- -- A priority search queue efficiently supports the operations of -- both a search tree and a priority queue. A Binding is a product -- of a key and a priority. Bindings can be inserted, deleted, modified -- and queried in logarithmic time, and the binding with the least -- priority can be retrieved in constant time. A queue can be built from -- a list of bindings, sorted by keys, in linear time. @package PSQueue @version 1.2.0 module Data.PSQueue.Internal -- | k :-> p binds the key k with the priority -- p. data Binding k p (:->) :: !k -> !p -> Binding k p infix 0 :-> -- | The key of a binding key :: Binding k p -> k -- | The priority of a binding prio :: Binding k p -> p -- | A mapping from keys k to priorites p. data PSQ k p Void :: PSQ k p Winner :: !k -> !p -> !LTree k p -> !k -> PSQ k p -- | O(1) The number of bindings in a queue. size :: PSQ k p -> Int -- | O(1) True if the queue is empty. null :: PSQ k p -> Bool -- | O(log n) The priority of a given key, or Nothing if the key is -- not bound. lookup :: Ord k => k -> PSQ k p -> Maybe p empty :: PSQ k p -- | O(1) Build a queue with one binding. singleton :: k -> p -> PSQ k p -- | O(log n) Insert a binding into the queue. insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p -- | O(log n) Insert a binding with a combining function. insertWith :: (Ord k, Ord p) => (p -> p -> p) -> k -> p -> PSQ k p -> PSQ k p -- | O(log n) Insert a binding with a combining function. insertWithKey :: (Ord k, Ord p) => (k -> p -> p -> p) -> k -> p -> PSQ k p -> PSQ k p -- | O(log n) Remove a binding from the queue. delete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p -- | O(log n) Adjust the priority of a key. adjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k p -- | O(log n) Adjust the priority of a key. adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k p -- | O(log n) The expression (update f k q) updates the -- priority p bound k (if it is in the queue). If -- (f p) is Nothing, the binding is deleted. If it is -- (Just z), the key k is bound to the new -- priority z. update :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k p -- | O(log n). The expression (updateWithKey f k q) updates -- the priority p bound k (if it is in the queue). If -- (f k p) is Nothing, the binding is deleted. If it is -- (Just z), the key k is bound to the new -- priority z. updateWithKey :: (Ord k, Ord p) => (k -> p -> Maybe p) -> k -> PSQ k p -> PSQ k p -- | O(log n). The expression (alter f k q) alters -- the priority p bound to k, or absence thereof. alter -- can be used to insert, delete, or update a priority in a queue. alter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k p -- | O(n) The keys of a priority queue keys :: PSQ k p -> [k] -- | O(n log n) Build a queue from a list of bindings. fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p -- | O(n) Build a queue from a list of bindings in order of -- ascending keys. The precondition that the keys are ascending is not -- checked. fromAscList :: (Eq k, Ord p) => [Binding k p] -> PSQ k p -- | O(n) Build a queue from a list of distinct bindings in order of -- ascending keys. The precondition that keys are distinct and ascending -- is not checked. fromDistinctAscList :: Ord p => [Binding k p] -> PSQ k p foldm :: (a -> a -> a) -> a -> [a] -> a -- | O(n) Convert a queue to a list. toList :: PSQ k p -> [Binding k p] -- | O(n) Convert a queue to a list in ascending order of keys. toAscList :: PSQ k p -> [Binding k p] toAscLists :: PSQ k p -> Sequ (Binding k p) -- | O(n) Convert a queue to a list in descending order of keys. toDescList :: PSQ k p -> [Binding k p] toDescLists :: PSQ k p -> Sequ (Binding k p) -- | O(1) The binding with the lowest priority. findMin :: PSQ k p -> Maybe (Binding k p) -- | O(log n) Remove the binding with the lowest priority. deleteMin :: Ord p => PSQ k p -> PSQ k p -- | O(log n) Retrieve the binding with the least priority, and the -- rest of the queue stripped of that binding. minView :: Ord p => PSQ k p -> Maybe (Binding k p, PSQ k p) secondBest :: Ord p => LTree k p -> k -> PSQ k p -- | O(r(log n - log r) atMost p q is a list of all the -- bindings in q with priority less than p, in order of -- ascending keys. Effectively, -- -- 
--   atMost p' q = filter (\(k:->p) -> p<=p') . toList
--
atMost :: Ord p => p -> PSQ k p -> [Binding k p] atMosts :: Ord p => p -> PSQ k p -> Sequ (Binding k p) -- | O(r(log n - log r)) atMostRange p (l,u) q is a list of -- all the bindings in q with a priority less than p -- and a key in the range (l,u) inclusive. Effectively, -- -- 
--   atMostRange p' (l,u) q = filter (\(k:->p) -> l<=k && k<=u ) . atMost p'
--
atMostRange :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> [Binding k p] atMostRanges :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> Sequ (Binding k p) inrange :: Ord a => a -> (a, a) -> Bool -- | Right fold over the bindings in the queue, in key order. foldr :: (Binding k p -> b -> b) -> b -> PSQ k p -> b -- | Left fold over the bindings in the queue, in key order. foldl :: (b -> Binding k p -> b) -> b -> PSQ k p -> b type Size = Int data LTree k p Start :: LTree k p LLoser :: {-# UNPACK #-} !Size -> !k -> !p -> !LTree k p -> !k -> !LTree k p -> LTree k p RLoser :: {-# UNPACK #-} !Size -> !k -> !p -> !LTree k p -> !k -> !LTree k p -> LTree k p size' :: LTree k p -> Size left :: LTree a b -> LTree a b right :: LTree a b -> LTree a b maxKey :: PSQ k p -> k lloser :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p rloser :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p omega :: Int lbalance :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p rbalance :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p lbalanceLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p lbalanceRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p rbalanceLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p rbalanceRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p lsingleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p rsingleLeft :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p lsingleRight :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p rsingleRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p ldoubleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p ldoubleRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p rdoubleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p rdoubleRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p play :: Ord p => PSQ k p -> PSQ k p -> PSQ k p data TourView k p Null :: TourView k p Single :: !k -> !p -> TourView k p Play :: !PSQ k p -> !PSQ k p -> TourView k p tourView :: PSQ k p -> TourView k p instance (GHC.Read.Read k, GHC.Read.Read p) => GHC.Read.Read (Data.PSQueue.Internal.Binding k p) instance (GHC.Show.Show k, GHC.Show.Show p) => GHC.Show.Show (Data.PSQueue.Internal.Binding k p) instance (GHC.Classes.Ord k, GHC.Classes.Ord p) => GHC.Classes.Ord (Data.PSQueue.Internal.Binding k p) instance (GHC.Classes.Eq k, GHC.Classes.Eq p) => GHC.Classes.Eq (Data.PSQueue.Internal.Binding k p) instance GHC.Show.Show a => GHC.Show.Show (Data.PSQueue.Internal.Sequ a) instance (GHC.Show.Show k, GHC.Show.Show p) => GHC.Show.Show (Data.PSQueue.Internal.PSQ k p) instance (GHC.Classes.Eq k, GHC.Classes.Eq p) => GHC.Classes.Eq (Data.PSQueue.Internal.PSQ k p) -- | A priority search queue (henceforth queue) efficiently -- supports the operations of both a search tree and a priority queue. A -- Binding is a product of a key and a priority. Bindings can be -- inserted, deleted, modified and queried in logarithmic time, and the -- binding with the least priority can be retrieved in constant time. A -- queue can be built from a list of bindings, sorted by keys, in linear -- time. -- -- This implementation is due to Ralf Hinze. -- -- module Data.PSQueue -- | k :-> p binds the key k with the priority -- p. data Binding k p (:->) :: !k -> !p -> Binding k p infix 0 :-> -- | The key of a binding key :: Binding k p -> k -- | The priority of a binding prio :: Binding k p -> p -- | A mapping from keys k to priorites p. data PSQ k p -- | O(1) The number of bindings in a queue. size :: PSQ k p -> Int -- | O(1) True if the queue is empty. null :: PSQ k p -> Bool -- | O(log n) The priority of a given key, or Nothing if the key is -- not bound. lookup :: Ord k => k -> PSQ k p -> Maybe p empty :: PSQ k p -- | O(1) Build a queue with one binding. singleton :: k -> p -> PSQ k p -- | O(log n) Insert a binding into the queue. insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p -- | O(log n) Insert a binding with a combining function. insertWith :: (Ord k, Ord p) => (p -> p -> p) -> k -> p -> PSQ k p -> PSQ k p -- | O(log n) Remove a binding from the queue. delete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p -- | O(log n) Adjust the priority of a key. adjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k p -- | O(log n) Adjust the priority of a key. adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k p -- | O(log n) The expression (update f k q) updates the -- priority p bound k (if it is in the queue). If -- (f p) is Nothing, the binding is deleted. If it is -- (Just z), the key k is bound to the new -- priority z. update :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k p -- | O(log n). The expression (updateWithKey f k q) updates -- the priority p bound k (if it is in the queue). If -- (f k p) is Nothing, the binding is deleted. If it is -- (Just z), the key k is bound to the new -- priority z. updateWithKey :: (Ord k, Ord p) => (k -> p -> Maybe p) -> k -> PSQ k p -> PSQ k p -- | O(log n). The expression (alter f k q) alters -- the priority p bound to k, or absence thereof. alter -- can be used to insert, delete, or update a priority in a queue. alter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k p -- | O(n) The keys of a priority queue keys :: PSQ k p -> [k] -- | O(n) Convert a queue to a list. toList :: PSQ k p -> [Binding k p] -- | O(n) Convert a queue to a list in ascending order of keys. toAscList :: PSQ k p -> [Binding k p] -- | O(n) Convert a queue to a list in descending order of keys. toDescList :: PSQ k p -> [Binding k p] -- | O(n log n) Build a queue from a list of bindings. fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p -- | O(n) Build a queue from a list of bindings in order of -- ascending keys. The precondition that the keys are ascending is not -- checked. fromAscList :: (Eq k, Ord p) => [Binding k p] -> PSQ k p -- | O(n) Build a queue from a list of distinct bindings in order of -- ascending keys. The precondition that keys are distinct and ascending -- is not checked. fromDistinctAscList :: Ord p => [Binding k p] -> PSQ k p -- | O(1) The binding with the lowest priority. findMin :: PSQ k p -> Maybe (Binding k p) -- | O(log n) Remove the binding with the lowest priority. deleteMin :: Ord p => PSQ k p -> PSQ k p -- | O(log n) Retrieve the binding with the least priority, and the -- rest of the queue stripped of that binding. minView :: Ord p => PSQ k p -> Maybe (Binding k p, PSQ k p) -- | O(r(log n - log r) atMost p q is a list of all the -- bindings in q with priority less than p, in order of -- ascending keys. Effectively, -- -- 
--   atMost p' q = filter (\(k:->p) -> p<=p') . toList
--
atMost :: Ord p => p -> PSQ k p -> [Binding k p] -- | O(r(log n - log r)) atMostRange p (l,u) q is a list of -- all the bindings in q with a priority less than p -- and a key in the range (l,u) inclusive. Effectively, -- -- 
--   atMostRange p' (l,u) q = filter (\(k:->p) -> l<=k && k<=u ) . atMost p'
--
atMostRange :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> [Binding k p] -- | Right fold over the bindings in the queue, in key order. foldr :: (Binding k p -> b -> b) -> b -> PSQ k p -> b -- | Left fold over the bindings in the queue, in key order. foldl :: (b -> Binding k p -> b) -> b -> PSQ k p -> b