www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - "extend" property for arrays

reply 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
#{
#	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?
Aug 12 2005
parent reply "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
 #{
 # 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.
Aug 12 2005
parent reply "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.
Aug 12 2005
parent reply BCS <BCS_member pathlink.com> writes:
Another thought, any way to make data.length += 10; work?
data.length = data.length + 10 just looks bad.
Aug 12 2005
parent "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.
Aug 12 2005