-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | Pure priority search queues
--   
--   The psqueues package provides Priority Search Queues in three
--   different flavors.
--   
--   
--   
- OrdPSQ k p v, which uses the Ord k instance to
--   provide fast insertion, deletion and lookup. This implementation is
--   based on Ralf Hinze's A Simple Implementation Technique for
--   Priority Search Queues. Hence, it is similar to the PSQueue
--   library, although it is considerably faster and provides a slightly
--   different API.
--   
- IntPSQ p v is a far more efficient implementation. It
--   fixes the key type to Int and uses a radix tree (like
--   IntMap) with an additional min-heap property.
--   
- HashPSQ k p v is a fairly straightforward extension of
--   IntPSQ: it simply uses the keys' hashes as indices in the
--   IntPSQ. If there are any hash collisions, it uses an
--   OrdPSQ to resolve those. The performance of this
--   implementation is comparable to that of IntPSQ, but it is
--   more widely applicable since the keys are not restricted to
--   Int, but rather to any Hashable datatype.
--   
--   
--   Each of the three implementations provides the same API, so they can
--   be used interchangeably. The benchmarks show how they perform relative
--   to one another, and also compared to the other Priority Search Queue
--   implementations on Hackage: PSQueue and
--   fingertree-psqueue.
--   
--   
--   
--   Typical applications of Priority Search Queues include:
--   
--   
--   
- Caches, and more specifically LRU Caches;
--   
- Schedulers;
--   
- Pathfinding algorithms, such as Dijkstra's and A*.
--   
@package psqueues
@version 0.2.8.3

-- | IntPSQ fixes the key type to Int. It is generally much
--   faster than an OrdPSQ.
--   
--   Many operations have a worst-case complexity of O(min(n,W)). This
--   means that the operation can -- become linear in the number of
--   elements with a maximum of W -- the number of bits in an Int (32 or
--   64).
module Data.IntPSQ

-- | A priority search queue with Int keys and priorities of type
--   p and values of type v. It is strict in keys,
--   priorities and values.
data IntPSQ p v

-- | O(1) True if the queue is empty.
null :: IntPSQ p v -> Bool

-- | O(n) The number of elements stored in the queue.
size :: IntPSQ p v -> Int

-- | O(min(n,W)) Check if a key is present in the the queue.
member :: Int -> IntPSQ p v -> Bool

-- | O(min(n,W)) The priority and value of a given key, or
--   Nothing if the key is not bound.
lookup :: Int -> IntPSQ p v -> Maybe (p, v)

-- | O(1) The element with the lowest priority.
findMin :: Ord p => IntPSQ p v -> Maybe (Int, p, v)

-- | O(1) The empty queue.
empty :: IntPSQ p v

-- | O(1) Build a queue with one element.
singleton :: Ord p => Int -> p -> v -> IntPSQ p v

-- | O(min(n,W)) Insert a new key, priority and value into the
--   queue. If the key is already present in the queue, the associated
--   priority and value are replaced with the supplied priority and value.
insert :: Ord p => Int -> p -> v -> IntPSQ p v -> IntPSQ p v

-- | O(min(n,W)) Delete a key and its priority and value from the
--   queue. When the key is not a member of the queue, the original queue
--   is returned.
delete :: Ord p => Int -> IntPSQ p v -> IntPSQ p v

-- | O(min(n,W)) Delete the binding with the least priority, and
--   return the rest of the queue stripped of that binding. In case the
--   queue is empty, the empty queue is returned again.
deleteMin :: Ord p => IntPSQ p v -> IntPSQ p v

-- | O(min(n,W)) The expression alter f k queue alters the
--   value x at k, or absence thereof. alter can
--   be used to insert, delete, or update a value in a queue. It also
--   allows you to calculate an additional value b.
alter :: Ord p => (Maybe (p, v) -> (b, Maybe (p, v))) -> Int -> IntPSQ p v -> (b, IntPSQ p v)

-- | O(min(n,W)) A variant of alter which works on the
--   element with the minimum priority. Unlike alter, this variant
--   also allows you to change the key of the element.
alterMin :: Ord p => (Maybe (Int, p, v) -> (b, Maybe (Int, p, v))) -> IntPSQ p v -> (b, IntPSQ p v)

-- | O(n*min(n,W)) Build a queue from a list of (key, priority,
--   value) tuples. If the list contains more than one priority and value
--   for the same key, the last priority and value for the key is retained.
fromList :: Ord p => [(Int, p, v)] -> IntPSQ p v

-- | O(n) Convert a queue to a list of (key, priority, value)
--   tuples. The order of the list is not specified.
toList :: IntPSQ p v -> [(Int, p, v)]

-- | O(n) Obtain the list of present keys in the queue.
keys :: IntPSQ p v -> [Int]

-- | O(min(n,W)) Insert a new key, priority and value into the
--   queue. If the key is already present in the queue, then the evicted
--   priority and value can be found the first element of the returned
--   tuple.
insertView :: Ord p => Int -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v)

-- | O(min(n,W)) Delete a key and its priority and value from the
--   queue. If the key was present, the associated priority and value are
--   returned in addition to the updated queue.
deleteView :: Ord p => Int -> IntPSQ p v -> Maybe (p, v, IntPSQ p v)

-- | O(min(n,W)) Retrieve the binding with the least priority, and
--   the rest of the queue stripped of that binding.
minView :: Ord p => IntPSQ p v -> Maybe (Int, p, v, IntPSQ p v)

-- | Return a list of elements ordered by key whose priorities are at most
--   pt, and the rest of the queue stripped of these elements. The
--   returned list of elements can be in any order: no guarantees there.
atMostView :: Ord p => p -> IntPSQ p v -> ([(Int, p, v)], IntPSQ p v)

-- | O(n) Modify every value in the queue.
map :: (Int -> p -> v -> w) -> IntPSQ p v -> IntPSQ p w

-- | O(n) Maps a function over the values and priorities of the
--   queue. The function f must be monotonic with respect to the
--   priorities. I.e. if x < y, then fst (f k x v) < fst
--   (f k y v). The precondition is not checked. If f
--   is not monotonic, then the result will be invalid.
unsafeMapMonotonic :: (Key -> p -> v -> (q, w)) -> IntPSQ p v -> IntPSQ q w

-- | O(n) Strict fold over every key, priority and value in the
--   queue. The order in which the fold is performed is not specified.
fold' :: (Int -> p -> v -> a -> a) -> a -> IntPSQ p v -> a

-- | Internal function to insert a key that is *not* present in the
--   priority queue.
unsafeInsertNew :: Ord p => Key -> p -> v -> IntPSQ p v -> IntPSQ p v

-- | Internal function to insert a key with priority larger than the
--   maximal priority in the heap. This is always the case when using the
--   PSQ as the basis to implement a LRU cache, which associates a
--   access-tick-number with every element.
unsafeInsertIncreasePriority :: Ord p => Key -> p -> v -> IntPSQ p v -> IntPSQ p v
unsafeInsertIncreasePriorityView :: Ord p => Key -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v)

-- | This name is not chosen well anymore. This function:
--   
--   
--   
- Either inserts a value at a new key with a prio higher than the
--   max of the entire PSQ.
--   
- Or, overrides the value at the key with a prio strictly higher
--   than the original prio at that key (but not necessarily the max of the
--   entire PSQ).
--   
unsafeInsertWithIncreasePriority :: Ord p => (p -> v -> p -> v -> (p, v)) -> Key -> p -> v -> IntPSQ p v -> IntPSQ p v
unsafeInsertWithIncreasePriorityView :: Ord p => (p -> v -> p -> v -> (p, v)) -> Key -> p -> v -> IntPSQ p v -> (Maybe (p, v), IntPSQ p v)

-- | This can NOT be used to delete elements.
unsafeLookupIncreasePriority :: Ord p => (p -> v -> (Maybe b, p, v)) -> Key -> IntPSQ p v -> (Maybe b, IntPSQ p v)

-- | O(n^2) Internal function to check if the IntPSQ is
--   valid, i.e. if all invariants hold. This should always be the case.
valid :: Ord p => IntPSQ p v -> Bool

-- | An OrdPSQ uses the Ord instance of the key type to build
--   a priority search queue.
--   
--   It is based on Ralf Hinze's work.
--   
--   
--   
- Hinze, R., A Simple Implementation Technique for Priority Search
--   Queues, ICFP 2001, pp. 110-121
--   
--   
--   http://citeseer.ist.psu.edu/hinze01simple.html
--   
--   This means it is similar to the PSQueue package but our
--   benchmarks showed it perform quite a bit faster.
module Data.OrdPSQ

-- | A mapping from keys k to priorites p and values
--   v. It is strict in keys, priorities and values.
data OrdPSQ k p v

-- | O(1) True if the queue is empty.
null :: OrdPSQ k p v -> Bool

-- | O(1) The number of elements in a queue.
size :: OrdPSQ k p v -> Int

-- | O(log n) Check if a key is present in the the queue.
member :: Ord k => k -> OrdPSQ k p v -> Bool

-- | O(log n) The priority and value of a given key, or
--   Nothing if the key is not bound.
lookup :: Ord k => k -> OrdPSQ k p v -> Maybe (p, v)

-- | O(1) The element with the lowest priority.
findMin :: OrdPSQ k p v -> Maybe (k, p, v)

-- | O(1) The empty queue.
empty :: OrdPSQ k p v

-- | O(1) Build a queue with one element.
singleton :: k -> p -> v -> OrdPSQ k p v

-- | O(log n) Insert a new key, priority and value into the queue.
--   If the key is already present in the queue, the associated priority
--   and value are replaced with the supplied priority and value.
insert :: (Ord k, Ord p) => k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v

-- | O(log n) Delete a key and its priority and value from the
--   queue. When the key is not a member of the queue, the original queue
--   is returned.
delete :: (Ord k, Ord p) => k -> OrdPSQ k p v -> OrdPSQ k p v

-- | O(log n) Delete the binding with the least priority, and return
--   the rest of the queue stripped of that binding. In case the queue is
--   empty, the empty queue is returned again.
deleteMin :: (Ord k, Ord p) => OrdPSQ k p v -> OrdPSQ k p v

-- | O(log n) The expression alter f k queue alters the
--   value x at k, or absence thereof. alter can
--   be used to insert, delete, or update a value in a queue. It also
--   allows you to calculate an additional value b.
alter :: (Ord k, Ord p) => (Maybe (p, v) -> (b, Maybe (p, v))) -> k -> OrdPSQ k p v -> (b, OrdPSQ k p v)

-- | O(log n) A variant of alter which works on the element
--   with the minimum priority. Unlike alter, this variant also
--   allows you to change the key of the element.
alterMin :: (Ord k, Ord p) => (Maybe (k, p, v) -> (b, Maybe (k, p, v))) -> OrdPSQ k p v -> (b, OrdPSQ k p v)

-- | O(n*log n) Build a queue from a list of (key, priority, value)
--   tuples. If the list contains more than one priority and value for the
--   same key, the last priority and value for the key is retained.
fromList :: (Ord k, Ord p) => [(k, p, v)] -> OrdPSQ k p v

-- | O(n) Convert a queue to a list of (key, priority, value)
--   tuples. The order of the list is not specified.
toList :: OrdPSQ k p v -> [(k, p, v)]

-- | O(n) Convert to a list in ascending order by key.
toAscList :: OrdPSQ k p v -> [(k, p, v)]

-- | O(n) Obtain the list of present keys in the queue.
keys :: OrdPSQ k p v -> [k]

-- | O(log n) Insert a new key, priority and value into the queue.
--   If the key is already present in the queue, then the evicted priority
--   and value can be found the first element of the returned tuple.
insertView :: (Ord k, Ord p) => k -> p -> v -> OrdPSQ k p v -> (Maybe (p, v), OrdPSQ k p v)

-- | O(log n) Delete a key and its priority and value from the
--   queue. If the key was present, the associated priority and value are
--   returned in addition to the updated queue.
deleteView :: (Ord k, Ord p) => k -> OrdPSQ k p v -> Maybe (p, v, OrdPSQ k p v)

-- | O(log n) Retrieve the binding with the least priority, and the
--   rest of the queue stripped of that binding.
minView :: (Ord k, Ord p) => OrdPSQ k p v -> Maybe (k, p, v, OrdPSQ k p v)

-- | Return a list of elements ordered by key whose priorities are at most
--   pt, and the rest of the queue stripped of these elements. The
--   returned list of elements can be in any order: no guarantees there.
atMostView :: (Ord k, Ord p) => p -> OrdPSQ k p v -> ([(k, p, v)], OrdPSQ k p v)

-- | O(n) Modify every value in the queue.
map :: (k -> p -> v -> w) -> OrdPSQ k p v -> OrdPSQ k p w

-- | O(n) Maps a function over the values and priorities of the
--   queue. The function f must be monotonic with respect to the
--   priorities. I.e. if x < y, then fst (f k x v) < fst
--   (f k y v). The precondition is not checked. If f
--   is not monotonic, then the result will be invalid.
unsafeMapMonotonic :: forall k p q v w. (k -> p -> v -> (q, w)) -> OrdPSQ k p v -> OrdPSQ k q w

-- | O(n) Strict fold over every key, priority and value in the
--   queue. The order in which the fold is performed is not specified.
fold' :: (k -> p -> v -> a -> a) -> a -> OrdPSQ k p v -> a

-- | O(n^2) Internal function to check if the OrdPSQ is
--   valid, i.e. if all invariants hold. This should always be the case.
valid :: (Ord k, Ord p) => OrdPSQ k p v -> Bool

-- | A HashPSQ offers very similar performance to IntPSQ.
--   In case of collisions, it uses an OrdPSQ locally to solve
--   those.
--   
--   This means worst case complexity is usually given by O(min(n,W),
--   log n), where W is the number of bits in an Int.
--   This simplifies to O(min(n,W)) since log n is always
--   smaller than W on current machines.
module Data.HashPSQ

-- | A priority search queue with keys of type k and priorities of
--   type p and values of type v. It is strict in keys,
--   priorities and values.
data HashPSQ k p v

-- | O(1) True if the queue is empty.
null :: HashPSQ k p v -> Bool

-- | O(n) The number of elements stored in the PSQ.
size :: HashPSQ k p v -> Int

-- | O(min(n,W)) Check if a key is present in the the queue.
member :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Bool

-- | O(min(n,W)) The priority and value of a given key, or
--   Nothing if the key is not bound.
lookup :: (Ord k, Hashable k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v)

-- | O(1) The element with the lowest priority.
findMin :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v)

-- | O(1) The empty queue.
empty :: HashPSQ k p v

-- | O(1) Build a queue with one element.
singleton :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v

-- | O(min(n,W)) Insert a new key, priority and value into the
--   queue. If the key is already present in the queue, the associated
--   priority and value are replaced with the supplied priority and value.
insert :: (Ord k, Hashable k, Ord p) => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v

-- | O(min(n,W)) Delete a key and its priority and value from the
--   queue. When the key is not a member of the queue, the original queue
--   is returned.
delete :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> HashPSQ k p v

-- | O(min(n,W)) Delete the binding with the least priority, and
--   return the rest of the queue stripped of that binding. In case the
--   queue is empty, the empty queue is returned again.
deleteMin :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> HashPSQ k p v

-- | O(min(n,W)) The expression alter f k queue alters the
--   value x at k, or absence thereof. alter can
--   be used to insert, delete, or update a value in a queue. It also
--   allows you to calculate an additional value b.
alter :: (Hashable k, Ord k, Ord p) => (Maybe (p, v) -> (b, Maybe (p, v))) -> k -> HashPSQ k p v -> (b, HashPSQ k p v)

-- | O(min(n,W)) A variant of alter which works on the
--   element with the minimum priority. Unlike alter, this variant
--   also allows you to change the key of the element.
alterMin :: (Hashable k, Ord k, Ord p) => (Maybe (k, p, v) -> (b, Maybe (k, p, v))) -> HashPSQ k p v -> (b, HashPSQ k p v)

-- | O(n*min(n,W)) Build a queue from a list of (key, priority,
--   value) tuples. If the list contains more than one priority and value
--   for the same key, the last priority and value for the key is retained.
fromList :: (Hashable k, Ord k, Ord p) => [(k, p, v)] -> HashPSQ k p v

-- | O(n) Convert a queue to a list of (key, priority, value)
--   tuples. The order of the list is not specified.
toList :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [(k, p, v)]

-- | O(n) Obtain the list of present keys in the queue.
keys :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> [k]

-- | O(min(n,W)) Insert a new key, priority and value into the
--   queue. If the key is already present in the queue, then the evicted
--   priority and value can be found the first element of the returned
--   tuple.
insertView :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)

-- | O(min(n,W)) Delete a key and its priority and value from the
--   queue. If the key was present, the associated priority and value are
--   returned in addition to the updated queue.
deleteView :: (Hashable k, Ord k, Ord p) => k -> HashPSQ k p v -> Maybe (p, v, HashPSQ k p v)

-- | O(min(n,W)) Retrieve the binding with the least priority, and
--   the rest of the queue stripped of that binding.
minView :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Maybe (k, p, v, HashPSQ k p v)

-- | Return a list of elements ordered by key whose priorities are at most
--   pt, and the rest of the queue stripped of these elements. The
--   returned list of elements can be in any order: no guarantees there.
atMostView :: (Hashable k, Ord k, Ord p) => p -> HashPSQ k p v -> ([(k, p, v)], HashPSQ k p v)

-- | O(n) Modify every value in the queue.
map :: (k -> p -> v -> w) -> HashPSQ k p v -> HashPSQ k p w

-- | O(n) Maps a function over the values and priorities of the
--   queue. The function f must be monotonic with respect to the
--   priorities. I.e. if x < y, then fst (f k x v) < fst
--   (f k y v). The precondition is not checked. If f
--   is not monotonic, then the result will be invalid.
unsafeMapMonotonic :: (k -> p -> v -> (q, w)) -> HashPSQ k p v -> HashPSQ k q w

-- | O(n) Strict fold over every key, priority and value in the
--   queue. The order in which the fold is performed is not specified.
fold' :: (k -> p -> v -> a -> a) -> a -> HashPSQ k p v -> a
unsafeLookupIncreasePriority :: (Hashable k, Ord k, Ord p) => k -> p -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)
unsafeInsertIncreasePriority :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> HashPSQ k p v
unsafeInsertIncreasePriorityView :: (Hashable k, Ord k, Ord p) => k -> p -> v -> HashPSQ k p v -> (Maybe (p, v), HashPSQ k p v)

-- | O(n^2) Internal function to check if the HashPSQ is
--   valid, i.e. if all invariants hold. This should always be the case.
valid :: (Hashable k, Ord k, Ord p) => HashPSQ k p v -> Bool
