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:


















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:


















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

Why doesn't this produce an exception?

Thomas
Dec 23 2004