C# List removeall taking two arguments in the predicate?

Question

(I've done as much as possible search based on keywords of "removeall where" or "removeall two argument predicate" without much luck so here goes)

The problem is I have a list of objects (of Class Wave) and a relationship function as: private bool AinB(Wave A, Wave B), returning true if A 'is in' B. Also AinB(x,y) is true guarantees AinB(y,x) is false.

What's the best way to remove all of the objects in the list where the objects 'is in' another object in the list? i.e., after the removal, the list should only contain objects where neither are in the 'is in' relationship with any other object in the list?

ideally this can be done easily as a

listX.RemoveAll( (x,y) => AinB(x,y)) but of course this is not legal in C#, also there's no easy way to specify which to remove, x or y.

I thought about looping through the list with an index

int i = listX.Count - 1;
while (i>=0)
{
    int r = listX.RemoveAll(X => AinB(X, listX[i]));
    i = i - r - 1;
}

This seems to work, but I am wondering if there's better way with straight linq code to solve the problem. Thanks.

Answer 1

Unfortunately I can't think of any way to do this that's not at least O(n^2). But the good news is that it's not that hard from a LINQ perspective:

listX.RemoveAll(item => listX.Any(isin => AinB(item, isin)));

Answer 2

Use a normal for loop that inspects the highest element first down to the lowest element in the list. Inspect the element at the current position for any duplicates within the list, if found remove the current element (and possibly decrement your iterator).

Example:

List<string> stuff = new List<string>(); //full of stuff
for(int i = stuff.Count - 1; i > 0; i--)
{
    //Edited here for more efficiency.
    for (int x = i - 1; x > 0; x--)
    {
        if (stuff[x] == stuff[i])
        {
            stuff.RemoveAt(i);
            break; //or possibly continue;
        }
    }
}

This was hand-coded here so it might have a few syntactical errors, feel free to shoot me an edit if you find something's not quite right.

If you're a wizard with LINQ you could also try grouping the objects in the list and then just selecting the first object in each group for your output list..

Answer 3

you can use the LINQ Except call,

List a = new List();
a.Add("a");
a.Add("b");
a.Add("c");
List b = new List();
b.Add("b");
b.Add("c");
b.Add("d");
List c = a.Except(b);

list c will contain only item "a";

you can even make it more clever by giving a compare object,

List c = a.Except(b, new CompareObject());