pure-priority-queue-0.13: A pure priority queue.

Data.PurePriorityQueue.Internal

Description

This module exposes the internals of a pure priority queue, implemented on top of Data.Map.

Estimates of worst-case time complexity are given. The value n is the number of elements in the queue. The value p is the cardinality of the set of priorities of the elements in the queue. p is never greater than n.

Synopsis

# Documentation

newtype MinMaxQueue p a Source

A queue of values of type `a` with priority of type `p`.

Constructors

 MinMaxQueue FieldsunMinMaxQueue :: Map p [a]

Instances

 Functor (MinMaxQueue p) Foldable (MinMaxQueue p) (Eq p, Eq a) => Eq (MinMaxQueue p a) (Ord p, Ord a) => Ord (MinMaxQueue p a) Ord p => Monoid (MinMaxQueue p a)

O(1) An empty priority queue.

null :: MinMaxQueue p a -> BoolSource

O(1) Test whether a priority queue is empty.

singleton :: Ord p => a -> p -> MinMaxQueue p aSource

O(1) A priority queue with a single entry.

insert :: Ord p => a -> p -> MinMaxQueue p a -> MinMaxQueue p aSource

O(log p) Insert a value with given priority into a priority queue.

deleteMin :: Ord p => MinMaxQueue p a -> MinMaxQueue p aSource

O(log p) Remove the value with the minimum priority from the queue.

If the queue is empty, `deleteMin` returns `empty`. Ties are broken arbitrarily.

deleteMax :: Ord p => MinMaxQueue p a -> MinMaxQueue p aSource

O(log p) Remove the value with the maximum priority from the queue.

If the queue is empty, `deleteMax` returns `empty`. Ties are broken arbitrarily.

Arguments

 :: Ord p => (Map p [a] -> Maybe ((p, [a]), Map p [a])) The view function -> MinMaxQueue p a The priority queue -> Maybe ((a, p), MinMaxQueue p a)

Applies a `Data.Map.Map` view function to a given priority queue.

minView :: Ord p => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)Source

O(log p) View a priority queue to get the (value, priority) pair with the lowest priority and the remainder of the queue.

Ties are broken arbitrarily.

maxView :: Ord p => MinMaxQueue p a -> Maybe ((a, p), MinMaxQueue p a)Source

O(log p) View a priority queue to get the (value, priority) pair with the highest priority and the remainder of the queue.

Ties are broken arbitrarily.

minPriority :: Ord p => MinMaxQueue p a -> Maybe pSource

O(log p) Get the minimum priority of the elements in the queue.

maxPriority :: Ord p => MinMaxQueue p a -> Maybe pSource

O(log p) Get the maximum priority of the elements in the queue.

foldWithPriority :: Ord p => (p -> a -> b -> b) -> b -> MinMaxQueue p a -> bSource

O(n) Fold the priorities and values of a priority queue.

splitByPriority :: Ord p => p -> MinMaxQueue p a -> (MinMaxQueue p a, MinMaxQueue p a)Source

O(log p) Split a priority queue `q` into two queues `(q1, q2)` by the given priority `p`, such that `q1` contains exactly the entries with priority less than `p`, and `q2` containes exactly the entries with priority greater than or equal to `p`.

size :: Ord p => MinMaxQueue p a -> IntSource

O(n) The number of entries in a priority queue.

filter :: Ord p => (a -> Bool) -> MinMaxQueue p a -> MinMaxQueue p aSource

O(n) Filter all values that satisfy the predicate.

filterWithPriority :: Ord p => (a -> p -> Bool) -> MinMaxQueue p a -> MinMaxQueue p aSource

O(n) Filter all entries that satisfy the predicate.

toAscList :: Ord p => MinMaxQueue p a -> [(a, p)]Source

O(n) Convert the priority queue into a list of (value, priority) pairs in ascending priority.

Ties are broken in an arbitrary manner.