Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Data.Seqn.Internal.PQueue
Description
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!
Synopsis
- newtype PQueue a = PQueue (MSeq (Elem a))
- newtype Elem a = Elem a
- newtype Min a = Min a
- empty :: PQueue a
- singleton :: a -> PQueue a
- fromList :: Ord a => [a] -> PQueue a
- concatMap :: (Ord b, Foldable f) => (a -> PQueue b) -> f a -> PQueue b
- insert :: Ord a => a -> PQueue a -> PQueue a
- min :: Ord a => PQueue a -> Maybe a
- minView :: Ord a => PQueue a -> Maybe (a, PQueue a)
- toSortedList :: Ord a => PQueue a -> [a]
- data Entry k a = Entry !k a
- entryPrio :: Entry k a -> k
- entryValue :: Entry k a -> a
PQueue
A minimum priority queue.
PQueue
can be used as a maximum priority queue by wrapping its elements
with Down
.
Instances
Foldable PQueue Source # |
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 # elem :: Eq a => a -> PQueue a -> Bool # maximum :: Ord a => PQueue a -> a # minimum :: Ord a => PQueue a -> a # | |
Eq1 PQueue Source # | |
Ord1 PQueue Source # | |
Defined in Data.Seqn.Internal.PQueue | |
Show1 PQueue Source # | |
NFData1 PQueue Source # | |
Defined in Data.Seqn.Internal.PQueue | |
FoldableWithIndex Int PQueue Source # | Folds in insertion order. |
Defined in Data.Seqn.Internal.PQueue | |
Ord a => Monoid (PQueue a) Source # |
|
Ord a => Semigroup (PQueue a) Source # |
|
Ord a => IsList (PQueue a) Source # | |
(Ord a, Read a) => Read (PQueue a) Source # | |
Show a => Show (PQueue a) Source # | |
NFData a => NFData (PQueue a) Source # | |
Defined in Data.Seqn.Internal.PQueue | |
Eq a => Eq (PQueue a) Source # | Insertion order. |
Ord a => Ord (PQueue a) Source # | Lexicographical ordering, in insertion order. |
Defined in Data.Seqn.Internal.PQueue | |
type Item (PQueue a) Source # | |
Defined in Data.Seqn.Internal.PQueue |
Constructors
Elem a |
Instances
Read a => Read (Elem a) Source # | |
Show a => Show (Elem a) Source # | |
NFData a => NFData (Elem a) Source # | |
Defined in Data.Seqn.Internal.PQueue | |
Eq a => Eq (Elem a) Source # | |
Ord a => Ord (Elem a) Source # | |
Ord a => Measured (Elem a) Source # | |
type Measure (Elem a) Source # | |
Defined in Data.Seqn.Internal.PQueue |
Constructors
Min a |
concatMap :: (Ord b, Foldable f) => (a -> PQueue b) -> f a -> PQueue b Source #
\(O \left(\sum_i \log n_i \right)\).
Map over a Foldable
and concatenate the results.
insert :: Ord a => a -> PQueue a -> PQueue a Source #
\(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
minView :: Ord a => PQueue a -> Maybe (a, PQueue a) Source #
\(O(\log n)\). The minimum element in the queue, with the rest of the queue.
toSortedList :: Ord a => PQueue a -> [a] Source #
\(O(n \log n)\). Convert to a sorted list.
Entry
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) Source # | |
(Read k, Read a) => Read (Entry k a) Source # | |
(Show k, Show a) => Show (Entry k a) Source # | |
(NFData k, NFData a) => NFData (Entry k a) Source # | |
Defined in Data.Seqn.Internal.PQueue | |
Eq k => Eq (Entry k a) Source # | Compares by |
Ord k => Ord (Entry k a) Source # | Compares by |
entryValue :: Entry k a -> a Source #
The value.