Safe Haskell	None
Language	Haskell98

Data.FingerTree.PSQueue

Synopsis

Documentation

data Binding k p #

Constructors

k :-> p

Instances

(Eq p, Eq k) => Eq (Binding k p) #
Methods (==) :: Binding k p -> Binding k p -> Bool # (/=) :: Binding k p -> Binding k p -> Bool #
(Ord p, Ord k) => Ord (Binding k p) #
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 #
(Show p, Show k) => Show (Binding k p) #
Methods showsPrec :: Int -> Binding k p -> ShowS # show :: Binding k p -> String # showList :: [Binding k p] -> ShowS #

data PSQ k p #

Instances

(Eq k, Eq p) => Eq (PSQ k p) #
Methods (==) :: PSQ k p -> PSQ k p -> Bool # (/=) :: PSQ k p -> PSQ k p -> Bool #
(Ord k, Ord p) => Ord (PSQ k p) #
Methods compare :: PSQ k p -> PSQ k p -> Ordering # (<) :: PSQ k p -> PSQ k p -> Bool # (<=) :: PSQ k p -> PSQ k p -> Bool # (>) :: PSQ k p -> PSQ k p -> Bool # (>=) :: PSQ k p -> PSQ k p -> Bool # max :: PSQ k p -> PSQ k p -> PSQ k p # min :: PSQ k p -> PSQ k p -> PSQ k p #
(Show k, Show p) => Show (PSQ k p) #
Methods showsPrec :: Int -> PSQ k p -> ShowS # show :: PSQ k p -> String # showList :: [PSQ k p] -> ShowS #

size :: (Ord k, Ord p) => PSQ k p -> Int #

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

null :: (Ord k, Ord p) => PSQ k p -> Bool #

O(1). Test if a queue is empty.

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

O(log n). Determine if a key is in the queue, and its priority.

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

O(1). The empty queue.

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

O(1). Construct a queue with a single key/priority binding.

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

O(log n). Alters a priority search queue such that lookup k (alter f k q) = f (lookup k q). This can be used to insert, delete, or update a priority in a queue.

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

O(log n). Delete a key from a queue.

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

O(log n). Adjust the priority of a key in the queue, provided that key exists.

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

O(log n). Adjust the priority of a key in the queue, provided that key exists, according to a function which additionally takes the key as a parameter.

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

O(log n). Update or delete a priority in the queue, provided that key exists.

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

O(log n). Update or delete a priority in the queue, provided that key exists, according to a function which additionally takes the key as a parameter.

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

O(n). Flatten a queue into a list of bindings.

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

O(n). Extract the list of keys of a queue.

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

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

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

O(n log n). Contstruct a queue from an already ascending list of bindings. Does not check that the list is sorted.

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

O(log n). Split a queue into the element with minimum priority, and the remainder.

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

O(1). Find the binding with minimum priority in a queue.

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

O(log n). Delete the key with minimum priority from a queue.

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

O(log n). The expression range (l,u) q selects the keys k from q where l <= k and k <= u.

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

O(r (log n)). Finds all the bindings in a queue whose priority is less than the given value.

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

Right fold over the list of bindings in a queue.

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

Left fold over the list of bindings in a queue.