| Copyright | (c) Masahiro Sakai 2012 |
|---|---|
| License | BSD-style |
| Maintainer | masahiro.sakai@gmail.com |
| Stability | provisional |
| Portability | non-portable (MultiParamTypeClasses, FlexibleInstances, BangPatterns) |
| Safe Haskell | None |
| Language | Haskell2010 |
ToySolver.Internal.Data.PriorityQueue
Description
Priority queue implemented as array-based binary heap.
- 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 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 a | q -> a where
- enqueue :: q -> a -> m ()
- enqueueBatch :: q -> [a] -> m ()
- class Monad m => Dequeue q m a | q -> a where
- dequeue :: q -> m (Maybe a)
- dequeueBatch :: q -> m [a]
- class Monad m => QueueSize q m where
- 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 | |
| QueueSize (PriorityQueue a) IO | |
| Enqueue (PriorityQueue a) IO a | |
| Dequeue (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.
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 a | q -> a where
Minimal complete definition
Methods
enqueue :: q -> a -> m ()
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 ()
class Monad m => Dequeue q m a | q -> a where
Minimal complete definition
Methods
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]
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.