Oberon-2 sample for finding Anagrams.

anagrams.pas

MODULE Anagrams;

TYPE STRING        = ARRAY 10 OF CHAR;
     Word          = POINTER TO WordRec;
     WordRec       = RECORD
                        text : STRING;
                        next : Word
                   END;
     Node          = POINTER TO NodeRec;
     NodeRec       = RECORD
                        key   : STRING;
                        next  : Node;
                        count : INTEGER;
                        words : Word
                   END;
     Dictionary*   = POINTER TO DictionaryRec;
     DictionaryRec = RECORD
                        nodes: Node
                   END;
     StringArrayP* = POINTER TO StringArray;
     StringArray*  = ARRAY OF STRING;

PROCEDURE (dict: Dictionary) newHash(str: ARRAY OF CHAR; VAR out: STRING);
VAR temp : CHAR;
    i, j : INTEGER;
BEGIN
    (* Bubble-sort characters in the string *)
    FOR i := 0 TO LEN(str) - 3 DO
        FOR j := i + 1 TO LEN(str) - 2 DO
            IF (str[i] > str[j]) THEN
                temp := str[i];
                str[i] := str[j];
                str[j] := temp;
            END
        END
    END;
    FOR i := 0 TO LEN(str) - 1 DO
        out[i] := str[i]
    END
END newHash;

PROCEDURE (node: Node) newWord(str: ARRAY OF CHAR);
VAR word, iter : Word;
    i          : INTEGER;
BEGIN
    INC(node^.count);
    NEW(word);
    FOR i := 0 TO LEN(str) - 1 DO
        word^.text[i] := str[i];
    END;
    word^.next := NIL;
    iter := node^.words;
    IF iter = NIL THEN
        node^.words := word
    ELSE
        WHILE iter^.next # NIL DO
            iter := iter^.next
        END;
        iter^.next := word
    END
END newWord;

PROCEDURE (dict: Dictionary) getNode(hash: STRING) : Node;
VAR prev, node : Node;
BEGIN
    prev := NIL;
    node := dict^.nodes;
    WHILE (node # NIL) & (node^.key < hash) DO
        prev := node;
        node := node^.next
    END;
    IF (node # NIL) & (node^.key = hash) THEN
        (* Found *)
    ELSIF prev = NIL THEN
        (* Either the dictionary is empty, or the node should go before the first one *)
        NEW(node);
        node^.count := 0;
        node^.key := hash;
        node^.next := dict^.nodes;
        dict^.nodes := node
    ELSIF (node = NIL) OR (node^.key # hash) THEN
        (* Either we're at the end of the dictionary, or we should insert a new node *)
        NEW(node);
        node^.count := 0;
        node^.key := hash;
        node^.next := prev^.next;
        prev^.next := node
    END;
    RETURN node
END getNode;

PROCEDURE (dict: Dictionary) addWord*(str: ARRAY OF CHAR);
VAR node : Node;
    hash : STRING;
BEGIN
    dict.newHash(str, hash);
    node := dict.getNode(hash);
    node.newWord(str)
END addWord;

PROCEDURE newDict*() : Dictionary;
VAR dict : Dictionary;
BEGIN
    NEW(dict);
    dict^.nodes := NIL;
    RETURN dict
END newDict;

PROCEDURE (dict: Dictionary) anagramOf*(str: ARRAY OF CHAR) : StringArrayP;
VAR word : Word;
    node : Node;
    ret : POINTER TO StringArray;
    i : INTEGER;
    hash : STRING;
BEGIN
    dict.newHash(str, hash);
    ret := NIL;
    node := dict^.nodes;
    WHILE node^.key < hash DO
        node := node^.next
    END;
    IF node^.key = hash THEN
        word := node^.words;
        NEW(ret, node^.count);
        FOR i := 0 TO LEN(ret^)-1 DO
            ret^[i] := word^.text;
            word := word^.next
        END
    END;
    RETURN ret
END anagramOf;

END Anagrams.

Usage:

MODULE TestAnagrams;

IMPORT Anagrams, Out;

VAR dict    : Anagrams.Dictionary;
    matches : Anagrams.StringArrayP;
    i       : INTEGER;

BEGIN
    dict := Anagrams.newDict();
    dict.addWord("cat");
    dict.addWord("act");
    dict.addWord("dog");
    dict.addWord("god");

    matches := dict.anagramOf("cat");
    Out.String("# Matches: "); Out.Int(LEN(matches^), 0); Out.Ln();
    FOR i := 0 TO LEN(matches^) - 1 DO
        Out.String(matches^[i]); Out.Ln();
    END;
    ASSERT(LEN(matches^) = 2);
    ASSERT(matches^[0] = "cat");
    ASSERT(matches^[1] = "act");
    Out.String("All passed"); Out.Ln();
END TestAnagrams.