Add remove_all(predicate) to Array

[cgbeutler]

Describe the project you are working on

A game in C#

Describe the problem or limitation you are having in your project

I have an array of WeakRef that I occasionally scrub. Removing multiple items from a Godot Array gets annoying.
Since C# has lambda support, it'd be nice to have something like List's RemoveAll for Godot's Array class.
It would likely be a touch faster as well.
If/when GDScript lambdas are ready, it could benefit from this function as well.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Basically you could do something like:

var weakItems = new Godot.Collections.Array<WeakRef>();
...
weakItems.RemoveAll( (it) => it.GetRef() == null );

For those unfamiliar, the lambda takes in each item and returns a boolean of whether or not it should be deleted.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

When doing a "remove all", it's best if you can iterate just once and only move items once.

Something like:

public static void RemoveAll<T>( this Array<T> self, Predicate<T> match )
{
  if (self == null) throw new ArgumentNullException( nameof(self) );
  if (match == null) throw new ArgumentNullException( nameof(match) );
  
  var iDest = 0;
  for (int iSource = 0; iSource < self.Count; iSource++)
  {
    if (!match.Invoke( self[iSource] ))
    {
      if (iDest != iSource) self[iDest] = self[iSource];
      iDest++;
    }
  }
  if (self.Count > iDest) self.Resize( iDest );
}

Not sure if some of that could be done on the C++ side, especially if GDScript gets lambdas.

If this enhancement will not be used often, can it be worked around with a few lines of script?

I've seen a lot of folks recommending various ways to remove a lot of items. Each method is of varying speed. I imagine they are usually fine enough.
The method pasted above is an extension method, so folks can just use that.

Is there a reason why this should be core and not an add-on in the asset library?

Removing items from a list based on a condition is fairly useful...?
This is a 'nice to have' not a 'need'.

[AaronRecord]

This has already been implemented in 4.0 (the filter method): godotengine/godot#38645

Lambda functions have been added to GDScript too:
godotengine/godot#47454

[cgbeutler]

This has already been implemented in 4.0 (the filter method): godotengine/godot#38645

Filter is more like Where, as it isn't an in-place operation.
RemoveAll is in-place for memory and speed.

[Calinou]

RemoveAll is in-place for memory and speed.

I think that when you're willing to optimize for memory and speed, using an imperative loop is better as it also avoids creating a lambda and all that stuff. Readability generally becomes a secondary concern when performance is critical.

[cgbeutler]

@Calinou Yeah, I really wish more stuff supported some of the functional concepts like inlining anonymous functions. Then RemoveAll could just unwrap into an imperative loop. (At least, as far as I know, c# can't do that atm.)

[dalexeev]

weakItems.RemoveAll( (it) => it.GetRef() == null );

weakItems = weakItems.Filter( (it) => it.GetRef() != null );

[cgbeutler]

@dalexeev yeah, that was already discussed above

[idbrii]

RemoveAll is in-place for memory and speed.

I think that when you're willing to optimize for memory and speed, using an imperative loop is better as it also avoids creating a lambda and all that stuff. Readability generally becomes a secondary concern when performance is critical.

Generally, I'd agree, but remove is a special case where you need to be careful about how you iterate over the list while removing. There are several questions about it because you need to iterate in reverse, right?

func remove_if(t: Array, should_remove_fn):
    for i in range(t.size() - 1, -1, -1):
        if should_remove_fn(t[i]):
            t.remove(i)

But even then, it's not really efficient because you should only shift each element once:

func remove_if(t: Array, should_remove_fn):
    var n = t.size()
    var keep = 0

    for i in range(n):
        if should_remove_fn(t[i], i, keep):
            t[i] = null
        else:
            # To keep i, move it into keep's position unless it's already there.
            if i != keep:
                t[keep] = t[i]
                t[i] = null
            keep += 1 # Increment position of where we'll place the next kept value.

    # Remove the nulls
    for i in range(keep, n):
        t.remove(i)

    return t

(A rough and untested port of a lua implementation.)

Thus having Array.remove_if would make it much easier to efficiently remove from a list and should make it easier for beginners to avoid incorrectly removing while iterating.