Anagram finder in Swift

This is the Swift implementation of the anagram program. The problem and the solution is described in the main anagram article. Do read that article first.

For large inputs the Swift program uses 9 times as much processing time and 3 times as much memory as the C++ version.

In Swift 4 there is no printf-style formatting, so I rolled my own printf(). It only cover simple types and strings, not objects in general.

The source code

import Foundation

let MINIMUM = 3
var comparisons = 0

//--------------------------------------------------------------------------------------- printf

func get_addr(_ cchars : ContiguousArray<CChar>) -> UnsafePointer<CChar> {
     return cchars.withUnsafeBufferPointer {
         ptr in ptr.baseAddress!;
     }
}

func printf(_ format : String, _ args : CVarArg...) {
    var argv        = Array<CVarArg               >()
    var utf8strings = Array<ContiguousArray<CChar>>()

    argv.reserveCapacity(args.count)
    for arg in args {
        let str : String? = arg as? String;
        if (str != nil) {
            let cchars  : ContiguousArray<CChar> = str!.utf8CString
            let first_p : UnsafePointer  <CChar> = get_addr(cchars)
            argv.append(first_p)
            utf8strings.append(cchars)
        } else {
            argv.append(arg)
        }
    }
    _ = withVaList(argv) {
        vprintf(format, $0);
    }
}

//--------------------------------------------------------------------------------------- Word

class Word : Comparable {
    var offset  = 0;
    var value   = "";
    var unified = "";

    init(_ offset : Int, _ value : String, _ unified : String) {
        self.offset  = offset;
        self.value   = value;
        self.unified = unified;
    }

    static func compare(_ a : Word, _ b : Word) -> Int {
        comparisons += 1;
        if (a.unified < b.unified) {
            return -1;
        } else if (a.unified > b.unified) {
            return +1;
        } else {
            return a.offset - b.offset;
        }
    }

    static func <(a : Word, b : Word) -> Bool {
        return compare(a, b) < 0;
    }

    static func ==(a : Word, b : Word) -> Bool {
        return compare(a, b) == 0;
    }
};

//--------------------------------------------------------------------------------------- AnagramFinder

class AnagramFinder {
    var low_offset = 0;
    var len        = 0;
    var words      = Array<Word>();
    var accepted   = Array<Word>();

    init(_ text : String, _ len : Int) {
        self.len = len;
        let count = text.count - len + 1
        var begin = text.index(text.startIndex, offsetBy: 0);
        var end   = text.index(text.startIndex, offsetBy: len-1);

        self.words.reserveCapacity(count);
        for i in 0..<count {
            end   = text.index(end,   offsetBy: 1);
            let value = String(text[begin..<end]);
            begin = text.index(begin, offsetBy: 1);

            words.append(Word(i, value, get_unified(value)));
        }
    }

    func get_unified(_ value : String) -> String {
        return String(value.sorted());
    }

    func print_one_result() {
        printf("%3d:", accepted.count);
        for it in accepted {
            printf(" %4d:%s", it.offset, it.value)
        }
        printf("\n");
    }

    func add_candidate(_ cand : Int) {
        let c = words[cand];
        if (c.offset < low_offset) {
            return;
        }
        for it in accepted {
            if (c.value == it.value) {
                return;
            }
        }
        accepted.append(c);
        low_offset = c.offset+len;
    }

    func add_range(_ begin : Int, _ end : Int) {
        if (end - begin >= MINIMUM) {
            accepted.removeAll();
            low_offset = 0;
            for i in begin..<end {
                add_candidate(i);
            }
            if (accepted.count >= MINIMUM) {
                print_one_result();
            }
        }
    }

    func find_all() {
        words.sort();
        var begin = 0;
        for i in 1..<(words.count-1) {
            if (words[i].unified != words[begin].unified) {
                add_range(begin, i);
                begin = i;
            }
        }
        add_range(begin, words.count);
    }
};

//--------------------------------------------------------------------------------------- main program

func read_text() -> String {
    var rval : String  = "";
    var buf  : String? = readLine();

    rval.reserveCapacity(500*512);
    while (buf != nil) {
        let line : String = buf!.uppercased();
        for ch : Character in line {
            if (ch >= "A" && ch <= "Z") { //--- No isLetter in Swift 4
                rval.append(ch);
            }
        }
        buf = readLine();
    }
    return rval;
}

func main() {
    var from  = 6;
    var to    = 6;
    let text  = read_text();
    let argc  : Int           = Int(CommandLine.argc)
    let argv  : Array<String> = CommandLine.arguments;

    if (argc > 1) {
        from = Int(argv[1])!;
        to   = from;
    }

    if (argc > 2) {
        to = Int(argv[2])!;
    }

    for len in from..<(to+1) {
        printf("%slen = %d\n", (len > from) ? "\n" : "", len);
        AnagramFinder(text, len).find_all();
    }
    printf("string length = %5d, comparisons = %d\n", text.count, comparisons);
}

main();

You can reach me by email at “lars dash 7 dot sdu dot se” or by telephone +46 705 189090

View source for the content of this page.