Copyright | (c) Masahiro Sakai 2012 |
---|---|
License | BSD-style |
Maintainer | masahiro.sakai@gmail.com |
Stability | provisional |
Portability | non-portable (MultiParamTypeClasses, FlexibleInstances, BangPatterns, ScopedTypeVariables) |
Safe Haskell | None |
Language | Haskell2010 |
Priority queue implemented as array-based binary heap.
Synopsis
- data PriorityQueue a
- type Index = Int
- newPriorityQueue :: Ord a => IO (PriorityQueue a)
- newPriorityQueueBy :: (a -> a -> IO Bool) -> IO (PriorityQueue a)
- class Monad m => NewFifo q (m :: Type -> Type) where
- newFifo :: m q
- getElems :: PriorityQueue a -> IO [a]
- clear :: PriorityQueue a -> IO ()
- clone :: PriorityQueue a -> IO (PriorityQueue a)
- class Monad m => Enqueue q (m :: Type -> Type) a | q -> a where
- enqueue :: q -> a -> m ()
- enqueueBatch :: q -> [a] -> m ()
- class Monad m => Dequeue q (m :: Type -> Type) a | q -> a where
- dequeue :: q -> m (Maybe a)
- dequeueBatch :: q -> m [a]
- class Monad m => QueueSize q (m :: Type -> Type) where
- rebuild :: PriorityQueue a -> IO ()
- getHeapArray :: PriorityQueue a -> IO (IOArray Index a)
- getHeapVec :: PriorityQueue a -> IO (Vec a)
- resizeHeapCapacity :: PriorityQueue a -> Int -> IO ()
PriorityQueue type
data PriorityQueue a Source #
Priority queue implemented as array-based binary heap.
Instances
Ord a => NewFifo (PriorityQueue a) IO Source # | |
Defined in ToySolver.Internal.Data.PriorityQueue newFifo :: IO (PriorityQueue a) # | |
QueueSize (PriorityQueue a) IO Source # | |
Defined in ToySolver.Internal.Data.PriorityQueue queueSize :: PriorityQueue a -> IO Int # | |
Enqueue (PriorityQueue a) IO a Source # | |
Defined in ToySolver.Internal.Data.PriorityQueue enqueue :: PriorityQueue a -> a -> IO () # enqueueBatch :: PriorityQueue a -> [a] -> IO () # | |
Dequeue (PriorityQueue a) IO a Source # | |
Defined in ToySolver.Internal.Data.PriorityQueue dequeue :: PriorityQueue a -> IO (Maybe a) # dequeueBatch :: PriorityQueue a -> IO [a] # |
Constructors
newPriorityQueue :: Ord a => IO (PriorityQueue a) Source #
Build a priority queue with default ordering ('(<)' of Ord
class)
newPriorityQueueBy :: (a -> a -> IO Bool) -> IO (PriorityQueue a) Source #
Build a priority queue with a given less than operator.
class Monad m => NewFifo q (m :: Type -> Type) where #
Construct a new FIFO queue.
Instances
NewFifo PriorityQueue IO Source # | |
Defined in ToySolver.Internal.Data.IndexedPriorityQueue newFifo :: IO PriorityQueue # | |
Ord a => NewFifo (PriorityQueue a) IO Source # | |
Defined in ToySolver.Internal.Data.PriorityQueue newFifo :: IO (PriorityQueue a) # | |
PrimMonad m => NewFifo (SeqQueue m a) m Source # | |
Defined in ToySolver.Internal.Data.SeqQueue |
Operators
getElems :: PriorityQueue a -> IO [a] Source #
Return a list of all the elements of a priority queue. (not sorted)
clear :: PriorityQueue a -> IO () Source #
Remove all elements from a priority queue.
clone :: PriorityQueue a -> IO (PriorityQueue a) Source #
Create a copy of a priority queue.
class Monad m => Enqueue q (m :: Type -> Type) a | q -> a where #
Put an item into a queue. May block while trying to do so.
No constraint is placed on the behavior of the queue except that
every item put in "really ought to" come out sometime before
dequeue
returns a Nothing
.
enqueueBatch :: q -> [a] -> m () #
Instances
Enqueue PriorityQueue IO Value Source # | |
Defined in ToySolver.Internal.Data.IndexedPriorityQueue enqueue :: PriorityQueue -> Value -> IO () # enqueueBatch :: PriorityQueue -> [Value] -> IO () # | |
Enqueue q m a => Enqueue (WQueue q) m a | |
Defined in Data.Queue | |
Enqueue (PriorityQueue a) IO a Source # | |
Defined in ToySolver.Internal.Data.PriorityQueue enqueue :: PriorityQueue a -> a -> IO () # enqueueBatch :: PriorityQueue a -> [a] -> IO () # | |
PrimMonad m => Enqueue (SeqQueue m a) m a Source # | |
Defined in ToySolver.Internal.Data.SeqQueue |
class Monad m => Dequeue q (m :: Type -> Type) a | q -> a where #
Pull an item out of a queue. Should not block. No ordering
constraints are implied other than that any item that went into
the queue "really ought to" come out before dequeue
returns
Nothing
.
dequeueBatch :: q -> m [a] #
Instances
Dequeue PriorityQueue IO Value Source # | |
Defined in ToySolver.Internal.Data.IndexedPriorityQueue dequeue :: PriorityQueue -> IO (Maybe Value) # dequeueBatch :: PriorityQueue -> IO [Value] # | |
Dequeue q m a => Dequeue (RQueue q) m a | |
Defined in Data.Queue | |
Dequeue (PriorityQueue a) IO a Source # | |
Defined in ToySolver.Internal.Data.PriorityQueue dequeue :: PriorityQueue a -> IO (Maybe a) # dequeueBatch :: PriorityQueue a -> IO [a] # | |
PrimMonad m => Dequeue (SeqQueue m a) m a Source # | |
Defined in ToySolver.Internal.Data.SeqQueue |
class Monad m => QueueSize q (m :: Type -> Type) where #
Instances
QueueSize PriorityQueue IO Source # | |
Defined in ToySolver.Internal.Data.IndexedPriorityQueue queueSize :: PriorityQueue -> IO Int # | |
QueueSize (PriorityQueue a) IO Source # | |
Defined in ToySolver.Internal.Data.PriorityQueue queueSize :: PriorityQueue a -> IO Int # | |
PrimMonad m => QueueSize (SeqQueue m a) m Source # | |
Defined in ToySolver.Internal.Data.SeqQueue |
rebuild :: PriorityQueue a -> IO () Source #
getHeapArray :: PriorityQueue a -> IO (IOArray Index a) Source #
Get the internal representation of a given priority queue.
getHeapVec :: PriorityQueue a -> IO (Vec a) Source #
Get the internal representation of a given priority queue.
Misc operations
resizeHeapCapacity :: PriorityQueue a -> Int -> IO () Source #
Pre-allocate internal buffer for n
elements.