Implementation of OrderBy and ThenBy

MyExtensionMethod.cs

// implement OrderBy and ThenBy
// reference1: http://msmvps.com/blogs/jon_skeet/archive/2011/01/04/reimplementing-linq-to-objects-part-26a-iorderedenumerable.aspx
// reference2: http://msmvps.com/blogs/jon_skeet/archive/2011/01/05/reimplementing-linq-to-objects-part-26b-orderby-descending-thenby-descending.aspx

using System;
using System.Collections.Generic;
using System.Linq;

namespace OrderByAndThenBySample
{
    #region ExtensionMethod

    public static class MyExtensionMethod
    {
        public static IOrderedEnumerable<TSource> MyOrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
        {
            return MyOrderBy(source, keySelector, Comparer<TKey>.Default);
        }

        public static IOrderedEnumerable<TSource> MyThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector)
        {
            return MyThenBy(source, keySelector, Comparer<TKey>.Default);
        }

        /// <summary>
        /// 把這一次OrderBy的comparer加入MyOrderedEnumerable()中存著，以待後續若還有ThenBy()，可以將comparer結合起來
        /// 當外部展開MyOrderBy的結果時，則會呼叫MyOrderedEnumerable的GetEnumrator()，則會執行排序演算法
        /// </summary>
        /// <typeparam name="TSource">The type of the source.</typeparam>
        /// <typeparam name="TKey">The type of the key.</typeparam>
        /// <param name="source">The source.</param>
        /// <param name="keySelector">The key selector.</param>
        /// <param name="comparer">The comparer.</param>
        /// <returns></returns>
        /// <exception cref="System.ArgumentException">source</exception>
        public static IOrderedEnumerable<TSource> MyOrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            if (source == null)
            {
                throw new ArgumentException("source");
            }

            return new MyOrderedEnumerable<TSource>(source, new ProjectKeyToElementComparer<TSource, TKey>(keySelector, comparer));
        }

        /// <summary>
        /// 從OrderBy()的部份可以看到，現在的source已經是MyOrderedEnumerable的結構了。裡面已經存放著先前的comparer。
        /// 在MyOrderedEnumerable.CreateOrderedEnumerable()方法中，則會再將這一次ThenBy()的Comparer加入。
        /// 讓實際在排序中比較大小時，
        /// </summary>
        /// <typeparam name="TSource">The type of the source.</typeparam>
        /// <typeparam name="TKey">The type of the key.</typeparam>
        /// <param name="source">The source.</param>
        /// <param name="keySelector">The key selector.</param>
        /// <param name="comparer">The comparer.</param>
        /// <returns></returns>
        /// <exception cref="System.ArgumentException">source</exception>
        public static IOrderedEnumerable<TSource> MyThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            if (source == null)
            {
                throw new ArgumentException("source");
            }

            return source.CreateOrderedEnumerable(keySelector, comparer, false);
        }
    }

    #endregion ExtensionMethod

    #region 輔助的class

    /// <summary>
    /// 實作IOrderedEnumerable(T)，用來結合截至目前為止的compare，與這一次要加入的comparer
    /// 當延遲執行時，才在GetEnumerator中，執行排序演算法。
    /// 排序演算法中比較大小的原則是，先用第一個comparer比，比不出來再比下一個，直到比完為止。
    /// </summary>
    /// <typeparam name="TSource">The type of the source.</typeparam>
    public class MyOrderedEnumerable<TSource> : IOrderedEnumerable<TSource>
    {
        private IEnumerable<TSource> _source;
        private IComparer<TSource> _untilNowComparer;

        /// <summary>
        /// Initializes a new instance of the <see cref="MyOrderedEnumerable{TSource}"/> class.
        /// </summary>
        /// <param name="source">The source.</param>
        /// <param name="comparer">目前為止的comparer</param>
        public MyOrderedEnumerable(IEnumerable<TSource> source, IComparer<TSource> comparer)
        {
            this._source = source;
            this._untilNowComparer = comparer;
        }

        /// <summary>
        /// 要把之前所有的comparer跟這一次的comparer包起來，因為需要先比前面的comparer, 比不出來再用這次的comparer比。
        /// </summary>
        /// <typeparam name="TKey">The type of the key.</typeparam>
        /// <param name="keySelector">The key selector.</param>
        /// <param name="comparer">這一次ThenBy的comparer</param>
        /// <param name="descending">if set to <c>true</c> [descending].</param>
        /// <returns></returns>
        public IOrderedEnumerable<TSource> CreateOrderedEnumerable<TKey>(Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending)
        {
            IComparer<TSource> thisTimeComparer = new ProjectKeyToElementComparer<TSource, TKey>(keySelector, comparer);
            var comboComparer = new ComboComparer<TSource>(this._untilNowComparer, thisTimeComparer);

            return new MyOrderedEnumerable<TSource>(this._source, comboComparer);
        }

        /// <summary>
        /// 當延遲執行時 (如foreach或ToList展開MyOrderedEnumerable物件)，實作排序演算法，逐次將最小的element回傳出來
        /// </summary>
        /// <returns>目前最小的element</returns>
        public IEnumerator<TSource> GetEnumerator()
        {
            // 可以實作任何排序演算法，目前為 bubble sort, O(n^2), it's suck, but it works
            List<TSource> elements = this._source.ToList();
            while (elements.Count > 0)
            {
                TSource minElement = elements[0];
                int minIndex = 0;
                for (int i = 1; i < elements.Count; i++)
                {
                    // 比較大小的關鍵，使用IComparer的Compare()來決定大小
                    // 遞迴展開，這邊的_untilNowComparer基本上型別應為ComboComparer，也就是有兩組以上的comparer
                    if (this._untilNowComparer.Compare(elements[i], minElement) < 0)
                    {
                        minElement = elements[i];
                        minIndex = i;
                    }
                }
                elements.RemoveAt(minIndex);
                yield return minElement;
            }
        }

        /// <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>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }

    /// <summary>
    /// 傳TSource進來，TSource透過keySelector取得key，也就是要比較的值
    /// 透過IComparer(TKey)來比較兩個TSource
    /// 目的是讓不同的IComparer(TKey)，都可以變成相同的IComparer(TSource)
    /// </summary>
    /// <typeparam name="TSource">The type of the source.</typeparam>
    /// <typeparam name="TKey">The type of the key.</typeparam>
    public class ProjectKeyToElementComparer<TSource, TKey> : IComparer<TSource>
    {
        private Func<TSource, TKey> _keySelector;
        private IComparer<TKey> _comparer;

        public ProjectKeyToElementComparer(Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            this._keySelector = keySelector;
            this._comparer = comparer;
        }

        public int Compare(TSource x, TSource y)
        {
            var xKey = this._keySelector(x);
            var yKey = this._keySelector(y);

            var result = this._comparer.Compare(xKey, yKey);
            return result;
        }
    }

    /// <summary>
    /// 自己組合兩個comparer, 透過decorator來無限組合n個comparer。
    /// 當外面使用IComparer(T).Compare()時，則會依序比較，直到所有comparer比完為止。
    /// </summary>
    /// <typeparam name="TSource">The type of the source.</typeparam>
    public class ComboComparer<TSource> : IComparer<TSource>
    {
        private IComparer<TSource> _untilNowComparer;
        private IComparer<TSource> _thisTimeComparer;

        public ComboComparer(IComparer<TSource> untilNowComparer, IComparer<TSource> thisTimeComparer)
        {
            this._untilNowComparer = untilNowComparer;
            this._thisTimeComparer = thisTimeComparer;
        }

        /// <summary>
        /// 先比之前的comparer, 比不出來的話，再比這一次的comparer
        /// </summary>
        /// <param name="x">The x.</param>
        /// <param name="y">The y.</param>
        /// <returns></returns>
        public int Compare(TSource x, TSource y)
        {
            var untilNowComparerResult = this._untilNowComparer.Compare(x, y);
            if (untilNowComparerResult != 0)
            {
                return untilNowComparerResult;
            }

            return this._thisTimeComparer.Compare(x, y);
        }
    }

    #endregion 輔助的class
}

TestOrderByWithComparer.cs

using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using OrderByAndThenBySample;

namespace TestOrderByAndThenBySample
{
    [TestClass]
    public class TestOrderByWithComparer
    {
        [TestMethod]
        public void TestOrderBy_Father_And_ThenBy_Son_ThenBy_Cars_With_Comparer()
        {
            var candidates = GetCandidates();

            var result = candidates
                .MyOrderBy(x => x.Father, new FatherComparer())
                .MyThenBy(x => x.Son, new SonComparer())
                .MyThenBy(x => x.Cars, new CarsComparer())
                .ToList();

            Assert.AreEqual(result.Count, 4);

            Assert.AreEqual(result[0].Id, 3);
            Assert.AreEqual(result[1].Id, 2);
            Assert.AreEqual(result[2].Id, 4);
            Assert.AreEqual(result[3].Id, 1);
        }

        private IEnumerable<Canadidate> GetCandidates()
        {
            var result = new List<Canadidate>
            {
                new Canadidate
                {
                    Id=1,
                    Father = new Father{Money=200},
                    Son = new Son{Height = 180},
                    Cars = new List<Car> { new Car{Price=100}},
                },

                new Canadidate
                {
                    Id=2,
                    Father = new Father{Money=100},
                    Son = new Son{Height = 190},
                    Cars = new List<Car> { new Car{Price=60}, new Car{Price=60}},
                },

                new Canadidate
                {
                    Id=3,
                    Father = new Father{Money=100},
                    Son = new Son{Height = 170},
                    Cars = new List<Car> { new Car{Price=50},new Car{Price=50}},
                },

                new Canadidate
                {
                    Id=4,
                    Father = new Father{Money=200},
                    Son = new Son{Height = 180},
                    Cars = new List<Car> { new Car{ Price=20}, new Car{Price=20}},
                },
            };

            return result;
        }
    }

    public class Canadidate
    {
        public int Id { get; set; }

        public Father Father { get; set; }

        public Son Son { get; set; }

        public List<Car> Cars { get; set; }
    }

    public class Father
    {
        public int Money { get; set; }
    }

    public class Son
    {
        public int Height { get; set; }
    }

    public class SonComparer : IComparer<Son>
    {
        public int Compare(Son x, Son y)
        {
            return x.Height.CompareTo(y.Height);
        }
    }

    public class FatherComparer : IComparer<Father>
    {
        public int Compare(Father x, Father y)
        {
            return x.Money.CompareTo(y.Money);
        }
    }

    public class Car
    {
        public int Price { get; set; }
    }

    public class CarsComparer : IComparer<List<Car>>
    {
        public int Compare(List<Car> x, List<Car> y)
        {
            var xValue = x.Sum(car => car.Price);
            var yValue = y.Sum(car => car.Price);

            return xValue.CompareTo(yValue);
        }
    }
}

TestOrderByWithoutComparer.cs

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using OrderByAndThenBySample;

namespace TestOrderByAndThenBySample
{
    [TestClass]
    public class TestOrderByWithoutComparer
    {
        [TestMethod]
        public void TestOrderByName()
        {
            var employees = GetEmployees();

            var employeesOrderByName = employees.MyOrderBy(x => x.Name).ToList();

            Assert.AreEqual(employeesOrderByName.Count, 4);

            Assert.AreEqual(employeesOrderByName[0].Id, 1);
            Assert.AreEqual(employeesOrderByName[1].Id, 2);
            Assert.AreEqual(employeesOrderByName[2].Id, 4);
            Assert.AreEqual(employeesOrderByName[3].Id, 3);
        }

        [TestMethod]
        public void Test_OrderBy_Age_And_ThenBy_Salary()
        {
            var employees = GetEmployees();            

            var employeesOrderByName = employees
                .MyOrderBy(x => x.Age)
                .MyThenBy(x => x.Salary)
                .MyThenBy(x=>x.Name)
                .ToList();

            Assert.AreEqual(employeesOrderByName.Count, 4);

            Assert.AreEqual(employeesOrderByName[0].Id, 2);
            Assert.AreEqual(employeesOrderByName[1].Id, 1);
            Assert.AreEqual(employeesOrderByName[2].Id, 4);
            Assert.AreEqual(employeesOrderByName[3].Id, 3);
        }

        private IEnumerable<Employee> GetEmployees()
        {
            var result = new List<Employee>
            {
                new Employee{ Id = 1, Salary = 300, Name = "Apple", Age =10},
                new Employee{ Id = 2, Salary = 200, Name = "Bob", Age =10},
                new Employee{ Id = 3, Salary = 100, Name = "Dog", Age =30},
                new Employee{ Id = 4, Salary = 100, Name = "Cat", Age =30},
            };

            return result;
        }
    }

    public class Employee
    {
        public int Id { get; set; }

        public int Salary { get; set; }

        public string Name { get; set; }

        public int Age { get; set; }
    }
}