www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Automatic opApply iteration counter

reply bearophile <bearophileHUGS lycos.com> writes:
I have not written this as enhancement request on Bugzilla because while I have
a clear (small) problem, I think my possible solution is bad (see at the
bottom).

This is how I can use opApply() to create a lazy generator of the first
Fibonacci numbers, inside opApply there can be a good amount of code:


import std.stdio: writeln;
struct Xfibonacci {
    long max;
    this(long inmax) { max = inmax; }
    int opApply(int delegate(ref long) dg) {
        int result;
        long a=0, b=1;
        while (a < max) {
            result = dg(b);
            if (result) break;
            a += b;
            result = dg(a);
            if (result) break;
            b += a;
        }
        return result;
    }
}
void main() {
    foreach (f; Xfibonacci(200))
        writeln(f);
}



But in many situations it's good to have an interation counter too, to index
the given item:
foreach (i, f; Xfibonacci(2_000))

To allow both the foreach version with and without index I have to duplicate
the body of the opApply, but this code duplication is bad:


import std.stdio: writeln;
struct Xfibonacci {
    long max;
    this(long inmax) { max = inmax; }
    int opApply(int delegate(ref long) dg) {
        int result;
        long a=0, b=1;
        while (a < max) {
            result = dg(b);
            if (result) break;
            a += b;
            result = dg(a);
            if (result) break;
            b += a;
        }
        return result;
    }
    int opApply(int delegate(ref int, ref long) dg) {
        int result, index;
        long a=0, b=1;
        while (a < max) {
            result = dg(index, b);
            if (result) break;
            index++;
            a += b;
            result = dg(index, a);
            if (result) break;
            b += a;
            index++;
        }
        return result;
    }
}
void main() {
    foreach (i, f; Xfibonacci(2_000))
        writeln(i, " ", f);
}



To avoid the code duplication I can define a generic Enumerate (with its helper
function 'enumerate'), very similar to the enumerate() present in Python for
the same purpose:


import std.stdio: writeln;
import std.traits: ReturnType;

struct Xfibonacci {
    long max;
    this(long inmax) { max = inmax; }
    int opApply(int delegate(ref long) dg) {
        int result;
        long a=0, b=1;
        while (a < max) {
            result = dg(b);
            if (result) break;
            a += b;
            result = dg(a);
            if (result) break;
            b += a;
        }
        return result;
    }
}

struct Enumerate(Iter) {
    Iter iterable;
    int index;
    alias ReturnType!(typeof({foreach(x; iterable) return x; assert(0); }))
ItemType;

    int opApply(int delegate(ref int, ref ItemType) dg) {
        int result;
        foreach (el; iterable) {
            result = dg(index, el);
            if (result) break;
            index++;
        }
        return result;
    }
}

Enumerate!Iter enumerate(Iter)(Iter iterable, int start=0) {
    return Enumerate!Iter(iterable, start);
}

void main() {
    foreach (i, f; enumerate(Xfibonacci(2_000)))
        writeln(i, " ", f);
}


This is not too much bad, but the Fibonacci numbers now come out of two
opApply, so the compiler fail in optimizing the code well.

So I propose the automatic generation of the indexed version:


import std.stdio: writeln;
struct Xfibonacci {
    long max;
    this(long inmax) { max = inmax; }
    int opApply(int delegate(ref long) dg) {
        int result;
        long a=0, b=1;
        while (a < max) {
            result = dg(b);
            if (result) break;
            a += b;
            result = dg(a);
            if (result) break;
            b += a;
        }
        return result;
    }
}
void main() {
    foreach (f; Xfibonacci(200)) // OK
        writeln(f);
    foreach (i, f; Xfibonacci(200)) // OK
        writeln(f);        
}


This can cause problems if Xfibonacci already contains an OpApply that yields
two or more items... To me it seems to lead to a messy situation... If you have
alternative solutions please tell me.

Bye,
bearophile
Apr 13 2010
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
bearophile Wrote:

 I have not written this as enhancement request on Bugzilla because while I
have a clear (small) problem, I think my possible solution is bad (see at the
bottom).
 

 To allow both the foreach version with and without index I have to duplicate
the body of the opApply, but this code duplication is bad:

No. This is how I do it in dcollections (for optional keys in map containers):
 import std.stdio: writeln;
 struct Xfibonacci {
     long max;
     this(long inmax) { max = inmax; }
     int opApply(int delegate(ref long) dg) {

return opApply(&_dg);
     }
     int opApply(int delegate(ref int, ref long) dg) {
         int result, index;
         long a=0, b=1;
         while (a < max) {
             result = dg(index, b);
             if (result) break;
             index++;
             a += b;
             result = dg(index, a);
             if (result) break;
             b += a;
             index++;
         }
         return result;
     }
 }

Don't forget, opApply is just a function, you can use it as such :)
Apr 13 2010
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 13 Apr 2010 06:13:37 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:

 Don't forget, opApply is just a function, you can use it as such :)

Oh, and don't forget to always make opApply take a scope delegate! Otherwise, it allocates the calling function's frame on the heap (in D2 at least). -Steve
Apr 13 2010