Data.IntMinMaxQueue

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.

See README.md for more information.

IntMinMaxQueue type

data IntMinMaxQueue a

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

Instances

Functor IntMinMaxQueue

Defined in Data.IntMinMaxQueue

Methods

fmap :: (a -> b) -> IntMinMaxQueue a -> IntMinMaxQueue b

(<$) :: a -> IntMinMaxQueue b -> IntMinMaxQueue a

Foldable IntMinMaxQueue

Defined in Data.IntMinMaxQueue

Methods

fold :: Monoid m => IntMinMaxQueue m -> m

foldMap :: Monoid m => (a -> m) -> IntMinMaxQueue a -> m

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

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

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

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

foldr1 :: (a -> a -> a) -> IntMinMaxQueue a -> a

foldl1 :: (a -> a -> a) -> IntMinMaxQueue a -> a

toList :: IntMinMaxQueue a -> [a]

null :: IntMinMaxQueue a -> Bool

length :: IntMinMaxQueue a -> Int

elem :: Eq a => a -> IntMinMaxQueue a -> Bool

maximum :: Ord a => IntMinMaxQueue a -> a

minimum :: Ord a => IntMinMaxQueue a -> a

sum :: Num a => IntMinMaxQueue a -> a

product :: Num a => IntMinMaxQueue a -> a

Eq1 IntMinMaxQueue

Defined in Data.IntMinMaxQueue

Methods

liftEq :: (a -> b -> Bool) -> IntMinMaxQueue a -> IntMinMaxQueue b -> Bool

Ord1 IntMinMaxQueue

Defined in Data.IntMinMaxQueue

Methods

liftCompare :: (a -> b -> Ordering) -> IntMinMaxQueue a -> IntMinMaxQueue b -> Ordering

Read1 IntMinMaxQueue

Defined in Data.IntMinMaxQueue

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (IntMinMaxQueue a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [IntMinMaxQueue a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (IntMinMaxQueue a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [IntMinMaxQueue a]

Show1 IntMinMaxQueue

Defined in Data.IntMinMaxQueue

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> IntMinMaxQueue a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [IntMinMaxQueue a] -> ShowS

Eq a => Eq (IntMinMaxQueue a)

Defined in Data.IntMinMaxQueue

Methods

(==) :: IntMinMaxQueue a -> IntMinMaxQueue a -> Bool

(/=) :: IntMinMaxQueue a -> IntMinMaxQueue a -> Bool

Data a => Data (IntMinMaxQueue a)

Defined in Data.IntMinMaxQueue

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> IntMinMaxQueue a -> c (IntMinMaxQueue a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (IntMinMaxQueue a)

toConstr :: IntMinMaxQueue a -> Constr

dataTypeOf :: IntMinMaxQueue a -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (IntMinMaxQueue a))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (IntMinMaxQueue a))

gmapT :: (forall b. Data b => b -> b) -> IntMinMaxQueue a -> IntMinMaxQueue a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> IntMinMaxQueue a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> IntMinMaxQueue a -> r

gmapQ :: (forall d. Data d => d -> u) -> IntMinMaxQueue a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> IntMinMaxQueue a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> IntMinMaxQueue a -> m (IntMinMaxQueue a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> IntMinMaxQueue a -> m (IntMinMaxQueue a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> IntMinMaxQueue a -> m (IntMinMaxQueue a)

Ord a => Ord (IntMinMaxQueue a)

Defined in Data.IntMinMaxQueue

Methods

compare :: IntMinMaxQueue a -> IntMinMaxQueue a -> Ordering

(<) :: IntMinMaxQueue a -> IntMinMaxQueue a -> Bool

(<=) :: IntMinMaxQueue a -> IntMinMaxQueue a -> Bool

(>) :: IntMinMaxQueue a -> IntMinMaxQueue a -> Bool

(>=) :: IntMinMaxQueue a -> IntMinMaxQueue a -> Bool

max :: IntMinMaxQueue a -> IntMinMaxQueue a -> IntMinMaxQueue a

min :: IntMinMaxQueue a -> IntMinMaxQueue a -> IntMinMaxQueue a

Read a => Read (IntMinMaxQueue a)

Defined in Data.IntMinMaxQueue

Methods

readsPrec :: Int -> ReadS (IntMinMaxQueue a)

readList :: ReadS [IntMinMaxQueue a]

readPrec :: ReadPrec (IntMinMaxQueue a)

readListPrec :: ReadPrec [IntMinMaxQueue a]

Show a => Show (IntMinMaxQueue a)

Defined in Data.IntMinMaxQueue

Methods

showsPrec :: Int -> IntMinMaxQueue a -> ShowS

show :: IntMinMaxQueue a -> String

showList :: [IntMinMaxQueue a] -> ShowS

type Prio = Int

Construction

empty :: IntMinMaxQueue a

O(1). The empty queue.

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

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

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

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

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

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

fromMap :: IntMap (NonEmpty a) -> IntMinMaxQueue a

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

Size

null :: IntMinMaxQueue a -> Bool

O(1). Is the queue empty?

notNull :: IntMinMaxQueue a -> Bool

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

size :: IntMinMaxQueue a -> Int

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

Maximum size

withMaxSize :: IntMinMaxQueue a -> Int -> IntMinMaxQueue a

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.

maxSize :: IntMinMaxQueue a -> Maybe Int

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

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.

peekMin :: IntMinMaxQueue a -> Maybe a

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

peekMax :: IntMinMaxQueue a -> Maybe a

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

deleteMin :: IntMinMaxQueue a -> IntMinMaxQueue a

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

deleteMax :: IntMinMaxQueue a -> IntMinMaxQueue a

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

pollMin :: IntMinMaxQueue a -> Maybe (a, IntMinMaxQueue a)

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

pollMax :: IntMinMaxQueue a -> Maybe (a, IntMinMaxQueue a)

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

takeMin :: Int -> IntMinMaxQueue a -> IntMinMaxQueue a

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

takeMax :: Int -> IntMinMaxQueue a -> IntMinMaxQueue a

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

dropMin :: Int -> IntMinMaxQueue a -> IntMinMaxQueue a

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

dropMax :: Int -> IntMinMaxQueue a -> IntMinMaxQueue a

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

Map a function over all elements in the queue.

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

Map a function over all elements in the queue.

Folds

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

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

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

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

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

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

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

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

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

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]

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

An alias for toAscList.

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

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

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

Maps

toMap :: IntMinMaxQueue a -> IntMap (NonEmpty a)

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