ModulePSQueue-1.2.2Haskell2010

Data.PSQueue.Internal

Contents

Binding Type
Priority Search Queue Type
Query
Construction
Insertion
Delete/Update
Conversion
Priority Queue
Fold
Internals

Synopsis

data Binding
value key
value prio
data PSQ
value size
value null
value lookup
value empty
value singleton
value insert
value insertWith
value insertWithKey
value delete
value adjust
value adjustWithKey
value update
value updateWithKey
value alter
value keys
value fromList
value fromAscList
value fromDistinctAscList
value foldm
value toList
value toAscList
value toAscLists
value toDescList
value toDescLists
value findMin
value deleteMin
value minView
value secondBest
value atMost
value atMosts
value atMostRange
value atMostRanges
value inrange
value foldr
value foldl
type Size
data LTree
value size'
value left
value right
value maxKey
value lloser
value rloser
value omega
value lbalance
value rbalance
value lbalanceLeft
value lbalanceRight
value rbalanceLeft
value rbalanceRight
value lsingleLeft
value rsingleLeft
value lsingleRight
value rsingleRight
value ldoubleLeft
value ldoubleRight
value rdoubleLeft
value rdoubleRight
value play
data TourView
value tourView
value ltreeDot
value pennantDot

PackagePSQueue-1.2.2
Exports67
LanguageHaskell2010
LicenceBSD-3-Clause
SourceInternal.hs

Binding Type

datadata Binding k p

Source#

k :-> p binds the key k with the priority p.

Constructors

k :-> pinfix 0

Instances4Eq, Ord, Read, Show

(Eq k, Eq p) => Eq (Binding k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal
(Ord k, Ord p) => Ord (Binding k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal
(Read k, Read p) => Read (Binding k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal
(Show k, Show p) => Show (Binding k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal

valuekey :: Binding k p -> k

Source#

The key of a binding

valueprio :: Binding k p -> p

Source#

The priority of a binding

Priority Search Queue Type

datadata PSQ k p

Source#

A mapping from keys k to priorites p.

Constructors

Void
Winner !k !p !(LTree k p) !k

Instances2Eq, Show

(Eq k, Eq p) => Eq (PSQ k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal
(Show k, Show p) => Show (PSQ k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal

Query

valuesize :: PSQ k p -> Int

Source#

O(1) The number of bindings in a queue.

valuenull :: PSQ k p -> Bool

Source#

O(1) True if the queue is empty.

valuelookup :: Ord k => k -> PSQ k p -> Maybe p

Source#

O(log n) The priority of a given key, or Nothing if the key is not bound.

Construction

valueempty :: PSQ k p

valuesingleton :: k -> p -> PSQ k p

Source#

O(1) Build a queue with one binding.

Insertion

valueinsert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p

Source#

O(log n) Insert a binding into the queue.

valueinsertWith

:: (Ord k, Ord p)
=> p -> p -> p
-> k
-> p
-> PSQ k p
-> PSQ k p

Source#

O(log n) Insert a binding with a combining function.

valueinsertWithKey

:: (Ord k, Ord p)
=> k -> p -> p -> p
-> k
-> p
-> PSQ k p
-> PSQ k p

Source#

O(log n) Insert a binding with a combining function.

Delete/Update

valuedelete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p

Source#

O(log n) Remove a binding from the queue.

valueadjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k p

Source#

O(log n) Adjust the priority of a key.

valueadjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k p

Source#

O(log n) Adjust the priority of a key.

valueupdate :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k p

Source#

O(log n) The expression (update f k q) updates the priority p bound k (if it is in the queue). If (f p) is Nothing, the binding is deleted. If it is (Just z), the key k is bound to the new priority z.

valueupdateWithKey

:: (Ord k, Ord p)
=> k -> p -> Maybe p
-> k
-> PSQ k p
-> PSQ k p

Source#

O(log n). The expression (updateWithKey f k q) updates the priority p bound k (if it is in the queue). If (f k p) is Nothing, the binding is deleted. If it is (Just z), the key k is bound to the new priority z.

valuealter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k p

Source#

O(log n). The expression (alter f k q) alters the priority p bound to k, or absence thereof. alter can be used to insert, delete, or update a priority in a queue.

Conversion

valuekeys :: PSQ k p -> [k]

Source#

O(n) The keys of a priority queue

valuefromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p

Source#

O(n log n) Build a queue from a list of bindings.

valuefromAscList :: (Eq k, Ord p) => [Binding k p] -> PSQ k p

Source#

O(n) Build a queue from a list of bindings in order of ascending keys. The precondition that the keys are ascending is not checked.

valuefromDistinctAscList :: Ord p => [Binding k p] -> PSQ k p

Source#

O(n) Build a queue from a list of distinct bindings in order of ascending keys. The precondition that keys are distinct and ascending is not checked.

valuefoldm :: (a -> a -> a) -> a -> [a] -> a

valuetoList :: PSQ k p -> [Binding k p]

Source#

O(n) Convert a queue to a list.

valuetoAscList :: PSQ k p -> [Binding k p]

Source#

O(n) Convert a queue to a list in ascending order of keys.

valuetoAscLists :: PSQ k p -> Sequ (Binding k p)

valuetoDescList :: PSQ k p -> [Binding k p]

Source#

O(n) Convert a queue to a list in descending order of keys.

valuetoDescLists :: PSQ k p -> Sequ (Binding k p)

Priority Queue

valuefindMin :: PSQ k p -> Maybe (Binding k p)

Source#

O(1) The binding with the lowest priority.

valuedeleteMin :: Ord p => PSQ k p -> PSQ k p

Source#

O(log n) Remove the binding with the lowest priority.

valueminView :: Ord p => PSQ k p -> Maybe (Binding k p, PSQ k p)

Source#

O(log n) Retrieve the binding with the least priority, and the rest of the queue stripped of that binding.

valuesecondBest :: Ord p => LTree k p -> k -> PSQ k p

valueatMost :: Ord p => p -> PSQ k p -> [Binding k p]

Source#

O(r(log n - log r) atMost p q is a list of all the bindings in q with priority less than p, in order of ascending keys. Effectively,

  atMost p' q = filter (\(k:->p) -> p<=p') . toList

valueatMosts :: Ord p => p -> PSQ k p -> Sequ (Binding k p)

valueatMostRange :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> [Binding k p]

Source#

O(r(log n - log r)) atMostRange p (l,u) q is a list of all the bindings in q with a priority less than p and a key in the range (l,u) inclusive. Effectively,

   atMostRange p' (l,u) q = filter (\(k:->p) -> l<=k && k<=u ) . atMost p'

valueatMostRanges

:: (Ord k, Ord p)
=> p
-> (k, k)
-> PSQ k p
-> Sequ (Binding k p)

valueinrange :: Ord a => a -> (a, a) -> Bool

Fold

valuefoldr :: (Binding k p -> b -> b) -> b -> PSQ k p -> b

Source#

Right fold over the bindings in the queue, in key order.

valuefoldl :: (b -> Binding k p -> b) -> b -> PSQ k p -> b

Source#

Left fold over the bindings in the queue, in key order.

Internals

typetype Size = Int

datadata LTree k p

Constructors

Start
LLoser !Size !k !p !(LTree k p) !k !(LTree k p)
RLoser !Size !k !p !(LTree k p) !k !(LTree k p)

valuesize' :: LTree k p -> Size

valueleft :: LTree a b -> LTree a b

valueright :: LTree a b -> LTree a b

valuemaxKey :: PSQ k p -> k

valuelloser :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuerloser :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valueomega :: Int

valuelbalance :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuerbalance :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuelbalanceLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuelbalanceRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuerbalanceLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuerbalanceRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuelsingleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuersingleLeft :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuelsingleRight :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuersingleRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valueldoubleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valueldoubleRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuerdoubleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valuerdoubleRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p

valueplay :: Ord p => PSQ k p -> PSQ k p -> PSQ k p

datadata TourView k p

Constructors

Null
Single !k !p
Play !(PSQ k p) !(PSQ k p)

valuetourView :: PSQ k p -> TourView k p

valueltreeDot :: (Show k, Show p) => PSQ k p -> String

valuepennantDot :: (Show k, Show p, Ord p) => PSQ k p -> String