(*-------------------------------------------------------------------------*)
(*                                                                         *)
(*  Amiga Oberon Interface Module: STRING             Date: 02-Nov-92      *)
(*                                                                         *)
(*   © 1992 by Fridtjof Siebert                                            *)
(*                                                                         *)
(*-------------------------------------------------------------------------*)

MODULE STRING;

IMPORT BT * := BasicTypes, Strings, SYSTEM;

TYPE
  STRING * = POINTER TO STRINGDesc;

  STRINGDesc * = RECORD (BT.COMPAREABLEDesc)

    chars-: BT.DynString;   (* The characters of this string *)

    len: LONGINT;

  (*
   * invariant
   *   chars#NIL;
   *   len>=0;
   *   (len<LEN(chars^)) IMPLIES (chars[len]=0X)
   *)

  END;

CONST
  Blank * = " ";


PROCEDURE Create * (n: LONGINT): STRING;
(*
 * Allocate Space for at least n characters
 *
 * require
 *   n>=0
 *
 * ensure
 *   Result.Capacity() >= n;
 *   Result.Empty();
 *
 *)

VAR
  s: STRING;

BEGIN
  NEW(s);
  NEW(s.chars,n);
  s.len := 0;
  RETURN s;
END Create;


PROCEDURE CreateString * (s: ARRAY OF CHAR): STRING;
(*
 * Create new STRING and copy a to it.
 *
 * ensure
 *   Result.Capacity() >= LEN(s);
 *   Result.chars^ = s;
 *)

VAR
  a: STRING;

BEGIN
  NEW(a);
  NEW(a.chars,LEN(s)+1);
  a.len := 0;
  WHILE (a.len<LEN(s)) & (s[a.len]#0X) DO
    a.chars[a.len] := s[a.len];
    INC(a.len)
  END;
  a.chars[a.len] := 0X;
  RETURN a;
END CreateString;


PROCEDURE (a: STRING) Capacity * (): LONGINT;
(*
 * Number of characters that fit in a.chars^.
 *
 * ensure
 *   Result >= 0;
 *)

BEGIN
  RETURN LEN(a.chars^);
END Capacity;


PROCEDURE (a: STRING) Compare * (b: BT.COMPAREABLE): LONGINT;
(*
 * Compare strings a and b
 *
 * ensure
 *   a.chars^ = b.chars^ IMPLIES Result = 0
 *   a.chars^ < b.chars^ IMPLIES Result < 0
 *   a.chars^ > b.chars^ IMPLIES Result > 0
 *)

VAR
  i,l: LONGINT;

BEGIN
  WITH b: STRING DO
    i := -1; l := a.len; IF l>b.len THEN l := b.len END;
    REPEAT
      INC(i);
    UNTIL (i=l) OR (a.chars[i]#b.chars[i]);
    IF i=a.len THEN
      IF i=b.len THEN RETURN  0
                 ELSE RETURN -1 END;
    ELSIF i=b.len THEN
      RETURN 1
    ELSE
      RETURN ORD(a.chars[i])-ORD(b.chars[i]);
    END;
  END;
END Compare;


PROCEDURE (a: STRING) Equal   * (b: BT.COMPAREABLE): BOOLEAN; (* a = b *)
(*
 * are both strings equal?
 *
 * ensure
 *   Result = (a.chars^ = b.chars^)
 *)

BEGIN
  RETURN a.chars^ = b(STRING).chars^;
END Equal;


PROCEDURE (a: STRING) Count * (): LONGINT;
(*
 * Determine length of a.
 *
 * ensure
 *   Result>=0;
 *)

BEGIN
  RETURN a.len;
END Count;


PROCEDURE ^ (a: STRING) Enlarge * (newsize: LONGINT);


PROCEDURE (a: STRING) Adapt * (s: ARRAY OF CHAR);
(*
 * copy s to a
 *
 * ensure
 *   a.chars^ = s;
 *)

BEGIN
  a.Enlarge(LEN(s));
  COPY(s,a.chars^);
  a.len := 0;
  WHILE (a.len<LEN(a.chars^)) & (a.chars[a.len]#0X) DO INC(a.len) END;
END Adapt;


PROCEDURE (a: STRING) Append * (b: STRING);
(*
 * Append a copy of b to a.
 *
 * require
 *   b#NIL;
 *
 * ensure
 *   a.Count() = OLD a.Count() + b.Count;
 *)

VAR
  i: LONGINT;
BEGIN
  a.Enlarge(a.len + b.len);
  FOR i:=0 TO b.len-1 DO
    a.chars[a.len] := b.chars[i];
    INC(a.len);
  END;
  IF a.len<LEN(a.chars^) THEN a.chars[a.len] := 0X END;
END Append;


PROCEDURE (a: STRING) Clear *;
(*
 * ensure
 *   a.Count() = 0
 *)

BEGIN
  a.len := 0;
  a.chars[0] := 0X;
END Clear;


PROCEDURE (a: STRING) Copy * (b: STRING);
(*
 * Copy b to a.
 *
 * require
 *   b#NIL;
 *
 * ensure
 *   a.Equal(b);
 *)

BEGIN
  a.Enlarge(b.len);
  COPY(b.chars^,a.chars^);
  a.len := b.len;
END Copy;


PROCEDURE (a: STRING) Empty * (): BOOLEAN;
(*
 * Is string empty?
 *
 * ensure
 *   Result = (a.Count()=0)
 *)
BEGIN
  RETURN a.len=0;
END Empty;


PROCEDURE (a: STRING) Extend * (c: CHAR);
(*
 * Add c at end;
 *
 * require
 *   c#0X;
 *
 * ensure
 *   a.Count() = old a.Count()+1;
 *   a.chars[a.Count()-1] = c;
 *)

BEGIN
  a.Enlarge(a.len+1);
  a.chars[a.len] := c;
  INC(a.len);
  IF a.len<LEN(a.chars^) THEN a.chars[a.len] := 0X END;
END Extend;


PROCEDURE (a: STRING) ExtendString * (s: ARRAY OF CHAR);
(*
 * Appen s at end;
 *
 * ensure
 *   a.Count() = old a.Count() + String.Length(s);
 *   for all i: 0..Strings.Length[s]-1, a.chars[a.Count()-str.Length(s)+i] = s[i];
 *)

VAR
  l,i: LONGINT;

BEGIN
  l := Strings.Length(s);
  a.Enlarge(a.len+l);
  i := l;
  WHILE i>0 DO
    DEC(i);
    a.chars[a.len+i] := s[i];
  END;
  INC(a.len,l);
  IF a.len<LEN(a.chars^) THEN a.chars[a.len] := 0X END;
END ExtendString;


PROCEDURE (a: STRING) FillBlank *;
(*
 * fill a with blanks
 *
 * ensure
 *   -- for all i: 0..a.Capacity()-1, a.chars[i] = Blank;
 *)

VAR
  i: LONGINT;
BEGIN
  FOR i:=0 TO LEN(a.chars^)-1 DO
    a.chars[i] := Blank;
  END;
  a.len := LEN(a.chars^);
END FillBlank;


PROCEDURE (a: STRING) HashCode * (): LONGINT;
(*
 * Determine Hash code value for current string.
 *
 * ensure
 *   Result >= 0;
 *)

VAR
  i: LONGINT;
  Result: LONGINT;
  Temp: LONGINT;
BEGIN
  Result := 0;
  FOR i := 0 TO a.len DO
    Temp := Result * 80H + ORD(a.chars[i]);
    Result := Temp DIV 800000H + Temp MOD 800000H;
  END;
  RETURN Result;
END HashCode;


PROCEDURE (a: STRING) Head * (n: LONGINT);
(*
 * Remove all but the first n characters of the string.
 * Do nothing for n >= a.Count();
 *
 * require
 *   n >= 0;
 * ensure
 *   n <  OLD a.Count() IMPLIES a.Count() = n;
 *   n >= OLD a.Count() IMPLIES a.Count() = OLD a.Count;
 *)

BEGIN
  IF n<a.len THEN
    a.len := n;
    a.chars[n] := 0X;
  END;
END Head;


PROCEDURE (a: STRING) IndexOf * (c: CHAR; i: LONGINT): LONGINT;
(*
 * index of first occurence of c, starting at position i.
 * <0 if not fount.
 *
 * require
 *   i>=0;
 *   i< a.Capacity();
 * ensure
 *   (Result = -1) OR (a.chars[Result] = c);
 *)
VAR
  Result: LONGINT;
BEGIN
  Result := -1;
  WHILE (i<a.len) & (Result<0) DO
    IF a.chars[i]=c THEN
      Result := i;
    END;
    INC(i);
  END;
  RETURN Result;
END IndexOf;


PROCEDURE (a: STRING) LeftAdjust * ;
(*
 * Remove leading blanks
 *
 * ensure
 *   (a.Count()=0) OR (a.chars[0]#Blank);
 *)

VAR
  i,j: LONGINT;
BEGIN
  i := 0;
  WHILE (i<a.len) & (a.chars[i]=Blank) DO
    INC(i);
  END;
  IF i>0 THEN
    FOR j:=i TO a.len-1 DO
      a.chars[j-i] := a.chars[j];
    END;
    DEC(a.len,i);
    a.chars[a.len] := 0X;
  END;
END LeftAdjust;


PROCEDURE (a: STRING) Precede * (c: CHAR);
(*
 * Add c at front
 *
 * require
 *   c#0X;
 * ensure
 *   a.chars[0] = c;
 *   a.Count() = OLD a.Count() + 1
 *)

VAR
  i: LONGINT;
BEGIN
  a.Enlarge(a.len+1);
  FOR i := a.len TO 1 BY -1 DO
    a.chars[i] := a.chars[i-1];
  END;
  a.chars[0] := c;
  INC(a.len);
  IF a.len<LEN(a.chars^) THEN a.chars[a.len] := 0X END;
END Precede;


PROCEDURE (a: STRING) Prepend * (b: STRING);
(*
 * prepend a copy of s at front of a
 *
 * require
 *   b#NIL
 * ensure
 *   a.Count() = OLD a.Count() + b.Count();
 *)

VAR
  i: LONGINT;
BEGIN
  a.Enlarge(a.len+b.len);
  FOR i:=a.len-1 TO 0 BY -1 DO
    a.chars[i+b.len] := a.chars[i];
  END;
  FOR i:=0 TO b.len-1 DO
    a.chars[i] := b.chars[i];
  END;
  INC(a.len,b.len);
  IF a.len<LEN(a.chars^) THEN a.chars[a.len] := 0X END;
END Prepend;


PROCEDURE (a: STRING) Put * (c: CHAR; i: LONGINT);
(*
 * Set character at position i to c.
 *
 * require
 *   i >= 0;
 *   i < a.Count();
 *   c # 0X;
 * ensure
 *   a.chars[i] = c;
 *)

BEGIN
  a.chars[i] := c;
END Put;


PROCEDURE (a: STRING) Remove * (i: LONGINT);
(*
 * Remove i-th Character.
 *
 * require
 *   i >= 0;
 *   i < a.Count();
 * ensure
 *   a.Count() = OLD a.Count() - 1
 *)

BEGIN
  DEC(a.len);
  FOR i := i TO a.len-1 DO
    a.chars[i] := a.chars[i+1];
  END;
  a.chars[a.len] := 0X;
END Remove;


PROCEDURE (a: STRING) RemoveAllOccurences * (c: CHAR);
(*
 * remove all occurences of c
 *
 * ensure
 *   for all i: 0..a.Count()-1, a.chars[i]#c;
 *   a.Count() = OLD a.Count() - # of occurences of c within initial a.
 *)

VAR
  i,d: LONGINT;
BEGIN
  i := 0; d := 0;
  REPEAT
    WHILE (i+d<a.len) & (a.chars[i+d]=c) DO                             INC(d) END;
    WHILE (i+d<a.len) & (a.chars[i+d]#c) DO a.chars[i] := a.chars[i+d]; INC(i) END;
  UNTIL i+d>=a.len;
  IF d>0 THEN
    DEC(a.len,d);
    a.chars[a.len] := 0X;
  END;
END RemoveAllOccurences;


PROCEDURE (a: STRING) Resize * (newsize: LONGINT);
(*
 * Reallocate if needed to accommodate at least newsize characters.
 *
 * require
 *   newsize >= 0;
 * ensure
 *   a.Capacity() >= newsize
 *)

VAR
  new: BT.DynString;
BEGIN
  IF newsize>LEN(a.chars^) THEN
    NEW(new,newsize);
    COPY(a.chars^,new^);
    a.chars := new;
  END;
END Resize;


PROCEDURE (a: STRING) Enlarge * (newsize: LONGINT);
(*
 * Reallocate if needed to accommodate at least newsize characters.
 * This routine allocates more chars than are actually needed, so many
 * calls to Enlarge() don't end in too many allocates.
 *
 * require
 *   newsize >= 0;
 * ensure
 *   a.Capacity() >= newsize
 *)

VAR
  new: BT.DynString;
BEGIN
  IF newsize>LEN(a.chars^) THEN
    a.Resize(newsize + newsize DIV 2);
  END;
END Enlarge;


PROCEDURE (a: STRING) RightAdjust *;
(*
 * Remove trailing Blanks.
 *
 * ensure
 *   (a.Count()=0) OR (a.chars[a.Count()-1]#Blank)
 *)

BEGIN
  WHILE (a.len>0) & (a.chars[a.len-1]=Blank) DO
    DEC(a.len);
    a.chars[a.len] := 0X;
  END;
END RightAdjust;


PROCEDURE (a: STRING) Shrink * (t: STRING; n1,n2: LONGINT);
(*
 * remove characters outside of interval n1..n2
 *
 * require
 *   t#NIL;
 *   0  <= n1;
 *   n1 <= n2;
 *   n2 <  t.Count();
 * ensure
 *   a.Equal(t.Substring(n1,n2));
 *)

VAR
  i: LONGINT;
BEGIN
  a.Enlarge(n2-n1+1);
  FOR i := 0 TO n2-n1 DO
    a.chars[i] := t.chars[n1+i];
  END;
  a.len := n2-n1+1;
  IF a.len<LEN(a.chars^) THEN a.chars[a.len] := 0X END;
END Shrink;


PROCEDURE (a: STRING) Substring * (n1,n2: LONGINT): STRING;
(*
 * Copy of substring of current string containing all characters
 * at indices between n1 and n2.
 *
 * require
 *   0  <= n1;
 *   n1 <= n2;
 *   n2 <  t.Count()
 * ensure
 *   Result.Count = n2 - n1 + 1;
 *   for all i: 0 .. n2-n1, Result.chars[i] = a.chars[n1+i]
 *)

VAR
  new: STRING;
  i: LONGINT;
BEGIN
  new := Create(n2-n1+2);
  FOR i := 0 TO n2-n1 DO
    new.chars[i] := a.chars[n1+i];
  END;
  new.len := n2-n1+1;
  new.chars[new.len] := 0X;
  RETURN new;
END Substring;


PROCEDURE (a: STRING) Tail * (n: LONGINT);
(*
 * Remove all but the last n characters of the string.
 * Do nothing for n >= a.Count();
 *
 * require
 *   n >= 0;
 * ensure
 *   n <  OLD a.Count() IMPLIES a.Count() = n;
 *   n >= OLD a.Count() IMPLIES a.Count() = OLD a.Count;
 *)

VAR
  i: LONGINT;

BEGIN
  IF n<a.len THEN
    FOR i:=0 TO n-1 DO
      a.chars[i] := a.chars[a.len - n + i];
    END;
    a.len := n;
    a.chars[n] := 0X;
  END;
END Tail;


PROCEDURE (a: STRING) ToC * (): SYSTEM.ADDRESS;
(*
 * Address of the string that a C function may cast into a pointer to a
 * C form of the string. Useful only for interfacing with C software.
 *)

BEGIN
  a.Enlarge(a.len+1);
  RETURN SYSTEM.ADR(a.chars^);
END ToC;


PROCEDURE (a: STRING) ToInteger * (): LONGINT;
(*
 * Integer value of current string, assumed to contain digits only.
 * When applied to "123", will yield 123.
 *
 * require
 *   for all i: 0..a.Count()-1, ("0"<=a.chars[i]) & (a.chars[i]<="9")
 *)

VAR
  Result: LONGINT;
  i: LONGINT;
  negative: BOOLEAN;

BEGIN
  Result := 0; negative := FALSE;
  IF a.len>0 THEN
    CASE a.chars[0] OF
    | "-": i := 1; negative := TRUE;
    | "+": i := 1;
    ELSE   i := 0;
    END;
    WHILE (i<a.len) DO
      CASE a.chars[i] OF
      | "0".."9":
        IF Result < (MAX(LONGINT) - (ORD(a.chars[i]) - ORD("0"))) DIV 10 THEN
          Result := 10 * Result + (ORD(a.chars[i]) - ORD("0"));
        END;
      ELSE END;
      INC(i);
    END;
  END;
  RETURN Result;
END ToInteger;


PROCEDURE (a: STRING) ToLower *;
(*
 * Convert a to lower case
 *)

VAR
  i: LONGINT;
BEGIN
  FOR i:=0 TO a.len-1 DO
    CASE a.chars[i] OF
    | "A".."Z","À".."Ö","Ø".."þ": a.chars[i] := CHR(ORD(a.chars[i]) + 32)
    ELSE END;
  END;
END ToLower;


PROCEDURE (a: STRING) ToUpper *;
(*
 * Convert a to lower case
 *)

VAR
  i: LONGINT;
BEGIN
  FOR i:=0 TO a.len-1 DO
    CASE a.chars[i] OF
    | "a".."z","à".."ö","ø".."þ": a.chars[i] := CHR(ORD(a.chars[i]) - 32)
    ELSE END;
  END;
END ToUpper;


END STRING.