CODEWITHSUNDEEP
c#linqextension-methodsienumerable
abelenky
abelenky

Reputation: 64682

Using Array and IEnumerable in an Extension Method

I'm trying to write an extension method like this:

static class MyExtensions
{
    public static int FindSubArray(this Array x, Array y)
    {
        int offset = 0;
        for (int i = 0; i < x.Length; ++i)
        {
            if (y.SequenceEqual(x.Skip(i).Take(y.Length)))
            {
                offset = i;
                break;
            }
        }
        return offset;
    }
}

However, the compiler tells me that Array does not have a .Skip() method. Only IEnumerable does:

error CS1061: 'Array' does not contain a definition for 'Skip' and no accessible extension method 'Skip'

But when I changed the parameter types to IEnumerable<T>, it says that IEnumerable does not have a .Length property, only Array has that.

error CS1061: 'IEnumerable' does not contain a definition for 'Length' and no accessible extension method 'Length'

When I wrote similar code outside an extension method, with both types as byte[], it had no problem with me using .Skip() and .Length as it easily converted byte[] to an IEnumerable<byte> when needed.

How can I write my extension method to use both .Skip and .Length?

Upvotes: 0

Views: 547

Answers (5)

Denis Kurkov
Denis Kurkov

Reputation: 11

Change signuture and use this

public static int FindSubArray<T>(this IReadOnlyList<T> sourceCollection, IReadOnlyList<T> collectionToFind)
    {
        for (var i = 0; i <= sourceCollection.Count - collectionToFind.Count; i++)
        {
            var matched = true;
            for (var j = 0; j < collectionToFind.Count; j++)
            {
                if (sourceCollection[i + j].Equals(collectionToFind[j]))
                    continue;

                matched = false;
                break;
            }

            if (matched)
                return i;
        }
        return -1;
    }

Upvotes: 0

Jordan Rieger
Jordan Rieger

Reputation: 2664

Here's a solution that allows you to use Array and SequenceEquals(). (Though I'll echo others who have suggested that this is not a very performant solution, nor likely the most convenient.)

    public static int FindSubArray(this Array x, Array y)
    {
        int offset = 0;

        var loYArray = new List<Object>();
        var ieYArray = y.GetEnumerator();
        while (ieYArray.MoveNext())
            loYArray.Add(ieYArray.Current);

        for (int i = 0; i < x.Length; ++i)
        {
            var loXSubArray = new List<Object>();
            var ieXArray = x.GetEnumerator();
            var iSkip = 0;

            while (ieXArray.MoveNext())
            {
                iSkip++;
                if (iSkip > i)
                    loXSubArray.Add(ieXArray.Current);
                if (loXSubArray.Count >= y.Length)
                    break;
            }

            if (loYArray.SequenceEqual(loXSubArray))
                return i;
        }
        return -1;
    }

This solution uses Object boxing and creates multiple redundant copies of the arrays. If you don't need to use Array or SequenceEquals(), I'd recommend @NetMage's solution.

Upvotes: 0

Lee
Lee

Reputation: 144136

You can make the method generic and change the argument types:

public static int FindSubArray<T>(this T[] x, T[] y) { ... }

alternatively you can use IReadOnlyCollection<T> which implements IEnumerable<T> and has a Count property:

public static int FindSubArray<T>(this IReadOnlyCollection<T> x, IReadOnlyCollection<T> y)
{
    int offset = 0;
    for (int i = 0; i < x.Count; ++i)
    {
        if (y.SequenceEqual(x.Skip(i).Take(y.Count)))
        {
            offset = i;
            break;
        }
    }
    return offset;
}

It's worth noting this approach to finding subsequences is not very efficient, and you might want to look at other algorithms like Boyer-Moore or Knuth-Morris-Pratt.

Upvotes: 3

Vishnu
Vishnu

Reputation: 897

You can use the IEnumerable with Count instead of Length property.

public static class MyExtensions
    {
        public static int FindSubArray<T>(this IEnumerable<T> x, IEnumerable<T> y)
        {
            int offset = 0;
            for (int i = 0; i < x.Count(); ++i)
            {
                if (y.SequenceEqual(x.Skip(i).Take(y.Count())))
                {
                    offset = i;
                    break;
                }
            }
            return offset;
        }

Upvotes: 0

NetMage
NetMage

Reputation: 26917

If you really wanted to use Array, you can. It will not be as performant as generics for most value types, as they will be boxed to object and a generic Equals method test must be done, but it is possible. Instead of using LINQ, just implement your own sequence comparison. Also, don't start so far that you will run off the end trying to match the subsequence.

Finally, return -1 when not found, as 0 is a valid matching return value.

static class MyExtensions {
    public static int FindSubArray(this Array x, Array y) {
        for (int i = 0; i < x.Length-y.Length+1; ++i) {
            var found = true;
            for (int j = 0; j < y.Length; ++j) {
                if (!((IList)x)[i + j].Equals(((IList)y)[j])) {
                    found = false;
                    break;
                }
            }
            if (found)
                return i;
        }
        return -1;
    }
}

Upvotes: 0

Related Questions