%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 2014-2019, 2021-2022 The Mercury Team
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: psqueue.m.
% Main author: Matthias Güdemann.
% Stability: low.
%
% This module implements priority search queues. A priority search queue,
% or psqueue for short, combines in a single ADT the functionality of both
% a map and a priority queue.
%
% Psqueues map from priorities to keys and back. This module provides functions
% and predicates to lookup the priority of a key, to insert and to remove
% priority-key pairs, to adjust the priority of a given key, and to retrieve
% the priority/key pair with the highest conceptual priority. However,
% since in many applications of psqueues, a low number represents high
% priority; for example, Dijkstra's shortest path algorithm wants to process
% the nearest nodes first. Therefore, given two priorities PrioA and PrioB,
% this module considers priority PrioA to have the higher conceptual priority
% if compare(CMP, PrioA, PrioB) returns CMP = (<). If priorities are numerical,
% which is common but is not required, then higher priorities are represented
% by lower numbers.
%
% The operations in this module are based on the algorithms described in
% Ralf Hinze: A simple implementation technique for priority search queues,
% Proceedings of the International Conference on Functional Programming 2001,
% pages 110-121. They use a weight-balanced tree to store priority/key pairs,
% to allow the following operation complexities:
%
% psqueue.insert insert new priority/key pair: O(log n)
% psqueue.lookup lookup the priority of a key: O(log n)
% psqueue.adjust adjust the priority of a key: O(log n)
% psqueue.peek: read highest priority pair: O(1)
% psqueue.remove_least: remove highest priority pair: O(log n)
% psqueue.remove remove pair with given key: O(log n)
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module psqueue.
:- interface.
:- import_module assoc_list.
%--------------------------------------------------%
:- type psqueue(P, K).
% Create an empty priority search queue.
%
:- func init = psqueue(P, K).
:- pred init(psqueue(P, K)::out) is det.
% True iff the priority search queue is empty.
%
:- pred is_empty(psqueue(P, K)::in) is semidet.
% Create a singleton psqueue.
%
:- func singleton(P, K) = psqueue(P, K).
:- pred singleton(P::in, K::in, psqueue(P, K)::out) is det.
% Insert key K with priority P into the given priority search queue.
% Fail if the key already exists.
%
:- pred insert(P::in, K::in, psqueue(P, K)::in, psqueue(P, K)::out) is semidet.
:- pragma type_spec(pred(insert/4), P = int).
% Insert key K with priority P into the given priority search queue.
% Throw an exception if the key already exists.
%
:- func det_insert(psqueue(P, K), P, K) = psqueue(P, K).
:- pred det_insert(P::in, K::in, psqueue(P, K)::in, psqueue(P, K)::out) is det.
:- pragma type_spec(func(det_insert/3), P = int).
:- pragma type_spec(pred(det_insert/4), P = int).
% Return the highest priority priority/key pair in the given queue.
% Fail if the queue is empty.
%
:- pred peek(psqueue(P, K)::in, P::out, K::out) is semidet.
% Return the highest priority priority/key pair in the given queue.
% Throw an exception if the queue is empty.
%
:- pred det_peek(psqueue(P, K)::in, P::out, K::out) is det.
% Remove the element with the top priority. If the queue is empty, fail.
%
:- pred remove_least(P::out, K::out, psqueue(P, K)::in, psqueue(P, K)::out)
is semidet.
:- pragma type_spec(pred(remove_least/4), P = int).
% Remove the element with the top priority. If the queue is empty,
% throw an exception.
%
:- pred det_remove_least(P::out, K::out, psqueue(P, K)::in, psqueue(P, K)::out)
is det.
:- pragma type_spec(pred(det_remove_least/4), P = int).
% Create an association list from a priority search queue.
% The returned list will be in ascending order, sorted first on priority,
% and then on key.
%
:- func to_assoc_list(psqueue(P, K)) = assoc_list(P, K).
:- pred to_assoc_list(psqueue(P, K)::in, assoc_list(P, K)::out) is det.
:- pragma type_spec(func(to_assoc_list/1), P = int).
:- pragma type_spec(pred(to_assoc_list/2), P = int).
% Create a priority search queue from an assoc_list of priority/key pairs.
%
:- func from_assoc_list(assoc_list(P, K)) = psqueue(P, K).
:- pred from_assoc_list(assoc_list(P, K)::in, psqueue(P, K)::out) is det.
:- pragma type_spec(func(from_assoc_list/1), P = int).
:- pragma type_spec(pred(from_assoc_list/2), P = int).
% Remove the element with the given key from a priority queue.
% Fail if it is not in the queue.
%
:- pred remove(P::out, K::in, psqueue(P, K)::in, psqueue(P, K)::out)
is semidet.
:- pragma type_spec(pred(remove/4), P = int).
% Remove the element with the given key from a priority queue.
% Throw an exception if it is not in the queue.
%
:- pred det_remove(P::out, K::in, psqueue(P, K)::in, psqueue(P, K)::out)
is det.
:- pragma type_spec(pred(det_remove/4), P = int).
% Adjust the priority of the specified element; the new priority will be
% the value returned by the given adjustment function on the old priority.
% Fail if the element is not in the queue.
%
:- pred adjust((func(P) = P)::in, K::in, psqueue(P, K)::in, psqueue(P, K)::out)
is semidet.
:- pragma type_spec(pred(adjust/4), P = int).
% Search for the priority of the specified key. If it is not in the queue,
% fail.
%
:- pred search(psqueue(P, K)::in, K::in, P::out) is semidet.
:- pragma type_spec(pred(search/3), P = int).
% Search for the priority of the specified key. If it is not in the queue,
% throw an exception.
%
:- func lookup(psqueue(P, K), K) = P.
:- pred lookup(psqueue(P, K)::in, K::in, P::out) is det.
:- pragma type_spec(func(lookup/2), P = int).
:- pragma type_spec(pred(lookup/3), P = int).
% Return all priority/key pairs whose priority is less than or equal to
% the given priority.
%
:- func at_most(psqueue(P, K), P) = assoc_list(P, K).
:- pred at_most(psqueue(P, K)::in, P::in, assoc_list(P, K)::out) is det.
:- pragma type_spec(func(at_most/2), P = int).
:- pragma type_spec(pred(at_most/3), P = int).
% Return the number of priority/key pairs in the given queue.
%
:- func size(psqueue(P, K)) = int.
:- pred size(psqueue(P, K)::in, int::out) is det.
:- pragma type_spec(func(size/1), P = int).
:- pragma type_spec(pred(size/2), P = int).
%--------------------------------------------------%