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


-- | Heaps in Haskell
--   
--   A flexible Haskell implementation of minimum, maximum,
--   minimum-priority, maximum-priority and custom-ordered heaps.
@package heap
@version 1.0.4


-- | A flexible implementation of min-, max-, min-priority, max-priority
--   and custom-priority heaps based on the leftist-heaps from Chris
--   Okasaki's book "Purely Functional Data Structures", Cambridge
--   University Press, 1998, chapter 3.1.
--   
--   There are different flavours of <a>Heap</a>s, each of them following a
--   different strategy when ordering its elements:
--   
--   <ul>
--   <li>Choose <a>MinHeap</a> or <a>MaxHeap</a> if you need a simple
--   minimum or maximum heap (which always keeps the minimum/maximum
--   element at the head of the <a>Heap</a>).</li>
--   <li>If you wish to manually annotate a value with a priority, e. g. an
--   <tt>IO ()</tt> action with an <a>Int</a> use <a>MinPrioHeap</a> or
--   <a>MaxPrioHeap</a>. They manage <tt>(prio, val)</tt> tuples so that
--   only the priority (and not the value) influences the order of
--   elements.</li>
--   <li>If you still need something different, define a custom order for
--   the heap elements by implementing an instance of <a>HeapItem</a> and
--   let the maintainer know what's missing.</li>
--   </ul>
--   
--   All sorts of heaps mentioned above (<a>MinHeap</a>, <a>MaxHeap</a>,
--   <a>MinPrioHeap</a> and <a>MaxPrioHeap</a>) are built on the same
--   underlying type: <tt><a>HeapT</a> prio val</tt>. It is a simple
--   minimum priority heap. The trick is, that you never insert <tt>(prio,
--   val)</tt> pairs directly: You only insert an "external
--   representation", usually called <tt>item</tt>, and an appropriate
--   <a>HeapItem</a> instance is used to <a>split</a> the <tt>item</tt> to
--   a <tt>(prio, val)</tt> pair. For details refer to the documentation of
--   <a>HeapItem</a>.
module Data.Heap

-- | The basic heap type. It stores priority-value pairs <tt>(prio,
--   val)</tt> and always keeps the pair with minimal priority on top. The
--   value associated to the priority does not have any influence on the
--   ordering of elements.
data HeapT prio val

-- | This type alias is an abbreviation for a <a>HeapT</a> which uses the
--   <a>HeapItem</a> instance of <tt>pol item</tt> to organise its
--   elements.
type Heap pol item = HeapT (Prio pol item) (Val pol item)

-- | A <a>Heap</a> which will always extract the minimum first.
type MinHeap a = Heap MinPolicy a

-- | A <a>Heap</a> which will always extract the maximum first.
type MaxHeap a = Heap MaxPolicy a

-- | A <a>Heap</a> storing priority-value pairs <tt>(prio, val)</tt>. The
--   order of elements is solely determined by the priority <tt>prio</tt>,
--   the value <tt>val</tt> has no influence. The priority-value pair with
--   minmal priority will always be extracted first.
type MinPrioHeap prio val = Heap FstMinPolicy (prio, val)

-- | A <a>Heap</a> storing priority-value pairs <tt>(prio, val)</tt>. The
--   order of elements is solely determined by the priority <tt>prio</tt>,
--   the value <tt>val</tt> has no influence. The priority-value pair with
--   maximum priority will always be extracted first.
type MaxPrioHeap prio val = Heap FstMaxPolicy (prio, val)

-- | <tt><a>HeapItem</a> pol item</tt> is a type class for items that can
--   be stored in a <a>HeapT</a>. A raw <tt><a>HeapT</a> prio val</tt> only
--   provides a minimum priority heap (i. e. <tt>val</tt> doesn't influence
--   the ordering of elements and the pair with minimal <tt>prio</tt> will
--   be extracted first, see <a>HeapT</a> documentation). The job of this
--   class is to translate between arbitrary <tt>item</tt>s and
--   priority-value pairs <tt>(<a>Prio</a> pol item, <a>Val</a> pol
--   item)</tt>, depending on the policy <tt>pol</tt> to be used. This way,
--   we are able to use <a>HeapT</a> not only as <a>MinPrioHeap</a>, but
--   also as <a>MinHeap</a>, <a>MaxHeap</a>, <a>MaxPrioHeap</a> or a custom
--   implementation. In short: The job of this class is to deconstruct
--   arbitrary <tt>item</tt>s into a <tt>(prio, val)</tt> pairs that can be
--   handled by a minimum priority <a>HeapT</a>.
--   
--   Example: Consider you want to use <tt><a>HeapT</a> prio val</tt> as a
--   <tt><a>MaxHeap</a> a</tt>. You would have to invert the order of
--   <tt>a</tt> (e. g. by introducing <tt>newtype InvOrd a = InvOrd a</tt>
--   along with an apropriate <a>Ord</a> instance for it) and then use a
--   <tt>type <a>MaxHeap</a> a = <a>HeapT</a> (InvOrd a) ()</tt>. You'd
--   also have to translate every <tt>x</tt> to <tt>(InvOrd x, ())</tt>
--   before insertion and back after removal in order to retrieve your
--   original type <tt>a</tt>.
--   
--   This functionality is provided by the <a>HeapItem</a> class. In the
--   above example, you'd use a <a>MaxHeap</a>. The according instance
--   declaration is of course already provided and looks like this
--   (simplified):
--   
--   @data <a>MaxPolicy</a>
--   
--   instance (<a>Ord</a> a) =&gt; <a>HeapItem</a> <a>MaxPolicy</a> a where
--   newtype <a>Prio</a> <a>MaxPolicy</a> a = MaxP a deriving (<a>Eq</a>)
--   type <a>Val</a> <a>MaxPolicy</a> a = () <a>split</a> x = (MaxP x, ())
--   <a>merge</a> (MaxP x, _) = x
--   
--   instance (<a>Ord</a> a) =&gt; <a>Ord</a> (<a>Prio</a> <a>MaxPolicy</a>
--   a) where <a>compare</a> (MaxP x) (MaxP y) = <a>compare</a> y x @
--   
--   <a>MaxPolicy</a> is a phantom type describing which <a>HeapItem</a>
--   instance is actually meant (e. g. we have to distinguish between
--   <a>MinHeap</a> and <a>MaxHeap</a>, which is done via <a>MinPolicy</a>
--   and <a>MaxPolicy</a>, respectively) and <tt>MaxP</tt> inverts the
--   ordering of <tt>a</tt>, so that the maximum will be on top of the
--   <a>HeapT</a>.
--   
--   The conversion functions <a>split</a> and <a>merge</a> have to make
--   sure that
--   
--   <ol>
--   <li><tt>forall p v. <a>split</a> (<a>merge</a> (p, v)) == (p, v)</tt>
--   (<a>merge</a> and <a>split</a> don't remove, add or alter
--   anything)</li>
--   <li><tt>forall p v f. <a>fst</a> (<a>split</a> (<a>merge</a> (p, f v))
--   == <a>fst</a> (<a>split</a> (<a>merge</a> (p, v)))</tt> (modifying the
--   associated value <tt>v</tt> doesn't alter the priority
--   <tt>p</tt>)</li>
--   </ol>
class (Ord (Prio pol item)) => HeapItem pol item where {
    data family Prio pol item :: *;
    type family Val pol item :: *;
}

-- | Translate an <tt>item</tt> into a priority-value pair.
split :: HeapItem pol item => item -> (Prio pol item, Val pol item)

-- | Restore the <tt>item</tt> from a priority-value pair.
merge :: HeapItem pol item => (Prio pol item, Val pol item) -> item

-- | Policy type for a <a>MinHeap</a>.
data MinPolicy

-- | Policy type for a <a>MaxHeap</a>.
data MaxPolicy

-- | Policy type for a <tt>(prio, val)</tt> <a>MinPrioHeap</a>.
data FstMinPolicy

-- | Policy type for a <tt>(prio, val)</tt> <a>MaxPrioHeap</a>.
data FstMaxPolicy

-- | <i>O(1)</i>. Is the <a>HeapT</a> empty?
isEmpty :: HeapT prio val -> Bool

-- | <i>O(1)</i>. Is the <a>HeapT</a> empty?
null :: HeapT prio val -> Bool

-- | <i>O(1)</i>. The total number of elements in the <a>HeapT</a>.
size :: HeapT prio val -> Int

-- | <i>O(1)</i>. Construct an empty <a>HeapT</a>.
empty :: HeapT prio val

-- | <i>O(1)</i>. Create a singleton <a>HeapT</a>.
singleton :: (HeapItem pol item) => item -> Heap pol item

-- | <i>O(log n)</i>. Insert a single item into the <a>HeapT</a>.
insert :: (HeapItem pol item) => item -> Heap pol item -> Heap pol item

-- | <i>O(log max(n, m))</i>. Form the union of two <a>HeapT</a>s.
union :: (Ord prio) => HeapT prio val -> HeapT prio val -> HeapT prio val

-- | Build the union of all given <a>HeapT</a>s.
unions :: (Ord prio) => [HeapT prio val] -> HeapT prio val

-- | <i>O(1)</i> for the head, <i>O(log n)</i> for the tail. Find the item
--   with minimal associated priority and remove it from the <a>Heap</a>
--   (i. e. find head and tail of the heap) if it is not empty. Otherwise,
--   <a>Nothing</a> is returned.
view :: (HeapItem pol item) => Heap pol item -> Maybe (item, Heap pol item)

-- | <i>O(1)</i>. Find the item with minimal associated priority on the
--   <a>Heap</a> (i. e. its head) if it is not empty. Otherwise,
--   <a>Nothing</a> is returned.
viewHead :: (HeapItem pol item) => Heap pol item -> Maybe item

-- | <i>O(log n)</i>. Remove the item with minimal associated priority and
--   from the <a>Heap</a> (i. e. its tail) if it is not empty. Otherwise,
--   <a>Nothing</a> is returned.
viewTail :: (HeapItem pol item) => Heap pol item -> Maybe (Heap pol item)

-- | Remove all items from a <a>HeapT</a> not fulfilling a predicate.
filter :: (HeapItem pol item) => (item -> Bool) -> Heap pol item -> Heap pol item

-- | Partition the <a>Heap</a> into two. <tt><a>partition</a> p h = (h1,
--   h2)</tt>: All items in <tt>h1</tt> fulfil the predicate <tt>p</tt>,
--   those in <tt>h2</tt> don't. <tt><tt>union</tt> h1 h2 = h</tt>.
partition :: (HeapItem pol item) => (item -> Bool) -> Heap pol item -> (Heap pol item, Heap pol item)

-- | Take the first <tt>n</tt> items from the <a>Heap</a>.
take :: (HeapItem pol item) => Int -> Heap pol item -> [item]

-- | Remove first <tt>n</tt> items from the <a>Heap</a>.
drop :: (HeapItem pol item) => Int -> Heap pol item -> Heap pol item

-- | <tt><a>splitAt</a> n h</tt>: Return a list of the first <tt>n</tt>
--   items of <tt>h</tt> and <tt>h</tt>, with those elements removed.
splitAt :: (HeapItem pol item) => Int -> Heap pol item -> ([item], Heap pol item)

-- | <tt><a>takeWhile</a> p h</tt>: List the longest prefix of items in
--   <tt>h</tt> that satisfy <tt>p</tt>.
takeWhile :: (HeapItem pol item) => (item -> Bool) -> Heap pol item -> [item]

-- | <tt><a>dropWhile</a> p h</tt>: Remove the longest prefix of items in
--   <tt>h</tt> that satisfy <tt>p</tt>.
dropWhile :: (HeapItem pol item) => (item -> Bool) -> Heap pol item -> Heap pol item

-- | <tt><a>span</a> p h</tt>: Return the longest prefix of items in
--   <tt>h</tt> that satisfy <tt>p</tt> and <tt>h</tt>, with those elements
--   removed.
span :: (HeapItem pol item) => (item -> Bool) -> Heap pol item -> ([item], Heap pol item)

-- | <tt><a>break</a> p h</tt>: The longest prefix of items in <tt>h</tt>
--   that do <i>not</i> satisfy <tt>p</tt> and <tt>h</tt>, with those
--   elements removed.
break :: (HeapItem pol item) => (item -> Bool) -> Heap pol item -> ([item], Heap pol item)

-- | <i>O(n log n)</i>. Build a <a>Heap</a> from the given items. Assuming
--   you have a sorted list, you probably want to use <a>fromDescList</a>
--   or <a>fromAscList</a>, they are faster than this function.
fromList :: (HeapItem pol item) => [item] -> Heap pol item

-- | <i>O(n log n)</i>. List all items of the <a>Heap</a> in no specific
--   order.
toList :: (HeapItem pol item) => Heap pol item -> [item]

-- | <i>O(n)</i>. Create a <a>Heap</a> from a list providing its items in
--   ascending order of priority (i. e. in the same order they will be
--   removed from the <a>Heap</a>). This function is faster than
--   <a>fromList</a> but not as fast as <a>fromDescList</a>.
--   
--   <i>The precondition is not checked</i>.
fromAscList :: (HeapItem pol item) => [item] -> Heap pol item

-- | <i>O(n log n)</i>. List the items of the <a>Heap</a> in ascending
--   order of priority.
toAscList :: (HeapItem pol item) => Heap pol item -> [item]

-- | <i>O(n)</i>. Create a <a>Heap</a> from a list providing its items in
--   descending order of priority (i. e. they will be removed inversely
--   from the <a>Heap</a>). Prefer this function over <a>fromList</a> and
--   <a>fromAscList</a>, it's faster.
--   
--   <i>The precondition is not checked</i>.
fromDescList :: (HeapItem pol item) => [item] -> Heap pol item

-- | <i>O(n log n)</i>. List the items of the <a>Heap</a> in descending
--   order of priority. Note that this function is not especially efficient
--   (it is implemented in terms of <a>reverse</a> and <a>toAscList</a>),
--   it is provided as a counterpart of the efficient <a>fromDescList</a>
--   function.
toDescList :: (HeapItem pol item) => Heap pol item -> [item]
