Safe Haskell	Safe
Language	Haskell2010

Data.PSQueue.Internal

Contents

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

Synopsis

data Binding k p = k :-> p
key :: Binding k p -> k
prio :: Binding k p -> p
data PSQ k p
- = Void
- | Winner k p (LTree k p) k
size :: PSQ k p -> Int
null :: PSQ k p -> Bool
lookup :: (Ord k, Ord p) => k -> PSQ k p -> Maybe p
empty :: (Ord k, Ord p) => PSQ k p
singleton :: (Ord k, Ord p) => k -> p -> PSQ k p
insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p
insertWith :: (Ord k, Ord p) => (p -> p -> p) -> k -> p -> PSQ k p -> PSQ k p
insertWithKey :: (Ord k, Ord p) => (k -> p -> p -> p) -> k -> p -> PSQ k p -> PSQ k p
delete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p
adjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k p
adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k p
update :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k p
updateWithKey :: (Ord k, Ord p) => (k -> p -> Maybe p) -> k -> PSQ k p -> PSQ k p
alter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k p
keys :: (Ord k, Ord p) => PSQ k p -> [k]
fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
fromAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
fromDistinctAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
foldm :: (a -> a -> a) -> a -> [a] -> a
toList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
toAscList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
toAscLists :: (Ord k, Ord p) => PSQ k p -> Sequ (Binding k p)
toDescList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
toDescLists :: (Ord k, Ord p) => PSQ k p -> Sequ (Binding k p)
findMin :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p)
deleteMin :: (Ord k, Ord p) => PSQ k p -> PSQ k p
minView :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p, PSQ k p)
secondBest :: (Ord k, Ord p) => LTree k p -> k -> PSQ k p
atMost :: (Ord k, Ord p) => p -> PSQ k p -> [Binding k p]
atMosts :: (Ord k, Ord p) => p -> PSQ k p -> Sequ (Binding k p)
atMostRange :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> [Binding k p]
atMostRanges :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> Sequ (Binding k p)
inrange :: Ord a => a -> (a, a) -> Bool
foldr :: (Ord k, Ord p) => (Binding k p -> b -> b) -> b -> PSQ k p -> b
foldl :: (Ord k, Ord p) => (b -> Binding k p -> b) -> b -> PSQ k p -> b
type Size = Int
data LTree k p
- = Start
- | LLoser !Size !k !p (LTree k p) !k (LTree k p)
- | RLoser !Size !k !p (LTree k p) !k (LTree k p)
size' :: LTree k p -> Size
left :: LTree a b -> LTree a b
right :: LTree a b -> LTree a b
maxKey :: PSQ k p -> k
lloser :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p
rloser :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p
omega :: Int
lbalance :: (Ord k, Ord p) => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
rbalance :: (Ord k, Ord p) => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
lbalanceLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
lbalanceRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
rbalanceLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
rbalanceRight :: Ord a => k -> a -> LTree k a -> k -> LTree k a -> LTree k a
lsingleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
rsingleLeft :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p
lsingleRight :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p
rsingleRight :: Ord a => k -> a -> LTree k a -> k -> LTree k a -> LTree k a
ldoubleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
ldoubleRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
rdoubleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
rdoubleRight :: Ord a => k -> a -> LTree k a -> k -> LTree k a -> LTree k a
play :: (Ord k, Ord p) => PSQ k p -> PSQ k p -> PSQ k p
unsafePlay :: (Ord k, Ord p) => PSQ k p -> PSQ k p -> PSQ k p
data TourView k p
- = Null
- | Single k p
- | (PSQ k p) `Play` (PSQ k p)
tourView :: Ord k => PSQ k p -> TourView k p

Binding Type

data Binding k p Source #

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

Constructors

k :-> p infix 0

Instances

Instances details

(Read k, Read p) => Read (Binding k p) Source #
Instance details Defined in Data.PSQueue.Internal Methods readsPrec :: Int -> ReadS (Binding k p) # readList :: ReadS [Binding k p] # readPrec :: ReadPrec (Binding k p) # readListPrec :: ReadPrec [Binding k p] #
(Show k, Show p) => Show (Binding k p) Source #
Instance details Defined in Data.PSQueue.Internal Methods showsPrec :: Int -> Binding k p -> ShowS # show :: Binding k p -> String # showList :: [Binding k p] -> ShowS #
(Eq k, Eq p) => Eq (Binding k p) Source #
Instance details Defined in Data.PSQueue.Internal Methods (==) :: Binding k p -> Binding k p -> Bool # (/=) :: Binding k p -> Binding k p -> Bool #
(Ord k, Ord p) => Ord (Binding k p) Source #
Instance details Defined in Data.PSQueue.Internal Methods compare :: Binding k p -> Binding k p -> Ordering # (<) :: Binding k p -> Binding k p -> Bool # (<=) :: Binding k p -> Binding k p -> Bool # (>) :: Binding k p -> Binding k p -> Bool # (>=) :: Binding k p -> Binding k p -> Bool # max :: Binding k p -> Binding k p -> Binding k p # min :: Binding k p -> Binding k p -> Binding k p #

key :: Binding k p -> k Source #

The key of a binding

prio :: Binding k p -> p Source #

The priority of a binding

Priority Search Queue Type

data PSQ k p Source #

A mapping from keys k to priorites p.

Constructors

Void
Winner k p (LTree k p) k

Instances

Instances details

(Show k, Show p, Ord k, Ord p) => Show (PSQ k p) Source #
Instance details Defined in Data.PSQueue.Internal Methods showsPrec :: Int -> PSQ k p -> ShowS # show :: PSQ k p -> String # showList :: [PSQ k p] -> ShowS #

Query

size :: PSQ k p -> Int Source #

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

null :: PSQ k p -> Bool Source #

O(1) True if the queue is empty.

lookup :: (Ord k, Ord p) => 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

empty :: (Ord k, Ord p) => PSQ k p Source #

singleton :: (Ord k, Ord p) => k -> p -> PSQ k p Source #

O(1) Build a queue with one binding.

Insertion

insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p Source #

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

insertWith :: (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.

insertWithKey :: (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

delete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p Source #

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

adjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k p Source #

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

adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k p Source #

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

update :: (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.

updateWithKey :: (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.

alter :: (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

keys :: (Ord k, Ord p) => PSQ k p -> [k] Source #

O(n) The keys of a priority queue

fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p Source #

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

fromAscList :: (Ord 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.

fromDistinctAscList :: (Ord k, 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.

foldm :: (a -> a -> a) -> a -> [a] -> a Source #

toList :: (Ord k, Ord p) => PSQ k p -> [Binding k p] Source #

O(n) Convert a queue to a list.

toAscList :: (Ord k, Ord p) => PSQ k p -> [Binding k p] Source #

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

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

toDescList :: (Ord k, Ord p) => PSQ k p -> [Binding k p] Source #

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

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

Priority Queue

findMin :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p) Source #

O(1) The binding with the lowest priority.

deleteMin :: (Ord k, Ord p) => PSQ k p -> PSQ k p Source #

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

minView :: (Ord k, 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.

secondBest :: (Ord k, Ord p) => LTree k p -> k -> PSQ k p Source #

atMost :: (Ord k, 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

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

atMostRange :: (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'

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

inrange :: Ord a => a -> (a, a) -> Bool Source #

Fold

foldr :: (Ord k, Ord p) => (Binding k p -> b -> b) -> b -> PSQ k p -> b Source #

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

foldl :: (Ord k, Ord p) => (b -> Binding k p -> b) -> b -> PSQ k p -> b Source #

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

Internals

type Size = Int Source #

data LTree k p Source #

Constructors

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

size' :: LTree k p -> Size Source #

left :: LTree a b -> LTree a b Source #

right :: LTree a b -> LTree a b Source #

maxKey :: PSQ k p -> k Source #

lloser :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

rloser :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

omega :: Int Source #

lbalance :: (Ord k, Ord p) => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

rbalance :: (Ord k, Ord p) => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

lbalanceLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

lbalanceRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

rbalanceLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

rbalanceRight :: Ord a => k -> a -> LTree k a -> k -> LTree k a -> LTree k a Source #

lsingleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

rsingleLeft :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

lsingleRight :: k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

rsingleRight :: Ord a => k -> a -> LTree k a -> k -> LTree k a -> LTree k a Source #

ldoubleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

ldoubleRight :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

rdoubleLeft :: Ord p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

rdoubleRight :: Ord a => k -> a -> LTree k a -> k -> LTree k a -> LTree k a Source #

play :: (Ord k, Ord p) => PSQ k p -> PSQ k p -> PSQ k p Source #

unsafePlay :: (Ord k, Ord p) => PSQ k p -> PSQ k p -> PSQ k p Source #

data TourView k p Source #

Constructors

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

tourView :: Ord k => PSQ k p -> TourView k p Source #