[Issue 6788] std.range.pairwise

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=6788

--- Comment #9 from bearophile_hugs at eml.cc ---
This shows a simple use case of pairwise, to compute the pairs of closest
points of an array 2D points.

The function closestPair1 uses just a pair of loops.

closestPair2 uses cartesianProduct of all index pairs plus a filter to avoid
comparing already seen pairs (because a distance is comutative), the code is
slow, it looks bad and it's noisy.

closestPair3 uses pairwise, and it's much nicer and simpler to write.

closestPair4 is similar, but it uses the optional "key" function argument (as
in the Python min/max functions) to further simplify the code. I'd really like
min/max of Phobos to be extended to support such optional key function.

Currently some /*in*/ are commented out to avoid troubles with immutable seeds
of reduce.



import std.algorithm, std.traits, std.typecons, std.range;

struct Pairwise(Range) {
    alias R = Unqual!Range;
    alias Pair = Tuple!(ForeachType!R, "a", ForeachType!R, "b");
    R _input;
    size_t i, j;

    this(Range r_) {
        this._input = r_;
        j = 1;
    }

    @property bool empty() {
        return j >= _input.length;
    }

    @property Pair front() {
        return Pair(_input[i], _input[j]);
    }

    void popFront() {
        if (j >= _input.length - 1) {
            i++;
            j = i + 1;
        } else {
            j++;
        }
    }
}

Pairwise!Range pairwise(Range)(Range r)
if (isRandomAccessRange!Range && hasLength!Range && !isNarrowString!Range) {
    return typeof(return)(r);
}

//-----------------------

struct V2 { double x, y; }

double distance(in V2 p1, in V2 p2) pure nothrow @nogc @safe {
    return (p1.x - p2.x) ^^ 2 + (p1.y - p2.y) ^^ 2;
}

auto closestPair1(in V2[] points) pure nothrow @nogc @safe {
    auto minD = Unqual!(typeof(V2.x)).infinity;
    V2 minP1, minP2;
    foreach (immutable i, const p1; points.dropBackOne)
        foreach (const p2; points[i + 1 .. $]) {
            immutable d = distance(p1, p2);
            if (d < minD) {
                minD = d;
                minP1 = p1;
                minP2 = p2;
            }
        }
    return tuple(minP1, minP2);
}

auto closestPair2(/*in*/ V2[] points) pure nothrow @nogc @safe {
    auto pairs = cartesianProduct(points.length.iota, points.length.iota)
                 .filter!(ij => ij[1] > ij[0]);
    immutable ij = reduce!((ij1, ij2) =>
            distance(points[ij1[0]], points[ij1[1]]) <
            distance(points[ij2[0]], points[ij2[1]]) ? ij1 : ij2)
        (pairs.front, pairs.dropOne);
    return tuple(points[ij[0]], points[ij[1]]);
}

auto closestPair3(/*in*/ V2[] points) pure @safe {
    return points
           .pairwise
           .reduce!((t1, t2) => t1[].distance < t2[].distance ? t1 : t2);
}


template min(alias F) {
    T min(T)(T x, T y) {
        return F(x) < F(y) ? x : y;
    }
}

auto closestPair4(/*in*/ V2[] points) pure @safe {
    return points.pairwise.reduce!(min!(t => t[].distance));
}

void main() {
    import std.stdio, std.random;

    auto points = new V2[10];
    foreach (ref p; points)
        p = V2(uniform01, uniform01);

    points.writeln;
    points.closestPair1.writeln;
    points.closestPair2.writeln;
    points.closestPair3.writeln;
    points.closestPair4.writeln;
}

--