Copyright	(c) Masahiro Sakai 2012
License	BSD-style
Maintainer	masahiro.sakai@gmail.com
Stability	provisional
Portability	non-portable
Safe Haskell	Safe-Inferred
Language	Haskell2010
Extensions	Cpp BangPatterns TypeSynonymInstances FlexibleInstances ConstrainedClassMethods MultiParamTypeClasses MagicHash

ToySolver.Internal.Data.IndexedPriorityQueue

Contents

PriorityQueue type
Constructors
Operators
Misc operations

Description

Priority queue implemented as array-based binary heap.

Synopsis

data PriorityQueue
type Value = Int
type Index = Int
newPriorityQueue :: IO PriorityQueue
newPriorityQueueBy :: (Value -> Value -> IO Bool) -> IO PriorityQueue
class Monad m => NewFifo q (m :: Type -> Type) where
- newFifo :: m q
getElems :: PriorityQueue -> IO [Value]
clear :: PriorityQueue -> IO ()
clone :: PriorityQueue -> IO PriorityQueue
class Monad m => Enqueue q (m :: Type -> Type) a | q -> a where
- enqueue :: q -> a -> m ()
- enqueueBatch :: q -> [a] -> m ()
class Monad m => Dequeue q (m :: Type -> Type) a | q -> a where
- dequeue :: q -> m (Maybe a)
- dequeueBatch :: q -> m [a]
class Monad m => QueueSize q (m :: Type -> Type) where
- queueSize :: q -> m Int
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.

Instances

Instances details

NewFifo PriorityQueue IO Source #
Instance details Defined in ToySolver.Internal.Data.IndexedPriorityQueue Methods newFifo :: IO PriorityQueue #
QueueSize PriorityQueue IO Source #
Instance details Defined in ToySolver.Internal.Data.IndexedPriorityQueue Methods queueSize :: PriorityQueue -> IO Int #
Dequeue PriorityQueue IO Value Source #
Instance details Defined in ToySolver.Internal.Data.IndexedPriorityQueue Methods dequeue :: PriorityQueue -> IO (Maybe Value) # dequeueBatch :: PriorityQueue -> IO [Value] #
Enqueue PriorityQueue IO Value Source #
Instance details Defined in ToySolver.Internal.Data.IndexedPriorityQueue Methods enqueue :: PriorityQueue -> Value -> IO () # enqueueBatch :: PriorityQueue -> [Value] -> IO () #

type Value = Int Source #

type Index = Int Source #

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.

class Monad m => NewFifo q (m :: Type -> Type) where #

Construct a new FIFO queue.

Methods

newFifo :: m q #

Instances

Instances details

NewFifo PriorityQueue IO Source #
Instance details Defined in ToySolver.Internal.Data.IndexedPriorityQueue Methods newFifo :: IO PriorityQueue #
Ord a => NewFifo (PriorityQueue a) IO Source #
Instance details Defined in ToySolver.Internal.Data.PriorityQueue Methods newFifo :: IO (PriorityQueue a) #
PrimMonad m => NewFifo (SeqQueue m a) m Source #
Instance details Defined in ToySolver.Internal.Data.SeqQueue Methods newFifo :: m (SeqQueue m a) #

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 :: Type -> Type) 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

Instances details

Enqueue PriorityQueue IO Value Source #
Instance details Defined in ToySolver.Internal.Data.IndexedPriorityQueue Methods enqueue :: PriorityQueue -> Value -> IO () # enqueueBatch :: PriorityQueue -> [Value] -> IO () #
Enqueue q m a => Enqueue (WQueue q) m a
Instance details Defined in Data.Queue Methods enqueue :: WQueue q -> a -> m () # enqueueBatch :: WQueue q -> [a] -> m () #
Enqueue (PriorityQueue a) IO a Source #
Instance details Defined in ToySolver.Internal.Data.PriorityQueue Methods enqueue :: PriorityQueue a -> a -> IO () # enqueueBatch :: PriorityQueue a -> [a] -> IO () #
PrimMonad m => Enqueue (SeqQueue m a) m a Source #
Instance details Defined in ToySolver.Internal.Data.SeqQueue Methods enqueue :: SeqQueue m a -> a -> m () # enqueueBatch :: SeqQueue m a -> [a] -> m () #

class Monad m => Dequeue q (m :: Type -> Type) 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

Instances details

Dequeue PriorityQueue IO Value Source #
Instance details Defined in ToySolver.Internal.Data.IndexedPriorityQueue Methods dequeue :: PriorityQueue -> IO (Maybe Value) # dequeueBatch :: PriorityQueue -> IO [Value] #
Dequeue q m a => Dequeue (RQueue q) m a
Instance details Defined in Data.Queue Methods dequeue :: RQueue q -> m (Maybe a) # dequeueBatch :: RQueue q -> m [a] #
Dequeue (PriorityQueue a) IO a Source #
Instance details Defined in ToySolver.Internal.Data.PriorityQueue Methods dequeue :: PriorityQueue a -> IO (Maybe a) # dequeueBatch :: PriorityQueue a -> IO [a] #
PrimMonad m => Dequeue (SeqQueue m a) m a Source #
Instance details Defined in ToySolver.Internal.Data.SeqQueue Methods dequeue :: SeqQueue m a -> m (Maybe a) # dequeueBatch :: SeqQueue m a -> m [a] #

class Monad m => QueueSize q (m :: Type -> Type) where #

Methods

queueSize :: q -> m Int #

return the number of elements in the queue

Instances

Instances details

QueueSize PriorityQueue IO Source #
Instance details Defined in ToySolver.Internal.Data.IndexedPriorityQueue Methods queueSize :: PriorityQueue -> IO Int #
QueueSize (PriorityQueue a) IO Source #
Instance details Defined in ToySolver.Internal.Data.PriorityQueue Methods queueSize :: PriorityQueue a -> IO Int #
PrimMonad m => QueueSize (SeqQueue m a) m Source #
Instance details Defined in ToySolver.Internal.Data.SeqQueue Methods queueSize :: SeqQueue m a -> m Int #

member :: PriorityQueue -> Value -> IO Bool Source #

update :: PriorityQueue -> Value -> IO () Source #

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.