www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Deleting elemtens from dynamic arrays

reply Markus Dangl <danglm in.tum.de> writes:
Hi again, another topic:

Is there an easy way of deleting elements from dynamic arrays?
Currently i have to walk the array and do alot of copying etc.
Maybe i could use templates to implement a function for deleting an 
array element, but i dunno how (i'm a newbie to creating templates).

Thanks,
Markus
Dec 19 2004
parent reply Derek Parnell <derek psych.ward> writes:
On Mon, 20 Dec 2004 03:02:46 +0100, Markus Dangl wrote:

 Hi again, another topic:
 
 Is there an easy way of deleting elements from dynamic arrays?
 Currently i have to walk the array and do alot of copying etc.
 Maybe i could use templates to implement a function for deleting an 
 array element, but i dunno how (i'm a newbie to creating templates).
 
 Thanks,
 Markus

Here is some code you can adapt ... <code> template RI(T) { void RemItems( inout T[] pSource, int pFrom, int pTo) { int lNewLength; // Validate arguments. if (pFrom < 0) pFrom = 0; if (pTo >= pSource.length) pTo = pSource.length-1; // Optimize for a NOP request. if (pFrom > pTo) return; // Check for a non-truncate request. lNewLength = pFrom + pSource.length-pTo-1; if (pTo != pSource.length-1) { // Copy a duplicate of the RHS we want to keep to where // we now want it to be. pSource[pFrom .. lNewLength] = pSource[pTo+1..length].dup; }; // Adjust the array's new length; pSource.length = lNewLength; } } alias RI!(int).RemItems RemIntItems; alias RI!(char).RemItems RemCharItems; alias RI!(long).RemItems RemLongItems; alias RI!(float).RemItems RemFloatItems; // Now let's test it ... import std.stdio; void pI(int[] x) { foreach( int i; x) { writef("%d ", i); }; writef("\n"); } void main() { int[] A; char[] B; A.length = 0; A ~= 1; A ~= 2; A ~= 3; A ~= 4; A ~= 5; A ~= 6; A ~= 7; writef(" : "); pI(A); writef("6,6: "); RemIntItems(A, 6, 6); pI(A); writef("3,4: "); RemIntItems(A, 3, 4); pI(A); writef("0,0: "); RemIntItems(A, 0, 0); pI(A); B = "qwertyuiop".dup; writef(" : "); writefln(B); writef("2,5: "); RemCharItems(B, 2, 5); writefln(B); } </code> -- Derek Melbourne, Australia 20/12/2004 3:54:43 PM
Dec 19 2004
parent reply "Garett Bass" <gtbass studiotekne.com> writes:
Just a quick note, you could change:

    ... int pFrom ...

to:

    ... uint pFrom ...

to avoid the validation:

    if (pFrom < 0) pFrom = 0;

you may also do likewise for pTo, which you might want to 
make sure is >= pFrom.  I didn't check your algorithm to see 
if it happily handles the case pFrom > pTo.

Regards,
Garett


 template RI(T) {
    void RemItems( inout T[] pSource, int pFrom, int pTo)
    {
    int lNewLength;
    // Validate arguments.
    if (pFrom < 0) pFrom = 0;
    if (pTo   >= pSource.length) pTo = pSource.length-1;
    ... 

Dec 19 2004
parent reply Derek Parnell <derek psych.ward> writes:
On Mon, 20 Dec 2004 00:27:07 -0600, Garett Bass wrote:

 Just a quick note, you could change:
 
     ... int pFrom ...
 
 to:
 
     ... uint pFrom ...
 
 to avoid the validation:
 
     if (pFrom < 0) pFrom = 0;

Thanks. Sounds good.
 you may also do likewise for pTo, which you might want to 
 make sure is >= pFrom.  I didn't check your algorithm to see 
 if it happily handles the case pFrom > pTo.

It just returns without modifying the array. A NOP in effect as the caller is asking to remove non-existent items. One could throw an exception but it most likely does no harm to do nothing. -- Derek Melbourne, Australia 20/12/2004 5:59:12 PM
Dec 19 2004
next sibling parent Markus Dangl <danglm in.tum.de> writes:
I took your version, changed pForm to uint and rewrote it to a second 
version for removing only one element. It works great, thank you very much!

<code>
template RemoveItem(T) {
   void RemItem( inout T[] pSource, uint pIndex)
   {
     int lNewLength;

     // Validate arguments.
     if (pIndex >= pSource.length) return;

     lNewLength = pSource.length - 1;

     // Check for a non-truncate request.
     if (pIndex != lNewLength)
     {
         // Copy a duplicate of the RHS we want to keep to where
         // we now want it to be.
         pSource[pIndex .. lNewLength] = pSource[pIndex+1 .. length].dup;
     };

     // Adjust the array's new length;
     pSource.length = lNewLength;
   }
}
</code>
Dec 20 2004
prev sibling parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Mon, 20 Dec 2004 18:03:19 +1100, Derek Parnell <derek psych.ward> wrote:
 On Mon, 20 Dec 2004 00:27:07 -0600, Garett Bass wrote:

 Just a quick note, you could change:

     ... int pFrom ...

 to:

     ... uint pFrom ...

 to avoid the validation:

     if (pFrom < 0) pFrom = 0;

Thanks. Sounds good.

Slightly OT... This is an example of a problem for which I have been unable to decide the best solution. Imagine if you will: # void foo(uint a) # { # writef("foo: ",a,"\n"); # } # # void bar(int a) # { # writef("bar: ",a,"\n"); # } # # void main() # { # int a = -1; # foo(a); # bar(a); # } This program will print: foo: 4294967295 bar: -1 So, as you can see it has implicitly converted the int to a uint, meaning the -1 is represented as 4294967295. If this function is expecting an index of >= 0 then -1 is clearly wrong, and throwing an exception could be a valid choice of action, however, if you are using a uint as described then you cannot be sure they passed a -1 as they could equally have passed 4294967295. Given that both -1 and 4294967295 are likely to be out of bounds it's not a big problem, but I am interested on other peoples opinion of the different solutions they have taken in the past and why they chose those solutions. Regan
Dec 20 2004
parent "Thomas Kuehne" <thomas-dloop kuehne.cn> writes:
Regan Heath schrieb in opsjbp8mzv23k2f5 ally
 Slightly OT...

 This is an example of a problem for which I have been unable to decide the
 best solution.
 Imagine if you will:

 # void foo(uint a)
 # {
 # writef("foo: ",a,"\n");
 # }
 #
 # void bar(int a)
 # {
 # writef("bar: ",a,"\n");
 # }
 #
 # void main()
 # {
 # int a = -1;
 # foo(a);
 # bar(a);
 # }

 This program will print:

 foo: 4294967295
 bar: -1

 So, as you can see it has implicitly converted the int to a uint, meaning
 the -1 is represented as 4294967295.

 If this function is expecting an index of >= 0 then -1 is clearly wrong,
 and throwing an exception could be a valid choice of action, however, if
 you are using a uint as described then you cannot be sure they passed a -1
 as they could equally have passed 4294967295.

 Given that both -1 and 4294967295 are likely to be out of bounds it's not
 a big problem, but I am interested on other peoples opinion of the
 different solutions they have taken in the past and why they chose those
 solutions.

I haven't checked it, but this looks like an over/under-flow issue. Solution 1: user defined type with getter and setter functions Solution 2: Hack the compiler / lib to throw exceptions on over/under-flow. Too bad there isn't any ufloat type. This got me thinking ... # int i = cast(int) float.nan; Why doesn't this produce an exception? Thomas
Dec 23 2004