Entry tags:

d language, programming

xflatten, flatten in D
In the last versions of my D language libs I have re-written maybe for the 4-th time the function and the iterator to flatten a given iterable in an eager/lazy way, and this time I think the code may be as flexible and fast as it gets.

Here I show only a summary of the code relative to the xflatten, that's more interesting. I have removed some checks and extra capabilities, so for the full version take a look into the source code itself (func.d module):
http://www.fantascienza.net/leonardo/so/libs_d.zip

The Xflatten (there's an helper function template xflatten that I don't show here), given a n-dimensional iterable, yields the bottom level items. So for example:

xflatten([1.1, 2.1, 3.1]) ==> 1.1 2.1 3.1
xflatten([[[1, 2], [3]], [[4], [5, 6]]]) ==> 1 2 3 4 5 6
xflatten([xrange(2), xrange(3)]) ==> 0 1 0 1 2

The summarized code is very short:

class Xflatten(TyItems) {
    this(TyItems items) {
        this.items = items;
    }

    int opApply(int delegate(ref BaseType!(TyItems)) dg) {
        int result;
        mixin(XflattenHelper!("items", "result = dg(", "); if (result) goto END;",
                              IterableLevels!(typeof(items))));
        END:
        return result;
    }
}

XflattenHelper!() is a template that computes a string at compile time, the mixin in D is similar to C macros, it allows to mix-in the string in place, as normal code that will be compiled.

XflattenHelper takes as input the name of an iterable, two parts of a string that contains the instructions to perform on the leaves of the iterable, and the number of levels of the iterable. This number is computed at compile time by another template, IterableLevels. The XflattenHelper code is:

template XflattenHelper(string iterable, string yield_p1, string yield_p2, int level) {
    static if (level == 0) {
        const string XflattenHelper = "{ " ~ yield_p1 ~ iterable ~ yield_p2 ~ " }";
    } else {
        const string XflattenHelper = "foreach(" ~ iterable ~ "_x; " ~ iterable ~ ")\n" ~
                                      XflattenHelper!(iterable ~ "_x", yield_p1, yield_p2, level-1);
    }
}

So given an iterable like this, that's an array of lazy iterables that yield integers:
[xrange(2), xrange(3)]
Then at compile time XflattenHelper produces code like:

foreach(items_x; items)
foreach(items_x_x; items_x)
{ result = dg(items_x_x); if (result) goto END; }

That's the general and faster way to iterate on the leaves and yield them from the opApply (opApply is the iteration protocol in D).

IterableLevels too is short, but it uses more complex templates:
template IterableLevels(TyIter) {
    static if (IsIterable!(TyIter))
        const int IterableLevels = 1 + IterableLevels!(BaseType1!(TyIter));
    else
        const int IterableLevels = 0;
}

Where IsIterable!() is a template that becomes true at compile time if TyIter is the type of something that can be iterated, like an array, a lazy generator class/struct, etc. BaseType1!() allows to "go down one level", and it works with most kind of iterables. For the full code of such tree of templates you can see into the templates.d module of the libs.