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


-- | Priority Search Queue
--   
--   A <i>priority search queue</i> efficiently supports the opperations of
--   both a search tree and a priority queue. A <a>Binding</a> 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.1


-- | A <i>priority search queue</i> (henceforth <i>queue</i>) efficiently
--   supports the opperations of both a search tree and a priority queue. A
--   <a>Binding</a> 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.
--   
--   <ul>
--   <li>Hinze, R., <i>A Simple Implementation Technique for Priority
--   Search Queues</i>, ICFP 2001, pp. 110-121</li>
--   </ul>
--   
--   <a>http://citeseer.ist.psu.edu/hinze01simple.html</a>
module Data.PSQueue

-- | <tt>k :-&gt; p</tt> binds the key <tt>k</tt> with the priority
--   <tt>p</tt>.
data Binding k p
(:->) :: k -> p -> Binding k p

-- | The key of a binding
key :: Binding k p -> k

-- | The priority of a binding
prio :: Binding k p -> p

-- | A mapping from keys <tt>k</tt> to priorites <tt>p</tt>.
data PSQ k p

-- | <i>O(1)</i> The number of bindings in a queue.
size :: PSQ k p -> Int

-- | <i>O(1)</i> True if the queue is empty.
null :: PSQ k p -> Bool

-- | <i>O(log n)</i> The priority of a given key, or Nothing if the key is
--   not bound.
lookup :: (Ord k, Ord p) => k -> PSQ k p -> Maybe p
empty :: (Ord k, Ord p) => PSQ k p

-- | O(1) Build a queue with one binding.
singleton :: (Ord k, Ord p) => k -> p -> PSQ k p

-- | <i>O(log n)</i> Insert a binding into the queue.
insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p

-- | <i>O(log n)</i> Insert a binding with a combining function.
insertWith :: (Ord k, Ord p) => (p -> p -> p) -> k -> p -> PSQ k p -> PSQ k p

-- | <i>O(log n)</i> Remove a binding from the queue.
delete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p

-- | <i>O(log n)</i> Adjust the priority of a key.
adjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k p

-- | <i>O(log n)</i> Adjust the priority of a key.
adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k p

-- | <i>O(log n)</i> The expression (<tt>update f k q</tt>) updates the
--   priority <tt>p</tt> bound <tt>k</tt> (if it is in the queue). If
--   (<tt>f p</tt>) is <a>Nothing</a>, the binding is deleted. If it is
--   (<tt><a>Just</a> z</tt>), the key <tt>k</tt> is bound to the new
--   priority <tt>z</tt>.
update :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k p

-- | <i>O(log n)</i>. The expression (<tt>updateWithKey f k q</tt>) updates
--   the priority <tt>p</tt> bound <tt>k</tt> (if it is in the queue). If
--   (<tt>f k p</tt>) is <a>Nothing</a>, the binding is deleted. If it is
--   (<tt><a>Just</a> z</tt>), the key <tt>k</tt> is bound to the new
--   priority <tt>z</tt>.
updateWithKey :: (Ord k, Ord p) => (k -> p -> Maybe p) -> k -> PSQ k p -> PSQ k p

-- | <i>O(log n)</i>. The expression (<tt><a>alter</a> f k q</tt>) alters
--   the priority <tt>p</tt> bound to <tt>k</tt>, 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

-- | <i>O(n)</i> The keys of a priority queue
keys :: (Ord k, Ord p) => PSQ k p -> [k]

-- | <i>O(n)</i> Convert a queue to a list.
toList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]

-- | <i>O(n)</i> Convert a queue to a list in ascending order of keys.
toAscList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]

-- | <i>O(n)</i> Convert a queue to a list in descending order of keys.
toDescList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]

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

-- | <i>O(n)</i> Build a queue from a list of bindings in order of
--   ascending keys. The precondition that the keys are ascending is not
--   checked.
fromAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p

-- | <i>O(n)</i> 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 k, Ord p) => [Binding k p] -> PSQ k p

-- | <i>O(1)</i> The binding with the lowest priority.
findMin :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p)

-- | <i>O(log n)</i> Remove the binding with the lowest priority.
deleteMin :: (Ord k, Ord p) => PSQ k p -> PSQ k p

-- | <i>O(log n)</i> Retrieve the binding with the least priority, and the
--   rest of the queue stripped of that binding.
minView :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p, PSQ k p)

-- | <i>O(r(log n - log r)</i> <tt>atMost p q</tt> is a list of all the
--   bindings in <tt>q</tt> with priority less than <tt>p</tt>, in order of
--   ascending keys. Effectively,
--   
--   <pre>
--   atMost p' q = filter (\(k:-&gt;p) -&gt; p&lt;=p') . toList
--   </pre>
atMost :: (Ord k, Ord p) => p -> PSQ k p -> [Binding k p]

-- | <i>O(r(log n - log r))</i> <tt>atMostRange p (l,u) q</tt> is a list of
--   all the bindings in <tt>q</tt> with a priority less than <tt>p</tt>
--   and a key in the range <tt>(l,u)</tt> inclusive. Effectively,
--   
--   <pre>
--   atMostRange p' (l,u) q = filter (\(k:-&gt;p) -&gt; l&lt;=k &amp;&amp; k&lt;=u ) . <a>atMost</a> p'
--   </pre>
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 :: (Ord k, Ord p) => (Binding k p -> b -> b) -> b -> PSQ k p -> b

-- | Left fold over the bindings in the queue, in key order.
foldl :: (Ord k, Ord p) => (b -> Binding k p -> b) -> b -> PSQ k p -> b
instance (GHC.Read.Read k, GHC.Read.Read p) => GHC.Read.Read (Data.PSQueue.Binding k p)
instance (GHC.Show.Show k, GHC.Show.Show p) => GHC.Show.Show (Data.PSQueue.Binding k p)
instance (GHC.Classes.Ord k, GHC.Classes.Ord p) => GHC.Classes.Ord (Data.PSQueue.Binding k p)
instance (GHC.Classes.Eq k, GHC.Classes.Eq p) => GHC.Classes.Eq (Data.PSQueue.Binding k p)
instance (GHC.Show.Show k, GHC.Show.Show p, GHC.Classes.Ord k, GHC.Classes.Ord p) => GHC.Show.Show (Data.PSQueue.PSQ k p)
instance GHC.Show.Show a => GHC.Show.Show (Data.PSQueue.Sequ a)
