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

functor LazyQueue (structure Stream : STREAM) : QUEUE =
    (* Implementation of queues as a pair of lazy lists.                   *)
    (*                                                                     *)
    (* O(log n) worst-case performance, but O(1) amortized performance     *)
    (* without the restrictions of the standard implementation of queues.  *)
struct
    open Stream

    datatype 'a Queue = Queue of {front  : 'a Stream, sizef  : int,
                                  rear   : 'a list,   sizer  : int}

    (* INVARIANTS                                           *)
    (*   1.  sizef = length front /\ sizer = length rear    *)
    (*   2.  sizef >= sizer                                 *)

    (* 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 *)
    fun queue (q as {front,sizef,rear,sizer}) =
	  if sizer <= sizef then Queue q
	  else (* sizer = sizef+1 *)
              let val front = rotate (front,rear,Stream.empty)
                  val sizef = sizef + sizer
              in
                  Queue {front = front, sizef = sizef,
                         rear  = [],    sizer = 0}
              end
	      
    exception Empty

    val empty = Queue {front = Stream.empty, sizef = 0,
                       rear  = [],           sizer = 0}

    fun isempty (Queue {sizef,...}) = sizef = 0
	(* by Invariant 2, sizef = 0 implies sizer = 0 *)

    fun size (Queue {sizef,sizer,...}) = sizef + sizer

    fun insert (x, Queue {front,sizef,rear,sizer}) = 
          queue {front = front,     sizef = sizef,
                 rear  = x :: rear, sizer = sizer+1}

    fun insertf (x, Queue {front,sizef,rear,sizer}) = 
          Queue {front = cons (x,front), sizef = sizef+1,
                 rear  = rear,           sizer = sizer}
    
    fun remove (Queue {front,sizef,rear,sizer}) =
	  if Stream.isempty front then raise Empty
	  else (head front,
		queue {front = tail front, sizef = sizef-1,
		       rear  = rear,       sizer = sizer})

end