fgap_list.sa

 
---------------------------> Sather 1.1 source file <--------------------------
-- gap_list.sa<2>: Gap lists
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
-- Translated from the original by S. Omohundro
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: fgap_list.sa,v 1.4 1996/06/01 21:36:19 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 FGAP_LIST{T} < $STR 
class FGAP_LIST{T} < $STR is
   -- An array replacement for linked lists.
   -- The class `GAP_LIST{T}' is an array based list structure like `LIST{T}'
   -- but it supports insertions and deletions from the middle of the list
   -- as well as the end.  This structure consists of an extensible array
   -- with a "gap" region in the middle. When an insertion or deletion is
   -- required, the gap is first moved to the proper location by moving
   -- elements around.  Element access is by index and skips over the gap
   -- wherever it may lie. As long as most insertions and deletions are
   -- fairly close in location to the preceding one, the movement of
   -- elements accross the gap will not be extensive. Algorithms which are
   -- based on doubly linked lists often have a single pointer which moves
   -- up and down the list inserting and deleting elements as it moves. Such
   -- algorithms will also operate efficiently with gap lists.  Sometimes
   -- this structure is refered to as a "double stack" since it may be
   -- viewed as two stack which approach one another. It has found wide use
   -- in text editors (such as GNU Emacs) and turns out to be much more
   -- efficient in practice than more obvious structures such as a linked
   -- list of strings for each line.
   private include COMPARE{T};
   private include AREF{T};

   private attr gap_start,gap_size: INT;	
   -- Start of gap and size of gap.

   --              ------ Initialization/Duplication ------
   create: SAME is
      -- A new `GAP_LIST' with default `size=5'.
      res ::= new(5); 
      res.gap_size := 5;
      return res;
   end; -- create
   
   create(a: $ELT{T}): SAME is
      res ::= #SAME;
      loop res := res.append(a.elt!) end;
      return res;
   end;
      
   create_sized(n: INT): SAME is
      -- A new `GAP_LIST' with `size=n'.
      res ::= new(n); 
      res.gap_size := n;
      return res;
   end; -- create_sized

   --              ------ Insertion/Removal --------------- 
   append(e: T): SAME is return insert(size,e) end;
   
   insert(i: INT, e: T): SAME pre 0 <= i and i <= size is
      -- Insert element `e' at location `i' pushing later elements forward.
      -- Elements may be inserted anywhere in the list or at the very end
      -- of the list
      res ::= self;
      if gap_size = 0 then		-- no gap, so double size
	 res := new(2 * asize); 
	 res.gap_start := asize; 
	 res.gap_size := res.asize - res.gap_start; 
	 loop res.set!(elt!) end;
	 clear;			-- help the garbage collector
      end; -- if
      res.move_gap(i);
      res[i] := e;
      res.gap_start := res.gap_start + 1;
      res.gap_size := res.gap_size - 1;
      return res;
   end; -- insert
   
   delete(i: INT): SAME  pre has_ind(i) is 
      -- Delete the `i'th element.
      move_gap(i); 
      gap_size := gap_size + 1;
      return self;
   end; -- delete
   
   replace(i: INT, e: T) pre has_ind(i) is
      -- Replace the `i'th element by `e'.
      if i < gap_start then [i] := e else [gap_size + i] := e end;
   end; -- replace

   clear is
      -- Clear the list.
      i: INT := 0; loop until!(i=asize);
	 [i] := elt_nil;
	 i := i + 1
      end; -- loop
      gap_start := 0; 
      gap_size := asize;
   end; -- clear

   --              ------ Access/Measurement --------------
   get(i: INT): T is
      -- Retrieve the `i'th element.
      if i < gap_start then return [i] else return [gap_size + i] end;
   end; -- get

   
   set(i: INT,val: T) is
      -- Set the ith element
      if i < gap_start then [i] := val else [gap_size + i] := val; end;
   end; -- get

   size: INT is
      -- The total number of elements.
      return asize - gap_size;
   end; -- size

   --              ------ Queries/Comparison --------------
   is_empty: BOOL is
      -- True if `self' is empty.
      return (gap_size = asize);
   end; -- is_empty

   has_ind(i: INT): BOOL is return (0 <= i and i < size) end;
   
   equals(e: $ARR{T}): BOOL is
      if e.size /= size then return false end;
      loop if ~elt_eq(e.elt!,elt!) then return false end; end;
      return true;
   end;
      
   --              ------ Cursor --------------------------
   elt!: T is
      i ::= 0; sz ::= size;
      loop until!(i = sz); yield get(i); i := i + 1; end;
   end;

   set!(e: T) is
      i ::= 0; sz ::= size;
      loop until!(i = sz); [i] := e; yield; i := i + 1; end;
   end;      
   
   str: STR is
      -- Prints out a string version of the flist of the components 
      -- that are under $STR
      res ::= #FSTR("{");
      loop 
	 e ::= elt!;
	 typecase e
	 when $STR then res := res+",".separate!(e.str); 
	 else -- do nothing
	 end;
      end;
      res := res+"}";
      return(res.str);
   end;
   
   --              ------ Implementation ------------------
   private move_gap(l: INT) pre l <= size is
      -- Move the gap to start at `l'. Must have `l<=size'.
      if l <= gap_start then
	 b: INT := l + gap_size;
	 i: INT := gap_start + gap_size - 1; 
	 loop until!(i < b);
	    [i] := [i - gap_size];
	    i := i - 1
	 end; -- loop
      else
	 i: INT := gap_start; 
	 loop until!(i = l);  [i] := [i + gap_size];  i := i + 1 end; -- loop
      end; -- if
      gap_start := l;
   end; -- move_gap
   
   
end;
--~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~