/* heap.q: priority queue data structure implemented as binary trees
   $Id: heap.q,v 1.2 2004/01/28 16:54:43 agraef Exp $ */

/* This file is part of the Q programming system.

   The Q programming system is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   The Q programming system is distributed in the hope that it will be
   useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */

include stdlib, stddecl;

/* Heaps allow quick (constant time) access to the smallest member, and to
   remove the smallest nember and insert new elements in logarithmic time.
   This implementation does not allow quick update of heap members; if
   such functionality is required, bags should be used instead (see bag.q).
   
   Heap members must be ordered by the <= predicate. Multiple instances
   of the same element may be stored in a heap; however, the order in
   which equal elements are retrieved is not specified. */

public type Heap = private const nil, bin B X H1 H2;

/* Construction and type checking: */

public emptyheap;		// return the empty heap
public heap Xs;			// construct heap from list Xs
public isheap X;		// check whether X is a heap

/* Overloaded and public operations: */

// #H				// size of a heap

// null H			// tests whether H is the empty heap
// list H, members H		// lists members of H in ascending order

// first H			// first (i.e. smallest) member of H
// rmfirst H			// remove smallest member from H
// insert H X			// insert H into X

/* Implementation: ********************************************************/

private last H;			// return last member of heap
private rmlast H;		// remove last member from heap
private update H;		// update heap after deletion

emptyheap			= nil;
heap Xs:List			= foldl insert nil Xs;

isheap _:Heap			= true;
isheap _			= false otherwise;

#nil				= 0;
#bin 0 _ H1 _			= #H1*2+1;
#bin 1 _ H1 _			= #H1*2;

null nil			= true;
null _:Heap			= false otherwise;

members H:Heap			= [] if null H;
				= [first H|members (rmfirst H)] otherwise;

first (bin _ X _ _)		= X;

rmfirst (bin 0 _ nil nil)	= nil;
rmfirst (bin 0 _ H1 H2)		= update (bin 1 (last H2) H1 (rmlast H2));
rmfirst (bin 1 _ H1 H2)		= update (bin 0 (last H1) (rmlast H1) H2);

insert nil Y			= bin 0 Y nil nil;
insert (bin 0 X H1 H2) Y	= bin 1 X (insert H1 Y) H2 if X<=Y;
				= bin 1 Y (insert H1 X) H2 otherwise;
insert (bin 1 X H1 H2) Y	= bin 0 X H1 (insert H2 Y) if X<=Y;
				= bin 0 Y H1 (insert H2 X) otherwise;

last (bin 0 X nil nil)		= X;
last (bin 0 _ _ H2)		= last H2;
last (bin 1 _ H1 _)		= last H1;

rmlast (bin 0 _ nil nil)	= nil;
rmlast (bin 0 X H1 H2)		= bin 1 X H1 (rmlast H2);
rmlast (bin 1 X H1 H2)		= bin 0 X (rmlast H1) H2;

update (bin 0 X nil nil)	= bin 0 X nil nil;
update (bin 1 X (bin B1 X1 H1 H2) nil)
				= bin 1 X (bin B1 X1 H1 H2) nil
				      if X<=X1;
				= bin 1 X1 (update (bin B1 X H1 H2))
				  nil otherwise;
update (bin B X (bin B1 X1 H1 H2) (bin B2 X2 H3 H4))
				= bin B X (bin B1 X1 H1 H2)
				  (bin B2 X2 H3 H4)
				      if (X<=X1) and then (X<=X2);
				= bin B X1 (update (bin B1 X H1 H2))
				  (bin B2 X2 H3 H4)
				      if X1<=X2;
				= bin B X2 (bin B1 X1 H1 H2)
				  (update (bin B2 X H3 H4))
				      otherwise;

/* equality: */

(nil = nil)			= true;
(nil = bin _ _ _ _)		= false;
(bin _ _ _ _ = nil)		= false;
(bin B1 X1 H1 H2 = bin B2 X2 H3 H4)
				= (B1=B2) and then (X1=X2) and then (H1=H3)
				  and then (H2=H4);

nil <> nil			= false;
nil <> bin _ _ _ _		= true;
bin _ _ _ _ <> nil		= true;
bin B1 X1 H1 H2 <> bin B2 X2 H3 H4
				= (B1<>B2) or else (X1<>X2) or else (H1<>H3)
				  or else (H2<>H4);