1/*  Part of SWI-Prolog
    2
    3    Author:        Lars Buitinck
    4    E-mail:        larsmans@gmail.com
    5    WWW:           http://www.swi-prolog.org
    6    Copyright (c)  2006-2015, Lars Buitinck
    7    All rights reserved.
    8
    9    Redistribution and use in source and binary forms, with or without
   10    modification, are permitted provided that the following conditions
   11    are met:
   12
   13    1. Redistributions of source code must retain the above copyright
   14       notice, this list of conditions and the following disclaimer.
   15
   16    2. Redistributions in binary form must reproduce the above copyright
   17       notice, this list of conditions and the following disclaimer in
   18       the documentation and/or other materials provided with the
   19       distribution.
   20
   21    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   22    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   23    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   24    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   25    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   26    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   27    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   28    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   29    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   30    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   31    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   32    POSSIBILITY OF SUCH DAMAGE.
   33*/
   34
   35:- module(heaps,
   36          [ add_to_heap/4,              % +Heap0, +Priority, ?Key, -Heap
   37            delete_from_heap/4,         % +Heap0, -Priority, +Key, -Heap
   38            empty_heap/1,               % +Heap
   39            get_from_heap/4,            % ?Heap0, ?Priority, ?Key, -Heap
   40            heap_size/2,                % +Heap, -Size:int
   41            heap_to_list/2,             % +Heap, -List:list
   42            is_heap/1,                  % +Term
   43            list_to_heap/2,             % +List:list, -Heap
   44            merge_heaps/3,              % +Heap0, +Heap1, -Heap
   45            min_of_heap/3,              % +Heap, ?Priority, ?Key
   46            min_of_heap/5,              % +Heap, ?Priority1, ?Key1,
   47                                        %        ?Priority2, ?Key2
   48            singleton_heap/3            % ?Heap, ?Priority, ?Key
   49          ]).   50
   51/** <module> heaps/priority queues
   52 *
   53 * Heaps are data structures that return the entries inserted into them in an
   54 * ordered fashion, based on a priority. This makes them the data structure of
   55 * choice for implementing priority queues, a central element of algorithms
   56 * such as best-first/A* search and Kruskal's minimum-spanning-tree algorithm.
   57 *
   58 * This module implements min-heaps, meaning that items are retrieved in
   59 * ascending order of key/priority. It was designed to be compatible with
   60 * the SICStus Prolog library module of the same name. merge_heaps/3 and
   61 * singleton_heap/3 are SWI-specific extension. The portray_heap/1 predicate
   62 * is not implemented.
   63 *
   64 * Although the data items can be arbitrary Prolog data, keys/priorities must
   65 * be ordered by @=</2. Be careful when using variables as keys, since binding
   66 * them in between heap operations may change the ordering.
   67 *
   68 * The current version implements pairing heaps. These support insertion and
   69 * merging both in constant time, deletion of the minimum in logarithmic
   70 * amortized time (though delete-min, i.e., get_from_heap/3, takes linear time
   71 * in the worst case).
   72 *
   73 * @author Lars Buitinck
   74 */
   75
   76/*
   77 * Heaps are represented as heap(H,Size) terms, where H is a pairing heap and
   78 * Size is an integer. A pairing heap is either nil or a term
   79 * t(X,PrioX,Sub) where Sub is a list of pairing heaps t(Y,PrioY,Sub) s.t.
   80 * PrioX @< PrioY. See predicate is_heap/2, below.
   81 */
   82
   83%!  add_to_heap(+Heap0, +Priority, ?Key, -Heap) is semidet.
   84%
   85%   Adds Key with priority Priority  to   Heap0,  constructing a new
   86%   heap in Heap.
   87
   88add_to_heap(heap(Q0,M),P,X,heap(Q1,N)) :-
   89    meld(Q0,t(X,P,[]),Q1),
   90    N is M+1.
   91
   92%!  delete_from_heap(+Heap0, -Priority, +Key, -Heap) is semidet.
   93%
   94%   Deletes Key from Heap0, leaving its priority in Priority and the
   95%   resulting data structure in Heap.   Fails if Key is not found in
   96%   Heap0.
   97%
   98%   @bug This predicate is extremely inefficient and exists only for
   99%        SICStus compatibility.
  100
  101delete_from_heap(Q0,P,X,Q) :-
  102    get_from_heap(Q0,P,X,Q),
  103    !.
  104delete_from_heap(Q0,Px,X,Q) :-
  105    get_from_heap(Q0,Py,Y,Q1),
  106    delete_from_heap(Q1,Px,X,Q2),
  107    add_to_heap(Q2,Py,Y,Q).
  108
  109%!  empty_heap(?Heap) is semidet.
  110%
  111%   True if Heap is an empty heap. Complexity: constant.
  112
  113empty_heap(heap(nil,0)).
  114
  115%!  singleton_heap(?Heap, ?Priority, ?Key) is semidet.
  116%
  117%   True if Heap is a heap with the single element Priority-Key.
  118%
  119%   Complexity: constant.
  120
  121singleton_heap(heap(t(X,P,[]), 1), P, X).
  122
  123%!  get_from_heap(?Heap0, ?Priority, ?Key, -Heap) is semidet.
  124%
  125%   Retrieves the minimum-priority  pair   Priority-Key  from Heap0.
  126%   Heap is Heap0 with that pair removed.   Complexity:  logarithmic
  127%   (amortized), linear in the worst case.
  128
  129get_from_heap(heap(t(X,P,Sub),M), P, X, heap(Q,N)) :-
  130    pairing(Sub,Q),
  131    N is M-1.
  132
  133%!  heap_size(+Heap, -Size:int) is det.
  134%
  135%   Determines the number of elements in Heap. Complexity: constant.
  136
  137heap_size(heap(_,N),N).
  138
  139%!  heap_to_list(+Heap, -List:list) is det.
  140%
  141%   Constructs a list List  of   Priority-Element  terms, ordered by
  142%   (ascending) priority. Complexity: $O(n \log n)$.
  143
  144heap_to_list(Q,L) :-
  145    to_list(Q,L).
  146to_list(heap(nil,0),[]) :- !.
  147to_list(Q0,[P-X|Xs]) :-
  148    get_from_heap(Q0,P,X,Q),
  149    heap_to_list(Q,Xs).
  150
  151%!  is_heap(+X) is semidet.
  152%
  153%   Returns true if X is a heap.  Validates the consistency of the
  154%   entire heap. Complexity: linear.
  155
  156is_heap(V) :-
  157    var(V), !, fail.
  158is_heap(heap(Q,N)) :-
  159    integer(N),
  160    nonvar(Q),
  161    (   Q == nil
  162    ->  N == 0
  163    ;   N > 0,
  164        Q = t(_,MinP,Sub),
  165        are_pairing_heaps(Sub, MinP)
  166    ).
  167
  168% True iff 1st arg is a pairing heap with min key @=< 2nd arg,
  169% where min key of nil is logically @> any term.
  170is_pairing_heap(V, _) :-
  171    var(V),
  172    !,
  173    fail.
  174is_pairing_heap(nil, _).
  175is_pairing_heap(t(_,P,Sub), MinP) :-
  176    MinP @=< P,
  177    are_pairing_heaps(Sub, P).
  178
  179% True iff 1st arg is a list of pairing heaps, each with min key @=< 2nd arg.
  180are_pairing_heaps(V, _) :-
  181    var(V),
  182    !,
  183    fail.
  184are_pairing_heaps([], _).
  185are_pairing_heaps([Q|Qs], MinP) :-
  186    is_pairing_heap(Q, MinP),
  187    are_pairing_heaps(Qs, MinP).
  188
  189%!  list_to_heap(+List:list, -Heap) is det.
  190%
  191%   If List is a list of  Priority-Element  terms, constructs a heap
  192%   out of List. Complexity: linear.
  193
  194list_to_heap(Xs,Q) :-
  195    empty_heap(Empty),
  196    list_to_heap(Xs,Empty,Q).
  197
  198list_to_heap([],Q,Q).
  199list_to_heap([P-X|Xs],Q0,Q) :-
  200    add_to_heap(Q0,P,X,Q1),
  201    list_to_heap(Xs,Q1,Q).
  202
  203%!  min_of_heap(+Heap, ?Priority, ?Key) is semidet.
  204%
  205%   Unifies Key with  the  minimum-priority   element  of  Heap  and
  206%   Priority with its priority value. Complexity: constant.
  207
  208min_of_heap(heap(t(X,P,_),_), P, X).
  209
  210%!  min_of_heap(+Heap, ?Priority1, ?Key1, ?Priority2, ?Key2) is semidet.
  211%
  212%   Gets the two minimum-priority elements from Heap. Complexity: logarithmic
  213%   (amortized).
  214%
  215%   Do not use this predicate; it exists for compatibility with earlier
  216%   implementations of this library and the SICStus counterpart. It performs
  217%   a linear amount of work in the worst case that a following get_from_heap
  218%   has to re-do.
  219
  220min_of_heap(Q,Px,X,Py,Y) :-
  221    get_from_heap(Q,Px,X,Q0),
  222    min_of_heap(Q0,Py,Y).
  223
  224%!  merge_heaps(+Heap0, +Heap1, -Heap) is det.
  225%
  226%   Merge the two heaps Heap0 and Heap1 in Heap. Complexity: constant.
  227
  228merge_heaps(heap(L,K),heap(R,M),heap(Q,N)) :-
  229    meld(L,R,Q),
  230    N is K+M.
  231
  232
  233% Merge two pairing heaps according to the pairing heap definition.
  234meld(nil,Q,Q) :- !.
  235meld(Q,nil,Q) :- !.
  236meld(L,R,Q) :-
  237    L = t(X,Px,SubL),
  238    R = t(Y,Py,SubR),
  239    (   Px @< Py
  240    ->  Q = t(X,Px,[R|SubL])
  241    ;   Q = t(Y,Py,[L|SubR])
  242    ).
  243
  244% "Pair up" (recursively meld) a list of pairing heaps.
  245pairing([], nil).
  246pairing([Q], Q) :- !.
  247pairing([Q0,Q1|Qs], Q) :-
  248    meld(Q0, Q1, Q2),
  249    pairing(Qs, Q3),
  250    meld(Q2, Q3, Q)