(* Chris Okasaki
   School of Computer Science
   Carnegie Mellon University
   Pittsburgh, PA 15213
   cokasaki@cs.cmu.edu *)

functor Queue (structure Stream : STREAM) : QUEUE =
    (* Implementation of queues with O(1) worst-case performance. *)
struct
    open Stream

    datatype 'a Queue = Queue of {front  : 'a Stream,
                                  rear   : 'a list,
				  pending: 'a Stream}

    (* INVARIANTS                                        *)
    (*   1. length front >= length rear                  *)
    (*   2. length pending = length front - length rear  *)
    (*   3. (in the absence of insertf's)                *)
    (*      pending = nthtail (front, length rear)       *)

    (* rotate (xs,ys,rys) = xs @ rev ys @ rys         *)
    (*   always called with length ys = length xs + 1 *)
    fun rotate (xs,y::ys,rys) =
          if Stream.isempty xs then cons (y,rys)
          else lcons (head xs,
                      fn () => rotate (tail xs,ys,cons (y, rys)))

    (* Psuedo-constructor that enforces invariant *)
    (*   always called with length pending = length front - length rear + 1 *)
    fun queue {front,rear,pending} =
	  if Stream.isempty pending then (* length rear = length front + 1 *)
              let val front = rotate (front,rear,Stream.empty)
              in
                  Queue {front = front, rear = [], pending = front}
              end
	  else
	      Queue {front = front, rear = rear, pending = tail pending}
	      
    exception Empty

    val empty = Queue {front = Stream.empty, rear = [], pending = Stream.empty}

    fun isempty (Queue {front,...}) = Stream.isempty front
	(* by Invariant 1, front = empty implies rear = [] *)

    fun size (Queue {front,rear,pending}) =
	Stream.size pending + 2 * length rear
	(* = Stream.size front + length rear -- by Invariant 2 *)

    fun insert (x, Queue {front,rear,pending}) = 
          queue {front = front, rear = x :: rear, pending = pending}

    fun insertf (x, Queue {front,rear,pending}) = 
          Queue {front = cons (x,front), rear = rear, 
		 pending = cons (x,pending)}

    fun remove (Queue {front,rear,pending}) =
	  if Stream.isempty front then raise Empty
	  else (head front,
		queue {front = tail front, rear = rear, pending = pending})

end