MODULE M3CHash;

(***************************************************************************)
(*                      Copyright (C) Olivetti 1989                        *)
(*                          All Rights reserved                            *)
(*                                                                         *)
(* Use and copy of this software and preparation of derivative works based *)
(* upon this software are permitted to any person, provided this same      *)
(* copyright notice and the following Olivetti warranty disclaimer are     *) 
(* included in any copy of the software or any modification thereof or     *)
(* derivative work therefrom made by any person.                           *)
(*                                                                         *)
(* This software is made available AS IS and Olivetti disclaims all        *)
(* warranties with respect to this software, whether expressed or implied  *)
(* under any law, including all implied warranties of merchantibility and  *)
(* fitness for any purpose. In no event shall Olivetti be liable for any   *)
(* damages whatsoever resulting from loss of use, data or profits or       *)
(* otherwise arising out of or in connection with the use or performance   *)
(* of this software.                                                       *)
(***************************************************************************)

IMPORT Text, Word;

REVEAL
  Table = BRANDED OBJECT
    size: CARDINAL;
    idCreator: IdCreator;
    ids: REF ARRAY OF Id;
  END;

  Id = BRANDED OBJECT
    next: Id;
    text: Text.T;
  END;

  Value = BRANDED OBJECT
    sum, sumOfSums := 0;
  END;


<*INLINE*> PROCEDURE NewValue(): Value RAISES {}=
  BEGIN
    RETURN NEW(Value);
  END NewValue;


<*INLINE*> PROCEDURE ResetValue(v: Value) RAISES {}=
  BEGIN
    v.sum := 0; v.sumOfSums := 0;
  END ResetValue;


<*INLINE*> PROCEDURE AddCharToValue(ch: CHAR; v: Value) RAISES {}=
  BEGIN
    v.sum := Word.Plus(v.sum, ORD(ch));
    v.sumOfSums := Word.Plus(v.sumOfSums, v.sum);
  END AddCharToValue;


<*INLINE*> PROCEDURE Create(
    t: Table;
    text: Text.T;
    VAR list: Id)
    : Id
    RAISES {}=
  BEGIN
    WITH new = t.idCreator.new(text) DO
      new.next := list;
      new.text := text;
      list := new;
      RETURN new;
    END;
  END Create;


<*INLINE*> PROCEDURE Equal(
    t: Text.T;
    READONLY chars: ARRAY OF CHAR)
    : BOOLEAN
    RAISES {}=
  BEGIN
    FOR i := 0 TO LAST(chars) DO
      IF Text.GetChar(t, i) # chars[i] THEN RETURN FALSE END;
    END;
    RETURN TRUE;
  END Equal;


<*INLINE*> PROCEDURE FindChars(
    READONLY chars: ARRAY OF CHAR;
    id: Id)
    : Id
    RAISES {}=
  BEGIN
    WHILE id # NIL DO
      IF Text.Length(id.text) = NUMBER(chars) AND Equal(id.text, chars) THEN
        EXIT;
      ELSE
        id := id.next;
      END;
    END;
    RETURN id;
  END FindChars;


PROCEDURE EnterCharsWithValue(
    t: Table;
    v: Value;
    READONLY chars: ARRAY OF CHAR)
    : Id
    RAISES {}=
  BEGIN
    WITH id = t.ids[v.sumOfSums MOD t.size], found = FindChars(chars, id) DO
      IF found # NIL THEN
        RETURN found;
      ELSE
        RETURN Create(t, Text.FromChars(chars), id);
      END;
    END;
  END EnterCharsWithValue;


<*INLINE*> PROCEDURE FindText(text: Text.T; id: Id): Id RAISES {}=
  BEGIN
    WHILE id # NIL DO
      IF Text.Equal(id.text, text) THEN
        EXIT;
      ELSE
        id := id.next;
      END;
    END;
    RETURN id;
  END FindText;


PROCEDURE EnterTextWithValue(t: Table; v: Value; text: Text.T): Id RAISES {}=
  BEGIN
    WITH id = t.ids[v.sumOfSums MOD t.size], found = FindText(text, id) DO
      IF found # NIL THEN
        RETURN found;
      ELSE
        RETURN Create(t, text, id);
      END;
    END;
  END EnterTextWithValue;


<*INLINE*> PROCEDURE TextValue(text: Text.T): Value RAISES {}=
  VAR
    v := NewValue();
  BEGIN
    FOR i := 0 TO Text.Length(text) - 1 DO
      AddCharToValue(Text.GetChar(text, i), v);
    END; (* for *)
    RETURN v;
  END TextValue;


PROCEDURE Enter(t: Table; text: Text.T): Id RAISES {}=
  BEGIN
    RETURN EnterTextWithValue(t, TextValue(text), text);
  END Enter;


PROCEDURE Lookup(t: Table; text: Text.T; VAR id: Id): BOOLEAN RAISES {}=
  VAR
    tempId := FindText(text, t.ids[TextValue(text).sumOfSums MOD t.size]);
  BEGIN
    IF tempId # NIL THEN id := tempId; RETURN TRUE ELSE RETURN FALSE END;
  END Lookup;


TYPE
  DefaultIdCreator = IdCreator OBJECT OVERRIDES new := DefaultNewId END;


PROCEDURE DefaultNewId(c: IdCreator; t: Text.T): Id RAISES {}=
  BEGIN
    RETURN NEW(Id);
  END DefaultNewId;


<*INLINE*> PROCEDURE NewDefaultIdCreator(): DefaultIdCreator RAISES {}=
  BEGIN
    RETURN NEW(DefaultIdCreator);
  END NewDefaultIdCreator;


VAR
  gDefaultIdCreator := NewDefaultIdCreator();


PROCEDURE New(
    size: CARDINAL;
    idCreator: IdCreator := NIL;
    init: Table := NIL)
    : Table
    RAISES {}=
  BEGIN
    IF init = NIL THEN init := NEW(Table) END;
    IF idCreator = NIL THEN idCreator := gDefaultIdCreator END;
    init.size := size;
    init.idCreator := idCreator;
    init.ids := NEW(REF ARRAY OF Id, size);
    RETURN init;
  END New;


PROCEDURE SetCreator(t: Table; idCreator: IdCreator): IdCreator RAISES {}=
  VAR
    old := t.idCreator;
  BEGIN
    t.idCreator := idCreator;
    RETURN old;
  END SetCreator;


<*INLINE*> PROCEDURE IdToText(id: Id): Text.T RAISES {}=
  BEGIN
    RETURN id.text;
  END IdToText;


BEGIN

END M3CHash.