Simple IFTI use

[Kevin Bealer]

In article <e0qcfd$24m3$1 at digitaldaemon.com>, Sean Kelly says...
>
>Kevin Bealer wrote:
>> Often when working with D arrays, I miss the "doubling" effect of push_back from
>> C++ std::vector.  With IFTI, this is possible (trivial, really) in D.  I put
>> some code here - the idea is to use existing arrays, no special classes, but
>> have an "append" functionality, like vector::push_back().
>> 
>> : // -*- c++ -*-
>> :
>> : import std.string;
>> :
>> : template push_back(T) {
>> :     // The first arg is inout only for performance reasons.
>> :
>> :     void push_back(inout T elem, inout T[] vec, inout int vsize)
>> :     {
>> :         assert(vec.length >= vsize);
>> :
>> :         if (vec.length != vsize) {
>> :             vec.length = (vec.length
>> :                           ? vec.length * 2
>> :                           : 4); // arbitrary
>> :         }
>> :
>> :         vec[vsize++] = elem;
>> :     }
>> : };
>> :
>> : // Usage
>> :
>> : import simplevec;
>> :
>> : Foo[] stuff; int stuff_size;
>> :
>> : Foo f = new Foo;
>> :
>> : push_back(f, stuff, stuff_size);
>
>If you flip the parameters:
>
>void push_back( inout T[] vec, T elem )
>
>The array trick could be used to call it like so:
>
>f.push_back( stuff );
>
>This would obviously also require an overload that doesn't take a third 
>parameter.
>
>Sean

There is a related definition that I've used that does not require a seperate
length primitive... it looks like this (I've flipped the args too):

:     void push_back(inout T[] vec, inout T elem)
:     {
:         int vsize = vec.length;
:
:         if (! (vsize & (vsize-1))) {
:             vec.length = vsize * 2;
:         }
:         vec.length = vsize+1;
:         vec[$-1] = elem;
:     }

The (vsize & (vsize-1)) tests for powers of two, so this doubles the capacity of
the array whenever length is 2, 4, 8, etc, and an element is added.  The length
is then reduced back to one more than the previous length.  The rest of the time
it just bumps .length by 1, which won't reallocate since the capacity has been
previously bumped.

The only hitch is, if you start with an array of length 70, this version can't
tell and will not do the capacity trick till you get to 128.  This won't matter
though if you use this template for all of the operations.

Kevin