depq-0.4.2: Double-ended priority queues
Copyright(c) Marco Zocca 2020
LicenseBSD3-style (see LICENSE)
Maintainer@ocramz
Stabilityexperimental
Portabilityportable
Safe HaskellSafe-Inferred
LanguageHaskell2010

Data.DEPQ

Description

Double-ended priority queue (DEPQ)

Allows for efficiently finding and removing both the minimum and maximum priority elements, due to the min-heap invariant property of the underlying representation.

See https://en.wikipedia.org/wiki/Double-ended_priority_queue for definitions; the current implementation is based on the "dual structure" method outlined in the wikipedia page.

Based on IntPSQ : https://hackage.haskell.org/package/psqueues-0.2.7.2/docs/Data-IntPSQ.html

Usage

Populate a DEPQ (either from a Foldable collection such as a list or array or by inserting incrementally) and query either of its extremes (with findMin, findMax, popMin, popMax, topK, bottomK).

Note

Import this module qualified (e.g. import qualified Data.DEPQ as DQ or similar), as some of the function names are pretty common (e.g. lookup, empty), and might collide with similar functions imported from other libraries.

Synopsis

Documentation

data DEPQ p a Source #

A double-ended priority queue

Instances

Instances details
Foldable (DEPQ p) Source # 
Instance details

Defined in Data.DEPQ

Methods

fold :: Monoid m => DEPQ p m -> m #

foldMap :: Monoid m => (a -> m) -> DEPQ p a -> m #

foldMap' :: Monoid m => (a -> m) -> DEPQ p a -> m #

foldr :: (a -> b -> b) -> b -> DEPQ p a -> b #

foldr' :: (a -> b -> b) -> b -> DEPQ p a -> b #

foldl :: (b -> a -> b) -> b -> DEPQ p a -> b #

foldl' :: (b -> a -> b) -> b -> DEPQ p a -> b #

foldr1 :: (a -> a -> a) -> DEPQ p a -> a #

foldl1 :: (a -> a -> a) -> DEPQ p a -> a #

toList :: DEPQ p a -> [a] #

null :: DEPQ p a -> Bool #

length :: DEPQ p a -> Int #

elem :: Eq a => a -> DEPQ p a -> Bool #

maximum :: Ord a => DEPQ p a -> a #

minimum :: Ord a => DEPQ p a -> a #

sum :: Num a => DEPQ p a -> a #

product :: Num a => DEPQ p a -> a #

(Ord p, Eq a) => Eq (DEPQ p a) Source # 
Instance details

Defined in Data.DEPQ

Methods

(==) :: DEPQ p a -> DEPQ p a -> Bool #

(/=) :: DEPQ p a -> DEPQ p a -> Bool #

(Show p, Show a) => Show (DEPQ p a) Source # 
Instance details

Defined in Data.DEPQ

Methods

showsPrec :: Int -> DEPQ p a -> ShowS #

show :: DEPQ p a -> String #

showList :: [DEPQ p a] -> ShowS #

(Ord p, Arbitrary p, Arbitrary a) => Arbitrary (DEPQ p a) Source # 
Instance details

Defined in Data.DEPQ

Methods

arbitrary :: Gen (DEPQ p a) #

shrink :: DEPQ p a -> [DEPQ p a] #

(NFData p, NFData a) => NFData (DEPQ p a) Source # 
Instance details

Defined in Data.DEPQ

Methods

rnf :: DEPQ p a -> () #

Creation

empty :: DEPQ p a Source #

The empty DEPQ

Conversion from/to lists

fromList Source #

Arguments

:: (Foldable t, Ord p) 
=> t (Int, p, a)

(key, priority, value)

-> DEPQ p a 

Populate a DEPQ from a Foldable container (e.g. a list)

toList :: DEPQ p v -> [(Int, p, v)] Source #

Produce a list of (key, priority, value) triples with the entries of the DEPQ

Note : the order of the output list is undefined

Predicates

null :: DEPQ p v -> Bool Source #

Is the DEPQ empty ?

valid :: Ord p => DEPQ p v -> Bool Source #

Is the DEPQ valid ?

Properties

size :: DEPQ p a -> Int Source #

Number of elements in the DEPQ

Modification

insert Source #

Arguments

:: Ord p 
=> Int

key

-> p

priority

-> a

value

-> DEPQ p a 
-> DEPQ p a 

Insert an element

delete Source #

Arguments

:: Ord p 
=> Int

key of the triple to be deleted

-> DEPQ p a 
-> DEPQ p a 

Delete a (key, priority, value) triple from the queue. When the key is not a member of the queue, the original queue is returned.

deleteMin :: Ord p => DEPQ p a -> DEPQ p a Source #

Delete the minimum-priority element in the DEPQ

deleteMax :: Ord p => DEPQ p a -> DEPQ p a Source #

Delete the maximum-priority element in the DEPQ

popMin :: Ord p => DEPQ p v -> Maybe ((Int, p, v), DEPQ p v) Source #

Return the minimum along with a new DEPQ without that element

popMax :: Ord p => DEPQ p v -> Maybe ((Int, p, v), DEPQ p v) Source #

Return the maximum along with a new DEPQ without that element

Lookup

lookup Source #

Arguments

:: Int

lookup key

-> DEPQ p v 
-> Maybe (p, v) 

Lookup a key

findMin :: Ord p => DEPQ p v -> Maybe (Int, p, v) Source #

O(1) Find the minimum-priority element in the DEPQ

findMax :: Ord p => DEPQ p v -> Maybe (Int, p, v) Source #

O(1) Find the maximum-priority element in the DEPQ

Top-K lookup

topK :: Ord p => Int -> DEPQ p v -> Seq (Int, p, v) Source #

K highest-scoring entries in the DEPQ

NB : this returns an empty sequence if there are fewer than K elements in the DEPQ

bottomK :: Ord p => Int -> DEPQ p v -> Seq (Int, p, v) Source #

K lowest-scoring entries in the DEPQ

NB : this returns an empty sequence if there are fewer than K elements in the DEPQ