Forward Difference Algorithm

Question

Is/Are there a function(s) in std.algorithm or std.range with which to lazily compute a forward difference? I need this to differentially pack sorted elements (integers) in a range. The integers happen to be SysTime timestamps.

Update: Proposed solution:

/** Compute Forward Difference of $(D range).
 */
auto ref forwardDifference(bool reverse = false, Range)(in Range range)
    @safe pure nothrow if (isInputRange!Range)
{
    import std.algorithm: map;
    import std.range: zip, dropOne;
    static if (reverse)
        return range.zip(range.dropOne).map!(a => a[1] - a[0]);
    else
        return range.zip(range.dropOne).map!(a => a[0] - a[1]);
}

unittest {
    const i = [1, 5, 9, 17];
    import std.algorithm: equal;
    assert(equal(i.forwardDifference!false, [ -4, -4, -8]));
    assert(equal(i.forwardDifference!true,  [ +4, +4, +8]));
}

Please comment on solution.

Answer 1

If I understand you correctly you mean something like this?

auto i = [1, 5, 9, 17];
writeln(i.zip(i.dropOne()).map!(a=>a[0] - a[1]));

Answer 2

Another way is to make your own range:

import std.range;
import std.stdio;

auto forwardDifference(Range)(Range r) if (isInputRange!Range)
{
    struct ForwardDifference
    {

        Range range;
        alias ElementType!Range E;
        E _front;
        bool needInitialize = true;

        this (Range range)
        {
            this.range = range;
        }

        E front()
        {
            if (needInitialize)
            {
                popFront();
            }
            return _front;
        }

        E moveFront()
        {
            popFront();
            return _front;
        }

        void popFront()
        {
            if (empty is false)
            {
                needInitialize = false;
                E rf = range.front;
                range.popFront();
                if (range.empty is false)
                {
                    _front = rf - range.front;
                }
            }
        }

        bool empty()
        {
            return range.empty;
        }
    }

    return ForwardDifference(r);
}
void main(string[] args)
{
    auto i = [1, 2, 3, 5, 7, 9];
    writeln(i.forwardDifference);
    stdin.readln;
}

Answer 3

Note that, given E e;, this doesn't work when e-e is of a different type than E itself, for example when E is std.datetime.SysTime its difference becomes of type Duration and this algorithm fails to instantiate. Here's a corrected version

auto forwardDifference(Range)(Range r) if (isInputRange!Range) {
import std.range: front, empty, popFront;

struct ForwardDifference {
    Range _range;
    alias E = ElementType!Range;
    typeof(_range.front - _range.front) _front;
    bool _needInitialize = true;

    this (Range range) { this._range = range; }

    auto ref front() {
        if (_needInitialize) { popFront(); }
        return _front;
    }

    auto ref moveFront() {
        popFront();
        return _front;
    }

    void popFront() {
        if (empty is false) {
            _needInitialize = false;
            E rf = _range.front;
            _range.popFront();
            if (_range.empty is false)
            {
                _front = _range.front - rf;
            }
        }
    }

    bool empty() { return _range.empty; }
}

return ForwardDifference(r);

}

The natural question now becomes: When should we create new specialized lazy evaluated ranges such as this one and when should we reuse and recombine existing ranges from std.range?