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


-- | Fully encapsulated monad transformers with queuelike functionality.
--   
--   Contains several implementations of data structures implementing a
--   <i>single-in, single-out</i> paradigm, and implements monad
--   transformers for their safe use. The monad transformer part of the
--   library includes tools to fully encapsulate single-threaded use of a
--   priority queue in a monad, including an array-based heap
--   implementation.
@package pqueue-mtl
@version 1.0.2


-- | Abstracts the implementation details of a single-insertion,
--   single-extraction queuelike structure.
module Data.Queue.Class

-- | A generic type class encapsulating a generic queuelike structure, that
--   supports single-insertion and single-extraction; this abstraction
--   includes priority queues, stacks, and FIFO queues. There are many
--   minimal implementations, so each method lists the prerequisites for
--   its default implementation. Most implementations will implement
--   <a>empty</a>, (<a>singleton</a> and <a>merge</a>) or <a>insert</a>,
--   (<a>peek</a> and <a>delete</a>) or <a>extract</a>, and <a>size</a>.
class Queuelike q e | q -> e
insert :: (Queuelike q e) => e -> q -> q
insertAll :: (Queuelike q e) => [e] -> q -> q
extract :: (Queuelike q e) => q -> Maybe (e, q)
peek :: (Queuelike q e) => q -> Maybe e
delete :: (Queuelike q e) => q -> Maybe q
empty :: (Queuelike q e) => q
singleton :: (Queuelike q e) => e -> q
fromList :: (Queuelike q e) => [e] -> q
size :: (Queuelike q e) => q -> Int
isEmpty :: (Queuelike q e) => q -> Bool
toList :: (Queuelike q e) => q -> [e]
toList_ :: (Queuelike q e) => q -> [e]
merge :: (Queuelike q e) => q -> q -> q
mergeAll :: (Queuelike q e) => [q] -> q


-- | A basic implementation of a stack implementing the Queue abstraction.
module Data.Queue.Stack
data Stack e
instance Monoid (Stack e)
instance Queuelike (Stack e) e


-- | A basic first-in, first-out queue implementation implementing the
--   <a>Queuelike</a> abstraction.
module Data.Queue.Queue
data Queue e
instance Monoid (Queue e)
instance Queuelike (Queue e) e


-- | Generic queue wrapper to transform a min-queue into a max-queue.
module Data.Queue.ReverseQueue
newtype Down a
Down :: a -> Down a
unDown :: Down a -> a

-- | Wrapper around a generic queue that reverses the ordering on its
--   elements.
data ReverseQueue q e
instance (Eq a) => Eq (Down a)
instance (Queuelike (q (Down e)) (Down e)) => Queuelike (ReverseQueue q e) e
instance (Ord a) => Ord (Down a)


-- | An alternate implementation of a priority queue based on a
--   <i>Fibonacci heap</i>.
--   
--   Fibonacci heaps, while not quite as internally functional as pairing
--   heaps, are generally less ad-hoc and may prove useful for some uses
--   (as well as serving as a useful testbed). A Fibonacci heap can be
--   thought of as a lazier binomial heap, designed to better take
--   advantage of the fact that in a lazy language a series of modification
--   operations will likely all be computed at once, preferably as late as
--   possible. The Fibonacci heap supports all <a>Queuelike</a> operations
--   with the same time complexity as PQueue.
module Data.Queue.FibQueue
data FQueue e
instance (Ord e) => Queuelike (FQueue e) e


-- | An efficient implementation of a priority queue.
--   
--   The implementation of <a>PQueue</a> is based on a <i>pairing heap</i>,
--   a simple and efficient implementation of a general-purpose priority
--   queue. <a>PQueue</a> supports <a>insert</a>, <a>merge</a>, and
--   <a>peek</a> in constant time, and <a>extract</a> and <a>delete</a> in
--   logarithmic time.
module Data.Queue.PQueue
data PQueue e
instance (Ord e) => Monoid (PQueue e)
instance (Read e) => Read (PQueue e)
instance (Show e) => Show (PQueue e)
instance (Read e) => Read (PHeap e)
instance (Show e) => Show (PHeap e)
instance (Ord e) => Queuelike (PQueue e) e
instance (Ord e) => Monoid (PHeap e)

module Data.Queue.Instances

module Data.Queue

module Control.Monad.Queue.Class

-- | Type that only orders on the key, ignoring the value completely;
--   frequently useful in priority queues, so made available here.
data (:->) e f
(:->) :: e -> f -> (:->) e f

-- | Typeclass abstraction of a monad with access to a mutable queue.
--   Minimal implementation: <a>queueInsert</a> or <a>queueInsertAll</a>,
--   <a>queuePeek</a>, <a>queueExtract</a> or <a>queueDelete</a>,
--   <a>queueSize</a>.
class (Monad m) => MonadQueue e m | m -> e
queueInsert :: (MonadQueue e m) => e -> m ()
queueInsertAll :: (MonadQueue e m) => [e] -> m ()
queueExtract :: (MonadQueue e m) => m (Maybe e)
queueDelete :: (MonadQueue e m) => m ()
queuePeek :: (MonadQueue e m) => m (Maybe e)
queueEmpty :: (MonadQueue e m) => m Bool
queueSize :: (MonadQueue e m) => m Int
instance (MonadQueue e m) => MonadQueue e (IntMapT f m)
instance (MonadQueue e m) => MonadQueue e (ListT m)
instance (MonadQueue e m) => MonadQueue e (MaybeT m)
instance (Monoid w, MonadQueue e m) => MonadQueue e (WriterT w m)
instance (Monoid w, MonadQueue e m) => MonadQueue e (WriterT w m)
instance (MonadQueue e m) => MonadQueue e (ReaderT r m)
instance (MonadQueue e m) => MonadQueue e (StateT s m)
instance (MonadQueue e m) => MonadQueue e (StateT s m)
instance (Ord f) => Ord (e :-> f)
instance (Eq f) => Eq (e :-> f)

module Control.Monad.Queue.Heap

-- | Monad based on an array implementation of a standard binary heap.
type HeapM s e = HeapT s e (ST s)

-- | Monad transformer based on an array implementation of a standard
--   binary heap.
data HeapT s e m a

-- | Runs an <a>HeapM</a> computation starting with an empty heap.
runHeapM :: (Ord e) => (forall s. HeapM s e a) -> a
runHeapMIO :: (Ord e) => HeapM RealWorld e a -> IO a
runHeapT :: (MonadST s m, Monad m) => HeapT s e m a -> m a
instance (Monad m) => Monad (HeapT s e m)
instance (MonadST s m) => MonadST s (HeapT s e m)
instance (MonadFix m) => MonadFix (HeapT s e m)
instance (MonadReader r m) => MonadReader r (HeapT s e m)
instance (MonadWriter w m) => MonadWriter w (HeapT s e m)
instance (MonadST s m, Monad m, Ord e) => MonadQueue e (HeapT s e m)
instance (MonadST s m, MonadState t m) => MonadState t (HeapT s e m)
instance MonadTrans (HeapT s e)


-- | A monad transformer allowing a purely functional queue implementation
--   (specifically, implementing the <a>Queuelike</a> abstraction) to be
--   used in a monadic, single-threaded fashion.
module Control.Monad.Queue.QueueT

-- | A monad transformer granting the underlying monad <tt>m</tt> access to
--   single-threaded actions on a queue.
newtype QueueT q m a
QueueT :: StateT q m a -> QueueT q m a
runQT :: QueueT q m a -> StateT q m a

-- | A monad controlling single-threaded access to a queue.
newtype QueueM q a
QueueM :: State q a -> QueueM q a
runQM :: QueueM q a -> State q a
type PQueueT e = QueueT (PQueue e)
type PQueueM e = QueueM (PQueue e)
type FibQueueT e = QueueT (FQueue e)
type FibQueueM e = QueueM (FQueue e)

-- | Unwraps a queue transformer, initializing it with an empty queue.
runQueueT :: (Monad m, Queuelike q e) => QueueT q m a -> m a

-- | Unwraps a queue transformer, initializing it with a queue with the
--   specified contents.
runQueueTOn :: (Monad m, Queuelike q e) => QueueT q m a -> [e] -> m a

-- | Executes a computation in a queue monad, starting with an empty queue.
runQueueM :: (Queuelike q e) => QueueM q a -> a

-- | Executes a computation in a queue monad, starting with a queue with
--   the specified contents.
runQueueMOn :: (Queuelike q e) => QueueM q a -> [e] -> a
instance MonadFix (QueueM q)
instance Monad (QueueM q)
instance (MonadReader r m) => MonadReader r (QueueT q m)
instance (MonadWriter w m) => MonadWriter w (QueueT q m)
instance (MonadIO m) => MonadIO (QueueT q m)
instance (MonadST s m) => MonadST s (QueueT q m)
instance (MonadFix m) => MonadFix (QueueT q m)
instance (Monad m) => Monad (QueueT q m)
instance MonadTrans (QueueT q)
instance (Queuelike q e) => MonadQueue e (QueueM q)
instance (Monad m, Queuelike q e) => MonadQueue e (QueueT q m)
instance (MonadState s m) => MonadState s (QueueT q m)

module Control.Monad.Queue.Instances

module Control.Monad.Queue