/* queue.q: efficient queue data structure (Frank Drewes, May 1993) */

/* This script provides a FIFO queue data structure which implements all
   fundamental queue operations (enqueue a new element, access and dequeue
   the head element of a queue) in logarithmic time. Furthermore, normal
   forms of queues are completely determined by the queue members, so queues
   can be compared syntactically (using the stdlib::eq predicate). */

/* Queues are represented as size-balanced binary trees. Empty queues are
   denoted as nil, and the bin constructor is used to represent the interior
   nodes of the tree. The leaves of the tree are denoted with the tip
   constructor, which carries a single queue element as its argument.
   The bin symbol takes three arguments: a balance factor which is either
   0 or 1 and is used to keep the tree balanced, and the left and right
   subtree. */

public type Queue = const nil, tip X, bin B X Y;

/* enqueue Q X appends X to the queue Q */

public enqueue Q X;

enqueue nil X		= tip X;
enqueue (tip X) Y	= bin 0 (tip X) (tip Y);
enqueue (bin B X Y) Z	= bin 1 (enqueue X Z) Y if B = 0;
			= bin 0 X (enqueue Y Z) if B = 1;

/* dequeue Q removes the first element from a queue */

public dequeue Q;

dequeue (tip X)		= nil;

// the following equations *must* be in the indicated order

dequeue (bin 0 (tip X) Y)
			= Y;
dequeue (bin B X Y)	= bin 1 Y (dequeue X) if B = 0;
			= bin 0 Y (dequeue X) otherwise;

/* hd Q returns the head element of a queue */

hd (tip X)		= X;
hd (bin B X Y)		= hd X;
	
/* members converts a queue to a list */

public members Q;
	
members nil		= [];
members Q:Queue		= [hd Q | members (dequeue Q)];

/* queue converts a list to a queue */

public queue Xs;

queue Xs:List		= foldl enqueue nil Xs;