Data.FingerTree.PSQueue

Documentation

data Binding k p

Constructors

k :-> p

Instances

(Eq k, Eq p) => Eq (Binding k p)

(Ord k, Ord p) => Ord (Binding k p)

(Show k, Show p) => Show (Binding k p)

(Ord k, Ord p) => Measured (KPS k p) (Binding k p)

data PSQ k p

Instances

(Ord k, Ord p) => Eq (PSQ k p)

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

(Ord k, Ord p, Show k, Show p) => Show (PSQ k p)

(Ord k, Ord p) => Measured (KPS k p) (PSQ k p)

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.