a_queue.sa

 
---------------------------> Sather 1.1 source file <--------------------------
-- a_queue.sa: Array based queue
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: a_queue.sa,v 1.4 1996/06/01 21:36:09 gomes Exp $
--
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
-- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
-- LICENSE contained in the file: Sather/Doc/License of the
-- Sather distribution. The license is also available from ICSI,
-- 1947 Center St., Suite 600, Berkeley CA 94704, USA.


class QUEUE{T} < $QUEUE{T} is include A_QUEUE{T}; end;


class A_QUEUE{T} < $QUEUE{T} 
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