linq way to insert element in order

Question

hello,

i have a collection of elements sorted by the elements' Name property. i need to insert a new element into the collection while maintaining the order. i am looking for a concise LINQ way to do this. my code is below. "this.Children" is the collection, and "d" is the new element that i need to insert. it takes two passes over the collection to find the insertion point. is there a way to get the index from the First() extension method? (please do not suggest using foreach, i know that :), i am learning LINQ).

thanks! konstantin

var v = this.Children.FirstOrDefault(x => string.Compare(x.Name, d.Name) > 0);
int index = this.Children.IndexOf(v);

if (index < 0)
{
    this.children.Add(d);
}
else
{
    this.Children.Insert(index, d);
}

Answer 1

Yes, using the overload of Select which includes the index as well as the value:

var pair = this.Children
               .Select((value, index) => new { value, index })
               .FirstOrDefault(x => string.Compare(x.value.Name, d.Name) > 0);

if (pair == null)
{
    Children.Add(d);
}
else
{
    Children.Insert(pair.index, d);
}

Note that this is still inefficient though - if you already know the values are sorted, you can use a binary chop to find out the insertion index. It's hard to give sample code for that without knowing the type of Children though... there's already List<T>.BinarySearch and Array.BinarySearch.

Learning LINQ is admirable - but it's also important to learn when using LINQ isn't the best way to go :)

Answer 2

Assuming that this.Children is a List<T>, you can use List<T>.BinarySearch with a custom comparer to efficiently find the position to insert the new element at:

IComparer<Foo> comparer = AnonymousComparer.Create<Foo>(
    (x, y) => string.Compare(x.Name, y.Name));

int index = this.Children.BinarySearch(d, comparer);
if (index < 0) index = ~index;
this.Children.Insert(index, d);

with

static class AnonymousComparer
{
    public static IComparer<T> Create<T>(Func<T, T, int> comparer)
    {
        if (comparer == null) { throw new ArgumentNullException("comparer"); }
        return new TheComparer<T>(comparer);
    }
    private class TheComparer<T> : IComparer<T>
    {
        private readonly Func<T, T, int> c;
        public TheComparer(Func<T, T, int> c) { this.c = c; }
        int IComparer<T>.Compare(T x, T y) { return this.c(x, y); }
    }
}

Answer 3

Well, you could always just use OrderBy after adding the new element...

var v = this.Children.Union(new List<TypeOfChildren>() { d }).OrderBy<TypeOfChildren, string>(x => x.Name).ToList<TypeOfChildren>();