• BCS (30/30) Aug 12 2005 I am working on a function for mapping a tree to an array and back to a ...
• Ben Hinkle (27/63) Aug 12 2005 Forgive me for plugging MinTL here but it has two relevant features for
• Ben Hinkle (8/18) Aug 12 2005 Let add another comment. The array can be filled without any allocations...
• BCS (2/2) Aug 12 2005 Another thought, any way to make data.length += 10; work?
• Ben Hinkle (5/7) Aug 12 2005 I suppose since dynamic arrays are builtin they can be made to do anythi...

BCS <BCS_member pathlink.com> writes:

I am working on a function for mapping a tree to an array and back to a tree (I
need to move it across a network). The code looks something like this (there is
a bit of overhead omitted for clarity):

#class Tree











This is a nasty little bit of code requiring one or more dynamic allocation for
each node. Noticing this it occurred to me that it would be handy to have a
"extend" property for arrays that would only change the length of the array if
it is shorter than the given length. With this the function becomes:

#void map(inout int[] to, inout int bace)









This, with and a good guess at the length of the array at the start, means no
reallocations.

Any thoughts?

"Ben Hinkle" <ben.hinkle gmail.com> writes:

"BCS" <BCS_member pathlink.com> wrote in message 
news:ddih6i$nfm$1 digitaldaemon.com...
I am working on a function for mapping a tree to an array and back to a 
tree (I
 need to move it across a network). The code looks something like this 
 (there is
 a bit of overhead omitted for clarity):

 #class Tree











 This is a nasty little bit of code requiring one or more dynamic 
 allocation for
 each node. Noticing this it occurred to me that it would be handy to have 
 a
 "extend" property for arrays that would only change the length of the 
 array if
 it is shorter than the given length. With this the function becomes:

 #void map(inout int[] to, inout int bace)









 This, with and a good guess at the length of the array at the start, means 
 no
 reallocations.

 Any thoughts?

Forgive me for plugging MinTL here but it has two relevant features for 
this.

In MinTL equivalent to "extend" is "capacity" in an ArrayList. One would 
code your example in MinTL as
  void map(inout ArrayList!(int) to)
  {
    to ~= data;
    left.map(to);
    right.map(to);
  }
And the user can make a guess at the capacity before calling map():
  ArrayList!(int) list;
  list.capacity = 20; // guess at tree size
  to.map(list);
If your tree type has a foreach you can also just do
  foreach(int val; to) list ~= val;
instead of having a special map() function. A dynamic array slice of the 
ArrayList is obtained by using the "values" property. So if you guess the 
tree size correctly there is only one allocation in the entire process of 
obtaining the dyanmic array.

MinTL also contains a capacity function for regular dynamic array but it 
only applies to arrays with non-zero length due to the behavior that setting 
the array length to/from 0 wipes the data ptr (see numerous threads in the 
archives for this). Therefore I think the ArrayList is a more predictable 
and compiler-indepenent way of managing capacity. 

"Ben Hinkle" <bhinkle mathworks.com> writes:

 And the user can make a guess at the capacity before calling map():
  ArrayList!(int) list;
  list.capacity = 20; // guess at tree size
  to.map(list);
 If your tree type has a foreach you can also just do
  foreach(int val; to) list ~= val;
 instead of having a special map() function. A dynamic array slice of the 
 ArrayList is obtained by using the "values" property. So if you guess the 
 tree size correctly there is only one allocation in the entire process of 
 obtaining the dyanmic array.

Let add another comment. The array can be filled without any allocations by 
setting the ArrayList to refer to a static array like so
  ArrayList!(int) list;
  int[20] data;
  list.data = data;
  to.map(list);
The local variable "data" will now contain the flattened tree and if that 
wasn't enough space the list will automatically reallocate from the heap. 

BCS <BCS_member pathlink.com> writes:

Another thought, any way to make data.length += 10; work?
data.length = data.length + 10 just looks bad.

"Ben Hinkle" <bhinkle mathworks.com> writes:

"BCS" <BCS_member pathlink.com> wrote in message 
news:ddj1na$18aq$1 digitaldaemon.com...
 Another thought, any way to make data.length += 10; work?
 data.length = data.length + 10 just looks bad.

I suppose since dynamic arrays are builtin they can be made to do anything. 
For user types the fact that length is a property makes it hard to have += 
work seamlessly.