| Copyright | (c) Masahiro Sakai 2012 |
|---|---|
| License | BSD-style |
| Maintainer | masahiro.sakai@gmail.com |
| Stability | provisional |
| Portability | non-portable (MultiParamTypeClasses, FlexibleInstances, BangPatterns, TypeSynonymInstances) |
| Safe Haskell | None |
| Language | Haskell2010 |
ToySolver.Internal.Data.IndexedPriorityQueue
Description
Priority queue implemented as array-based binary heap.
- data PriorityQueue
- type Value = Int
- type Index = Int
- newPriorityQueue :: IO PriorityQueue
- newPriorityQueueBy :: (Value -> Value -> IO Bool) -> IO PriorityQueue
- class Monad m => NewFifo q m where
- newFifo :: m q
- getElems :: PriorityQueue -> IO [Value]
- clear :: PriorityQueue -> IO ()
- clone :: PriorityQueue -> IO PriorityQueue
- 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
- member :: PriorityQueue -> Value -> IO Bool
- update :: PriorityQueue -> Value -> IO ()
- getHeapArray :: PriorityQueue -> IO (IOUArray Index Value)
- getHeapVec :: PriorityQueue -> IO (UVec Value)
- resizeHeapCapacity :: PriorityQueue -> Int -> IO ()
- resizeTableCapacity :: PriorityQueue -> Int -> IO ()
PriorityQueue type
data PriorityQueue Source
Priority queue implemented as array-based binary heap.
Constructors
newPriorityQueue :: IO PriorityQueue Source
Build a priority queue with default ordering ('(<)' of Ord class)
newPriorityQueueBy :: (Value -> Value -> IO Bool) -> IO PriorityQueue Source
Build a priority queue with a given less than operator.
Operators
getElems :: PriorityQueue -> IO [Value] Source
Return a list of all the elements of a priority queue. (not sorted)
clear :: PriorityQueue -> IO () Source
Remove all elements from a priority queue.
clone :: PriorityQueue -> IO PriorityQueue 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]
update :: PriorityQueue -> Value -> IO () Source
getHeapArray :: PriorityQueue -> IO (IOUArray Index Value) Source
Get the internal representation of a given priority queue.
getHeapVec :: PriorityQueue -> IO (UVec Value) Source
Get the internal representation of a given priority queue.
Misc operations
resizeHeapCapacity :: PriorityQueue -> Int -> IO () Source
Pre-allocate internal buffer for n elements.
resizeTableCapacity :: PriorityQueue -> Int -> IO () Source
Pre-allocate internal buffer for [0..n-1] values.