CODEWITHSUNDEEP
c#linq
Coxy
Coxy

Reputation: 8928

Linq way of checking that no items in a collection match any other item

I'm taking a collection of line segments and trimming any that overlap and I should get a collection that does not overlap as output.

To test my output I want to iterate over each item in the collection and ensure that it does not overlap with any other item.

Currently I have this code:

foreach (var assay in compiledAssays)
{
    if (compiledAssays.Where(a => a != assay).Any(a => a.Overlaps(assay)))
    {
        throw new ApplicationException("Something went wrong.");
    }
}

It's readable but it "smells bad" to me. Seems like it would be iterating through the collection at least three times to do the test.

Is there a better way of expressing this test?

Upvotes: 3

Views: 244

Answers (2)

Mark Hurd
Mark Hurd

Reputation: 10931

Your first Where clause is excluding exact duplicates (depending upon what != is defined to be for assay), as such you can use compiledAssays.Distinct as the base enumeration, but given you could use a sort to optimise the search for overlaps anyway, but at the expense of an extra loop, the now accepted answer's explicit double loop is fine, except it doesn't currently exclude all duplicates. It should be:

for (int i = 0; i < compiledAssays.Length; i++)
{
    for (int j = i + 1; j < compiledAssays.Length; j++)
    {
        if (compiledAssays[i] != compiledAssays[j]
          && compiledAssays[i].Overlaps(compiledAssays[j]))
        {
            throw new ApplicationException("Something went wrong.");
        }
    }
}

to replicate the OP, again assuming Overlaps is symmetric.

Upvotes: 1

sstan
sstan

Reputation: 36483

Well, merging the Where and the Any clauses would be a good first improvement:

foreach (var assay in compiledAssays)
{
    if (compiledAssays.Any(a => a != assay && a.Overlaps(assay)))
    {
        throw new ApplicationException("Something went wrong.");
    }
}

You can also try the more succinct:

if (compiledAssays.Any(a => compiledAssays.Any(b => a != b && a.Overlaps(b))))
{
    throw new ApplicationException("Something went wrong."");
}

Otherwise, if your primary concern is to minimize the amount of loops that are performed, I wouldn't use Linq. I would do this instead (assumes compiledAssays is an array, adjust as necessary):

for (int i = 0; i < compiledAssays.Length; i++)
{
    for (int j = i + 1; j < compiledAssays.Length; j++)
    {
        if (compiledAssays[i].Overlaps(compiledAssays[j]))
        {
            throw new ApplicationException("Something went wrong.");
        }
    }
}

EDIT: A very pertinent comment by Raymond Chen.

My last option assumes that the Overlaps function is symmetric.

In other words, that a.Overlaps(b) will always return the same value as b.Overlaps(a). If this is not the case, then my last option is incorrect.

Upvotes: 3

Related Questions