min-max-pqueue-0.1.0.1: Double-ended priority queues.

Data.IntMinMaxQueue

Description

Double-ended priority queues where priority values are integers, allowing efficient retrieval and removel from both ends of the queue.

A queue can be configured with a maximum size. Each time an insertion causes the queue to grow beyond the size limit, the greatest element will be automatically removed (rather than rejecting the insertion).

The implementation is backed by an IntMap (NonEmpty a). This means that certain operations, including peekMin, peekMax and fromList, are asymptotically more expensive than a mutable array based implementation. In a pure language like Haskell, a mutable array based implementation would be impure and need to operate inside monads. And in many applications, regardless of language, the additional time complexity would be a small or negligible price to pay to avoid destructive updates anyway.

If you only access one end of the queue (i.e., you need a regular priority queue), an implementation based on a kind of heap that is more amenable to purely functional implementations, such as binomial heap and pairing heap, is potentially more efficient. But always benchmark if performance is important; in my experience Map always wins, even for regular priority queues.

Synopsis

# IntMinMaxQueue type

A double-ended priority queue whose elements are compared on an Int field.

Instances

type Prio = Int Source #

# Construction

O(1). The empty queue.

singleton :: (a -> Prio) -> a -> IntMinMaxQueue a Source #

O(1). A queue with a single element.

fromList :: [(Prio, a)] -> IntMinMaxQueue a Source #

O(n * log n). Build a queue from a list of (priority, element) pairs.

fromListWith :: (a -> Prio) -> [a] -> IntMinMaxQueue a Source #

O(n * log n). Build a queue from a list of elements and a function from elements to priorities.

O(n) (due to calculating the queue size).

# Size

O(1). Is the queue empty?

O(1). Is the queue non-empty?

O(1). The total number of elements in the queue.

# Maximum size

Return a queue that is limited to the given number of elements. If the original queue has more elements than the size limit, the greatest elements will be dropped until the size limit is satisfied.

O(1). The size limit of the queue. It returns either Nothing (if the queue does not have a size limit) or Just n where n >= 0.

# Queue operations

insert :: (a -> Prio) -> a -> IntMinMaxQueue a -> IntMinMaxQueue a Source #

O(log n). Add the given element to the queue. If the queue has a size limit, and the insertion causes the queue to grow beyond its size limit, the greatest element will be removed from the queue, which may be the element just added.

O(log n). Retrieve the least element of the queue, if exists.

O(log n). Retrieve the greatest element of the queue, if exists.

O(log n). Remove the least element of the queue, if exists.

O(log n). Remove the greatest element of the queue, if exists.

O(log n). Remove and return the least element of the queue, if exists.

O(log n). Remove and return the greatest element of the queue, if exists.

takeMin n q returns a queue with the n least elements in q, or q itself if n >= size q.

takeMin n q returns a queue with the n greatest elements in q, or q itself if n >= size q.

dropMin n q returns a queue with the n least elements dropped from q, or empty if n >= size q.

dropMax n q returns a queue with the n greatest elements dropped from q, or empty if n >= size q.

# Traversal

## Map

map :: (a -> b) -> IntMinMaxQueue a -> IntMinMaxQueue b Source #

Map a function over all elements in the queue.

mapWithPriority :: (Prio -> a -> b) -> IntMinMaxQueue a -> IntMinMaxQueue b Source #

Map a function over all elements in the queue.

## Folds

foldr :: (a -> b -> b) -> b -> IntMinMaxQueue a -> b Source #

Fold the elements in the queue using the given right-associative binary operator, such that foldr f z == foldr f z . elems.

foldl :: (a -> b -> a) -> a -> IntMinMaxQueue b -> a Source #

Fold the elements in the queue using the given left-associative binary operator, such that foldl f z == foldl f z . elems.

foldrWithPriority :: (Prio -> a -> b -> b) -> b -> IntMinMaxQueue a -> b Source #

Fold the elements in the queue using the given right-associative binary operator, such that foldrWithPriority f z == foldr (uncurry f) z . toAscList.

foldlWithPriority :: (a -> Prio -> b -> a) -> a -> IntMinMaxQueue b -> a Source #

Fold the elements in the queue using the given left-associative binary operator, such that foldlWithPriority f z == foldr (uncurry . f) z . toAscList.

foldMapWithPriority :: Monoid m => (Prio -> a -> m) -> IntMinMaxQueue a -> m Source #

Fold the elements in the queue using the given monoid, such that foldMapWithPriority f == foldMap (uncurry f) . elems.

## Strict Folds

foldr' :: (a -> b -> b) -> b -> IntMinMaxQueue a -> b Source #

A strict version of foldr. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

foldl' :: (a -> b -> a) -> a -> IntMinMaxQueue b -> a Source #

A strict version of foldl. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

foldrWithPriority' :: (Prio -> a -> b -> b) -> b -> IntMinMaxQueue a -> b Source #

A strict version of foldrWithPriority. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

foldlWithPriority' :: (a -> Prio -> b -> a) -> a -> IntMinMaxQueue b -> a Source #

A strict version of foldlWithPriority. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

# Lists

elems :: IntMinMaxQueue a -> [a] Source #

Elements in the queue in ascending order of priority. Elements with the same priority are returned in no particular order.

toList :: IntMinMaxQueue a -> [(Prio, a)] Source #

An alias for toAscList.

toAscList :: IntMinMaxQueue a -> [(Prio, a)] Source #

Convert the queue to a list in ascending order of priority. Elements with the same priority are returned in no particular order.

toDescList :: IntMinMaxQueue a -> [(Prio, a)] Source #

Convert the queue to a list in descending order of priority. Elements with the same priority are returned in no particular order.

# Maps

O(n). Convert the queue to an IntMap.