C#: How to implement IOrderedEnumerable<T>

Question

I want to implement some various algorithms for practice, just to see how bad I really am and to get better :p

Anyways, I thought I would try to use IEnumerable<T> and IOrderedEnumerable<T> and other .Net collection types just to be compatible (so that what I write can be used more easily later).

But I can't find a way to return an instance of IOrderedEnumerable<T> other than using the OrderBy and ThenBy extension methods. So I guess I have to create my own class that implements this interface. But the interface doesn't quite make sense to me to be honest. It might, but I'm not sure.

I created an empty class, added the interface and then got ReSharper to add empty implementations for me. It looks like this:

class MyOrderedEnumerable<T> : IOrderedEnumerable<T>
{
    /// <summary>
    /// Performs a subsequent ordering on the elements of an <see cref="T:System.Linq.IOrderedEnumerable`1"/> according to a key.
    /// </summary>
    /// <returns>
    /// An <see cref="T:System.Linq.IOrderedEnumerable`1"/> whose elements are sorted according to a key.
    /// </returns>
    /// <param name="keySelector">The <see cref="T:System.Func`2"/> used to extract the key for each element.</param><param name="comparer">The <see cref="T:System.Collections.Generic.IComparer`1"/> used to compare keys for placement in the returned sequence.</param><param name="descending">true to sort the elements in descending order; false to sort the elements in ascending order.</param><typeparam name="TKey">The type of the key produced by <paramref name="keySelector"/>.</typeparam><filterpriority>2</filterpriority>
    public IOrderedEnumerable<T> CreateOrderedEnumerable<TKey>(Func<T, TKey> keySelector, IComparer<TKey> comparer, bool descending)
    {
        throw new NotImplementedException();
    }

    /// <summary>
    /// Returns an enumerator that iterates through the collection.
    /// </summary>
    /// <returns>
    /// A <see cref="T:System.Collections.Generic.IEnumerator`1"/> that can be used to iterate through the collection.
    /// </returns>
    /// <filterpriority>1</filterpriority>
    public IEnumerator<T> GetEnumerator()
    {
        throw new NotImplementedException();
    }

    /// <summary>
    /// Returns an enumerator that iterates through a collection.
    /// </summary>
    /// <returns>
    /// An <see cref="T:System.Collections.IEnumerator"/> object that can be used to iterate through the collection.
    /// </returns>
    /// <filterpriority>2</filterpriority>
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

What I don't understand is the CreateOrderedEnumerable method. What exactly is it meant to do? Well, I guess it of course would create an ordered enumerable, but how? Is the sorting algorithm itself supposed to go in there? And what will it sort? There is no collection of items going in to that method, so where is it meant to get the collection to order? How would you use the class? Is it meant to be implemented as for example a private helper class inside something that needs to sort stuff? So instead of a MyOrderedEnumerable<T> : IOrderedEnumerable<T>, you would have a QuickSorter<T> : IOrderedEnumerable<T> that took a collection in its constructor and sorted it when that CreateOrderedEnumerable method was called... but what would then happen if someone called GetEnumerator and started to enumerate before that method had been called?

Anyone have a clue?

---

Haha, just discovered I had asked something similar a while ago here. But that was just about if it was possible to return one. So I guess this question is a response to the one answer I got there =)

Answer 1

I have a sample implementation you could look at. It's not designed to be efficient by any means, but it should get you started.

Basically an IOrderedEnumerable<T> just needs to have an idea of its current ordering, so it can create a new one. Assuming you already have an IComparer<T> you build a new one by saying something like:

int Compare(T first, T second)
{
    if (baseComparer != null)
    {
        int baseResult = baseComparer.Compare(first, second);
        if (baseResult != 0)
        {
            return baseResult;
        }
    }
    TKey firstKey = keySelector(first);
    TKey secondKey = keySelector(second);

    return comparer.Compare(firstKey, secondKey);        
}

So basically you create a chain of comparers going from the "least significant" up to the "most significant". You also need to put the "descending" bit in there, but that's easy :)

In the sample linked above, the three different aspects are represented in three different classes already present in MiscUtil:

• ReverseComparer: reverses an existing IComparer<T>'s results
• LinkedComparer: creates one comparer from two, with one master and one slave
• ProjectionComparer: creates a comparer based on a projection from the original items to keys, delegating to another comparer to compare those keys.

Comparers are great for chaining together like this.