%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1994-1995, 1997, 1999, 2003-2007, 2009 The University of
% Melbourne.
% Copyright (C) 2013-2018 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: pqueue.m.
% Main author: conway.
% Stability: high.
%
% This module implements a priority queue ADT.
%
% A pqueue is a priority queue. A priority queue holds a collection
% of key-value pairs; the interface provides operations to create
% an empty priority queue, to insert a key-value pair into a priority
% queue, and to remove the element with the lowest key.
%
% Insertion/removal is not guaranteed to be "stable"; that is,
% if you insert two values with the same key, the order in which
% they will be removed is unspecified.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module pqueue.
:- interface.

:- import_module assoc_list.

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

:- type pqueue(K, V).

    % Create an empty priority queue.
    %
:- func init = pqueue(K, V).
:- pred init(pqueue(K, V)::out) is det.

    % Succeed iff the priority queue is empty.
    %
:- pred is_empty(pqueue(K, V)::in) is semidet.

    % Extract the smallest key-value pair from the priority queue without
    % removing it. Fails if the priority queue is empty.
    %
:- pred peek(pqueue(K, V)::in, K::out, V::out) is semidet.

    % Extract the smallest key from the priority queue without removing it.
    % Fail if the priority queue is empty.
    %
:- pred peek_key(pqueue(K, V)::in, K::out) is semidet.

    % Extract the smallest value from the priority queue without removing it.
    % Fail if the priority queue is empty.
    %
:- pred peek_value(pqueue(K, V)::in, V::out) is semidet.

    % As above, but call error/1 if the priority queue is empty.
    %
:- pred det_peek(pqueue(K, V)::in, K::out, V::out) is det.
:- func det_peek_key(pqueue(K, V)) = K.
:- func det_peek_value(pqueue(K, V)) = V.

    % Insert a value V with key K into the given priority queue,
    % and return the updated priority queue.
    %
:- func insert(pqueue(K, V), K, V) = pqueue(K, V).
:- pred insert(K::in, V::in, pqueue(K, V)::in, pqueue(K, V)::out)
    is det.

    % Remove the smallest item from the priority queue.
    % Fail if the priority queue is empty.
    %
:- pred remove(K::out, V::out, pqueue(K, V)::in, pqueue(K, V)::out)
    is semidet.

    % As above, but calls error/1 if the priority queue is empty.
    %
:- pred det_remove(K::out, V::out, pqueue(K, V)::in, pqueue(K, V)::out)
    is det.

    % Merge all the entries of one priority queue with another,
    % returning the merged list.
    %
:- func merge(pqueue(K, V), pqueue(K, V)) = pqueue(K, V).
:- pred merge(pqueue(K, V)::in, pqueue(K, V)::in, pqueue(K, V)::out)
    is det.

    % Extract all the items from a priority queue by repeated removal,
    % and place them in an association list.
    %
:- func to_assoc_list(pqueue(K, V)) = assoc_list(K, V).
:- pred to_assoc_list(pqueue(K, V)::in, assoc_list(K, V)::out)
    is det.

    % Insert all the key-value pairs in an association list
    % into a priority queue.
    %
:- func assoc_list_to_pqueue(assoc_list(K, V)) = pqueue(K, V).
:- pred assoc_list_to_pqueue(assoc_list(K, V)::in, pqueue(K, V)::out)
    is det.

    % A synonym for assoc_list_to_pqueue/1.
    %
:- func from_assoc_list(assoc_list(K, V)) = pqueue(K, V).

    % length(PQueue) = Length.
    %
    % Length is the number of items in PQueue.
    %
:- func length(pqueue(K, V)) = int.

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