Next: , Previous: prolog, Up: Top   [Contents]


60 psqueue

%--------------------------------------------------%
% 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).

%--------------------------------------------------%


Next: , Previous: prolog, Up: Top   [Contents]