------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1995 by International Computer Science Institute            --
-- This file is part of the GNU Sather library. It is free software; you may --
-- redistribute  and/or modify it under the terms of the GNU Library General --
-- Public  License (LGPL)  as published  by the  Free  Software  Foundation; --
-- either version 2 of the license, or (at your option) any later version.   --
-- This  library  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 Doc/LGPL for more details.       --
-- The license text is also available from:  Free Software Foundation, Inc., --
-- 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA                     --
-------------->  Please email comments to <bug-sather@gnu.org>  <--------------

-- a_queue.sa: Array based queue
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>

class QUEUE{T} < $QUEUE{T} is include A_QUEUE{T}; end;
-------------------------------------------------------------------
class A_QUEUE{T} < $QUEUE{T} is
   -- An array-based queue that expands using amortized doubling.
   include COMPARE{T};
   
   private attr buf: ARRAY{T};
   private attr head: INT;	-- Index of head
   private attr tail: INT;	-- Index of next insert

   --              ------ Initialization/Duplication ------
   create: SAME is
      return(create_capacity(1));
   end;

   create(a: $ELT{T}): SAME is
      -- Create from an ordered container of elements "a"
      -- Insert all the elements in "a" into the queue
      -- such that the last element of "a" will also be the last
      -- element of the queue
      res ::= #SAME;
      loop res.enq(a.elt!) end;
      return res;
   end;

   create_from(a: ARRAY{T}): SAME is
      -- Create from elements of the array "a". Convenient to
      -- specify the queue using an array literal as argument
      return #SAME(a);
   end;
   
   create_capacity(allocate: INT): SAME is
      -- Create, allocating for "allocate" elements. Can grow later
      return(new.build(allocate));
   end;

   copy: SAME is
      res ::= #SAME(self);
      return res;
   end;
		
   private build(sz: INT): SAME is
      buf := #(sz);
      head := 0;
      tail := 0;
      return(self);
   end;
   
   --              ------ Insertion/Removal --------------- 
   enq(e: T) pre ~void(self) is
      -- Enqueue the element "e" into the tail of the queue
      if ((tail+1).mod(buf.size) = head) then 
	 -- #OUT+"Doubling queue\n";
	 -- Queue is full, need to expand the buffer
	 r: ARRAY{T} := #ARRAY{T}(2*buf.size);
	 -- Copy from the head to the end of the original buffer
	 i ::= head; loop until!(i = buf.size);	    
	    r[i] := buf[i];
	    i := i + 1;
	 end;
	 -- Copy the wrap around portion (which must fit, due to the doubling)
	 if (tail < head) then
	    dest ::= buf.size;
	    i := 0; loop until!(i = tail);
	       r[dest] := buf[i];
	       i := i + 1;
	       dest := dest + 1;
	    end;
	    tail := buf.size+tail;
	 end;
	 buf := r;
      end;
      -- New insertion position
      buf[tail] := e;
      tail := (tail+1).mod(buf.size);
   end;
   
   remove: T pre ~is_empty is
      -- Error if the queue is empty
      res ::= buf[head];      
      -- erik: Invalidate the pointer, for the sake of the gc.
      -- (could be omitted for value types)
      buf[head] := void;
      head := (head+1).mod(buf.size);
      return(res)
   end;

   --              ------ Access/Measurement --------------
   current: T is return top end;
      
   top: T pre ~is_empty is
      -- Return the top most elemetn of the queue
      return(buf[head]);
   end;

   size: INT is 
      -- Return the number of elements in the queue
      if (tail >= head) then return(tail - head) 
      else return((buf.size-head)+tail); end;
   end;
   
   --              ------ Queries/Comparison --------------
   is_empty: BOOL pre ~void(self) is return(head=tail) end;
   
   has(el: T): BOOL is 
      loop e ::= elt!; if elt_eq(e,el) then return true end; end;
      return false;
   end;
      
   --              ------ Cursor --------------------------
   elt!: T pre ~void(self) is
      -- Return the elements in the queue in their normal order without
      -- changing the queue. Starts with the head of the queue 
      -- and works downward
      if (head = tail) then quit; end;
      i ::= head;
      loop until!(i = tail);
	 yield(buf[i]);
	 i := (i + 1).mod(buf.size);
      end;
   end;
      
   str: STR pre ~void(self) is
      res ::="";
      res := res+"["+head+","+tail+","+buf.size+"]";
      loop 
	 f ::= elt!;
         fstr: STR;
	 typecase f
	 when $STR then	fstr := f.str else fstr := "?" end;
         res := res+",".separate!(fstr);
      end;
      return(res);
   end;

end; -- class QUEUE
-------------------------------------------------------------------
