QuickSilverのあれ

どんなもんかと実装してみた．といってもObjective-Cよく分からなかったので，Ruby版のをベースに．実際速さを求めるなら，本家のようにNSRangeみたいな軽量な構造体使ったり，単一関数の再帰の方が速いかも．
なんにせよ，これだけ短いやつであんな探索出来るんだなぁとしみじみ．

// Written in the D programming language.

import std.array  : empty;
import std.conv   : to;
import std.regex  : regex, match;
import std.string : indexOf, CaseSensitive;
import std.traits : ReturnType, isSomeString;


/**
 * Abbreviation scoring for string by Alcor
 *
 * If you consider product level, you should use light-weight range instead of slice.
 */
struct AbbreviationScorer(String) if (isSomeString!(String))
{
  private:
    alias ReturnType!(regex!(String)) Regex;

    enum ERROR = -1.0;  // @@@BUG@@@ Give me Nullable!

    /* @@@BUG@@@ std.regex.match can't use const object */
    static /* immutable */ Regex ReWS, ReUpper;
    static this()
    {
        ReWS    = regex(to!(String)("\\s$"));
        ReUpper = regex(to!(String)("[A-Z]"));
    }

    String source_;


  public:
    /**
     * Initializes scorer object.
     *
     * Params:
     *   source = to search string.
     */
    this(String source)
    {
        source_ = source;
    }


    /**
     * Computes abbreviation score using _abbr_ string.
     *
     * Params:
     *   abbr = abbreviated string.
     * Out:
     *   Return value must not be negative.
     * Returns:
     *   score between 0.0 and 1.0.
     */
    double compute(String abbr)
    out(result)
    {
        /* @@@BUG@@@ http://d.puremagic.com/issues/show_bug.cgi?id=3667
        assert(result >= 0.0);
         */
    }
    body
    {
        if (abbr.empty)
            return 0.9;
        if (source_.length < abbr.length)
            return 0.0;

        auto abbrLength  = abbr.length;

        foreach (i; 0..abbrLength) {
            auto result = scoreFor(abbr, abbrLength - i);
            if (result != ERROR)
                return result;
        }

        return 0.0;
    }


  private:
    double scoreFor(String abbr, uint pivot)
    {
        auto ahead = abbr[0..pivot];
        auto atail = abbr[pivot..$];
        auto found = source_.indexOf(ahead, CaseSensitive.no);
        if (found == -1)
            return ERROR;

        auto tail      = source_[found + pivot..$];
        auto tailScore = abbreviationScorer(tail).compute(atail); 
        if (!(tailScore > 0.0))
            return ERROR;

        return (to!(double)(found) + pivot - penalty(found) + tailScore * tail.length) / source_.length;
    }


    double penalty(int found)
    {
        /+ @@@BUG@@@ std.regex.Regex can't construct at compile time
        static /* immutable */ Regex ReWS    = regex("\\s$");
        static /* immutable */ Regex ReUpper = regex("[A-Z]");
         +/
        if (found == 0)
            return 0.0;

        auto skipped = source_[0..found];

        auto matched = skipped.match(ReWS);
        if (!matched.empty) {
            auto length = matched.hit.length;
            return length + (skipped.length - length) * 0.15;
        }

        matched = source_[found..$].match(ReUpper);
        if (!matched.empty) {
            matched = skipped.match(ReUpper);
            auto length = matched.empty ? 0 : matched.hit.length;
            return length + (skipped.length - length) * 0.15; 
        }

        return skipped.length;
    }
}


/**
 * Shortcut for AbbreviationScorer construction.
 */
AbbreviationScorer!(String) abbreviationScorer(String)(String source)
{
    return typeof(return)(source);
}


version(unittest)
{
    import std.math      : approxEqual;
    import std.typetuple : TypeTuple;
}

unittest
{
    struct Test
    {
        string   source;
        string[] abbrs;
        double[] results;
    }

    static Test[] tests = [
        {"hello", ["h",  "he",  "hel", "helo", "hello", "llo", "lo", "ho", "hx"],
                  [0.92, 0.94,  0.96,  0.80,   1.00,     0.60, 0.40, 0.40, 0.00]},
        {"HelloWorld", ["hw"], [0.90]}
    ];

    foreach (Char; TypeTuple!(char, wchar, dchar))
    {
        alias immutable(Char)[] String;

        foreach (test; tests) {
            auto scorer = abbreviationScorer(to!(String)(test.source));

            foreach (i, abbr; test.abbrs) {
                assert(approxEqual(scorer.compute(to!(String)(abbr)), test.results[i]));
            }
        }
    }
}