PSQueue-1.2.2: Priority Search Queue

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 => k -> PSQ k p -> Maybe p
- empty :: PSQ k p
- singleton :: 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 :: PSQ k p -> [k]
- fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
- fromAscList :: (Eq k, Ord p) => [Binding k p] -> PSQ k p
- fromDistinctAscList :: Ord p => [Binding k p] -> PSQ k p
- foldm :: (a -> a -> a) -> a -> [a] -> a
- toList :: PSQ k p -> [Binding k p]
- toAscList :: PSQ k p -> [Binding k p]
- toAscLists :: PSQ k p -> Sequ (Binding k p)
- toDescList :: PSQ k p -> [Binding k p]
- toDescLists :: PSQ k p -> Sequ (Binding k p)
- findMin :: PSQ k p -> Maybe (Binding k p)
- deleteMin :: Ord p => PSQ k p -> PSQ k p
- minView :: Ord p => PSQ k p -> Maybe (Binding k p, PSQ k p)
- secondBest :: Ord p => LTree k p -> k -> PSQ k p
- atMost :: Ord p => p -> PSQ k p -> [Binding k p]
- atMosts :: 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 :: (Binding k p -> b -> b) -> b -> PSQ k p -> b
- foldl :: (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 p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
- rbalance :: 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 p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
- 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 p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
- 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 p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p
- play :: 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 :: PSQ k p -> TourView k p
- ltreeDot :: (Show k, Show p) => PSQ k p -> String
- pennantDot :: (Show k, Show p, Ord p) => PSQ k p -> String

# 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) Source # readList :: ReadS [Binding k p] Source # readPrec :: ReadPrec (Binding k p) Source # readListPrec :: ReadPrec [Binding k p] Source #
(Show k, Show p) => Show (Binding k p) Source # |
Instance details Defined in Data.PSQueue.Internal Methods showsPrec :: Int -> Binding k p -> ShowS Source # show :: Binding k p -> String Source # showList :: [Binding k p] -> ShowS Source #
(Eq k, Eq p) => Eq (Binding k p) Source # |
Instance details Defined in Data.PSQueue.Internal Methods (==) :: Binding k p -> Binding k p -> Bool Source # (/=) :: Binding k p -> Binding k p -> Bool Source #
(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 Source #

(<) :: Binding k p -> Binding k p -> Bool Source #

(<=) :: Binding k p -> Binding k p -> Bool Source #

(>) :: Binding k p -> Binding k p -> Bool Source #

(>=) :: Binding k p -> Binding k p -> Bool Source #

max :: Binding k p -> Binding k p -> Binding k p Source #

min :: Binding k p -> Binding k p -> Binding k p Source #

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) => Show (PSQ k p) Source # |
Instance details Defined in Data.PSQueue.Internal Methods showsPrec :: Int -> PSQ k p -> ShowS Source # show :: PSQ k p -> String Source # showList :: [PSQ k p] -> ShowS Source #
(Eq k, Eq p) => Eq (PSQ k p) Source # |
Instance details Defined in Data.PSQueue.Internal Methods (==) :: PSQ k p -> PSQ k p -> Bool Source # (/=) :: PSQ k p -> PSQ k p -> Bool Source #

# 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 => 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 :: PSQ k p Source #

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

fromDistinctAscList :: 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 :: PSQ k p -> [Binding k p] Source #

O(n) Convert a queue to a list.

toAscList :: PSQ k p -> [Binding k p] Source #

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

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

toDescList :: PSQ k p -> [Binding k p] Source #

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

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

# Priority Queue

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

O(1) The binding with the lowest priority.

deleteMin :: Ord p => PSQ k p -> PSQ k p Source #

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

minView :: 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 p => LTree k p -> k -> PSQ k p Source #

atMost :: 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 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 :: (Binding k p -> b -> b) -> b -> PSQ k p -> b Source #

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

foldl :: (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 p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

rbalance :: 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 p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p 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 p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p 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 p => k -> p -> LTree k p -> k -> LTree k p -> LTree k p Source #

play :: 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 :: PSQ k p -> TourView k p Source #

ltreeDot :: (Show k, Show p) => PSQ k p -> String Source #

pennantDot :: (Show k, Show p, Ord p) => PSQ k p -> String Source #