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.
- 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
- 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
- class Monad m => Dequeue q m a | q -> a where
- class Monad m => QueueSize q m 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.
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 #
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 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.