In D is there away to insert a element into a byte array.

Thanks,

JamesG

"JamesG" <JamesG_member@pathlink.com> wrote in message news:blk61e$212$1@digitaldaemon.com...
> In D is there away to insert a element into a byte array.

Increase the length of an array by one. Then, write a loop to ripple up all the elements above the insertion point, and then insert the new element.

JamesG wrote:
> In D is there away to insert a element into a byte array.
> 
> Thanks,
> 
> JamesG
> 
> 

Here's an example for dynamic arrays (modified from my vector template code):

NOTE: inserts are expensive in non-linked lists!

// previously declared

byte [] tmpArray;
byte [] byteArray;  // array we want to insert into

//====================

void insert(in int index, in byte T) {
	if (index >= byteArray.length-1)
		byteArray ~= T;
	else {
		// Make a copy of the array and store it in tmpArray
		// so we don't point to the same array space.
		tmpArray = byteArray.dup;
		
		// Chop and store the section of array before index
		byteArray = byteArray[0 .. index];
		
		// Store the byte next at index
		byteArray ~= T;
		
		// Store the remaining portion of the array.
		byteArray ~= tmpArray[index .. tmpArray.length];
	}
}


	

In article <blk7b6$41l$1@digitaldaemon.com>, Walter says...
>
>
>"JamesG" <JamesG_member@pathlink.com> wrote in message news:blk61e$212$1@digitaldaemon.com...
>> In D is there away to insert a element into a byte array.
>
>Increase the length of an array by one. Then, write a loop to ripple up all the elements above the insertion point, and then insert the new element.
>
>

to remove an element I successefuly did

// tested
a[5..a.length-1] = a[6..a.length]
a.length = a.length -1;

Is that invalid? it seems to be working

but the docs say:

Overlapping copies are an error:
s[0..2] = s[1..3];	error, overlapping copy
s[1..3] = s[0..2];	error, overlapping copy


can't we do the same to insert?

// not tested
a.length = a.length+1;
a[6..a.length] = a[5..a.length-1]
a[5] = newElement;

Ant

JamesG wrote:
> 
> In D is there away to insert a element into a byte array.

This is an int array example based on memmove. It should be easy to adapt:

    import string;

    alias char [] String;

    int [] itab= [1,12,7,14,11];

    void IntArrayPrint(String s,int [] ar) {
      printf("%.*s [",s);
      foreach(int i; ar) {
        printf(" %d",i);
      }
      printf(" ]\n");
    }

    void IntArrayIndInsElement(inout int [] ar,uint ind,int el) {
      if(ind>=ar.length) {
        ar ~= el;
      } else {
        int size=(ar.length-ind)*el.size;
        ar.length=ar.length+1;
        memmove(&ar[ind+1],&ar[ind],size);
        ar[ind]=el;
      }
    }

    int main (String [] args)
    {
      IntArrayPrint("itab before insert: ",itab);
      IntArrayIndInsElement(itab,3,6);
      IntArrayPrint("itab after insert ind=3 el=6: ",itab);
      IntArrayIndInsElement(itab,100,33);
      IntArrayPrint("itab after insert ind=100 el=33: ",itab);
      IntArrayIndInsElement(itab,0,-1);
      IntArrayPrint("itab after insert ind=0 el=-1: ",itab);
      return 0;
    }

Output:

    itab before insert:  [ 1 12 7 14 11 ]
    itab after insert ind=3 el=6:  [ 1 12 7 6 14 11 ]
    itab after insert ind=100 el=33:  [ 1 12 7 6 14 11 33 ]
    itab after insert ind=0 el=-1:  [ -1 1 12 7 6 14 11 33 ]


-- 
Helmut Leitner    leitner@hls.via.at
Graz, Austria   www.hls-software.com

Other examples are better.  But after looking at Helmets, a correction on mine:

if (index >= byteArray.length-1) ... // Oops!

should be:

if (index >= byteArray.length)

Later,
John

I don't have a problem with their being a non-template way to do this, but I would hope that when the D template library eventuates, it will generalise (and specialise, for performance, where needed) this operation

Just my two-pen'th

Matthew

"Helmut Leitner" <helmut.leitner@chello.at> wrote in message news:3F7DCE65.B19FD3AE@chello.at...
>
>
> JamesG wrote:
> >
> > In D is there away to insert a element into a byte array.
>
> This is an int array example based on memmove. It should be easy to adapt:
>
>     import string;
>
>     alias char [] String;
>
>     int [] itab= [1,12,7,14,11];
>
>     void IntArrayPrint(String s,int [] ar) {
>       printf("%.*s [",s);
>       foreach(int i; ar) {
>         printf(" %d",i);
>       }
>       printf(" ]\n");
>     }
>
>     void IntArrayIndInsElement(inout int [] ar,uint ind,int el) {
>       if(ind>=ar.length) {
>         ar ~= el;
>       } else {
>         int size=(ar.length-ind)*el.size;
>         ar.length=ar.length+1;
>         memmove(&ar[ind+1],&ar[ind],size);
>         ar[ind]=el;
>       }
>     }
>
>     int main (String [] args)
>     {
>       IntArrayPrint("itab before insert: ",itab);
>       IntArrayIndInsElement(itab,3,6);
>       IntArrayPrint("itab after insert ind=3 el=6: ",itab);
>       IntArrayIndInsElement(itab,100,33);
>       IntArrayPrint("itab after insert ind=100 el=33: ",itab);
>       IntArrayIndInsElement(itab,0,-1);
>       IntArrayPrint("itab after insert ind=0 el=-1: ",itab);
>       return 0;
>     }
>
> Output:
>
>     itab before insert:  [ 1 12 7 14 11 ]
>     itab after insert ind=3 el=6:  [ 1 12 7 6 14 11 ]
>     itab after insert ind=100 el=33:  [ 1 12 7 6 14 11 33 ]
>     itab after insert ind=0 el=-1:  [ -1 1 12 7 6 14 11 33 ]
>
>
> -- 
> Helmut Leitner    leitner@hls.via.at
> Graz, Austria   www.hls-software.com

I think overlapping copies should be allowed and should "do the right thing" meaning copy the contents unharmed, and not do a memory fill;  e.g. the compiler should code up either a count-up or count-down loop depending on the direction, and should choose the direction at compile time if the slice arguments are compile-time constants, and at runtime if they're not.

If you want to do a memory fill, assign one element to a whole slice.  There should be good code generation for that as well.

Someone should code up the "ultimate memcpy" routine as a template with parameters of what to move and how much, alignment; that's one of those ultra-generic things that really should only have to be done once.

This is one of those things that you might thing maybe shouldn't go into the core language, but in a library, to keep the language small.  But if you are going to go to all of the trouble to put dynamic arrays and slices into the base language, you might as well specify what happens when you overlap slice ranges.

I suppose there may be issues with aliasing and overlapping slices, but isn't there a way to say "if at compile time the compiler can figure out that the ranges point to different physical arrays, or do not overlap, it can generate the fastest code possible.  Otherwise it must test the pointers and make sure which direction it should go for the copy semantics to work, possibly providing both loops."

This is the kind of thing that if done right, once, in the compiler, will save countless thousands of lines of grief and pain due to forgetting that the ranges overlap, or by trying to remember how to code a (fast) memcpy or memfill for your particular datatypes, or calling a memcpy function like the old days where you have to calculate the addresses and can't use the convenient slice assignment notation.  People will get it wrong and make bugs, or end up making a really suboptimal loop.

Sean

"Ant" <Ant_member@pathlink.com> wrote in message news:blk982$6qs$1@digitaldaemon.com...
> In article <blk7b6$41l$1@digitaldaemon.com>, Walter says...
> >
> >
> >"JamesG" <JamesG_member@pathlink.com> wrote in message news:blk61e$212$1@digitaldaemon.com...
> >> In D is there away to insert a element into a byte array.
> >
> >Increase the length of an array by one. Then, write a loop to ripple up
all
> >the elements above the insertion point, and then insert the new element.
> >
> >
>
> to remove an element I successefuly did
>
> // tested
> a[5..a.length-1] = a[6..a.length]
> a.length = a.length -1;
>
> Is that invalid? it seems to be working
>
> but the docs say:
>
> Overlapping copies are an error:
> s[0..2] = s[1..3]; error, overlapping copy
> s[1..3] = s[0..2]; error, overlapping copy
>
>
> can't we do the same to insert?
>
> // not tested
> a.length = a.length+1;
> a[6..a.length] = a[5..a.length-1]
> a[5] = newElement;
>
> Ant
>
>

"Ant" <Ant_member@pathlink.com> wrote in message news:blk982$6qs$1@digitaldaemon.com...
> to remove an element I successefuly did
>
> // tested
> a[5..a.length-1] = a[6..a.length]
> a.length = a.length -1;
>
> Is that invalid? it seems to be working
>
> but the docs say:
>
> Overlapping copies are an error:
> s[0..2] = s[1..3]; error, overlapping copy
> s[1..3] = s[0..2]; error, overlapping copy
>
>
> can't we do the same to insert?
>
> // not tested
> a.length = a.length+1;
> a[6..a.length] = a[5..a.length-1]
> a[5] = newElement;

Overlapping array operations are not allowed. The reason for this is so that it's possible to use parallel operations on it. Non-overlapping arrays also allow more kinds of loop optimizations to be done.

> I suppose there may be issues with aliasing and overlapping slices, but isn't there a way to say "if at compile time the compiler can figure out that the ranges point to different physical arrays, or do not overlap, it can generate the fastest code possible.  Otherwise it must test the
pointers
> and make sure which direction it should go for the copy semantics to work, possibly providing both loops."
>
> This is the kind of thing that if done right, once, in the compiler, will save countless thousands of lines of grief and pain due to forgetting that the ranges overlap, or by trying to remember how to code a (fast) memcpy
or
> memfill for your particular datatypes, or calling a memcpy function like
the
> old days where you have to calculate the addresses and can't use the convenient slice assignment notation.  People will get it wrong and make bugs, or end up making a really suboptimal loop.

I'm sold. Let's do it.

Walter?