www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Duplicating multidimensional array

reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
Hello all,

I've been having some trouble trying to work out how to effectively duplicate a
multidimensional array in a way that preserves type qualifiers.

Now, obviously if we have a multidimensional array such as T[][] then calling
.dup will duplicate only the base array; so if we do something like,

      int[][] x = [[10, 0, 0, 0], [0, 10, 0, 0], [0, 0, 10, 0], [0, 0, 0, 10]];
      int[][] y = x.dup;

then y[i][j] will still be pointing to the same memory location as x[i][j].

We can write a "multidimensional duplication" function like this:

      T[][] multidup(T)(T[][] x)
      {
            T[][] tmp;
            foreach(row; x) {
                  tmp ~= row.dup;
            }
            return tmp;
      }

... which works for mutable T, but fails with const or immutable.

I had a go at implementing a version for const/immutable use:

      inout(T)[][] multidup(T)(T[][] x) inout
            if(!isMutable!T)
      {
            Unqual!T[][] tmp;
            foreach(row; x) {
                  tmp ~= row.dup;
            }
            return assumeUnique(tmp);
      }

... but this actually doesn't work for const (as assumeUnique only works with
immutable) and even with immutable input falls over:

dupmatrix.d(20): Error: cannot implicitly convert expression (assumeUnique(tmp))
of type immutable(int[])[] to const(int)[][]
dupmatrix.d(26): Error: template instance dupmatrix.multidup!(const(int)) error
instantiating
dupmatrix.d(26): Error: multidup (const(int)[][] x) is not callable using
argument types (const(int[][]))
/opt/ldc/include/d/std/range.d(611): Error: static assert  "Cannot put a char[]
into a Appender!(string)"
    instantiatied in /opt/ldc/include/d/std/format.d(1439):
put!(Appender!(string), char[])
    instantiatied in /opt/ldc/include/d/std/format.d(1341):
formatUnsigned!(Appender!(string), char)
    instantiatied in /opt/ldc/include/d/std/format.d(1315):
formatIntegral!(Appender!(string), ulong, char)
    ... (12 instantiations, -v to show) ...
    instantiatied in /opt/ldc/include/d/std/stdio.d(822):
formattedWrite!(LockingTextWriter, char, const(int[])[])
    instantiatied in /opt/ldc/include/d/std/stdio.d(1707):
write!(string,const(int[])[],char)
    instantiatied in dupmatrix.d(28): writeln!(string,const(int[])[])
joseph wakeling:~/code/test/D$ vi dupmatrix.d
joseph wakeling:~/code/test/D$ ldmd2 dupmatrix.d
dupmatrix.d(20): Error: cannot implicitly convert expression (assumeUnique(tmp))
of type immutable(int[])[] to immutable(int)[][]
dupmatrix.d(26): Error: template instance dupmatrix.multidup!(immutable(int))
error instantiating
dupmatrix.d(26): Error: multidup (immutable(int)[][] x) is not callable using
argument types (immutable(int[][]))
/opt/ldc/include/d/std/range.d(611): Error: static assert  "Cannot put a char[]
into a Appender!(string)"
    instantiatied in /opt/ldc/include/d/std/format.d(1439):
put!(Appender!(string), char[])
    instantiatied in /opt/ldc/include/d/std/format.d(1341):
formatUnsigned!(Appender!(string), char)
    instantiatied in /opt/ldc/include/d/std/format.d(1315):
formatIntegral!(Appender!(string), ulong, char)
    ... (12 instantiations, -v to show) ...
    instantiatied in /opt/ldc/include/d/std/stdio.d(822):
formattedWrite!(LockingTextWriter, char, immutable(int[])[])
    instantiatied in /opt/ldc/include/d/std/stdio.d(1707):
write!(string,immutable(int[])[],char)
    instantiatied in dupmatrix.d(28): writeln!(string,immutable(int[])[])

... at which point I feel that I really don't understand the type (and type
conversion) system well enough to proceed without advice :-(

Complete code attached.  Ideally I'd really like to have a solution that would
recursively extend to multidimensional arrays of _any_ dimension, just because I
guess that would be generally useful to everyone.

It strikes me that as the copy is scoped, I might be able to just do a cast from
Unqual!T[][] to T[][] safely, but it doesn't feel good to do so.

I remember Dan Davidson had some code for a "generic dup" function for structs
[1] that might be relevant here (and might already provide a general solution
for multidimensional arrays), but I thought I'd ask if anyone else has any
ideas.

[1]
http://www.digitalmars.com/d/archives/digitalmars/D/proposal_for_general_dup_function_182985.html
May 29 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/29/2013 10:22 AM, Joseph Rushton Wakeling wrote:


 I've been having some trouble trying to work out how to effectively
 duplicate a multidimensional array in a way that preserves type 


qualifiers.

Templates preserve type qualifiers. So, as long as the return type is 
the same as the parameter type, then the type qualifiers should be 
preserved:

T foo(T)(T x)
{
     // ...
}


     immutable int[][] x = [[10, 0, 0, 0],
                            [0, 10, 0, 0],
                            [0, 0, 10, 0],
                            [0, 0, 0, 10]];
     int[][] y = multidup(x);


As long as it is a conversion, std.conv.to handles that case for you:

import std.conv;
// ...
	int[][] y = x.to!(int[][]);

Done! :)

Unfortunately, std.conv.to is not a general copy tool. It does not do 
anything when converting to the same type. In other words, when the 
target type is the same as the source type it is a no-op, not a copy.

What do you think about the following recursive template solution? I 
have tested it only with arrays of int. :/

import std.stdio;
import std.traits;
import std.conv;

// This is for one-dimensional arrays
T multidup(T : E[], E)(T arr)
     if (!isArray!E)
{
     T result;

     static if (is (E == immutable)) {
         // No need to copy immutable elements
         result = arr;

     } else {
         // Otherwise, we must make a copy
         result = arr.dup;
     }

     return result;
}

// This is for array of array types
T multidup(T : E[], E)(T arr)
     if(isArray!E)
{
     T result;

     static if (is (E == immutable)) {
         // No need to go deeper than an immutable layer
         result == arr;

     } else {
         foreach(row; arr) {
             result ~= multidup(row);
         }
     }

     return result;
}

unittest
{
     {
         int[] a = [ 1, 2, 3 ];
         auto b = multidup(a);
         assert(typeid(b) is typeid(a));
         assert(a == b);
     }

     {
         immutable(int[]) a = [ 1, 2 ];
         auto b = multidup(a);
         assert(typeid(b) == typeid(immutable(int)[]));
         assert(a == b);
         assert(a.ptr == b.ptr);
     }

     {
         immutable(int)[] a = [ 1, 2, 3 ];
         auto b = multidup(a);
         assert(typeid(b) == typeid(a));
         assert(a == b);
         assert(a.ptr == b.ptr);
         // assert(a[0].ptr == b[0].ptr);
     }

     {
         immutable(int)[][] a = [ [ 1, 2, 3 ],
                                  [ 4, 5, 6 ],
                                  [ 7, 8, 9 ] ];
         auto b = multidup(a);
         assert(typeid(b) == typeid(a));
         assert(a == b);
         assert(a.ptr != b.ptr);
         foreach (i; 0 .. a.length) {
             assert(a[i].ptr == b[i].ptr);
         }
     }

     {
         alias Elem = const(int[])[];
         const(int[])[][]a = [ [ [ 1, 2, 3 ],
                                 [ 4, 5, 6 ],
                                 [ 7, 8, 9 ] ],

                               [ [ 1, 2, 3 ],
                                 [ 4, 5, 6 ],
                                 [ 7, 8, 9 ] ] ];

         auto b = multidup(a);
         assert(typeid(b) == typeid(a));
         assert(a == b);
         assert(a.ptr != b.ptr);
         foreach (i; 0 .. a.length) {
             assert(a[i].ptr != b[i].ptr);
         }
     }
}

void main()
{}

Is it usable in your situation?

Ali
May 30 2013
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 05/30/2013 09:36 AM, Ali Çehreli wrote:

 What do you think about the following recursive template solution? I have
tested
 it only with arrays of int. :/


Very impressed -- I would never have thought of that trick with the second
template parameter.  It's really nice to see these kinds of example, as it's
starting to bring to life the concepts of generic programming _as programming_,
not just simple templating of functions or classes.

I tried out the code with double-arrays of tuples, which is my use-case and
which works.  I guess it might fall over with complex structs or classes,
though. :-\

What do you reckon the impact of this will be performance-wise?  I'll try it out
of course, but what with all the array concatenations etc. I'm worried about
whether it might leak memory if repeated many times, and whether there might be
some other better way to copy all the values from one multidimensional array to
another.
May 30 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/30/2013 03:02 PM, Joseph Rushton Wakeling wrote:


 I would never have thought of that trick with the second template 


parameter.

Phobos is a source of ideas. ;)


 I guess it might fall over with complex structs or classes, though. :-\


Copying structs is trivial because they already have copy semantics:

     T b = a;  // b is a copy of a

However, that depends on correctly implemented copy semantics on T.

For classes, there is no syntax for copying. The type may have annotated 
a member function that it is the duplication function or we may know by 
convention that dup() is the equivalent of array .dup.


 What do you reckon the impact of this will be performance-wise?


As long there is no extra copy generated during the process, it should 
be fine. However, the usual issues around the current conservative GC 
applies. :/

Ali
May 30 2013
next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 05/31/2013 01:48 AM, Ali Çehreli wrote:

 Copying structs is trivial because they already have copy semantics:
 
     T b = a;  // b is a copy of a
 
 However, that depends on correctly implemented copy semantics on T.


By "complex structs" I meant things like structs containing arrays -- a regular
copy would just copy the reference and not duplicate the arrays.


 As long there is no extra copy generated during the process, it should be fine.
 However, the usual issues around the current conservative GC applies. :/


I'll get back to you on that one when I have results ... :-)
May 30 2013
prev sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/30/2013 04:48 PM, Ali Çehreli wrote:


 For classes, there is no syntax for copying. The type may have annotated
 a member function that it is the duplication function or we may know by
 convention that dup() is the equivalent of array .dup.


Kenji Hara responded to another thread on the main D newsgroup. 
Apparently, such a convention-based functionality is already being used 
by std.conv.to. Here is the excerpt:

On 05/30/2013 07:13 PM, Kenji Hara wrote:


 Current D does not provide generic way for deep copy of class object.
 But, you can use std.conv.to with adding a kind of copy constructor.

 class C
 {
      int x;
      this(int n) { x = n; }

      // Do deep copy, this is used by to!(array-type)(array)
      this(const C c) { this.x = c.x; }
 }
 void main()
 {
      const(C)[] carr = [new C(1), new C(2)];
      // C[] marr = carr.dup;
      // --> Error: cannot implicitly convert element type const(C) to
 mutable in carr.dup

      import std.conv;
      C[] marr = carr.to!(C[]);
      // For class arrays which need copy elements,
      // std.conv.to returns [new C(carr[0]), new C(carr[1]), ...]

      // modify element of returned array
      marr[0].x = 5;

      // Right now carr[0] and marr[0] are completely unrelated objects
      assert(carr[0].x == 1);
      assert(marr[0].x == 5);
 }

 Kenji Hara


Ali
May 30 2013