better-anagrams.pas

MODULE Anagram;

IMPORT Std, Map, Vector, String;

TYPE ANAGRAM*   = POINTER TO AnagramRec;
     AnagramRec = RECORD
                    words : Map.MAP
                  END;

PROCEDURE newDict*() : ANAGRAM;
VAR a: ANAGRAM;
BEGIN
    NEW(a);
    a.words := Map.Map();
    RETURN a
END newDict;

PROCEDURE (a: ANAGRAM) Length*() : INTEGER;
BEGIN
    RETURN a.words.Length();
END Length;

PROCEDURE (a: ANAGRAM) MakeHash(s: String.STRING) : String.STRING;
VAR temp : CHAR;
    i, j : INTEGER;
BEGIN
    s := s.Clone();
    (* Bubble-sort characters in the string *)
    FOR i := 0 TO s^.len - 3 DO
        FOR j := i + 1 TO s^.len - 2 DO
            IF (s^.str[i] > s^.str[j]) THEN
                temp := s^.str[i];
                s^.str[i] := s^.str[j];
                s^.str[j] := temp;
            END
        END
    END;
    RETURN s
END MakeHash;

PROCEDURE (a: ANAGRAM) AddWord*(s: String.STRING);
VAR o    : Std.OBJECT;
    vec  : Vector.VECTOR;
    hash : String.STRING;
BEGIN
    hash := MakeHash(s);
    o := a.words.Get(hash);
    IF o = NIL THEN
        vec := Vector.Vector();
        vec.PushBack(s);
        a.words.Put(hash, vec)
    ELSE
        o(Vector.VECTOR).PushBack(s)
    END
END AddWord;

PROCEDURE (a: ANAGRAM) AnagramOf*(s: String.STRING) : Vector.VECTOR;
VAR hash : String.STRING;
    o    : Std.OBJECT;
BEGIN
    hash := MakeHash(s);
    o := a.words.Get(hash);
    IF o = NIL THEN
        RETURN NIL
    ELSE
        RETURN o(Vector.VECTOR);
    END
END AnagramOf;

END Anagram.

Usage:

MODULE TestAnagram;

IMPORT Std, Vector, String, Anagram, Out;

VAR v : Vector.VECTOR;
    o : Std.OBJECT;
    i : INTEGER;
    a : Anagram.ANAGRAM;

BEGIN
    a := Anagram.newDict();
    a.AddWord(String.String("cat"));
    a.AddWord(String.String("act"));
    a.AddWord(String.String("dog"));
    a.AddWord(String.String("god"));

    ASSERT(a.Length() = 2);

    v := a.AnagramOf(String.String("cat"));

    ASSERT(v # NIL);
    ASSERT(v.Length() = 2);

    Out.String("Anagrams of cat"); Out.Ln();
    FOR i := 0 TO v.Length() - 1 DO
        o := v.At(i);
        Out.String(o(String.STRING).str^); Out.Ln();
    END
END TestAnagram.