------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1994 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>  <--------------

-- str.sa: Strings.
-- Integrated Rob's changes (escape, minus)
-------------------------------------------------------------------
class STR < $IS_LT{STR},$HASH,$STR,$ELT{CHAR},$FMT is
   -- Strings are represented as arrays of characters. Every
   -- character is significant.
   -- 
   -- References: Gonnet and Baeza-Yates, "Handbook of Algorithms and
   -- Data Structures", Addison Wesley, 1991.
   include COMPARABLE;
   private include AREF{CHAR} aget -> aget; 
   -- Make modification routines private.

   private shared buf:FSTR;	-- Character buffer.

   create:SAME is
      -- An empty string. (Occasionally useful in constructs like 
      -- `#STR + foo'). 
      return "" end;

   create(c:CHAR):SAME is
      -- String containing the single character 'c'.
      r::=new(1);
      r[0]:=c;
      return r;
   end;
    
   create_from_file(nm:STR):SAME is
      -- Open the file named `nm' in the current directory, create a
      -- string containing its contents and then close the file. Return
      -- void if there is no such file.
      fd::=RUNTIME::rt_file_open(nm);
      if fd<0 then return void end;
      sz::=RUNTIME::rt_file_size(fd);
      r::=new(sz);
      RUNTIME::rt_file_in_str(fd,r,0,sz);
      RUNTIME::rt_file_close(fd);
      return r 
   end;

   create_from_file_range(nm:STR,st,sz:INT):SAME is
      -- Open the file named `nm' in the current directory, create a
      -- string containing `sz' characters starting at `st'. Fill in
      -- the remainder with '\0' if the file is too small. Return
      -- void if there is no such file.
      fd::=RUNTIME::rt_file_open(nm);
      if fd<0 then return void end;
      fsz::=RUNTIME::rt_file_size(fd);
      r::=new(sz);
      if st+sz<fsz then RUNTIME::rt_file_in_str(fd,r,st,sz);
      else RUNTIME::rt_file_in_str(fd,r,st,fsz-st) end;
      RUNTIME::rt_file_close(fd);
      return r 
   end;

   create_from_c_string(s:EXT_OB):SAME is
      -- Create a Sather string from a C pointer.  Needless to say,
      -- use this with caution.
      if void(s) then return void end;
      len::=RUNTIME::strlen(s);
      r::=new(len);
      ext::=RUNTIME::memcpy(r,s,len);
      return r;
   end;

   create_from_memory_area(s:EXT_OB,len:INT):SAME is
      -- Create a Sather string from a memory area of size
      -- 'len' bytes starting at 's'.  Needless to say,
      -- use this with caution.
      if void(s) or len<=0 then return void end;
      r::=new(len);
      ext::=RUNTIME::memcpy(r,s,len);
      return r;
   end;
    
   size:INT is
      -- The number of characters in self. 0 if self is void. 
      if void(self) then return 0 else return asize end 
   end;

   cursor: STR_CURSOR is return #STR_CURSOR(self) end;
   
   length:INT is
      -- The number of characters in self. 0 if self is void.
      -- Another name for `size'.
      if void(self) then return 0 else return asize end 
   end;      

   char(i:INT):CHAR
   -- The character at index `i' of self.
      pre i.is_bet(0,asize-1) is
      return [i] 
   end;
    
   acopyn(s:FSTR,n:INT) pre n <= s.length is 
      -- copy "n" chars from "s" into "self".  Built-in.
      builtin STR_ACOPY_FSTR_INT;
   end;
    
   acopyn(s:STR,n:INT) pre n <= s.length is 
      -- copy "n" chars from "s" into "self".  Built-in.
      builtin STR_ACOPY_STR_INT;
   end;
    
   from_fstr(s:FSTR):SAME is
      -- A new string with the characters currently held in `s'.
      -- Returns empty string if emtpy.  Modified MBK.
      sz ::= s.size;		-- save it.
      if sz=0 then return "" end;
      r::=new(sz);
      r.acopyn(s,sz);
      --      loop r.aset!(s.elt!) end;
      return r 
   end;

   fstr:FSTR is
      -- An FSTR with the same characters as self.
      --      if size=0 then return void; end;
      --      r::=#FSTR(size);
      --      loop r:=r.push(elt!); end;
      --      return r;
      --      end;
      return #FSTR(self); 
   end;

   plus(sarg:$STR):SAME is
      -- A new string obtained by appending `sarg' to self.
      -- Either self or `s' may be void.  Sped up, MBK et al.
      
      -- This is the most general version. Specialized versions
      -- exploiting Sather 1.1 overloading rules follow
      
      can_delete:BOOL:=false;
      s:STR;

      -- This is a hack.  Om's STR representation allows 'void'
      -- for "", but that breaks $STR dispatching.  For the
      -- moment assume that any void arg must represent something
      -- that translates to "" and so there's no append.  The
      -- correct thing to do, however, is to get rid of the
      -- bad representation elsewhere in the libraries.
      if void(sarg) then return self end;

      s:=sarg.str;
      return append_destroy(s, false);
   end;

   -- Specialized versions of plus
   plus(sarg:STR):SAME is
      return append(sarg);
   end;
   
   -- the following ones could be optimized if one gets excited about
   -- it
   plus(sarg:FSTR):SAME is
      s::=sarg.str;
      return append_destroy(s, true);
   end;

   plus(arg:INT):SAME is
      s::=arg.str;
      return append_destroy(s, true);
   end;
   
   plus(arg:CHAR):SAME is
      s::=arg.str;
      return append_destroy(s, true);
   end;   
   
   append_destroy(s:SAME, destroy:BOOL):SAME is
      -- appends s to self and destroys s if possible
      r:STR;
      if size=0 then return s
      else
         sz ::= s.size;
         if sz=0 then return self
         else
            r:=new(asize+sz);
            r.acopyn(self,asize); 
            r.acopy(asize,s);
         end;
      end;
      if destroy and ~void(s) then
         -- 's' was just a temporary
         SYS::destroy(s);
      end;
      return r;
   end;
   
   append(s:SAME):SAME is
      -- A new string obtained by appending `s' to self.
      -- Either self or `s' may be void.    
      if void(self) then return s; end;
      if void(s) then return self; end;
      selfsize::=asize;
      ssize::=s.asize;
      r::=new(selfsize+ssize);
      r.acopy(self);
      r.acopy(selfsize,s);
      return r;
   end;
    
   append(s1,s2:SAME):SAME is
      -- A new string obtained by appending args to self.
      -- Any of the strings may be void.

      if void(self) then return s1.append(s2); end;
      if void(s1) then return self.append(s2); end;
      if void(s2) then return self.append(s1); end;

      p1::=asize;
      p2::=p1+s1.asize;
      p3::=p2+s2.asize;

      r::=new(p3);
      r.acopy(self);
      r.acopy(p1,s1);
      r.acopy(p2,s2);

      return r;
   end;

   append(s1,s2,s3:SAME):SAME is
      -- A new string obtained by appending args to self.
      -- Any of the strings may be void.

      if void(self) then return s1.append(s2,s3); end;
      if void(s1) then return self.append(s2,s3); end;
      if void(s2) then return self.append(s1,s3); end;
      if void(s3) then return self.append(s1,s2); end;

      p1::=asize;
      p2::=p1+s1.asize;
      p3::=p2+s2.asize;
      p4::=p3+s3.asize;

      r::=new(p4);
      r.acopy(self);
      r.acopy(p1,s1);
      r.acopy(p2,s2);
      r.acopy(p3,s3);

      return r;
   end;

   append(s1,s2,s3,s4:SAME):SAME is
      -- A new string obtained by appending args to self.
      -- Any of the strings may be void.

      if void(self) then return s1.append(s2,s3,s4); end;
      if void(s1) then return self.append(s2,s3,s4); end;
      if void(s2) then return self.append(s1,s3,s4); end;
      if void(s3) then return self.append(s1,s2,s4); end;
      if void(s3) then return self.append(s1,s2,s3); end;

      p1::=asize;
      p2::=p1+s1.asize;
      p3::=p2+s2.asize;
      p4::=p3+s3.asize;
      p5::=p4+s4.asize;

      r::=new(p5);
      r.acopy(self);
      r.acopy(p1,s1);
      r.acopy(p2,s2);
      r.acopy(p3,s3);
      r.acopy(p4,s4);

      return r;
   end;

   append(s1,s2,s3,s4,s5:SAME):SAME is
      -- A new string obtained by appending args to self.
      -- Any of the strings may be void.

      if void(self) then return s1.append(s2,s3,s4,s5); end;
      if void(s1) then return self.append(s2,s3,s4,s5); end;
      if void(s2) then return self.append(s1,s3,s4,s5); end;
      if void(s3) then return self.append(s1,s2,s4,s5); end;
      if void(s3) then return self.append(s1,s2,s3,s5); end;
      if void(s3) then return self.append(s1,s2,s3,s4); end;

      p1::=asize;
      p2::=p1+s1.asize;
      p3::=p2+s2.asize;
      p4::=p3+s3.asize;
      p5::=p4+s4.asize;
      p6::=p5+s5.asize;

      r::=new(p6);
      r.acopy(self);
      r.acopy(p1,s1);
      r.acopy(p2,s2);
      r.acopy(p3,s3);
      r.acopy(p4,s4);
      r.acopy(p5,s5);

      return r;
   end;

   append(s1,s2,s3,s4,s5,s6:SAME):SAME is
      -- A new string obtained by appending args to self.
      -- Any of the strings may be void.

      if void(self) then return s1.append(s2,s3,s4,s5,s6); end;
      if void(s1) then return self.append(s2,s3,s4,s5,s6); end;
      if void(s2) then return self.append(s1,s3,s4,s5,s6); end;
      if void(s3) then return self.append(s1,s2,s4,s5,s6); end;
      if void(s3) then return self.append(s1,s2,s3,s5,s6); end;
      if void(s3) then return self.append(s1,s2,s3,s4,s6); end;
      if void(s3) then return self.append(s1,s2,s3,s4,s5); end;

      p1::=asize;
      p2::=p1+s1.asize;
      p3::=p2+s2.asize;
      p4::=p3+s3.asize;
      p5::=p4+s4.asize;
      p6::=p5+s5.asize;
      p7::=p6+s6.asize;

      r::=new(p7);
      r.acopy(self);
      r.acopy(p1,s1);
      r.acopy(p2,s2);
      r.acopy(p3,s3);
      r.acopy(p4,s4);
      r.acopy(p5,s5);
      r.acopy(p6,s6);

      return r;
   end;

   str:STR is
      return self; end;

   fmt( f: STR ): STR is
      return BASE_FORMAT::fmt_str( self, f )
   end;
        
   pretty:STR is
      -- Pretty print self. This surrounds the string with 
      -- a pair of double quotes. Any non-printing characters or double 
      -- quotes are replaced by their special codes or the octal 
      -- representation.
      buf.clear; buf:=buf+'\"';
      loop c::=elt!;
         if c.is_print and c/='\"' and c/='\\' then buf:=buf+c
         else buf:=buf + '\\';
            case c
            when '\a' then buf:=buf+'a'  when '\b' then buf:=buf+'b'
            when '\f' then buf:=buf+'f'  when '\n' then buf:=buf+'n'
            when '\r' then buf:=buf+'r'  when '\t' then buf:=buf+'t'
            when '\v' then buf:=buf+'v'  when '\\' then buf:=buf+'\\'
            when '\"' then buf:=buf+'\"'
            else s::=c.int.octal_str; 
               buf:=buf+s.tail(s.size-2) end end end;
      buf:=buf+'\"'; return buf.str end;

            as_literal:STR is
      -- Returns the string described by self assuming it is in "string
      -- literal" form. This means it must begin and end with double
      -- quotes and must not contain any non-printing characters.
      -- The returned string eliminates the initial and final double 
      -- quotes and converts any escape codes to the corresponding 
      -- characters. self may consist of several double-quote enclosed
      -- strings separated by whitespace. In this case the strings are 
      -- concatenated together. If self is not in correct string literal
      -- format, returns void.

      if void(self) or size<2 or [0]/='\"' or [size-1]/='\"' then
         return void
      end;

      buf.clear; esc,oct,qt:BOOL; oval:INT;
      loop c::=aelt!(1,size-2);
         if qt then		-- We're between concatted strings.
            if c='\"' then qt:=false 
            elsif ~c.is_space then return void end; 
         else
            if oct then		-- we're in an octal escape code
               if c.is_octal_digit then oval:=oval*8+c.octal_digit_value 
               else buf:=buf+oval.char; oct:=false; esc:=false end end;
            if ~oct then
               if esc then	-- we've seen only a '\'
                  case c
                  when 'a' then buf:=buf+'\a'; esc:=false
                  when 'b' then buf:=buf+'\b'; esc:=false
                  when 'f' then buf:=buf+'\f'; esc:=false
                  when 'n' then buf:=buf+'\n'; esc:=false
                  when 'r' then buf:=buf+'\r'; esc:=false  
                  when 't' then buf:=buf+'\t'; esc:=false
                  when 'v' then buf:=buf+'\v'; esc:=false  
                  when '\\' then buf:=buf+'\\'; esc:=false
                  when '\"' then buf:=buf+'\"'; esc:=false  
                  when '\'' then buf:=buf+'\''; esc:=false
                  when '0','1','2','3','4','5','6','7' then 
                     oct:=true; oval:=c.octal_digit_value
                  else return void end; -- illegal escape code
               elsif c='\\' then esc:=true
               elsif c='\"' then qt:=true
               elsif c.is_print then buf:=buf+c
               else return void end; -- Illegal character
            end end end;
      if qt then return void	-- Must close internal quotes.
      elsif oct then buf:=buf+oval.char -- Ended with octal code.
      elsif esc then return void end; -- Ended with '\'
      return buf.str end;
    
   is_empty:BOOL is
      -- True if self has no characters. 
      -- Self may be void.
      return (void(self)) or (asize=0) end;
    
   private is_eq_helper(s:SAME,i:INT):BOOL is
      -- Matt Kennel, INLS.  The reason for this
      -- function's existence is that it will be overridden
      -- by "memcmp" in MACROS.
      loop if aelt!/=s.aelt! then return false end; end;
      return true;
   end;
    
   is_eq(s:SAME):BOOL is
      -- True if `s' equals self. Either may be void.
      if void(self) then
         if void(s) then return true
         elsif s.asize=0 then return true
         else return false end;
      elsif void(s) then 
         if asize=0 then return true else return false end
      elsif asize/=s.asize then return false 
      else
         return is_eq_helper(s,asize);
      end;
   end;

   is_lt(s:SAME):BOOL is
      -- True if self is lexicographically before `s'.
      -- Void is taken to be before everything else.
      if size=0 then 
         if s.size/=0 then return true else return false end
      elsif s.size=0 then return false
      else
         loop c::=aelt!; sc::=s.aelt!;
            if c>sc then return false
            elsif c<sc then return true end end;
         if size<s.size then return true 
         else return false end 
      end 
   end;

   is_leq(s:SAME):BOOL is
      -- True if self is lexicographically before `s' or equal to it.
      -- Either may be void.
      if size=0 then return true
      elsif s.size=0 then return false
      else
         loop c::=aelt!; sc::=s.aelt!;
            if c>sc then return false
            elsif c<sc then return true end end;
         if size<=s.size then return true
         else return false end 
      end 
   end;

   is_upper:BOOL is
      -- True if each alphabetic character of self is upper case.
      -- Self may be void.
      loop if ~elt!.is_upper then return false end end; 
      return true 
   end;

   is_lower:BOOL is
      -- True if each alphabetic character of self is lower case.
      -- Self may be void.
      loop if ~elt!.is_lower then return false end end; 
      return true 
   end;  
    
   upper:SAME is
      -- A copy of self with each character in upper case.
      -- Self may be void.
      if void(self) then return void end;
      r::=new(asize); 
      loop r.aset!(aelt!.upper) end; 
      return r 
   end;

   lower:SAME is
      -- A copy of self with each character in lower case.
      -- Self may be void.
      if void(self) then return void end;
      r::=new(asize); 
      loop r.aset!(aelt!.lower) end; 
      return r 
   end;
    
   capitalize:SAME is
      -- A copy of self with each word capitalized.
      -- Self may be void.
      if void(self) then return void end;
      r::=new(asize);
      sp::=true;		-- True if previous char was punct.
      loop c::=aelt!; 
         if sp then c:=c.upper end;
         if c.is_punct or c.is_space then sp:=true else sp:=false end;
         r.aset!(c) 
      end; 
      return r 
   end;

   head(i:INT):SAME 
   -- The first `i' characters of self.
   -- Self may be void if i=0.
      pre i.is_bet(0,size) is
      if void(self) then return void end;
      r::=new(i); r.acopy(self); 
      return r 
   end;
    
   tail(i:INT):SAME 
   -- The last `i' characters of self.
   -- Self may be void if i=0.
      pre i.is_bet(0,size) is
      if void(self) then return self end;
      r::=new(i); r.acopy(0,i,asize-i,self); 
      return r 
   end;      

   replace_suffix(old,rpl:SAME):SAME 
      pre length>=old.length and tail(old.length)=old is
      -- New string which replaces old suffix with new one.
      return head(length-old.size)+rpl;
   end;
    
   substring(beg,num:INT):SAME 
   -- The substring with `num' charcters whose first character has 
   -- index `beg'. Self may be void if beg=0 and num=0.
      pre num>=0 and beg.is_bet(0,size-num) is
      if void(self) then return void end;
      r::=new(num); r.acopy(0,num,beg,self); 
      return r 
   end;

   substring(beg:INT): SAME
      pre beg.is_bet(0,size)
   is
      if beg=0 then return void end;
      r::=new(size-beg); r.acopy(0,size-beg,beg,self); return r;
   end;

      
   reverse:SAME is
      -- A string whose characters are the reverse of those in self.
      -- Self may be void.
      if void(self) then return void end;
      r::=new(asize); 
      loop r.aset!(aelt!(asize-1,asize,-1)) end;
      return r 
   end;
    
   repeat(i:INT):SAME
   -- Self repeated `i' times. Self may be void.
      pre i>=0 is 
      if void(self) then return void end;
      r::=new(asize*i);
      loop r.acopy(0.step!(i,asize),self) end; 
      return r 
   end;

   contains(c:CHAR):BOOL is
      -- True if `c' appears in self. Self may be void.
      loop if elt!=c then return true end end;
      return false 
   end;

   count(c:CHAR):INT is
      -- The number of times `c' appears in self.
      -- Self may be void.
      r::=0; loop if elt!=c then r:=r+1 end end;
      return r 
   end;

   count(s:STR):INT is
      -- The number of times a character in `s' appears in self.
      -- Self may be void.
      if void(self) or void(s) then return 0 end;
      r::=0; loop if s.contains(elt!) then r:=r+1 end end;
      return r 
   end;
    
   search(c:CHAR):INT is
      -- The index of the first appearance of `c' in self or -1 if absent.
      -- Self may be void.
      loop r::=ind!; if [r]=c then return r end end; 
      return -1 
   end;

   search_backwards(c:CHAR):INT is
      -- The index of the last appearance of `c' in self or -1 if absent.
      -- Self may be void.
      if void(c) then return -1; end;
      loop r::=(size-1).downto!(0); if [r]=c then return r end end; 
      return -1 
   end;

   search(c:CHAR,st:INT):INT is
      -- The index of the first appearance of `c' at location `st' or
      -- greater in self or -1 if absent.
      -- Self may be void.
      loop r::=st.upto!(size-1); if [r]=c then return r end end; 
      return -1 
   end;
    
   search_backwards(c:CHAR,st:INT):INT is
      -- The index of the last appearance of `c' in self
      -- before st,or -1 if absent. Self may be void.
      if void(c) then return -1; end;
      loop r::=st.downto!(0); if [r]=c then return r end end; 
      return -1 
   end;

   replace(o,n:CHAR):SAME is
      -- A new string with each occurance of `o' replaced by `n'.
      -- Self may be void.
      if void(self) then return void end;
      r::=new(asize);
      loop c::=aelt!; if c=o then c:=n end; 
      r.aset!(c) end;
      return r 
   end;

   remove(c:CHAR):SAME is
      -- Self with all occurances of `c' removed.
      -- Self may be void.
      if void(self) then return void end;
      ns::=asize-count(c);
      if ns=0 then return void end;
      r::=new(ns);
      loop sc::=aelt!; 
         if ~(sc=c) then r.aset!(sc) end end;
      return r 
   end;
    
   escape(esc:CHAR, elist:SAME):SAME is
      -- return self w/ each occurance of esc & of all chars in elist 
      -- preceded by esc (Rob)
      if void(self) or void(esc) then return self end;
      buf::=#FSTR(self.length);  -- expand buf early? any stats?
      loop c::=self.elt!;
         if elist.contains(c) or c = esc then buf:=buf.push(esc); end;
         buf:=buf.push(c);
      end;
      ret::=self.from_fstr(buf);
      return ret;
   end;

   minus(s:SAME):SAME is 
      -- return self with the first instance of s deleted if any
      -- (Rob)
      return minus(s,0) 
   end;
   
   minus(s:SAME,start:INT):SAME is
      -- return self with the first instance of s after start deleted if any
      if void(s) or void(self) then return self end;
      loc::=search(s,start); if loc = -1 then return self end;
      front::=#FSTR( self.head(loc));
      back::=#FSTR(self.tail( self.length - (loc + s.length)));
      ret::=#STR; ret:=from_fstr( front.append(back));
      return ret;
   end;
   
   contains_chars_from(s:STR):BOOL is
      -- True if any of the characters in self are contained in `s'.
      -- Either may be void.
      loop if s.contains(elt!) then return true end end;
      return false 
   end;   
    
   count_chars_from(s:SAME):INT is
      -- The number of characters in self which are contained in `s'.
      -- Either may be void.
      r::=0; loop if s.contains(elt!) then r:=r+1 end end; 
      return r 
   end;
    
   search_chars_from(s:SAME):INT is
      -- The index of the first appearance in self of a character
      -- contained in `s' or -1 if none.
      -- Self or `s' may be void.
      loop r::=ind!; if s.contains([r]) then return r end end; 
      return -1 
   end;
    
   replace_chars_from(set:SAME,n:CHAR):SAME is
      -- A new string with character contained in `set' replaced by 
      -- `n'. Self may be void.
      if void(self) then return void end;
      r::=new(asize);
      loop c::=aelt!; if set.contains(c) then c:=n end; 
      r.aset!(c) end;
      return r 
   end;

   remove_chars_from(s:SAME):SAME is
      -- Self with all characters which are contained in `s' removed.
      -- Either may be void.
      if void(self) then return void end;
      if void(s) then return self end;
      ns::=asize-count(s); if ns=0 then return "" end;
      r::=new(ns);
      loop c::=aelt!; 
         if ~s.contains(c) then r.aset!(c) end end;
      return r 
   end;      

   is_prefix(s:SAME):BOOL is
      -- true is s is a prefix of self.
      if length<s.length then return false; end;
      loop if (elt!/=s.elt!) then return false; end; end;
      return true; 
   end;

   mismatch(s:SAME):INT is
      -- The index of the first character of self which differs from `s'.
      -- -1 if self is a prefix of `s'. Either may be void.
      if void(self) then return -1 end;
      if void(s) then return 0 end;
      r:INT;
      loop r:=ind!; if [r]/=s.aelt! then return r end end;
      if r=asize-1 then return -1 end;
      return r 
   end;

   search(s:SAME, st:INT):INT is
      -- the index of the first appearance of `s' at location `st' or
      -- greater in self or -1 if not found.  Self may be void.
      if void(s) then return st end;
      if void(self) then return -1 end;
      loop r::=st.upto!(asize-s.asize); 
	 match ::= true;
	 loop 
	    if aelt!(r) /= s.aelt! then match := false; break! end;
	 end;
	 if match=true then return r end
      end;
      return -1
   end;
   
   search(s:SAME):INT is
      -- The index of the leftmost substring of self which matches `s'.
      -- -1 if none. Uses simple algorithm which has good performance
      -- unless the strings are special (eg. many repeated values).
      -- Either string may be void. (Void matches void at 0).
      if void(s) then return 0 end;
      if void(self) then return -1 end;
      loop r::=0.upto!(asize-s.asize); match::=true;
         loop if aelt!(r)/=s.aelt! then 
            match:=false; break! end end;
         if match=true then return r end 
      end; 
      return -1 
   end;
   
   hash:INT is
      if void(self) or asize=0 then return 0 end;
      r::=0;
      i::=0;
      loop
         r:=r.mplus([i].int).mplus(i).mtimes(19); -- A nice prime
         i:=i+1;
         until!(i>=asize);
      end;
      return r;
   end;

   left(i:INT): SAME is return left(i,' ') end;
   
   left(i:INT,fill:CHAR):SAME is
      -- A string of at least `i' characters in which self 
      -- is left-justified and padded with spaces on the right. 
      -- Returns self if i<=size.
      if i<=size then return self end;
      if void(self) then return fill.str.repeat(i) end;
      r::=new(i); r.acopy(self);
      loop r.aset!(asize, fill) end; 
      return r 
   end;

   right(i:INT): SAME is return right(i,' ') end;
   
   right(i:INT,fill:CHAR):SAME is
      -- A string of at least `i' characters in which self 
      -- is right-justified and padded with spaces on the left. 
      -- Returns self if i<=size.   
      if i<=size then return self end;
      if void(self) then return fill.str.repeat(i) end;
      r::=new(i); r.acopy(i-asize,self);
      loop r.aset!(0, i-asize, fill) end;
      return r 
   end;

   center(i:INT): SAME is return center(i,' ') end;

   center(i:INT,fill:CHAR):SAME is
      -- A string of at least `i' characters in which self 
      -- is centered and padded with spaces on the left and right. 
      -- Returns self if i<=size.      
      if i<=size then return self end;
      if void(self) then return fill.str.repeat(i) end;
      r::=new(i);      
      lp::=(i-asize)/2;		-- Size of left padding.
      r.acopy(lp,self);
      loop r.aset!(0, lp, fill) end;
      loop r.aset!(lp+asize, fill) end;
      return r 
   end;

   concat_all(a: ARRAY{SAME}): SAME is
      -- Concatinate all array of STRING.  Separator is '\0'.
      r: SAME;
      l: INT := a.size;
      loop i ::= 0.upto!(l - 2);
         r :=  r  + a[i] + '\0';
      end; -- loop
      return r + a[l - 1];
   end;

   chunk!(chunk_size: INT): STR pre chunk_size >= 0 is
      -- Yield successive chunks of self, defined by the chunk size "size"
      --     s ::= "122333444455555";
      --     loop #OUT+s.chunk!(1)+","; end;
      --     "1,2,2,3,3,3,4,4,4,4,5,5,5,5,5"
      --     loop #OUT+s.chunk!(5.times!)+","; end;
      --     will print out ",1,22,333,4444,55555"
      cur_loc: INT := 0;
      str_sz: INT := size;
      loop until!(cur_loc >= str_sz);
         res: STR := substring(cur_loc,chunk_size);
         yield res;
         cur_loc := cur_loc+chunk_size;
      end;
   end;
   
   split!(once c: CHAR): STR is
      -- Yield successive substrings that are separated by the character "c"
      --     s ::= "This is \n a test \n of split";
      --     loop #OUT+"Next line:"+s.split!('\n'); end;
      -- The "c" characters will occur at the end of each string
      if void(self) then quit end;
      cur_loc: INT := 0;	-- Start of next string
      loop until!(cur_loc >= size-1);
         next_loc: INT := search(c,cur_loc);
         if next_loc >= 0 then	-- The character was found
            yield substring(cur_loc,next_loc-cur_loc+1);
            cur_loc := next_loc+1;
         else			-- The character was not found
            -- Use the rest of the string
            yield substring(cur_loc,size-cur_loc);
            cur_loc := size;	-- Terminate the loop at the next until
         end;
      end;
   end;

   separate!(s:$STR):STR is
      -- On the first iteration just outputs `s', on successive 
      -- iterations it outputs self followed by `s'. Useful for 
      -- forming lists, 
      --    loop #OUT + ", ".separate!(a.elt!) end;
      yield s.str; loop yield self + s.str end 
   end;

   elt!:CHAR is
      -- Yield the characters of self in order. 
      -- Self may be void.
      -- Modified (ben)
      if ~void(self) then 
         i ::= 0; sz ::= size;
         loop until!(i = sz); yield [i]; i := i + 1; end;
      end;
   end;
   --   if ~void(self) then loop yield aelt! end end end;
    
   elt!(once beg:INT):CHAR is
      -- Yield the characters of self in order starting at `beg'.
      -- Self may be void.
      -- Modified (ben)
      if ~void(self) then
         i ::= beg; sz ::= size;
         loop until!(i = sz); yield [i]; i := i + 1; end;
      end;
   end;
   -- if ~void(self) then loop yield aelt!(beg) end end end;
    
   elt!(once beg,once num:INT):CHAR is
      -- Yield 'num' characters of self in order starting at `beg'.
      -- Self may be void.
      -- Modified (ben)
      if ~void(self) then
         i ::= beg; sz ::= size.min(beg+num);
         loop until!(i = sz); yield [i]; i := i + 1; end;
      end;
   end;
   --   if ~void(self) then loop yield aelt!(beg,num) end end end;
    
   ind!:INT is
      -- Yield the indices of the characters of self in order. 
      -- Self may be void.
      -- Modified (ben)
      if ~void(self) then
         i ::= 0; sz ::= size;
         loop until!(i = sz);
            yield i;
            i := i + 1;
         end;
      end;
   end;
   --   if ~void(self) then loop yield aind! end end end;   

end; -- class STR

