Data.Seqn.Internal.PQueue

This is an internal module. You probably don't need to import this. Use Data.Seqn.PQueue instead.

WARNING

Definitions in this module allow violating invariants that would otherwise be guaranteed by Data.Seqn.PQueue. Use at your own risk!

PQueue

newtype PQueue a

A minimum priority queue.

PQueue can be used as a maximum priority queue by wrapping its elements with Down.

Constructors

PQueue (MSeq (Elem a))

Instances

Foldable PQueue

length

\(O(1)\).

Folds in insertion order.

Defined in Data.Seqn.Internal.PQueue

Methods

fold :: Monoid m => PQueue m -> m

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

foldMap' :: Monoid m => (a -> m) -> PQueue a -> m

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

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

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

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

foldr1 :: (a -> a -> a) -> PQueue a -> a

foldl1 :: (a -> a -> a) -> PQueue a -> a

toList :: PQueue a -> [a]

null :: PQueue a -> Bool

length :: PQueue a -> Int

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

maximum :: Ord a => PQueue a -> a

minimum :: Ord a => PQueue a -> a

sum :: Num a => PQueue a -> a

product :: Num a => PQueue a -> a

Eq1 PQueue

Defined in Data.Seqn.Internal.PQueue

Methods

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

Ord1 PQueue

Defined in Data.Seqn.Internal.PQueue

Methods

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

Show1 PQueue

Defined in Data.Seqn.Internal.PQueue

Methods

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

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

NFData1 PQueue

Defined in Data.Seqn.Internal.PQueue

Methods

liftRnf :: (a -> ()) -> PQueue a -> ()

FoldableWithIndex Int PQueue

Folds in insertion order.

Defined in Data.Seqn.Internal.PQueue

Methods

ifoldMap :: Monoid m => (Int -> a -> m) -> PQueue a -> m

ifoldMap' :: Monoid m => (Int -> a -> m) -> PQueue a -> m

ifoldr :: (Int -> a -> b -> b) -> b -> PQueue a -> b

ifoldl :: (Int -> b -> a -> b) -> b -> PQueue a -> b

ifoldr' :: (Int -> a -> b -> b) -> b -> PQueue a -> b

ifoldl' :: (Int -> b -> a -> b) -> b -> PQueue a -> b

Ord a => Monoid (PQueue a)

mempty

The empty queue.

Defined in Data.Seqn.Internal.PQueue

Methods

mempty :: PQueue a

mappend :: PQueue a -> PQueue a -> PQueue a

mconcat :: [PQueue a] -> PQueue a

Ord a => Semigroup (PQueue a)

(<>)

\(O(\left| \log n_1 - \log n_2 \right|)\). Concatenate two PQueues.

Defined in Data.Seqn.Internal.PQueue

Methods

(<>) :: PQueue a -> PQueue a -> PQueue a

sconcat :: NonEmpty (PQueue a) -> PQueue a

stimes :: Integral b => b -> PQueue a -> PQueue a

Ord a => IsList (PQueue a)

Defined in Data.Seqn.Internal.PQueue

Associated Types

type Item (PQueue a)

Methods

fromList :: [Item (PQueue a)] -> PQueue a

fromListN :: Int -> [Item (PQueue a)] -> PQueue a

toList :: PQueue a -> [Item (PQueue a)]

(Ord a, Read a) => Read (PQueue a)

Defined in Data.Seqn.Internal.PQueue

Methods

readsPrec :: Int -> ReadS (PQueue a)

readList :: ReadS [PQueue a]

readPrec :: ReadPrec (PQueue a)

readListPrec :: ReadPrec [PQueue a]

Show a => Show (PQueue a)

Defined in Data.Seqn.Internal.PQueue

Methods

showsPrec :: Int -> PQueue a -> ShowS

show :: PQueue a -> String

showList :: [PQueue a] -> ShowS

NFData a => NFData (PQueue a)

Defined in Data.Seqn.Internal.PQueue

Methods

rnf :: PQueue a -> ()

Eq a => Eq (PQueue a)

Insertion order.

Defined in Data.Seqn.Internal.PQueue

Methods

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

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

Ord a => Ord (PQueue a)

Lexicographical ordering, in insertion order.

Defined in Data.Seqn.Internal.PQueue

Methods

compare :: PQueue a -> PQueue a -> Ordering

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

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

(>) :: PQueue a -> PQueue a -> Bool

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

max :: PQueue a -> PQueue a -> PQueue a

min :: PQueue a -> PQueue a -> PQueue a

type Item (PQueue a)

Defined in Data.Seqn.Internal.PQueue

type Item (PQueue a) = a

newtype Elem a

Constructors

Elem a

Instances

Read a => Read (Elem a)

Defined in Data.Seqn.Internal.PQueue

Methods

readsPrec :: Int -> ReadS (Elem a)

readList :: ReadS [Elem a]

readPrec :: ReadPrec (Elem a)

readListPrec :: ReadPrec [Elem a]

Show a => Show (Elem a)

Defined in Data.Seqn.Internal.PQueue

Methods

showsPrec :: Int -> Elem a -> ShowS

show :: Elem a -> String

showList :: [Elem a] -> ShowS

NFData a => NFData (Elem a)

Defined in Data.Seqn.Internal.PQueue

Methods

rnf :: Elem a -> ()

Eq a => Eq (Elem a)

Defined in Data.Seqn.Internal.PQueue

Methods

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

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

Ord a => Ord (Elem a)

Defined in Data.Seqn.Internal.PQueue

Methods

compare :: Elem a -> Elem a -> Ordering

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

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

(>) :: Elem a -> Elem a -> Bool

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

max :: Elem a -> Elem a -> Elem a

min :: Elem a -> Elem a -> Elem a

Ord a => Measured (Elem a)

Defined in Data.Seqn.Internal.PQueue

Associated Types

type Measure (Elem a)

Methods

measure :: Elem a -> Measure (Elem a)

type Measure (Elem a)

Defined in Data.Seqn.Internal.PQueue

type Measure (Elem a) = Min a

newtype Min a

Constructors

Min a

Instances

NFData1 Min

Defined in Data.Seqn.Internal.PQueue

Methods

liftRnf :: (a -> ()) -> Min a -> ()

Ord a => Semigroup (Min a)

Defined in Data.Seqn.Internal.PQueue

Methods

(<>) :: Min a -> Min a -> Min a

sconcat :: NonEmpty (Min a) -> Min a

stimes :: Integral b => b -> Min a -> Min a

NFData a => NFData (Min a)

Defined in Data.Seqn.Internal.PQueue

Methods

rnf :: Min a -> ()

empty :: PQueue a

The empty queue.

singleton :: a -> PQueue a

A singleton queue.

fromList :: Ord a => [a] -> PQueue a

\(O(n)\). Create a queue from a list.

concatMap :: (Ord b, Foldable f) => (a -> PQueue b) -> f a -> PQueue b

\(O \left(\sum_i \log n_i \right)\). Map over a Foldable and concatenate the results.

insert :: Ord a => a -> PQueue a -> PQueue a

\(O(\log n)\). Insert an element into the queue.

Note: When inserting multiple elements, it is more efficient to concatenate a fresh queue rather than repeatedly insert elements.

q <> fromList xs          -- Good
foldl' (flip insert) q xs -- Worse

min :: Ord a => PQueue a -> Maybe a

\(O(1)\). The minimum element in the queue.

minView :: Ord a => PQueue a -> Maybe (a, PQueue a)

\(O(\log n)\). The minimum element in the queue, with the rest of the queue.

toSortedList :: Ord a => PQueue a -> [a]

\(O(n \log n)\). Convert to a sorted list.

Entry

data Entry k a

A priority associated with a value. A PQueue (Entry k a) may be used when the priority is separate from the value.

Constructors

Entry !k a

Instances

Functor (Entry k)

Defined in Data.Seqn.Internal.PQueue

Methods

fmap :: (a -> b) -> Entry k a -> Entry k b

(<$) :: a -> Entry k b -> Entry k a

(Read k, Read a) => Read (Entry k a)

Defined in Data.Seqn.Internal.PQueue

Methods

readsPrec :: Int -> ReadS (Entry k a)

readList :: ReadS [Entry k a]

readPrec :: ReadPrec (Entry k a)

readListPrec :: ReadPrec [Entry k a]

(Show k, Show a) => Show (Entry k a)

Defined in Data.Seqn.Internal.PQueue

Methods

showsPrec :: Int -> Entry k a -> ShowS

show :: Entry k a -> String

showList :: [Entry k a] -> ShowS

(NFData k, NFData a) => NFData (Entry k a)

Defined in Data.Seqn.Internal.PQueue

Methods

rnf :: Entry k a -> ()

Eq k => Eq (Entry k a)

Compares by k only.

Defined in Data.Seqn.Internal.PQueue

Methods

(==) :: Entry k a -> Entry k a -> Bool

(/=) :: Entry k a -> Entry k a -> Bool

Ord k => Ord (Entry k a)

Compares by k only.

Defined in Data.Seqn.Internal.PQueue

Methods

compare :: Entry k a -> Entry k a -> Ordering

(<) :: Entry k a -> Entry k a -> Bool

(<=) :: Entry k a -> Entry k a -> Bool

(>) :: Entry k a -> Entry k a -> Bool

(>=) :: Entry k a -> Entry k a -> Bool

max :: Entry k a -> Entry k a -> Entry k a

min :: Entry k a -> Entry k a -> Entry k a

entryPrio :: Entry k a -> k

The priority.

entryValue :: Entry k a -> a

The value.