Runtime: FindIndex for IReadOnlyList<T>?

[LYP951018]

Rationale and Usage

I think the usage for this API is almost same with List<T>.FindIndex. But this is a readonly API and should exist in IReadOnlyList<T>. Otherwise we have to fallback to mutable type, List<T> as interface, which is ... bad, or write a FindIndex extension method ourselves.

Questions

1. If we just use type switch to optimize for List<T> internally, what about custom classes (such as my SortedList) which implement IReadOnlyList and use an array internally, and I want to have a high-perf FindIndex?

2. Should we generalize to IEnumerable? What's the usage for IEnumerable.FindIndex?

[LYP951018]

It seems that making them extension methods is better and trivial to implement.

[jnm2]

I have FindFirstIndex and FindLastIndex as extension methods.

[JonHanna]

FindAll already exists as Where bar for the fact that FindAll returns List<T>, which doesn't make as much sense once you've moved away from defining it on List<T> (and one can always ToList() it), and it takes a Func<T, bool> rather than a Predicate<T> which is a more modern approach. Find exists as FirstOrDefault(). and FindLast exists as LastOrDefault(). These last two are already optimised for some types of sources, including IList<T>.

This leaves only FindIndex which could be implemented on IEnumerable<T> rather than necessarily on IList<T> or IReadOnlyList<T>, with optimised paths for those.

[jnm2]

FindLastIndex is useful too.

[JonHanna]

And likewise easily done for any IEnumerable<T>, and easily optimised for IList<T>. We shouldn't restrict it to lists if we don't need to.

[karelz]

@LYP951018 can you update your proposal based on the discussion? Also make sure to include formal API proposal in top post (see the example).

[JonHanna]

Should these live in linq?

```C#
namespace System.Linq
{
public static class Enumerable
{
public static int FindIndex(this IEnumerable source, Func predicate);
public static int FindLastIndex(this IEnumerable source, Func predicate);
}

public static class Queryable
{
    public static int FindIndex<TValue>(this IQueryable<TValue> source, Expression<Func<TValue, bool>> predicate);
    public static int FindLastIndex<TValue>(this IQueryable<TValue> source, Expression<Func<TValue, bool>> predicate);
}

}

[LYP951018]

@JonHanna But I couldn't find a usage for FindIndex of generalized IEnumerable. With IList<T> or IReadOnlyList<T>, I know that indexing is possible, and fast, so I could use the result of FindIndex and then do some indexing. But with IEnumerable, what could I do with index?

[LYP951018]

Also, why is Func<T, bool> more modern than Predicate<T>?

[JonHanna]

There's an analogy with ElementAt here, which is available for all enumerables and queryables but optimised for IList<T>.

As for Fuct<T, bool> being more modern, there's little justification in using any other delegate than Func and Action unless something like being ref means one cannot. Keeping to them prevents one having to wrap one delegate in another just to match a signature.

[LYP951018]

Many IEnumerables is one-pass, just like input iterators in C++. That means we could not pass the result of FindIndex to ElementAt. I could image an usage for ElementAt, just like Skip(n), but I could not figure out what could I do with index of IEnumerable ...

[RezaJooyandeh]

31156 will cover this with an extension method

[DaveInCaz]

Would/should adding IndexOf to IReadOnlyList be covered by this also?

[eiriktsarpalis]

I'm not entirely convinced that indices are very meaningful in the context of LINQ. It would almost certainly not be useful to find the index of a chained enumerable such as source.Where().GroupBy().OrderBy(). In practice, I have found this Select overload to be a good general-purpose solution in the rare cases where indices are significant.

Would/should adding IndexOf to IReadOnlyList be covered by this also?

It would probably be a breaking change. It has been argued that DIMs might provide a solution to this, however this is known to cause other problems.

[jnm2]

I'm not entirely convinced that indices are very meaningful in the context of LINQ.

It would mirror ElementAt.

Would/should adding IndexOf to IReadOnlyList be covered by this also?

I think this was meant as "adding an IndexOf extension method to IReadOnlyList" because the interface loses its generic variance if it declares a method where T is passed in.

[eiriktsarpalis]

I'm not entirely convinced that indices are very meaningful in the context of LINQ.

It would mirror ElementAt.

Sure, but ElementAt accepts an index whereas FindIndex returns one, so I would expect this might encourage double enumerations.

Would/should adding IndexOf to IReadOnlyList be covered by this also?

I think this was meant as "adding an IndexOf extension method to IReadOnlyList" because the interface loses its generic variance if it declares a method where T is passed in.

Something like this?

namespace System.Collections.Generic
{
    public static class CollectionExtensions
    {
        public static int IndexOf<T>(this IReadOnlyList<T> readOnlyList, T element)
        {
            if (readOnlyList is IList<T> list)
            {
                return list.IndexOf(element);
            }

            for (int i = 0; i < readOnlyList.Count; i++)
            {
                if (element.Equals(readOnlyList[i]))
                {
                    return i;
                }
            }

            return -1;
        }
    }
}

[jnm2]

Double enumeration is a separate topic, but doesn't the premise of ElementAt already imply double enumeration? The index is usually gotten by some means rather than just being fixed at, say, 2.

Yes, that's pretty much the extension method I have, except mine uses EqualityComparer<T>.Default.Equals to avoid NRE.