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 |
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
- getElems :: PriorityQueue -> IO [Value]
- clear :: PriorityQueue -> IO ()
- clone :: PriorityQueue -> IO PriorityQueue
- class Monad m => Enqueue q m a | q -> a where
- class Monad m => Dequeue q m a | q -> a where
- class Monad m => QueueSize q m where
- member :: PriorityQueue -> Value -> IO Bool
- update :: PriorityQueue -> Value -> IO ()
- rebuild :: PriorityQueue -> 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 #
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 #
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] #
rebuild :: PriorityQueue -> 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.