IMPLEMENTATION MODULE StringSpace;

IMPORT String;
IMPORT SYSTEM;
----------------------------------------------------
  ONCE CLASS HashFunc;
    METHOD ComputePartialHash (Txt: ARRAY OF CHAR;
                               Len: INTEGER): INTEGER;
      BEGIN
      RESULT := 9321871;
      FOR i := 0 TO Len - 1 DO
        RESULT := RESULT + ((RESULT + i) * SYSTEM.ORD(Txt[i]));
        END;
      IF RESULT < 0 THEN
        RESULT := -RESULT;
        END;
      END ComputePartialHash;

    METHOD ComputeHash (Txt: ARRAY OF CHAR): INTEGER;
      BEGIN
      RESULT := ComputePartialHash (Txt, Txt.SIZE);
      END ComputeHash;

  END HashFunc;
-----------------------------------------------------

  CLASS StringElement;
    INHERITS HashElement;

    VAR
      Txt: ARRAY OF CHAR;
      TheHash: INTEGER;

    REDEFINE METHOD CREATE (Text: ARRAY OF CHAR);
      BEGIN
      BASE;   
      Txt := Text;
      TheHash := HashFunc.ComputeHash(Txt);
      END CREATE;

    REDEFINE METHOD HashValue: INTEGER;
      BEGIN
      RESULT := TheHash;
      END HashValue;

    METHOD Text: ARRAY OF CHAR;
      BEGIN
      RESULT := Txt;
      END Text;

  END StringElement;
--------------------------------------------------------------
  CLASS StringHashSpace(Element IN StringElement);
    INHERITS HashSpace(Element);

    VAR
      LastElement: Element;

    METHOD StorePartialString(Text: ARRAY OF CHAR;
                              Len: INTEGER): ARRAY OF CHAR;
      VAR
        i: INTEGER;
        El: HashElement;
        HashEl: Element;
        a: ARRAY OF CHAR;
      BEGIN
      i := HashFunc.ComputePartialHash (Text, Len);
      El := Find(i);
      WHILE (El <> VOID) AND (RESULT = VOID) DO
        WHAT El OF
          IN Element:
            IF String.LimitedCompare (Text, TAG.Text, Len) = String.Equal THEN
              LastElement := TAG;
              RESULT := TAG.Text;
             ELSE
              El := Next;
              END;
            END;
          END;
        END;
      IF RESULT = VOID THEN
        IF Len <> Text.SIZE THEN
          a := Text.SLICE(0, Len);
         ELSE
          a := Text;
          END;
        HashEl := NewElement(a);
        IF Store (HashEl) THEN
          LastElement := HashEl;
          RESULT := a;
          END;
        END;
      END StorePartialString;

    METHOD StoreString(Text: ARRAY OF CHAR): ARRAY OF CHAR;
      BEGIN
      ASSERT Text <> VOID;
      RESULT := StorePartialString (Text, Text.SIZE);
      END StoreString;

    METHOD FindStringElement (Text: ARRAY OF CHAR): Element;
      BEGIN
      RESULT := FindPartialStringElement (Text, Text.SIZE);
      END FindStringElement;
      
    METHOD FindPartialStringElementWithHash (Text: ARRAY OF CHAR;
                                             Len,
                                             HashValue: INTEGER): Element;
      VAR
        El: Element;                                       
      BEGIN
      El := Find(HashValue);
      WHILE (El <> VOID) AND (RESULT = VOID) DO
        WHAT El OF
          IN Element:
            IF String.LimitedCompare (Text, TAG.Text, Len) = String.Equal THEN
              LastElement := TAG;
              RESULT := TAG;
             ELSE
              El := Next;
              END;
            END;
          END;
        END;
      END FindPartialStringElementWithHash;

    METHOD FindStringElementWithHash (Text: ARRAY OF CHAR;
                                      HashValue: INTEGER): Element;
      BEGIN
      RESULT := FindPartialStringElementWithHash (Text, 
                                                  Text.SIZE, 
                                                  HashValue);
      END FindStringElementWithHash;
                                        
    METHOD FindPartialStringElement (Text: ARRAY OF CHAR;
                                     Len: INTEGER): Element;
      BEGIN
      RESULT := FindPartialStringElementWithHash (Text, Len,
                       HashFunc.ComputePartialHash (Text, Len));
      END FindPartialStringElement;

    METHOD StorePartialElement (Text: ARRAY OF CHAR;
                                Len: INTEGER): Element;
      VAR
        Flag: BOOLEAN;
      BEGIN
      RESULT := FindPartialStringElement (Text, Len);
      IF RESULT = VOID THEN
        RESULT := NewElement(Text.SLICE(0, Len));
        Flag := Store (RESULT);
        ASSERT Flag;
        END;
      LastElement := RESULT;
      END StorePartialElement;

    METHOD StoreElement (StringEl: Element);
      VAR
        Flag: BOOLEAN;
        Temp: Element;
      BEGIN
      DEBUG
        IF FindStringElement (StringEl.Text) <> VOID THEN
          Temp := FindStringElement (StringEl.Text);
          ASSERT FALSE;
          END;
        END;
      Flag := Store (StringEl);
      ASSERT Flag;
      DEBUG 
        Temp := FindStringElement (StringEl.Text);
        END;
      LastElement := StringEl;
      END StoreElement;

    METHOD HashValue (Text: ARRAY OF CHAR): INTEGER;
      BEGIN
      IF (LastElement <> VOID) AND (Text = LastElement.Text) THEN
        RESULT := LastElement.HashValue;
       ELSE
        RESULT := HashFunc.ComputeHash (Text);
        END;
      END HashValue;

    REDEFINE METHOD Purge;
      BEGIN
      BASE;
      LastElement := VOID;
      END Purge;

  END StringHashSpace;
----------------------------------------------------------
  CLASS StringSpace;
    INHERITS StringHashSpace(StringElement);

    REDEFINE METHOD NewElement(Text: ARRAY OF CHAR): StringElement;
      BEGIN
      RESULT.CREATE (Text);
      END NewElement;

  END StringSpace;

END StringSpace;
