queuelike-1.0.9: A library of queuelike data structures, both functional and stateful.

Data.Queue.Class

Description

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

Synopsis

Documentation

data e :-> f Source

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 whereSource

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 Source

Methods

insert :: QueueKey q -> q -> qSource

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

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

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)Source

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)Source

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 qSource

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

empty :: qSource

Constructs an empty queue. The default implementation uses fromList.

singleton :: QueueKey q -> qSource

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

fromList :: [QueueKey q] -> qSource

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

size :: q -> IntSource

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

null :: q -> BoolSource

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

toList :: q -> [QueueKey q]Source

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

toList_ :: q -> [QueueKey q]Source

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

merge :: q -> q -> qSource

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] -> qSource

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)