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
#{
#	int[] map()
#	{
#		return data ~ left.map ~ right.map;
#	}
#
#	int data;
#	Tree left;
#	Tree right;
#}

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)
#{
#	bace += 1;
#	to.extend(bace);
#
#	to[base-1] = to;
#	left.map(to,base);
#	right.map(to,base);
#}

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

Any thoughts?

"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
> #{
> # int[] map()
> # {
> # return data ~ left.map ~ right.map;
> # }
> #
> # int data;
> # Tree left;
> # Tree right;
> #}
>
> 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)
> #{
> # bace += 1;
> # to.extend(bace);
> #
> # to[base-1] = to;
> # left.map(to,base);
> # right.map(to,base);
> #}
>
> 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.

> 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.

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

"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.