Getting the index of a sequence of items

Question

I was trying to get the index of a sequence of items inside an IEnumerable<T>

var collection = new[] { 1, 2, 3, 4, 5 };
var sequence   = new[] { 2, 3 };

// IndexOf is an extension method.
collection.IndexOf(sequence); // Should return 1

I wrote an IndexOf extension method for this and it works fine unless there are more than one of the first item of the sequence in collection, consecutively:

// There are two items that are 2, consecutively in the collection,
// which is the first item of the sequence.
var collection = new[] { 1, 2, 2, 3, 4, 5 };
var sequence   = new[] { 2, 3 };

collection.IndexOf(sequence); // Should return 2 but returns -1

Here is the IndexOf method:

public static int IndexOf<T>(this IEnumerable<T> collection,
    IEnumerable<T> sequence)
{
    var comparer = EqualityComparer<T>.Default;
    var counter = 0;
    var index = 0;
    var seqEnumerator = sequence.GetEnumerator();

    foreach (var item in collection)
        if (seqEnumerator.MoveNext())
        {
            if (!comparer.Equals(item, seqEnumerator.Current))
            {
                seqEnumerator.Dispose();
                seqEnumerator = sequence.GetEnumerator();
                counter = 0;

                // UPDATED AFTER MICHAEL'S ANSWER,
                // IT WORKS WITH THIS ADDED PART:
                seqEnumerator.MoveNext();
                if (comparer.Equals(item, seqEnumerator.Current))
                    counter++;
            }
            else counter++;
            index++;
        }
        else break;

    var done = !seqEnumerator.MoveNext();
    seqEnumerator.Dispose();
    return done ? index - counter : -1;
}

I couldn't figure out how to fix this.

Is this useful? http://stackoverflow.com/questions/3561776/find-sequence-in-ienumerablet-using-linq — coder_bro, Sep 06 '12 at 13:52
@Andre: It is zero-based. The first item of the *sequence*, found in the *collection* should be zero. — Şafak Gür, Sep 06 '12 at 13:54
Yes, but the result of your extension method should be 1 and not 2, right? — Andre Calil, Sep 06 '12 at 13:55
@Ngm: The method I provided in this question can be that question's answer if I can figure out what I do wrong and fix it. But this and that are not the same. — Şafak Gür, Sep 06 '12 at 13:56
@ŞafakGür Ok, sorry, now I see. Well, you could simply convert your `IEnumerable` to a string and use `string.IndexOf` =) — Andre Calil, Sep 06 '12 at 13:58
@Andre: True, that works with integer collections :) but what if I use this with a collections of a more complex type? — Şafak Gür, Sep 06 '12 at 14:00
@ŞafakGür You still could override `ToString` and `GetHashCode`. Yet, I'm taking a look at your code — Andre Calil, Sep 06 '12 at 14:04
I have two improvement suggestions - neither of which are regarding correctness: (1) you might consider providing an overload that lets you pass-in an `IEqualityComparer` so, for example if T were string, you could pass in a case-insensitive comparer. (2) Instead of calling `Dispose()` directly, you might wrap it in a `using` block so if something goes wrong and an exception is thrown, the enumerator will still be disposed. cheers. — devgeezer, Sep 08 '12 at 18:02

L.B · Answer 1 · 2012-09-08T20:59:29.703

3

public static int IndexOf<T>(this IEnumerable<T> collection,
                                IEnumerable<T> sequence)
{
    var ccount = collection.Count();
    var scount = sequence.Count();

    if (scount > ccount) return -1;

    if (collection.Take(scount).SequenceEqual(sequence)) return 0;

    int index = Enumerable.Range(1, ccount - scount + 1)
                          .FirstOrDefault(i => collection.Skip(i).Take(scount).SequenceEqual(sequence));
    if (index == 0) return -1;
    return index;
}

edited Sep 08 '12 at 20:59

answered Sep 06 '12 at 14:08

L.B

114,136
19
178
224

I tried to make it fast as possible by iterating the collection only once. Re-iterating the sequence is inevitable, though. – Şafak Gür Sep 06 '12 at 14:21
L.B, you could add `if (scount > ccount) return -1;` before the first `if`. Interesting. +1 – devgeezer Sep 08 '12 at 18:46

score 2 · Accepted Answer · answered Sep 06 '12 at 14:04

When you encounter wrong symbol on not first position you restarting the sequence iterator but you don't check if the current item is matching the start of the sequence iterator, so you actually never compare second 2 from collection to 2 from sequence .

Getting the index of a sequence of items

2 Answers2

Linked