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

ToySolver.Internal.Data.PriorityQueue

Contents

PriorityQueue type
Constructors
Operators
Misc operations

Description

Priority queue implemented as array-based binary heap.

Synopsis

PriorityQueue type

data PriorityQueue a Source #

Priority queue implemented as array-based binary heap.

Instances

Ord a => NewFifo (PriorityQueue a) IO Source #
Methods newFifo :: IO (PriorityQueue a) #
QueueSize (PriorityQueue a) IO Source #
Methods queueSize :: PriorityQueue a -> IO Int #
Enqueue (PriorityQueue a) IO a Source #
Methods enqueue :: PriorityQueue a -> a -> IO () # enqueueBatch :: PriorityQueue a -> [a] -> IO () #
Dequeue (PriorityQueue a) IO a Source #
Methods dequeue :: PriorityQueue a -> IO (Maybe a) # dequeueBatch :: PriorityQueue a -> IO [a] #

type Index = Int Source #

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 where #

Construct a new FIFO queue.

Minimal complete definition

newFifo

Methods

newFifo :: m q #

Instances

NewFifo PriorityQueue IO #
Methods newFifo :: IO PriorityQueue #
NewFifo (SeqQueue a) IO #
Methods newFifo :: IO (SeqQueue a) #
Ord a => NewFifo (PriorityQueue a) IO #
Methods newFifo :: IO (PriorityQueue a) #

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

enqueue

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 () #

Instances

Enqueue PriorityQueue IO Value #
Methods enqueue :: PriorityQueue -> Value -> IO () # enqueueBatch :: PriorityQueue -> [Value] -> IO () #
Enqueue q m a => Enqueue (WQueue q) m a
Methods enqueue :: WQueue q -> a -> m () # enqueueBatch :: WQueue q -> [a] -> m () #
Enqueue (SeqQueue a) IO a #
Methods enqueue :: SeqQueue a -> a -> IO () # enqueueBatch :: SeqQueue a -> [a] -> IO () #
Enqueue (PriorityQueue a) IO a #
Methods enqueue :: PriorityQueue a -> a -> IO () # enqueueBatch :: PriorityQueue a -> [a] -> IO () #

class Monad m => Dequeue q m a | q -> a where #

Minimal complete definition

dequeue

Methods

dequeue :: q -> m (Maybe a) #

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 #
Methods dequeue :: PriorityQueue -> IO (Maybe Value) # dequeueBatch :: PriorityQueue -> IO [Value] #
Dequeue q m a => Dequeue (RQueue q) m a
Methods dequeue :: RQueue q -> m (Maybe a) # dequeueBatch :: RQueue q -> m [a] #
Dequeue (SeqQueue a) IO a #
Methods dequeue :: SeqQueue a -> IO (Maybe a) # dequeueBatch :: SeqQueue a -> IO [a] #
Dequeue (PriorityQueue a) IO a #
Methods dequeue :: PriorityQueue a -> IO (Maybe a) # dequeueBatch :: PriorityQueue a -> IO [a] #

class Monad m => QueueSize q m where #

Minimal complete definition

queueSize

Methods

queueSize :: q -> m Int #

return the number of elements in the queue

Instances

QueueSize PriorityQueue IO #
Methods queueSize :: PriorityQueue -> IO Int #
QueueSize (SeqQueue a) IO #
Methods queueSize :: SeqQueue a -> IO Int #
QueueSize (PriorityQueue a) IO #
Methods queueSize :: PriorityQueue a -> IO Int #

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.