Module Dequeue

An implementation of double-ended queues supporting access at both ends in constant amortized time.

Author: Bernd Brassel, Olaf Chitil, Michael Hanus, Sebastian Fischer, Bjoern Peemoeller

Version: January 2015

Summary of exported operations:

 empty :: Queue a    The empty queue. cons :: a -> Queue a -> Queue a    Inserts an element at the front of the queue. snoc :: a -> Queue a -> Queue a    Inserts an element at the end of the queue. isEmpty :: Queue a -> Bool    Is the queue empty? deqLength :: Queue a -> Int    Returns the number of elements in the queue. deqHead :: Queue a -> a    The first element of the queue. deqTail :: Queue a -> Queue a    Removes an element at the front of the queue. deqLast :: Queue a -> a    The last element of the queue. deqInit :: Queue a -> Queue a    Removes an element at the end of the queue. deqReverse :: Queue a -> Queue a    Reverses a double ended queue. rotate :: Queue a -> Queue a    Moves the first element to the end of the queue. matchHead :: Queue a -> Maybe (a,Queue a)    Matches the front of a queue. matchLast :: Queue a -> Maybe (a,Queue a)    Matches the end of a queue. listToDeq :: [a] -> Queue a    Transforms a list to a double ended queue. deqToList :: Queue a -> [a]    Transforms a double ended queue to a list.

Exported datatypes:

Queue

The datatype of a queue.

Constructors:

Exported operations:

 empty :: Queue a    The empty queue. Further infos: solution complete, i.e., able to compute all solutions
 cons :: a -> Queue a -> Queue a    Inserts an element at the front of the queue.
 snoc :: a -> Queue a -> Queue a    Inserts an element at the end of the queue.
 isEmpty :: Queue a -> Bool    Is the queue empty?
 deqLength :: Queue a -> Int    Returns the number of elements in the queue.
 deqHead :: Queue a -> a    The first element of the queue.
 deqTail :: Queue a -> Queue a    Removes an element at the front of the queue.
 deqLast :: Queue a -> a    The last element of the queue.
 deqInit :: Queue a -> Queue a    Removes an element at the end of the queue.
 deqReverse :: Queue a -> Queue a    Reverses a double ended queue. Further infos: solution complete, i.e., able to compute all solutions
 rotate :: Queue a -> Queue a    Moves the first element to the end of the queue.
 matchHead :: Queue a -> Maybe (a,Queue a)    Matches the front of a queue. matchHead q is equivalent to if isEmpty q then Nothing else Just (deqHead q, deqTail q) but more efficient.
 matchLast :: Queue a -> Maybe (a,Queue a)    Matches the end of a queue. matchLast q is equivalent to if isEmpty q then Nothing else Just (deqLast q,deqInit q) but more efficient.
 listToDeq :: [a] -> Queue a    Transforms a list to a double ended queue.
 deqToList :: Queue a -> [a]    Transforms a double ended queue to a list.