Copyright | Copyright (c) 2009-2013, David Sorokin <david.sorokin@gmail.com> |
---|---|

License | BSD3 |

Maintainer | David Sorokin <david.sorokin@gmail.com> |

Stability | experimental |

Safe Haskell | Safe-Inferred |

Language | Haskell98 |

Tested with: GHC 7.6.3

This module defines a queue that can use the specified strategies. So, having only
the `FCFS`

, `LCFS`

, `SIRO`

and `StaticPriorities`

strategies, you can build
4 x 4 x 4 = 64 different types of the queue, each of them will have its own
behaviour.

- type FCFSQueue a = Queue FCFS DoubleLinkedList FCFS DoubleLinkedList FCFS DoubleLinkedList a
- type LCFSQueue a = Queue FCFS DoubleLinkedList LCFS DoubleLinkedList FCFS DoubleLinkedList a
- type SIROQueue a = Queue FCFS DoubleLinkedList SIRO Vector FCFS DoubleLinkedList a
- type PriorityQueue a = Queue FCFS DoubleLinkedList StaticPriorities PriorityQueue FCFS DoubleLinkedList a
- data Queue si qi sm qm so qo a
- newFCFSQueue :: Int -> Simulation (FCFSQueue a)
- newLCFSQueue :: Int -> Simulation (LCFSQueue a)
- newSIROQueue :: Int -> Simulation (SIROQueue a)
- newPriorityQueue :: Int -> Simulation (PriorityQueue a)
- newQueue :: (QueueStrategy si qi, QueueStrategy sm qm, QueueStrategy so qo) => si -> sm -> so -> Int -> Simulation (Queue si qi sm qm so qo a)
- enqueueStrategy :: Queue si qi sm qm so qo a -> si
- enqueueStoringStrategy :: Queue si qi sm qm so qo a -> sm
- dequeueStrategy :: Queue si qi sm qm so qo a -> so
- queueNull :: Queue si qi sm qm so qo a -> Event Bool
- queueFull :: Queue si qi sm qm so qo a -> Event Bool
- queueMaxCount :: Queue si qi sm qm so qo a -> Int
- queueCount :: Queue si qi sm qm so qo a -> Event Int
- enqueueCount :: Queue si qi sm qm so qo a -> Event Int
- enqueueLostCount :: Queue si qi sm qm so qo a -> Event Int
- enqueueStoreCount :: Queue si qi sm qm so qo a -> Event Int
- dequeueCount :: Queue si qi sm qm so qo a -> Event Int
- dequeueExtractCount :: Queue si qi sm qm so qo a -> Event Int
- queueLoadFactor :: Queue si qi sm qm so qo a -> Event Double
- enqueueRate :: Queue si qi sm qm so qo a -> Event Double
- enqueueStoreRate :: Queue si qi sm qm so qo a -> Event Double
- dequeueRate :: Queue si qi sm qm so qo a -> Event Double
- dequeueExtractRate :: Queue si qi sm qm so qo a -> Event Double
- queueWaitTime :: Queue si qi sm qm so qo a -> Event (SamplingStats Double)
- queueTotalWaitTime :: Queue si qi sm qm so qo a -> Event (SamplingStats Double)
- enqueueWaitTime :: Queue si qi sm qm so qo a -> Event (SamplingStats Double)
- dequeueWaitTime :: Queue si qi sm qm so qo a -> Event (SamplingStats Double)
- dequeue :: (DequeueStrategy si qi, DequeueStrategy sm qm, EnqueueStrategy so qo) => Queue si qi sm qm so qo a -> Process a
- dequeueWithOutputPriority :: (DequeueStrategy si qi, DequeueStrategy sm qm, PriorityQueueStrategy so qo po) => Queue si qi sm qm so qo a -> po -> Process a
- tryDequeue :: (DequeueStrategy si qi, DequeueStrategy sm qm) => Queue si qi sm qm so qo a -> Event (Maybe a)
- enqueue :: (EnqueueStrategy si qi, EnqueueStrategy sm qm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> a -> Process ()
- enqueueWithInputPriority :: (PriorityQueueStrategy si qi pi, EnqueueStrategy sm qm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> pi -> a -> Process ()
- enqueueWithStoringPriority :: (EnqueueStrategy si qi, PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> pm -> a -> Process ()
- enqueueWithInputStoringPriorities :: (PriorityQueueStrategy si qi pi, PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> pi -> pm -> a -> Process ()
- tryEnqueue :: (EnqueueStrategy sm qm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> a -> Event Bool
- tryEnqueueWithStoringPriority :: (PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> pm -> a -> Event Bool
- enqueueOrLost :: (EnqueueStrategy sm qm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> a -> Event Bool
- enqueueOrLost_ :: (EnqueueStrategy sm qm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> a -> Event ()
- enqueueWithStoringPriorityOrLost :: (PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> pm -> a -> Event Bool
- enqueueWithStoringPriorityOrLost_ :: (PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) => Queue si qi sm qm so qo a -> pm -> a -> Event ()
- waitWhileFullQueue :: Queue si qi sm qm so qo a -> Process ()
- queueSummary :: (Show si, Show sm, Show so) => Queue si qi sm qm so qo a -> Int -> Event ShowS
- queueNullChanged :: Queue si qi sm qm so qo a -> Signal Bool
- queueNullChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- queueFullChanged :: Queue si qi sm qm so qo a -> Signal Bool
- queueFullChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- queueCountChanged :: Queue si qi sm qm so qo a -> Signal Int
- queueCountChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- enqueueCountChanged :: Queue si qi sm qm so qo a -> Signal Int
- enqueueCountChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- enqueueLostCountChanged :: Queue si qi sm qm so qo a -> Signal Int
- enqueueLostCountChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- enqueueStoreCountChanged :: Queue si qi sm qm so qo a -> Signal Int
- enqueueStoreCountChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- dequeueCountChanged :: Queue si qi sm qm so qo a -> Signal Int
- dequeueCountChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- dequeueExtractCountChanged :: Queue si qi sm qm so qo a -> Signal Int
- dequeueExtractCountChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- queueLoadFactorChanged :: Queue si qi sm qm so qo a -> Signal Double
- queueLoadFactorChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- queueWaitTimeChanged :: Queue si qi sm qm so qo a -> Signal (SamplingStats Double)
- queueWaitTimeChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- queueTotalWaitTimeChanged :: Queue si qi sm qm so qo a -> Signal (SamplingStats Double)
- queueTotalWaitTimeChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- enqueueWaitTimeChanged :: Queue si qi sm qm so qo a -> Signal (SamplingStats Double)
- enqueueWaitTimeChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- dequeueWaitTimeChanged :: Queue si qi sm qm so qo a -> Signal (SamplingStats Double)
- dequeueWaitTimeChanged_ :: Queue si qi sm qm so qo a -> Signal ()
- enqueueInitiated :: Queue si qi sm qm so qo a -> Signal a
- enqueueStored :: Queue si qi sm qm so qo a -> Signal a
- enqueueLost :: Queue si qi sm qm so qo a -> Signal a
- dequeueRequested :: Queue si qi sm qm so qo a -> Signal ()
- dequeueExtracted :: Queue si qi sm qm so qo a -> Signal a
- queueChanged_ :: Queue si qi sm qm so qo a -> Signal ()

# Queue Types

type FCFSQueue a = Queue FCFS DoubleLinkedList FCFS DoubleLinkedList FCFS DoubleLinkedList a Source

A type synonym for the ordinary FIFO queue also known as the FCFS (First Come - First Serviced) queue.

type LCFSQueue a = Queue FCFS DoubleLinkedList LCFS DoubleLinkedList FCFS DoubleLinkedList a Source

A type synonym for the ordinary LIFO queue also known as the LCFS (Last Come - First Serviced) queue.

type SIROQueue a = Queue FCFS DoubleLinkedList SIRO Vector FCFS DoubleLinkedList a Source

A type synonym for the SIRO (Serviced in Random Order) queue.

type PriorityQueue a = Queue FCFS DoubleLinkedList StaticPriorities PriorityQueue FCFS DoubleLinkedList a Source

A type synonym for the queue with static priorities applied when storing the elements in the queue.

data Queue si qi sm qm so qo a Source

Represents a queue using the specified strategies for enqueueing (input), `si`

,
internal storing (in memory), `sm`

, and dequeueing (output), `so`

, where `a`

denotes
the type of items stored in the queue. Types `qi`

, `qm`

and `qo`

are
determined automatically and you should not care about them - they
are dependent types.

# Creating Queue

newFCFSQueue :: Int -> Simulation (FCFSQueue a) Source

Create a new FCFS queue with the specified capacity.

newLCFSQueue :: Int -> Simulation (LCFSQueue a) Source

Create a new LCFS queue with the specified capacity.

newSIROQueue :: Int -> Simulation (SIROQueue a) Source

Create a new SIRO queue with the specified capacity.

newPriorityQueue :: Int -> Simulation (PriorityQueue a) Source

Create a new priority queue with the specified capacity.

:: (QueueStrategy si qi, QueueStrategy sm qm, QueueStrategy so qo) | |

=> si | the strategy applied to the enqueueing (input) processes when the queue is full |

-> sm | the strategy applied when storing items in the queue |

-> so | the strategy applied to the dequeueing (output) processes when the queue is empty |

-> Int | the queue capacity |

-> Simulation (Queue si qi sm qm so qo a) |

Create a new queue with the specified strategies and capacity.

# Queue Properties and Activities

enqueueStrategy :: Queue si qi sm qm so qo a -> si Source

The strategy applied to the enqueueing (input) processes when the queue is full.

enqueueStoringStrategy :: Queue si qi sm qm so qo a -> sm Source

The strategy applied when storing (in memory) items in the queue.

dequeueStrategy :: Queue si qi sm qm so qo a -> so Source

The strategy applied to the dequeueing (output) processes when the queue is empty.

queueNull :: Queue si qi sm qm so qo a -> Event Bool Source

Test whether the queue is empty.

See also `queueNullChanged`

and `queueNullChanged_`

.

queueFull :: Queue si qi sm qm so qo a -> Event Bool Source

Test whether the queue is full.

See also `queueFullChanged`

and `queueFullChanged_`

.

queueMaxCount :: Queue si qi sm qm so qo a -> Int Source

The queue capacity.

queueCount :: Queue si qi sm qm so qo a -> Event Int Source

Return the queue size.

See also `queueCountChanged`

and `queueCountChanged_`

.

enqueueCount :: Queue si qi sm qm so qo a -> Event Int Source

Return the total number of input items that were enqueued.

See also `enqueueCountChanged`

and `enqueueCountChanged_`

.

enqueueLostCount :: Queue si qi sm qm so qo a -> Event Int Source

Return the number of lost items.

See also `enqueueLostCountChanged`

and `enqueueLostCountChanged_`

.

enqueueStoreCount :: Queue si qi sm qm so qo a -> Event Int Source

Return the total number of input items that were stored.

See also `enqueueStoreCountChanged`

and `enqueueStoreCountChanged_`

.

dequeueCount :: Queue si qi sm qm so qo a -> Event Int Source

Return the total number of requests for dequeueing the items, not taking into account the failed attempts to dequeue immediately without suspension.

See also `dequeueCountChanged`

and `dequeueCountChanged_`

.

dequeueExtractCount :: Queue si qi sm qm so qo a -> Event Int Source

Return the total number of output items that were actually dequeued.

See also `dequeueExtractCountChanged`

and `dequeueExtractCountChanged_`

.

queueLoadFactor :: Queue si qi sm qm so qo a -> Event Double Source

Return the load factor: the queue size divided by its maximum size.

See also `queueLoadFactorChanged`

and `queueLoadFactorChanged_`

.

enqueueRate :: Queue si qi sm qm so qo a -> Event Double Source

Return the rate of the input items that were enqueued: how many items per time.

enqueueStoreRate :: Queue si qi sm qm so qo a -> Event Double Source

Return the rate of the items that were stored: how many items per time.

dequeueRate :: Queue si qi sm qm so qo a -> Event Double Source

Return the rate of the requests for dequeueing the items: how many requests per time. It does not include the failed attempts to dequeue immediately without suspension.

dequeueExtractRate :: Queue si qi sm qm so qo a -> Event Double Source

Return the rate of the output items that were actually dequeued: how many items per time.

queueWaitTime :: Queue si qi sm qm so qo a -> Event (SamplingStats Double) Source

Return the wait time from the time at which the item was stored in the queue to the time at which it was dequeued.

See also `queueWaitTimeChanged`

and `queueWaitTimeChanged_`

.

queueTotalWaitTime :: Queue si qi sm qm so qo a -> Event (SamplingStats Double) Source

Return the total wait time from the time at which the enqueueing operation was initiated to the time at which the item was dequeued.

In some sense, `queueTotalWaitTime == queueInputWaitTime + queueWaitTime`

.

See also `queueTotalWaitTimeChanged`

and `queueTotalWaitTimeChanged_`

.

enqueueWaitTime :: Queue si qi sm qm so qo a -> Event (SamplingStats Double) Source

Return the enqueue wait time from the time at which the enqueueing operation was initiated to the time at which the item was stored in the queue.

See also `enqueueWaitTimeChanged`

and `enqueueWaitTimeChanged_`

.

dequeueWaitTime :: Queue si qi sm qm so qo a -> Event (SamplingStats Double) Source

Return the dequeue wait time from the time at which the item was requested for dequeueing to the time at which it was actually dequeued.

See also `dequeueWaitTimeChanged`

and `dequeueWaitTimeChanged_`

.

# Dequeuing and Enqueuing

:: (DequeueStrategy si qi, DequeueStrategy sm qm, EnqueueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> Process a | the dequeued value |

Dequeue suspending the process if the queue is empty.

dequeueWithOutputPriority Source

:: (DequeueStrategy si qi, DequeueStrategy sm qm, PriorityQueueStrategy so qo po) | |

=> Queue si qi sm qm so qo a | the queue |

-> po | the priority for output |

-> Process a | the dequeued value |

Dequeue with the output priority suspending the process if the queue is empty.

:: (DequeueStrategy si qi, DequeueStrategy sm qm) | |

=> Queue si qi sm qm so qo a | the queue |

-> Event (Maybe a) | the dequeued value of |

Try to dequeue immediately.

:: (EnqueueStrategy si qi, EnqueueStrategy sm qm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> a | the item to enqueue |

-> Process () |

Enqueue the item suspending the process if the queue is full.

enqueueWithInputPriority Source

:: (PriorityQueueStrategy si qi pi, EnqueueStrategy sm qm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> pi | the priority for input |

-> a | the item to enqueue |

-> Process () |

Enqueue with the input priority the item suspending the process if the queue is full.

enqueueWithStoringPriority Source

:: (EnqueueStrategy si qi, PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> pm | the priority for storing |

-> a | the item to enqueue |

-> Process () |

Enqueue with the storing priority the item suspending the process if the queue is full.

enqueueWithInputStoringPriorities Source

:: (PriorityQueueStrategy si qi pi, PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> pi | the priority for input |

-> pm | the priority for storing |

-> a | the item to enqueue |

-> Process () |

Enqueue with the input and storing priorities the item suspending the process if the queue is full.

:: (EnqueueStrategy sm qm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> a | the item which we try to enqueue |

-> Event Bool |

Try to enqueue the item. Return `False`

in the monad if the queue is full.

tryEnqueueWithStoringPriority Source

:: (PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> pm | the priority for storing |

-> a | the item which we try to enqueue |

-> Event Bool |

Try to enqueue with the storing priority the item. Return `False`

in
the monad if the queue is full.

:: (EnqueueStrategy sm qm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> a | the item which we try to enqueue |

-> Event Bool |

Try to enqueue the item. If the queue is full then the item will be lost
and `False`

will be returned.

:: (EnqueueStrategy sm qm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> a | the item which we try to enqueue |

-> Event () |

Try to enqueue the item. If the queue is full then the item will be lost.

enqueueWithStoringPriorityOrLost Source

:: (PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> pm | the priority for storing |

-> a | the item which we try to enqueue |

-> Event Bool |

Try to enqueue with the storing priority the item. If the queue is full
then the item will be lost and `False`

will be returned.

enqueueWithStoringPriorityOrLost_ Source

:: (PriorityQueueStrategy sm qm pm, DequeueStrategy so qo) | |

=> Queue si qi sm qm so qo a | the queue |

-> pm | the priority for storing |

-> a | the item which we try to enqueue |

-> Event () |

Try to enqueue with the storing priority the item. If the queue is full then the item will be lost.

# Awaiting

waitWhileFullQueue :: Queue si qi sm qm so qo a -> Process () Source

Wait while the queue is full.

# Summary

queueSummary :: (Show si, Show sm, Show so) => Queue si qi sm qm so qo a -> Int -> Event ShowS Source

Return the summary for the queue with desciption of its properties and activities using the specified indent.

# Derived Signals for Properties

queueNullChanged :: Queue si qi sm qm so qo a -> Signal Bool Source

Signal when the `queueNull`

property value has changed.

queueNullChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `queueNull`

property value has changed.

queueFullChanged :: Queue si qi sm qm so qo a -> Signal Bool Source

Signal when the `queueFull`

property value has changed.

queueFullChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `queueFull`

property value has changed.

queueCountChanged :: Queue si qi sm qm so qo a -> Signal Int Source

Signal when the `queueCount`

property value has changed.

queueCountChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `queueCount`

property value has changed.

enqueueCountChanged :: Queue si qi sm qm so qo a -> Signal Int Source

Signal when the `enqueueCount`

property value has changed.

enqueueCountChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `enqueueCount`

property value has changed.

enqueueLostCountChanged :: Queue si qi sm qm so qo a -> Signal Int Source

Signal when the `enqueueLostCount`

property value has changed.

enqueueLostCountChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `enqueueLostCount`

property value has changed.

enqueueStoreCountChanged :: Queue si qi sm qm so qo a -> Signal Int Source

Signal when the `enqueueStoreCount`

property value has changed.

enqueueStoreCountChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `enqueueStoreCount`

property value has changed.

dequeueCountChanged :: Queue si qi sm qm so qo a -> Signal Int Source

Signal when the `dequeueCount`

property value has changed.

dequeueCountChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `dequeueCount`

property value has changed.

dequeueExtractCountChanged :: Queue si qi sm qm so qo a -> Signal Int Source

Signal when the `dequeueExtractCount`

property value has changed.

dequeueExtractCountChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `dequeueExtractCount`

property value has changed.

queueLoadFactorChanged :: Queue si qi sm qm so qo a -> Signal Double Source

Signal when the `queueLoadFactor`

property value has changed.

queueLoadFactorChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `queueLoadFactor`

property value has changed.

queueWaitTimeChanged :: Queue si qi sm qm so qo a -> Signal (SamplingStats Double) Source

Signal when the `queueWaitTime`

property value has changed.

queueWaitTimeChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `queueWaitTime`

property value has changed.

queueTotalWaitTimeChanged :: Queue si qi sm qm so qo a -> Signal (SamplingStats Double) Source

Signal when the `queueTotalWaitTime`

property value has changed.

queueTotalWaitTimeChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `queueTotalWaitTime`

property value has changed.

enqueueWaitTimeChanged :: Queue si qi sm qm so qo a -> Signal (SamplingStats Double) Source

Signal when the `enqueueWaitTime`

property value has changed.

enqueueWaitTimeChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `enqueueWaitTime`

property value has changed.

dequeueWaitTimeChanged :: Queue si qi sm qm so qo a -> Signal (SamplingStats Double) Source

Signal when the `dequeueWaitTime`

property value has changed.

dequeueWaitTimeChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal when the `dequeueWaitTime`

property value has changed.

# Basic Signals

enqueueInitiated :: Queue si qi sm qm so qo a -> Signal a Source

Return a signal that notifies when the enqueuing operation is initiated.

enqueueStored :: Queue si qi sm qm so qo a -> Signal a Source

Return a signal that notifies when the enqueuing operation is completed and the item is stored in the internal memory of the queue.

enqueueLost :: Queue si qi sm qm so qo a -> Signal a Source

Return a signal which notifies that the item was lost when
attempting to add it to the full queue with help of
`enqueueOrLost`

, `enqueueOrLost_`

or similar functions that imply
that the element can be lost. All their names are ending with `OrLost`

or `OrLost_`

.

In other cases the enqueued items are not lost but the corresponded process
can suspend until the internal queue storage is freed. Although there is one
exception from this rule. If the process trying to enqueue a new element was
suspended but then canceled through `cancelProcess`

from the outside then
the item will not be added.

dequeueRequested :: Queue si qi sm qm so qo a -> Signal () Source

Return a signal that notifies when the dequeuing operation was requested.

dequeueExtracted :: Queue si qi sm qm so qo a -> Signal a Source

Return a signal that notifies when the item was extracted from the internal storage of the queue and prepared for immediate receiving by the dequeuing process.

# Overall Signal

queueChanged_ :: Queue si qi sm qm so qo a -> Signal () Source

Signal whenever any property of the queue changes.

The property must have the corresponded signal. There are also characteristics similar to the properties but that have no signals. As a rule, such characteristics already depend on the simulation time and therefore they may change at any time point.