-- 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.2

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
ltreeDot :: (Show k, Show p) => PSQ k p -> String
pennantDot :: (Show k, Show p, Ord p) => PSQ k p -> String
instance (GHC.Classes.Eq k, GHC.Classes.Eq p) => GHC.Classes.Eq (Data.PSQueue.Internal.Binding k p)
instance (GHC.Classes.Eq k, GHC.Classes.Eq p) => GHC.Classes.Eq (Data.PSQueue.Internal.PSQ k p)
instance (GHC.Classes.Ord k, GHC.Classes.Ord p) => GHC.Classes.Ord (Data.PSQueue.Internal.Binding k p)
instance (GHC.Internal.Read.Read k, GHC.Internal.Read.Read p) => GHC.Internal.Read.Read (Data.PSQueue.Internal.Binding k p)
instance (GHC.Internal.Show.Show k, GHC.Internal.Show.Show p) => GHC.Internal.Show.Show (Data.PSQueue.Internal.Binding k p)
instance (GHC.Internal.Show.Show k, GHC.Internal.Show.Show p) => GHC.Internal.Show.Show (Data.PSQueue.Internal.PSQ k p)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.PSQueue.Internal.Sequ a)

-- | 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.
--   
--   
--   
- Hinze, R., A Simple Implementation Technique for Priority
--   Search Queues, ICFP 2001, pp. 110-121
--   
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
