www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Struct Flattening

reply dsimcha <dsimcha yahoo.com> writes:
I'm working on porting dstats to ranges and I've run across an interesting
problem.  I've defined a range that I'm going to use for joint entropy, etc.
It's basically a tuple with some special properties.  Let's say I have a
template struct:

struct Joint(T...) {
   T ranges;
}

It's built with:

SomeType joint(T...)(T args) { // do stuff. }

When one of the arguments is a Joint, I want it to flatten.  For example,

Joint!(uint[], uint[]) r1;
uint[] r2;
auto result = joint(r1, r2);
// result is a Joint!(uint[], uint[], uint[]), not a
// Joint!(Joint!(uint[], uint[]), uint[]).

Is there an easy metaprogramming trick that I've overlooked to make stuff
flatten like this?
Apr 21 2009
next sibling parent reply Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Wed, Apr 22, 2009 at 12:42 AM, dsimcha <dsimcha yahoo.com> wrote:

 I'm working on porting dstats to ranges and I've run across an interestin=


g

 problem. =A0I've defined a range that I'm going to use for joint entropy,=


 etc.

 It's basically a tuple with some special properties. =A0Let's say I have =


a

 template struct:

 struct Joint(T...) {
 =A0 T ranges;
 }

 It's built with:

 SomeType joint(T...)(T args) { // do stuff. }

 When one of the arguments is a Joint, I want it to flatten. =A0For exampl=


e,

 Joint!(uint[], uint[]) r1;
 uint[] r2;
 auto result =3D joint(r1, r2);
 // result is a Joint!(uint[], uint[], uint[]), not a
 // Joint!(Joint!(uint[], uint[]), uint[]).

 Is there an easy metaprogramming trick that I've overlooked to make stuff
 flatten like this?


So before reading the following solution, don't get your hopes up too
much.  There's a compiler bug that prevents it from working.

template Tuple(T...)
{
	alias T Tuple;
}

template FlattenJoint(T : Joint!(U), U...)
{
	alias FlatJoint!(U) FlattenJoint;
}

template FlattenJoint(T)
{
	alias T FlattenJoint;
}

template FlatJoint(T...)
{
	static if(T.length =3D=3D 0)
		alias Tuple!() FlatJoint;
	else
		alias Tuple!(FlattenJoint!(T[0]), FlatJoint!(T[1 .. $])) FlatJoint;
}

struct Joint(T...)
{
	FlatJoint!(T) ranges;
}

void main()
{
	Joint!(uint[], uint[]) r1;
	Joint!(Joint!(uint[], uint[]), uint[]) r2;

	pragma(msg, typeof(r1.ranges).stringof);
	pragma(msg, typeof(r2.ranges).stringof);
}

This will print out:

(uint[], uint[])
(uint[])

The second line really should be (uint[], uint[], uint[]), but there's
something wrong with the way DMD matches the FlattenJoint template.  I
was surprised, it does actually select the correct
specialization(FlattenJoint(T : Joint!(U), U...), but for some reason,
U is the empty tuple, even though T is Joint!(uint[], uint[]).

I think it might have something to do with this bug (D2 is()
expression, but a very similar mechanism and result):
http://d.puremagic.com/issues/show_bug.cgi?id=3D1944
Apr 21 2009
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Jarrett Billingsley (jarrett.billingsley gmail.com)'s article

 On Wed, Apr 22, 2009 at 12:42 AM, dsimcha <dsimcha yahoo.com> wrote:

 I'm working on porting dstats to ranges and I've run across an interestin


 g

 problem. I've defined a range that I'm going to use for joint entropy,


  etc.

 It's basically a tuple with some special properties. Let's say I have


 a

 template struct:

 struct Joint(T...) {
  T ranges;
 }

 It's built with:

 SomeType joint(T...)(T args) { // do stuff. }

 When one of the arguments is a Joint, I want it to flatten. For exampl


 e,

 Joint!(uint[], uint[]) r1;
 uint[] r2;
 auto result = joint(r1, r2);
 // result is a Joint!(uint[], uint[], uint[]), not a
 // Joint!(Joint!(uint[], uint[]), uint[]).

 Is there an easy metaprogramming trick that I've overlooked to make stuff
 flatten like this?


 So before reading the following solution, don't get your hopes up too
 much.  There's a compiler bug that prevents it from working.
 template Tuple(T...)
 {
 	alias T Tuple;
 }
 template FlattenJoint(T : Joint!(U), U...)
 {
 	alias FlatJoint!(U) FlattenJoint;
 }
 template FlattenJoint(T)
 {
 	alias T FlattenJoint;
 }
 template FlatJoint(T...)
 {
 	static if(T.length == 0)
 		alias Tuple!() FlatJoint;
 	else
 		alias Tuple!(FlattenJoint!(T[0]), FlatJoint!(T[1 .. $])) FlatJoint;
 }
 struct Joint(T...)
 {
 	FlatJoint!(T) ranges;
 }
 void main()
 {
 	Joint!(uint[], uint[]) r1;
 	Joint!(Joint!(uint[], uint[]), uint[]) r2;
 	pragma(msg, typeof(r1.ranges).stringof);
 	pragma(msg, typeof(r2.ranges).stringof);
 }
 This will print out:
 (uint[], uint[])
 (uint[])
 The second line really should be (uint[], uint[], uint[]), but there's
 something wrong with the way DMD matches the FlattenJoint template.  I
 was surprised, it does actually select the correct
 specialization(FlattenJoint(T : Joint!(U), U...), but for some reason,
 U is the empty tuple, even though T is Joint!(uint[], uint[]).
 I think it might have something to do with this bug (D2 is()
 expression, but a very similar mechanism and result):
 http://d.puremagic.com/issues/show_bug.cgi?id=1944


I guess I should clarify:  Getting the flattened type tuple is the easy part. 
He
hard part is getting the flattened parameter tuple, i.e. how do I copy all the
data over to the new Joint!(uint[], uint[], uint[]) struct in a generic way?
Apr 22 2009
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
dsimcha:

 I guess I should clarify:  Getting the flattened type tuple is the easy part. 
He
 hard part is getting the flattened parameter tuple, i.e. how do I copy all the
 data over to the new Joint!(uint[], uint[], uint[]) struct in a generic way?


On D1 I did solve such problem, take a look at the Xchain class into the func.d
module in my dlibs:
http://www.fantascienza.net/leonardo/so/libs_d.zip
xchain(xchain(s1, s2), s3) === xchain(s1, s2, s3)

Better still is to use the Xchainable class mixin, that gives better syntax:
s1 ~ s2 ~ s3  === xchain(xchain(s1, s2), s3) === xchain(s1, s2, s3)

Bye,
bearophile
Apr 22 2009
prev sibling parent reply Max Samukha <samukha voliacable.com.removethis> writes:
On Wed, 22 Apr 2009 13:45:16 +0000 (UTC), dsimcha <dsimcha yahoo.com>
wrote:


== Quote from Jarrett Billingsley (jarrett.billingsley gmail.com)'s article

 On Wed, Apr 22, 2009 at 12:42 AM, dsimcha <dsimcha yahoo.com> wrote:

 I'm working on porting dstats to ranges and I've run across an interestin


 g

 problem. I've defined a range that I'm going to use for joint entropy,


  etc.

 It's basically a tuple with some special properties. Let's say I have


 a

 template struct:

 struct Joint(T...) {
  T ranges;
 }

 It's built with:

 SomeType joint(T...)(T args) { // do stuff. }

 When one of the arguments is a Joint, I want it to flatten. For exampl


 e,

 Joint!(uint[], uint[]) r1;
 uint[] r2;
 auto result = joint(r1, r2);
 // result is a Joint!(uint[], uint[], uint[]), not a
 // Joint!(Joint!(uint[], uint[]), uint[]).

 Is there an easy metaprogramming trick that I've overlooked to make stuff
 flatten like this?


 So before reading the following solution, don't get your hopes up too
 much.  There's a compiler bug that prevents it from working.
 template Tuple(T...)
 {
 	alias T Tuple;
 }
 template FlattenJoint(T : Joint!(U), U...)
 {
 	alias FlatJoint!(U) FlattenJoint;
 }
 template FlattenJoint(T)
 {
 	alias T FlattenJoint;
 }
 template FlatJoint(T...)
 {
 	static if(T.length == 0)
 		alias Tuple!() FlatJoint;
 	else
 		alias Tuple!(FlattenJoint!(T[0]), FlatJoint!(T[1 .. $])) FlatJoint;
 }
 struct Joint(T...)
 {
 	FlatJoint!(T) ranges;
 }
 void main()
 {
 	Joint!(uint[], uint[]) r1;
 	Joint!(Joint!(uint[], uint[]), uint[]) r2;
 	pragma(msg, typeof(r1.ranges).stringof);
 	pragma(msg, typeof(r2.ranges).stringof);
 }
 This will print out:
 (uint[], uint[])
 (uint[])
 The second line really should be (uint[], uint[], uint[]), but there's
 something wrong with the way DMD matches the FlattenJoint template.  I
 was surprised, it does actually select the correct
 specialization(FlattenJoint(T : Joint!(U), U...), but for some reason,
 U is the empty tuple, even though T is Joint!(uint[], uint[]).
 I think it might have something to do with this bug (D2 is()
 expression, but a very similar mechanism and result):
 http://d.puremagic.com/issues/show_bug.cgi?id=1944


I guess I should clarify:  Getting the flattened type tuple is the easy part. 
He
hard part is getting the flattened parameter tuple, i.e. how do I copy all the
data over to the new Joint!(uint[], uint[], uint[]) struct in a generic way?


You could do it like this:

struct Joint(T...)
{
    T ranges;
}

template isJoint(T)
{
    enum isJoint = is(typeof(T.ranges)); // or whatever means you
choose to identify a Joint
}

template JointRetType(T...)
{
    static if (T.length)
    {
        static if (isJoint!(T[0]))
            alias Joint!(typeof(T[0].ranges),
typeof(JointRetType!(T[1..$]).ranges)) JointRetType;
        else
            alias Joint!(T[0], typeof(JointRetType!(T[1..$]).ranges))
JointRetType;
    }
    else
        alias Joint!() JointRetType;
}

private /+ auto +/ Joint!(T) flatJoint(T...)(T args)
{
    return Joint!(T)(args);
}

/+ auto +/ JointRetType!(T) joint(T...)(T args)
{
    static if (T.length)
    {
        static if (is(typeof(T[0].ranges)))
            return flatJoint(args[0].ranges,
joint(args[1..$]).ranges);
        else
            return flatJoint(args[0], joint(args[1..$]).ranges);
    }
    else
        return Joint!()();
}

void main()
{

    Joint!(uint[], uint[]) r1;
    uint[] r2;
    auto result = joint(r1, r2);
    static assert(is(typeof(result) == Joint!(uint[], uint[],
uint[])));
}

Could be optimized to eliminate excessive copying. JointRetType is
necessary because you can't use 'auto'
(http://d.puremagic.com/issues/show_bug.cgi?id=2863)
Apr 23 2009
parent Max Samukha <samukha voliacable.com.removethis> writes:
On Thu, 23 Apr 2009 10:45:01 +0200, Max Samukha
<samukha voliacable.com.removethis> wrote:


You could do it like this:

struct Joint(T...)
{
    T ranges;
}

template isJoint(T)
{
    enum isJoint = is(typeof(T.ranges)); // or whatever means you
choose to identify a Joint
}

template JointRetType(T...)
{
    static if (T.length)
    {
        static if (isJoint!(T[0]))
            alias Joint!(typeof(T[0].ranges),
typeof(JointRetType!(T[1..$]).ranges)) JointRetType;
        else
            alias Joint!(T[0], typeof(JointRetType!(T[1..$]).ranges))
JointRetType;
    }
    else
        alias Joint!() JointRetType;
}

private /+ auto +/ Joint!(T) flatJoint(T...)(T args)
{
    return Joint!(T)(args);
}

/+ auto +/ JointRetType!(T) joint(T...)(T args)
{
    static if (T.length)
    {
        static if (is(typeof(T[0].ranges)))
            return flatJoint(args[0].ranges,
joint(args[1..$]).ranges);
        else
            return flatJoint(args[0], joint(args[1..$]).ranges);
    }
    else
        return Joint!()();
}

void main()
{

    Joint!(uint[], uint[]) r1;
    uint[] r2;
    auto result = joint(r1, r2);
    static assert(is(typeof(result) == Joint!(uint[], uint[],
uint[])));
}

Could be optimized to eliminate excessive copying. JointRetType is
necessary because you can't use 'auto'
(http://d.puremagic.com/issues/show_bug.cgi?id=2863)


Without recursive calls:

template StaticTuple(T...)
{
    alias T StaticTuple;
}

struct Joint(T...)
{
    T ranges;
}

template isJoint(T)
{
    enum isJoint = is(typeof(T.ranges)); // or whatever means you
choose to identify a Joint
}

private template JointArgs(T...)
{
    static if (T.length)
    {
        static if (isJoint!(T[0]))
            alias StaticTuple!(typeof(T[0].ranges),
JointArgs!(T[1..$])) JointArgs;
        else
            alias StaticTuple!(T[0], JointArgs!(T[1..$])) JointArgs;
    }
    else
        alias StaticTuple!() JointArgs;
}

private template targetIndexes(size_t index, T...)
{
    static if (T.length)
    {
        static if (isJoint!(T[0]))
            alias StaticTuple!(index, targetIndexes!(index +
typeof(T[0].ranges).length, T[1..$])) targetIndexes;
        else
            alias StaticTuple!(index, targetIndexes!(index + 1,
T[1..$])) targetIndexes;
    }
    else
        alias StaticTuple!() targetIndexes;

}

Joint!(JointArgs!(T)) joint(T...)(T args)
{
    typeof(return) ret;

    foreach (i, _i; T)
    {
        enum targetIndex = targetIndexes!(0, T)[i];
        static if (isJoint!(T[i]))
        {
            foreach (j, _j; typeof(T[i].ranges))
                ret.ranges[targetIndex + j] = args[i].ranges[j];
        }
        else
            ret.ranges[targetIndex] = args[i];
    }

    return ret;
}

void main()
{

    auto r1 = Joint!(uint[], uint[])([1, 2], [3, 4]);
    uint[] r2 = [5, 6];
    auto result = joint(r1, r2);
    static assert(is(typeof(result) == Joint!(uint[], uint[],
uint[])));
    assert (result.ranges[0] == [1u, 2][]);
    assert (result.ranges[1] == [3u, 4][]);
    assert (result.ranges[2] == [5u, 6][]);
}
Apr 23 2009
prev sibling next sibling parent reply Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Wed, Apr 22, 2009 at 1:36 AM, Jarrett Billingsley
<jarrett.billingsley gmail.com> wrote:

 template FlattenJoint(T : Joint!(U), U...)
 {
 =A0 =A0 =A0 =A0alias FlatJoint!(U) FlattenJoint;
 }


Ah, I just thought of this!

template FlattenJoint(T : Joint!(U), U...)
{
	alias FlatJoint!(typeof(T.ranges)) FlattenJoint;
}

A bit less elegant, but it actually works.
Apr 21 2009
parent tama <repeatedly gmail.com> writes:
On Wed, 22 Apr 2009 14:42:34 +0900, Jarrett Billingsley  
<jarrett.billingsley gmail.com> wrote:


 On Wed, Apr 22, 2009 at 1:36 AM, Jarrett Billingsley
 <jarrett.billingsley gmail.com> wrote:

 template FlattenJoint(T : Joint!(U), U...)
 {
        alias FlatJoint!(U) FlattenJoint;
 }


 Ah, I just thought of this!

 template FlattenJoint(T : Joint!(U), U...)
 {
 	alias FlatJoint!(typeof(T.ranges)) FlattenJoint;
 }


template FlattenJoint(T : Joint!(U), U...)
{
	alias typeof(T.tupleof) FlattenJoint;
}

How about this?

-- 
tama <repeatedly gmail.com>
http://profile.livedoor.com/repeatedly/
メンバー募集中
http://tpf.techtalk.jp/
Apr 21 2009
prev sibling next sibling parent reply tama <repeatedly gmail.com> writes:
On Wed, 22 Apr 2009 13:42:27 +0900, dsimcha <dsimcha yahoo.com> wrote:


 It's basically a tuple with some special properties.  Let's say I have a
 template struct:

 struct Joint(T...) {
    T ranges;
 }

 It's built with:

 SomeType joint(T...)(T args) { // do stuff. }

 When one of the arguments is a Joint, I want it to flatten.  For example,

 Joint!(uint[], uint[]) r1;
 uint[] r2;
 auto result = joint(r1, r2);
 // result is a Joint!(uint[], uint[], uint[]), not a
 // Joint!(Joint!(uint[], uint[]), uint[]).

 Is there an easy metaprogramming trick that I've overlooked to make stuff
 flatten like this?


Hi,

---
import std.stdio, std.typetuple, std.traits;

struct Joint(T...)
{
     T ranges;
}

template flatten(T...)
{
     static if (T.length == 0)
         alias T flatten;
     else
         alias TypeTuple!(FieldTypeTuple!(T[0]), flatten!(T[1..$])) flatten;
}

Joint!(flatten!(T)) joint(T...)(T args)
{
     typeof(return) result;
     return result;
}

void main()
{

     Joint!(uint[], uint[]) r1;
     uint[] r2;
     auto result = joint(r1, r2);
     writeln(result);
}
---

Tested dmd 2.029 on Windows XP.

-- 
tama <repeatedly gmail.com>
http://profile.livedoor.com/repeatedly/
$B%a%s%P!<Jg=8Cf(B
http://tpf.techtalk.jp/
Apr 21 2009
next sibling parent tama <repeatedly gmail.com> writes:
On Wed, 22 Apr 2009 14:50:58 +0900, tama <repeatedly gmail.com> wrote:


 On Wed, 22 Apr 2009 13:42:27 +0900, dsimcha <dsimcha yahoo.com> wrote:


 It's basically a tuple with some special properties.  Let's say I have a
 template struct:

 struct Joint(T...) {
    T ranges;
 }

 It's built with:

 SomeType joint(T...)(T args) { // do stuff. }

 When one of the arguments is a Joint, I want it to flatten.  For  
 example,




Sorry, I overlooked this line:'(


-- 
tama <repeatedly gmail.com>
http://profile.livedoor.com/repeatedly/
$B%a%s%P!<Jg=8Cf(B
http://tpf.techtalk.jp/
Apr 21 2009
prev sibling parent tama <repeatedly gmail.com> writes:
On Wed, 22 Apr 2009 14:50:58 +0900, tama <repeatedly gmail.com> wrote:


 template flatten(T...)
 {
      static if (T.length == 0)
          alias T flatten;
      else
          alias TypeTuple!(FieldTypeTuple!(T[0]), flatten!(T[1..$]))  
 flatten;
 }


Fixed:

---
template flatten(T...)
{
     static if (T.length == 0)
         alias T flatten;
     else
         static if (is(T[0] == struct) && is(T[0] ==  
Joint!(typeof(T[0].tupleof))))
             alias TypeTuple!(typeof(T[0].tupleof), flatten!(T[1..$]))  
flatten;
         else
              alias TypeTuple!(T[0], flatten!(T[1..$])) flatten;
}
---

But look horrible.

-- 
tama <repeatedly gmail.com>
http://profile.livedoor.com/repeatedly/
$B%a%s%P!<Jg=8Cf(B
http://tpf.techtalk.jp/
Apr 22 2009
prev sibling parent GC <const.ref gmail.com> writes:
dsimcha Wrote:


 I'm working on porting dstats to ranges and I've run across an interesting
 problem.  I've defined a range that I'm going to use for joint entropy, etc.
 It's basically a tuple with some special properties.  Let's say I have a
 template struct:
 
 struct Joint(T...) {
    T ranges;
 }
 
 It's built with:
 
 SomeType joint(T...)(T args) { // do stuff. }
 
 When one of the arguments is a Joint, I want it to flatten.  For example,
 
 Joint!(uint[], uint[]) r1;
 uint[] r2;
 auto result = joint(r1, r2);
 // result is a Joint!(uint[], uint[], uint[]), not a
 // Joint!(Joint!(uint[], uint[]), uint[]).
 
 Is there an easy metaprogramming trick that I've overlooked to make stuff
 flatten like this?


As a variant:

template jFlate(T...)
{
    static if(T.length == 0)
        alias Tuple!() jFlate;
    else
        static if( is( typeof( T[0].range ) ) )
            alias Tuple!(jFlate!(typeof(T[0].range)), jFlate!(T[ 1 .. $ ]) )
jFlate; // typeof(T[0].range) or jFlate!(typeof(T[0].range)) if you need
Joint!(Joint!(uint[], Joint![uint])).range as  (uint[], uint[])
        else
            alias Tuple!(T[0], jFlate!(T[ 1 .. $ ]) ) jFlate;
}

Joint!(jFlate!(T)) joint(T...)(T args)
{
    return Joint!(jFlate!(T))();
}
Apr 23 2009