Data.Queue.Class

Abstracts the implementation details of a single-insertion, single-extraction queuelike structure.

Documentation

data e :-> f

Type that only orders on the key, ignoring the value completely; frequently useful in priority queues, so made available here.

Constructors

e :-> f

Instances

Eq f => Eq (:-> e f)

Ord f => Ord (:-> e f)

class IQueue q where

A generic type class encapsulating a generic queuelike structure, that supports single-insertion and single-extraction; this abstraction includes priority queues, stacks, and FIFO queues. There are many minimal implementations, so each method lists the prerequisites for its default implementation. Most implementations will implement empty, (singleton and merge) or insert, (peek and delete) or extract, and size. (The absolute minimal implementation is empty, insert, extract, and size.)

Associated Types

type QueueKey q

Methods

insert :: QueueKey q -> q -> q

Inserts a single element into the queue. The default implementation uses merge and singleton.

insertAll :: [QueueKey q] -> q -> q

Inserts several elements into the queue. The default implementation uses insert. (In some cases, it may be advantageous to override this implementation with xs `insertAll` q = q `merge` fromList xs.)

extract :: q -> Maybe (QueueKey q, q)

Attempts to extract an element from the queue; if the queue is empty, returns Nothing. The default implementation uses peek and delete.

top :: q -> Maybe (QueueKey q)

Gets the element that will next be extracted from the queue, if there is an element available. The default implementation uses extract.

delete :: q -> Maybe q

Deletes an element from the queue, if the queue is nonempty. The default implementation uses extract.

empty :: q

Constructs an empty queue. The default implementation uses fromList.

singleton :: QueueKey q -> q

Constructs a queue with a single element. The default implementation uses insert and empty.

fromList :: [QueueKey q] -> q

Constructs a queue with all of the elements in the list. The default implementation uses insertAll and empty.

size :: q -> Int

Gets the size of the queue. The default implementation uses toList_.

null :: q -> Bool

Checks if the queue is empty. The default implementation uses peek.

toList :: q -> [QueueKey q]

Extracts every element from the queue. The default implementation uses extract.

toList_ :: q -> [QueueKey q]

Extracts every element from the queue, with no guarantees upon order. The default implementation uses toList.

merge :: q -> q -> q

Merges two queues so that the contents of the second queue are inserted into the first queue in extraction order. The default implementation uses toList and insertAll.

mergeAll :: [q] -> q

Instances

Ord e => IQueue (PQueue e)

IQueue (Stack e)

IQueue (Queue e)

Ord e => IQueue (TrieQueue e)

(Ord k, Semigroup v) => IQueue (FusePHeap k v)