-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Implementation of priority search queues as finger trees.
--   
--   An implementation of priority search queues: a datastructure holding
--   key/priority bindings having fast operations both for extracting the
--   element with minimum priority and for modifying and looking up
--   elements by key.
@package fingertree-psqueue
@version 0.3

module Data.FingerTree.PSQueue
data Binding k p
(:->) :: k -> p -> Binding k p
data PSQ k p

-- | O(1). The number of bindings in a queue.
size :: (Ord k, Ord p) => PSQ k p -> Int

-- | O(1). Test if a queue is empty.
null :: (Ord k, Ord p) => PSQ k p -> Bool

-- | O(log n). Determine if a key is in the queue, and its priority.
lookup :: (Ord k, Ord p) => k -> PSQ k p -> Maybe p

-- | O(1). The empty queue.
empty :: (Ord k, Ord p) => PSQ k p

-- | O(1). Construct a queue with a single key/priority binding.
singleton :: (Ord k, Ord p) => k -> p -> PSQ k p

-- | O(log n). Alters a priority search queue such that <tt>lookup k (alter
--   f k q) = f (lookup k q)</tt>. This 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(log n). Delete a key from a queue.
delete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p

-- | O(log n). Adjust the priority of a key in the queue, provided that key
--   exists.
adjust :: (Ord k, Ord p) => (p -> p) -> k -> PSQ k p -> PSQ k p

-- | O(log n). Adjust the priority of a key in the queue, provided that key
--   exists, according to a function which additionally takes the key as a
--   parameter.
adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k p

-- | O(log n). Update or delete a priority in the queue, provided that key
--   exists.
update :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k p

-- | O(log n). Update or delete a priority in the queue, provided that key
--   exists, according to a function which additionally takes the key as a
--   parameter.
updateWithKey :: (Ord k, Ord p) => (k -> p -> Maybe p) -> k -> PSQ k p -> PSQ k p

-- | O(n). Flatten a queue into a list of bindings.
toList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]

-- | O(n). Extract the list of keys of a queue.
keys :: (Ord k, Ord p) => PSQ k p -> [k]

-- | O(n log n). Construct a queue from a list of bindings.
fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p

-- | O(n log n). Contstruct a queue from an already ascending list of
--   bindings. Does not check that the list is sorted.
fromAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p

-- | O(log n). Split a queue into the element with minimum priority, and
--   the remainder.
minView :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p, PSQ k p)

-- | O(1). Find the binding with minimum priority in a queue.
findMin :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p)

-- | O(log n). Delete the key with minimum priority from a queue.
deleteMin :: (Ord k, Ord p) => PSQ k p -> PSQ k p

-- | O(log n). The expression <tt>range (l,u) q</tt> selects the keys k
--   from q where <tt>l &lt;= k</tt> and <tt>k &lt;= u</tt>.
range :: (Ord k, Ord p) => (k, k) -> PSQ k p -> PSQ k p

-- | O(r (log n)). Finds all the bindings in a queue whose priority is less
--   than the given value.
atMost :: (Ord k, Ord p) => p -> PSQ k p -> [Binding k p]

-- | Right fold over the list of bindings in a queue.
foldr :: (Ord k, Ord p) => (Binding k p -> b -> b) -> b -> PSQ k p -> b

-- | Left fold over the list of bindings in a queue.
foldl :: (Ord k, Ord p) => (b -> Binding k p -> b) -> b -> PSQ k p -> b
instance (GHC.Classes.Ord p, GHC.Classes.Ord k) => Data.FingerTree.Measured (Data.FingerTree.PSQueue.KPS k p) (Data.FingerTree.PSQueue.PSQ k p)
instance (GHC.Show.Show k, GHC.Show.Show p) => GHC.Show.Show (Data.FingerTree.PSQueue.PSQ k p)
instance (GHC.Classes.Ord k, GHC.Classes.Ord p) => GHC.Classes.Ord (Data.FingerTree.PSQueue.PSQ k p)
instance (GHC.Classes.Eq k, GHC.Classes.Eq p) => GHC.Classes.Eq (Data.FingerTree.PSQueue.PSQ k p)
instance (GHC.Show.Show p, GHC.Show.Show k) => GHC.Show.Show (Data.FingerTree.PSQueue.KPS k p)
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (Data.FingerTree.PSQueue.Prio k a)
instance (GHC.Classes.Ord k, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.FingerTree.PSQueue.Prio k a)
instance (GHC.Classes.Eq k, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.FingerTree.PSQueue.Prio k a)
instance (GHC.Show.Show p, GHC.Show.Show k) => GHC.Show.Show (Data.FingerTree.PSQueue.Binding k p)
instance (GHC.Classes.Ord p, GHC.Classes.Ord k) => GHC.Classes.Ord (Data.FingerTree.PSQueue.Binding k p)
instance (GHC.Classes.Eq p, GHC.Classes.Eq k) => GHC.Classes.Eq (Data.FingerTree.PSQueue.Binding k p)
instance GHC.Show.Show a => GHC.Show.Show (Data.FingerTree.PSQueue.Key a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.FingerTree.PSQueue.Key a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.FingerTree.PSQueue.Key a)
instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.FingerTree.PSQueue.Prio k a)
instance GHC.Base.Monoid (Data.FingerTree.PSQueue.Key k)
instance GHC.Classes.Eq k => GHC.Classes.Eq (Data.FingerTree.PSQueue.KPS k p)
instance GHC.Classes.Ord k => GHC.Classes.Ord (Data.FingerTree.PSQueue.KPS k p)
instance GHC.Classes.Ord p => GHC.Base.Monoid (Data.FingerTree.PSQueue.KPS k p)
instance (GHC.Classes.Ord k, GHC.Classes.Ord p) => Data.FingerTree.Measured (Data.FingerTree.PSQueue.KPS k p) (Data.FingerTree.PSQueue.Binding k p)
