Hi, is there a way to remove a number of elements from an array by a range of indices in the standard library somewhere?

I wrote one (code below), but I'm wondering if there's a better way?

Also, can the below be made more efficient?

auto without(T, R)(T[] array, R indices) if (isForwardRange!R && isIntegral!(ElementType!R) && !isInfinite!R) {
    T[] newArray;
    ElementType!R start = 0;
    foreach (i; indices) {
        newArray ~= array[start .. i];
        start = i + 1;
    }
    newArray ~= array[start .. $];
    return newArray;
}

// Usage
long[] aa = [1, 2, 3, 4]
aa = aa.without([1, 3])

Thanks!

On 12/20/17 6:01 PM, aliak wrote:
> Hi, is there a way to remove a number of elements from an array by a range of indices in the standard library somewhere?
> 
> I wrote one (code below), but I'm wondering if there's a better way?
> 
> Also, can the below be made more efficient?
> 
> auto without(T, R)(T[] array, R indices) if (isForwardRange!R && isIntegral!(ElementType!R) && !isInfinite!R) {
>      T[] newArray;
>      ElementType!R start = 0;
>      foreach (i; indices) {
>          newArray ~= array[start .. i];
>          start = i + 1;
>      }
>      newArray ~= array[start .. $];
>      return newArray;
> }
> 
> // Usage
> long[] aa = [1, 2, 3, 4]
> aa = aa.without([1, 3])
> 
> Thanks!

I'm assuming here indices is sorted? Because it appears you expect that in your code. However, I'm going to assume it isn't sorted at first.

Now:

import std.range;
import std.algorithm;

auto indices = [1,2,3,4];
aa = aa.enumerate.filter!(a => !indicies.canFind(a[0])).map(a => a[1]).array;

Now, this is going to be O(n^2), but if indices is sorted, you could use binary search:

auto sortedIdxs = indices.assumeSorted; // also could be = indices.sort()

arr = arr.enumerate.filter!(a => !sortedIdxs.contains(a[0])).map(a => a[1]).array;

Complexity would be O(n lg(n))

It's not going to be as good as hand-written code, complexity wise, but it's definitely shorter to write :)

-Steve

On Wednesday, 20 December 2017 at 23:01:17 UTC, aliak wrote:
> Hi, is there a way to remove a number of elements from an array by a range of indices in the standard library somewhere?
>
> I wrote one (code below), but I'm wondering if there's a better way?
>
> Also, can the below be made more efficient?
>
> auto without(T, R)(T[] array, R indices) if (isForwardRange!R && isIntegral!(ElementType!R) && !isInfinite!R) {
>     T[] newArray;
>     ElementType!R start = 0;
>     foreach (i; indices) {
>         newArray ~= array[start .. i];
>         start = i + 1;
>     }
>     newArray ~= array[start .. $];
>     return newArray;
> }
>
> // Usage
> long[] aa = [1, 2, 3, 4]
> aa = aa.without([1, 3])
>
> Thanks!

Try std.algorithm.mutation.remove [1]:

```
import std.algorithm, std.range, std.stdio, std.typecons;
auto r = 10.iota.array;
r.remove(tuple(2, 4)).writeln;
```

Play with it: https://run.dlang.io/is/RcL3VX

[1] https://dlang.org/phobos/std_algorithm_mutation.html#remove

On Thursday, 21 December 2017 at 00:23:08 UTC, Steven Schveighoffer wrote:
> On 12/20/17 6:01 PM, aliak wrote:
>> Hi, is there a way to remove a number of elements from an array by a range of indices in the standard library somewhere?
>> 
>> I wrote one (code below), but I'm wondering if there's a better way?
>> 
>> Also, can the below be made more efficient?
>> 
>> auto without(T, R)(T[] array, R indices) if (isForwardRange!R && isIntegral!(ElementType!R) && !isInfinite!R) {
>>      T[] newArray;
>>      ElementType!R start = 0;
>>      foreach (i; indices) {
>>          newArray ~= array[start .. i];
>>          start = i + 1;
>>      }
>>      newArray ~= array[start .. $];
>>      return newArray;
>> }
>> 
>> // Usage
>> long[] aa = [1, 2, 3, 4]
>> aa = aa.without([1, 3])
>> 
>> Thanks!
>
> I'm assuming here indices is sorted? Because it appears you expect that in your code. However, I'm going to assume it isn't sorted at first.
>
> Now:
>
> import std.range;
> import std.algorithm;
>
> auto indices = [1,2,3,4];
> aa = aa.enumerate.filter!(a => !indicies.canFind(a[0])).map(a => a[1]).array;
>
> Now, this is going to be O(n^2), but if indices is sorted, you could use binary search:
>
> auto sortedIdxs = indices.assumeSorted; // also could be = indices.sort()
>
> arr = arr.enumerate.filter!(a => !sortedIdxs.contains(a[0])).map(a => a[1]).array;
>
> Complexity would be O(n lg(n))
>
> It's not going to be as good as hand-written code, complexity wise, but it's definitely shorter to write :)
>
> -Steve

isn't that n log(m), where n is length of array and m is length of indices?

If indices is sorted with no duplicates and random access then you can do it in linear time.

int i;
int ii;
int[] indicies = ...;
arr = arr.filter!((T t)
{
    scope(exit) i++;
    if (i == indicies[ii])
    {
        ii++;
        return false;
    }
    return true;
}).array;

On Thursday, 21 December 2017 at 00:52:29 UTC, Nicholas Wilson wrote:
> On Thursday, 21 December 2017 at 00:23:08 UTC, Steven Schveighoffer wrote:
>>
>> I'm assuming here indices is sorted? Because it appears you expect that in your code. However, I'm going to assume it isn't sorted at first.
>>
>> auto sortedIdxs = indices.assumeSorted; // also could be =
>>
>> It's not going to be as good as hand-written code, complexity wise, but it's definitely shorter to write :)
>>
>> -Steve
> If indices is sorted with no duplicates and random access then you can do it in linear time.


Ah yes, I guess sorted and unique as well would be the expected input. But nice to see the handling of non-sorted indices.

I tried to search for an assumeUnique function as well (the assumeSorted one was nice to see) but it's not what I thought it'd be - seems to be more of an assumeUnaliased. And I guess there's no assumeUniqueElements.

And the filter approach is nice! :) (just need to account for the last ii++ (when filter comes back in I think one case would be ii == indices.length and you'd get a range error)

Thanks for the feedback!

On 12/20/17 7:52 PM, Nicholas Wilson wrote:
> On Thursday, 21 December 2017 at 00:23:08 UTC, Steven Schveighoffer wrote:
>> On 12/20/17 6:01 PM, aliak wrote:
>>> Hi, is there a way to remove a number of elements from an array by a range of indices in the standard library somewhere?
>>>
>>> I wrote one (code below), but I'm wondering if there's a better way?
>>>
>>> Also, can the below be made more efficient?
>>>
>>> auto without(T, R)(T[] array, R indices) if (isForwardRange!R && isIntegral!(ElementType!R) && !isInfinite!R) {
>>>      T[] newArray;
>>>      ElementType!R start = 0;
>>>      foreach (i; indices) {
>>>          newArray ~= array[start .. i];
>>>          start = i + 1;
>>>      }
>>>      newArray ~= array[start .. $];
>>>      return newArray;
>>> }
>>>
>>> // Usage
>>> long[] aa = [1, 2, 3, 4]
>>> aa = aa.without([1, 3])
>>>
>>> Thanks!
>>
>> I'm assuming here indices is sorted? Because it appears you expect that in your code. However, I'm going to assume it isn't sorted at first.
>>
>> Now:
>>
>> import std.range;
>> import std.algorithm;
>>
>> auto indices = [1,2,3,4];
>> aa = aa.enumerate.filter!(a => !indicies.canFind(a[0])).map(a => a[1]).array;
>>
>> Now, this is going to be O(n^2), but if indices is sorted, you could use binary search:
>>
>> auto sortedIdxs = indices.assumeSorted; // also could be = indices.sort()
>>
>> arr = arr.enumerate.filter!(a => !sortedIdxs.contains(a[0])).map(a => a[1]).array;
>>
>> Complexity would be O(n lg(n))
>>
>> It's not going to be as good as hand-written code, complexity wise, but it's definitely shorter to write :)
>>
> 
> isn't that n log(m), where n is length of array and m is length of indices?

Strictly speaking, yes :) But lg(n) and lg(m) are going to be pretty insignificantly different.

> If indices is sorted with no duplicates and random access then you can do it in linear time.
> 
> int i;
> int ii;
> int[] indicies = ...;
> arr = arr.filter!((T t)
> {
>      scope(exit) i++;
>      if (i == indicies[ii])
>      {
>          ii++;
>          return false;
>      }
>      return true;
> }).array;
> 

Very nice! as aliak mentioned, however, you have a bug, as ii might extend beyond the size of indicies. So should be if(ii < indices.length && indicies[ii] == i).

We are always focused on using a chained one-liner, but your lambda stretches that ;)

Here's a similar solution with an actual range:

https://run.dlang.io/is/gR3CjF

Note, all done lazily. However, the indices must be sorted/unique.

-Steve

On Thursday, 21 December 2017 at 15:59:44 UTC, Steven Schveighoffer wrote:
> Here's a similar solution with an actual range:
>
> https://run.dlang.io/is/gR3CjF
>
> Note, all done lazily. However, the indices must be sorted/unique.
>
> -Steve

Noice! :D