On Monday, 4 April 2022 at 23:15:30 UTC, Enjoys Math wrote:

// remove an item from an array
template drop(T)
{
  T drop( inout T[] arr, T which )
  {			
    int i;
		T result;
		
		for (i=0; i < arr.length; i++)
		{
			if (arr[i] == which)
			{
				result = arr[i];
				break;
			}
		}
		
		debug if ( which >= arr.length)
        throw new Exception(str.format("Attempt to drop the %s of value %s from an array, but it was not found.", typeid(T), which));
		}
		
		for (; i < arr.length; i++)
		{
			arr[i] = arr[i + 1];
		}
		arr.length = arr.length - 1;

		return result;
  }
}

I'm guessing you're doing this to learn and measure. You might be better off using the slicing method though. It's also possible to do it with a single loop:

auto dropSlice(T)(T[] array, T which)
{
  T[] result;

  size_t i;                      // old index
  foreach(index, element; array)
  {
    if(element == which) {
      result ~= array[i..index]; // slice off
      i = index + 1;
    }
  }

  return result ~ array[i..$];   // last slice
}

void main()
{
  char[] dizi = "abcdefdg".dup;

  dizi.dropSlice('d').writeln;

SDB@79

On 4/4/22 7:15 PM, Enjoys Math wrote:

// remove an item from an array
template drop(T)
{
   T drop( inout T[] arr, T which )

Note to reader: this is D1 code, so inout was equivalent to ref.

I think this is a bug, it should be i you are testing.

this looks like a stray brace?

It has worse case complexity O(2n) = O(n) whereas the other one can run in half as long minimally and sometimes just as long (but still O(n)), but usually one needs to linear search for the entry first.

No, it's O(n) straight up, you are only iterating the entire array once.

As others mentioned, std.algorithm.remove can do this now. I'm not entirely sure of the benefit of returning the thing you tried to remove, though I suppose if the parameter defines equality with some extra data that isn't considered, maybe that does help you see what was removed?

I'd implement it probably like this (for D2):

auto drop(T)(ref T[] arr, T which)
{
   import std.algorithm, std.range;
   auto f = arr.find(which);
   debug if(f.empty) throw ...;
   auto result = arr.front;
   arr = arr.remove(&f[0] - &arr[0]); // god I hate this
   return result;
}

Still O(n).

-Steve

On Tuesday, 5 April 2022 at 14:10:44 UTC, Steven Schveighoffer wrote:

auto drop(T)(ref T[] arr, T which)
{
   import std.algorithm, std.range;
   auto f = arr.find(which);
   debug if(f.empty) throw ...;
   auto result = arr.front;
   arr = arr.remove(&f[0] - &arr[0]); // god I hate this
   return result;
}

I think you can get rid of the ugly pointer arithmetic using countUntil:

auto drop(T)(ref T[] arr, T which)
{
    import std.algorithm, std.range, std.exception;

    auto i = arr.countUntil(which);
    debug enforce(i < arr.length, "Not found");
    auto result = arr[i];
    arr = arr.remove(i);
    return result;
}

On 4/5/22 11:43 AM, Paul Backus wrote:

auto drop(T)(ref T[] arr, T which)
{
   import std.algorithm, std.range;
   auto f = arr.find(which);
   debug if(f.empty) throw ...;
   auto result = arr.front;
   arr = arr.remove(&f[0] - &arr[0]); // god I hate this
   return result;
}

auto drop(T)(ref T[] arr, T which)
{
     import std.algorithm, std.range, std.exception;

     auto i = arr.countUntil(which);
     debug enforce(i < arr.length, "Not found");
     auto result = arr[i];
     arr = arr.remove(i);
     return result;
}

Yeah, or use enumerate. But it's painful:

auto f = arr.enumerate.find!((v, w) => v[1] == w)(which);
auto result = f.front[1];
arr = arr.remove(result[0]);
return result;

I have a lib somewhere which isn't complete that allows remembering indexes for elements so you can tease out the original index, but it breaks when you use it on strings (of course).

-Steve

On Tuesday, 5 April 2022 at 14:10:44 UTC, Steven Schveighoffer wrote:

auto drop(T)(ref T[] arr, T which)
{
   import std.algorithm, std.range;
   auto f = arr.find(which);
   debug if(f.empty) throw ...;
   auto result = arr.front;
   arr = arr.remove(&f[0] - &arr[0]); // god I hate this
   return result;
}

First, you're neglecting the loop. Second, the returned value is the first element of the array. It should be as follows:

auto drop2(T)(ref T[] arr, T which)
{
  //auto f = arr.find(which);
  auto f = arr.find!(a => a == which);

  //debug if(f.empty) throw ...;
  auto result = f.front; // arr.front;

  //arr = arr.remove(&f[0] - &arr[0]);
  arr = remove!(a => a == which)(arr);

  return result;
}

We do not know the wishes of the programmer who made the development. But it is certain that he scanned until the end of the array. So it doesn't make sense for the resulting output to be equal to the which. In summary, one line is enough:

return remove!(a => a == which)(arr);

SDB@

On 4/5/22 11:47 PM, Salih Dincer wrote:

auto drop(T)(ref T[] arr, T which)
{
   import std.algorithm, std.range;
   auto f = arr.find(which);
   debug if(f.empty) throw ...;
   auto result = arr.front;
   arr = arr.remove(&f[0] - &arr[0]); // god I hate this
   return result;
}

oops, yes, that should have been auto result = f.front

auto drop2(T)(ref T[] arr, T which)
{
   //auto f = arr.find(which);
   auto f = arr.find!(a => a == which);

This is almost equivalent, but it requires a lambda and an allocation. So I'm not sure what thing you are trying to do here.

Yep, that's a bug on my part.

This runs through the array again, instead of just removing the one index that you already know. And also, the original code only removed one element, even if there were multiple matches. Yours removes them all.

We do not know the wishes of the programmer who made the development. But it is certain that he scanned until the end of the array.  So it doesn't make sense for the resulting output to be equal to the ```which```. In summary, one line is enough:

```d
return remove!(a => a == which)(arr);

The return is the element that was removed, not the array after removing the element. And even though it might feel equivalent to return the input, we don't know how the elements compare, so the array element might be different than the incoming parameter.

-Steve

On Wednesday, 6 April 2022 at 16:54:26 UTC, Steven Schveighoffer wrote:

I tried to get these results but it didn't work:

I'm a bit old-fashioned and I don't understand these lambda stuff. That's why I coded with classical logic and indexOf...

Source Code:
https://forum.dlang.org/post/pxkhngxmqgiwwymmgoyh@forum.dlang.org

Actually, I wrote this before, with a few magic touches, I got what I wanted.

SDB@79

On 4/6/22 2:32 PM, Salih Dincer wrote:

I'm not sure what your code there is trying to do exactly.

What I meant with my comment above is this:

With arr.find!(someLambda), if the lambda is using data from outside the lambda, it needs a closure, which means it may (probably does) allocate your needed data into a GC heap block that will then become garbage after the function is gone.

With arr.find(value), it searches the array for something that compares with the value. No allocation happens, and it's equivalent to what you would write in a for loop.

Especially for the code in question:

arr.find(val); // like a for loop, comparing each element to val
arr.find!(v => v == val); // requires a context pointer for val, may allocate.

There is no difference functionally -- both perform exactly the same task, but one is just more expensive.

-Steve