ISAさんがかんがえたSortedList{T}を、ちょっと自分風に弄ってみたよSortedList{T}

ネタ元：
ぼくのかんがえたSortedList - こげこげ堂はてな支舗
http://d.hatena.ne.jp/isaisstillalive/20091022/1256188497

ISAさんがかんがえたSortedList{T}を、もうちょっと考えてみた

自分だったらこうするかなぁ的に、id:isaisstillaliveさんのコードにちょっと手を加えてみました。

主な変更点としては、

　　・初期要素コレクションを指定できるコンストラクタを追加
　　　初期化時に何度もSortが走るのは嫌だから
　　・RemoveItemメソッドもオーバーライドし、Sortするようにした
　　　SortedListとしてのソートの整合性を保つために必要
　　・Equalsメソッドのオーバーライドに関わる実装
　　　EqualsによるCollectionの比較は、多くの場合インスタンスを比較したいものではなく、
　　　Collectionの要素が等しいかを比較したいことの方が多いんじゃないのかなあ的な。
　　・IListインターフェイスに対する拡張メソッドの提供
　　　SortをListのSortメソッドに依存するのではなく、IListに対してComparisonでクイックソートできるようにした。

以下、コードです。

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

namespace ClassLibrary1
{
    /// <summary>
    /// ISAさんがかんがえたSortedList{T}を、ちょっと自分風に弄ってみたよSortedList{T}
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class SortedList<TValue> : Collection<TValue>
    {
        /// <summary>
        /// <para>ソート条件</para>
        /// <para>同じ型の 2 つのオブジェクトを比較するdelegate</para>
        /// </summary>
        private Comparison<TValue> _comparision;

        /// <summary>
        /// <para>コンストラクタ</para>
        /// </summary>
        /// <exception cref="NotImplementedException">TがIComparableまたはIComparable{T}を実装していない場合に発生</exception>
        public SortedList() : this(new List<TValue>()) {}

        /// <summary>
        /// <para>コンストラクタ</para>
        /// <para>初期化後、与えられたIList{T}をソートします。</para>
        /// </summary>
        /// <param name="list">初期要素コレクション</param>
        public SortedList(IList<TValue> list)
            : base(list)
        {
            Initialize();
            Sort();
        }

        /// <summary>
        /// <para>コンストラクタ</para>
        /// </summary>
        /// <param name="comparision">同じ型の 2 つのオブジェクトを比較するdelegate</param>
        public SortedList(Comparison<TValue> comparision)
            : base(new List<TValue>())
        {
            this._comparision = comparision;
        }

        /// <summary>
        /// <para>コンストラクタ</para>
        /// <para>初期化後、与えられたIList{T}をソートします。</para>
        /// </summary>
        /// <param name="list">初期要素コレクション</param>
        /// <param name="comparision"></param>
        public SortedList(IList<TValue> list, Comparison<TValue> comparision)
            : base(list)
        {
            this._comparision = comparision;
            Sort();
        }

        /// <summary>
        /// Collection{T} 内の指定したインデックスの位置に要素を挿入した後、ソートします。
        /// </summary>
        /// <param name="index"></param>
        /// <param name="item"></param>
        protected override void InsertItem(int index, TValue item)
        {
            base.InsertItem(index, item);
            Sort();
        }

        /// <summary>
        /// 指定したインデックス位置にある要素を置き換えた後、ソートします。
        /// </summary>
        /// <param name="index"></param>
        /// <param name="item"></param>
        protected override void SetItem(int index, TValue item)
        {
            base.SetItem(index, item);
            Sort();
        }

        /// <summary>
        /// 指定したインデックス位置にある要素の削除後、ソートします。
        /// </summary>
        /// <param name="index"></param>
        protected override void RemoveItem(int index)
        {
            base.RemoveItem(index);
            Sort();
        }

        /// <summary>
        /// <para>Equals override</para>
        /// <para>Comparisonが等しい且つ、すべての要素が等しいかどうかを取得します。</para>
        /// </summary>
        /// <param name="obj">比較対象</param>
        /// <returns></returns>
        public override bool Equals(object obj)
        {
            if (!(obj is SortedList<TValue>)) return false;
            return this.Equals((SortedList<TValue>)obj);
        }

        /// <summary>
        /// <para>タイプセーフなEquals</para>
        /// <para>Comparisonが等しい且つ、すべての要素が等しいかどうかを取得します。</para>
        /// </summary>
        /// <param name="other">比較対象</param>
        /// <returns></returns>
        public bool Equals(SortedList<TValue> other)
        {
            if (ReferenceEquals(other, null)) return false;
            if (this._comparision != other._comparision) return false;
            return this.Except(other).Count() == 0;
        }
        
        /// <summary>
        /// 指定したインスタンスが同一かどうかを取得します。
        /// </summary>
        /// <param name="other">比較対象</param>
        /// <returns></returns>
        public bool ReferenceEquals(object other)
        {
            return ReferenceEquals(this, other);
        }

        #region 演算子オーバーロード
        /// <summary>
        /// ==演算子オーバーロード
        /// </summary>
        /// <param name="self"></param>
        /// <param name="other"></param>
        /// <returns></returns>
        public static bool operator ==(SortedList<TValue> self, SortedList<TValue> other)
        {
            if (ReferenceEquals(self, null)) return false;
            if (ReferenceEquals(other, null)) return false;
            if (ReferenceEquals(self, other)) return true;
            return self.Equals(other);
        }

        /// <summary>
        /// !=演算子オーバーロード
        /// </summary>
        /// <param name="self"></param>
        /// <param name="other"></param>
        /// <returns></returns>
        public static bool operator !=(SortedList<TValue> self, SortedList<TValue> other)
        {
            return !self.Equals(other);
        }
        #endregion

        /// <summary>
        /// GetHashCode
        /// </summary>
        /// <returns></returns>
        public override int GetHashCode()
        {
            //XORしておけばよいでしょう。
            int result = ReferenceEquals(this, null) ? 0 : base.GetHashCode();
            result = result ^ (this._comparision == null ? 0 : this._comparision.GetHashCode());
            return result;
        }

        /// <summary>
        /// <para>初期処理</para>
        /// <para>要素のソートに必要なインターフェイスが実装されているかどうか確認する。</para>
        /// </summary>
        private void Initialize()
        {
            if (ExistInterface<IComparable<TValue>>())
            {
                this._comparision = (self, other) => ((IComparable<TValue>)self).CompareTo(other);
                return;
            }

            if (ExistInterface<IComparable>())
            {
                this._comparision = (self, other) => ((IComparable)self).CompareTo(other);
                return;
            }

            //C#4.0であれば、契約りたいところである。今のところはオ・ア・ズ・ケ。
            throw new NotImplementedException("型[" + typeof(TValue).Name + "]：このコンストラクタ呼び出しには、IComparable<T> または IComparable のいずれかが実装されている必要があります。");
        }

        /// <summary>
        /// 対象のインターフェイスが実装されているか否かを取得します。
        /// </summary>
        /// <typeparam name="TInterface">対象のインターフェイス</typeparam>
        /// <returns></returns>
        private bool ExistInterface<TInterface>()
        {
            return Array.Exists(typeof(TValue).GetInterfaces(), (t) => t == typeof(TInterface));
        }

        /// <summary>
        /// Collection{T}の要素をソートします。
        /// </summary>
        private void Sort()
        {
            Items.QuickSort<TValue>(_comparision, 0, Items.Count - 1);
        }
    }

    /// <summary>
    /// IList{T}の拡張メソッドを提供
    /// </summary>
    public static class IListGenericExtensions
    {
        /// <summary>
        /// パーティション分割
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">IList{T}</param>
        /// <param name="comparison">同じ型の 2 つのオブジェクトを比較するdelegate</param>
        /// <param name="x">軸要素として使用する開始データの番号</param>
        /// <param name="y">軸要素として使用する終了データの番号</param>
        /// <returns>軸要素となるデータの番号</returns>
        public static int Partition<T>(this IList<T> list, Comparison<T> comparison, int x, int y)
        {
            if (list == null) return 0;
            if (list.Count <= 0) return 0;
            if (x < 0) return 0;
            if (y > list.Count - 1) return 0;

            T pivot = list[x];
            while (x < y)
            {
                while (comparison(list[y], pivot) > 0 && x < y) y--;
                if (x != y) list[x++] = list[y];
                while (comparison(list[x], pivot) < 0 && x < y) x++;
                if (x != y) list[y--] = list[x];
            }
            list[x] = pivot;
            return x;
        }

        /// <summary>
        /// IList{T}についてクイックソートします。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">IList{T}</param>
        /// <param name="comparison">同じ型の 2 つのオブジェクトを比較するdelegate</param>
        /// <param name="x">軸要素として使用する開始データの番号</param>
        /// <param name="y">軸要素として使用する終了データの番号</param>
        public static void QuickSort<T>(this IList<T> list, Comparison<T> comparison, int x, int y)
        {
            var pivot = list.Partition(comparison, x, y);
            if (x < pivot) 
                list.QuickSort(comparison, x, pivot - 1);
            if (y > pivot) 
                list.QuickSort(comparison, pivot + 1, y);
        }
    }
}

C#4.0であれば、契約プログラミングをしたいところですが、
うちのへぼスペックPCでは、とても厳しいのでVS2010はまだ導入していません。
ということで、今のところはオ・ア・ズ・ケということに。
Windows7も出たことですし、そろそろ新しいのんの購入を検討しているところです。