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

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 (Ord k, Ord p) => Eq (PSQ k p)
instance (Ord k, Ord p) => Ord (PSQ k p)
instance (Ord k, Ord p, Show k, Show p) => Show (PSQ k p)
instance (Ord k, Ord p) => Measured (KPS k p) (PSQ k p)
instance (Show k, Show p) => Show (KPS k p)
instance (Eq k, Eq p) => Eq (Binding k p)
instance (Ord k, Ord p) => Ord (Binding k p)
instance (Show k, Show p) => Show (Binding k p)
instance (Eq a) => Eq (Key a)
instance (Ord a) => Ord (Key a)
instance (Show a) => Show (Key a)
instance (Eq k, Eq a) => Eq (Prio k a)
instance (Ord k, Ord a) => Ord (Prio k a)
instance (Show k, Show a) => Show (Prio k a)
instance (Ord k, Ord p) => Measured (KPS k p) (Binding k p)
instance (Ord p) => Monoid (KPS k p)
instance (Ord k) => Ord (KPS k p)
instance (Eq k) => Eq (KPS k p)
instance Monoid (Key k)
instance (Ord a) => Monoid (Prio k a)