星辰.Net技术社区论坛

2. 排序方向你希望ReversibleSortedList类中的元素是以TKey（键）的顺序进行存储的，并且它即可以从小排到大，也可以从大排到小。当然，最佳方式就是在添加元素时找到合适的位置插入，插入后元素就已经按顺序排好。在一个有序数组中查找合适的插入点这样的算法并不困难，但FCL已经帮我们实现了，而且是采用速度最快的二分查找法（在MSDN中被称为“二进制搜索法”）。太棒了！它就是：静态方法Array.BinarySearch。下面我们来看MSDN中对它的介绍。”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
Array.BinarySearch一共有8个重载版本，最后一个是我们需要的：”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
public static int BinarySearch<T> (”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    T[] array, //要搜索的从零开始的一维排序 Array”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
int index, //要搜索的范围的起始索引。”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
int length, //要搜索的范围的长度。”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    T value, //要搜索的对象。”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    IComparer<T> comparer //比较元素时要使用的 IComparer 实现。”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
)”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
  其中，T表示数组元素的类型。对返回值的介绍是：如果找到 value，则为指定 array 中的指定 value 的索引。如果找不到 value 且 value 小于 array 中的一个或多个元素，则为一个负数，该负数是大于 value 的第一个元素的索引的按位求补。如果找不到 value 且 value 大于 array 中的任何元素，则为一个负数，该负数是最后一个元素的索引加 1的按位求补。”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
我们的ReversibleSortedList不能插入重复的键值。当返回值大于或等于0时，表明不能插入。当返回值小于零时，表明没有找到重复键，而且这时返回值还带有插入位置的信息。考虑得可真周到啊，赞一个！”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
求补是什么呢？就是把二进制数的0变成1，1变成0。对于int来说，由于它是有符号整数，求补会把正数变为负数，把负数变为正数。对一个数进行两次求补运算就会得到原来的数。哈哈，如果反回值小于0，对它求补就可以得到插入位置信息了。真是得来全不费工夫！”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
现在的问题是需要一个实现了[url=ms-help://MS.MSDNQTR.v80.chs/MS.MSDN.v80/MS.NETDEVFX.v20.chs/cpref2/html/T_System_Collections_Generic_IComparer%601.htm]IComparer[/url]<T>接口的类。可以在ReversibleSortedList声明一个嵌套类以解决这个问题。当然，在实现[url=ms-help://MS.MSDNQTR.v80.chs/MS.MSDN.v80/MS.NETDEVFX.v20.chs/cpref2/html/T_System_Collections_Generic_IComparer%601.htm]IComparer[/url]<T>接口的Compare方法时在里面做些手脚就可以实现正向和反向排序了。这时需要一个能表示正向和反向排序的东西，FCL里有现成的，它就是System.ComponentModel命名空间下的 ListSortDirection枚举。它有两个值：Ascending表示升序，Descending表示降序。下面的代码在1.0版本的基础上添加了实现[url=ms-help://MS.MSDNQTR.v80.chs/MS.MSDN.v80/MS.NETDEVFX.v20.chs/cpref2/html/T_System_Collections_Generic_IComparer%601.htm]IComparer[/url]<T>接口的内部类：SortDirectionComparer<T>。代码可直接拷贝运行，运行它纯粹是为了检查是否有错误，没有什么看得见的效果。”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
  ReversibleSortedList 0.2版本：添加了实现[url=ms-help://MS.MSDNQTR.v80.chs/MS.MSDN.v80/MS.NETDEVFX.v20.chs/cpref2/html/T_System_Collections_Generic_IComparer%601.htm]IComparer[/url]<T>接口的内部类”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
using System;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
using System.Collections;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
using System.Collections.Generic;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
using System.ComponentModel;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
public class ReversibleSortedList<TKey, TValue>”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
{”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    #region 成员变量”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    private TKey[] keys=new TKey[0]; //键数组”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    private TValue[] values; //值数组”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    private static TKey[] emptyKeys;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    private static TValue[] emptyValues;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    #endregion”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    #region 构造方法”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    //类型构造器”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    static ReversibleSortedList()”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    {”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        ReversibleSortedList<TKey, TValue>.emptyKeys = new TKey[0];”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        ReversibleSortedList<TKey, TValue>.emptyValues = new TValue[0];”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    public ReversibleSortedList()”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    {”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        this.keys = ReversibleSortedList<TKey, TValue>.emptyKeys;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        this.values = ReversibleSortedList<TKey, TValue>.emptyValues;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    #endregion”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    #region 公有属性”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    public int Capacity //容量属性”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    {”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        get”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        {”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
            return this.keys.Length;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    #endregion”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    #region SortDirectionComparer类定义”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    public class SortDirectionComparer<T> : IComparer<T>”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    {  //ListSortDirection 枚举，有两个值：”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        //Ascending按升序排列，Descending按降序排列”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        private System.ComponentModel.ListSortDirection _sortDir;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        //构造方法”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        public SortDirectionComparer() ”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        {  //默认为升序”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
            _sortDir = ListSortDirection.Ascending;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        //可指定排序方向的构造方法”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        public SortDirectionComparer(ListSortDirection sortDir)”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        {”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
            _sortDir = sortDir;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        //排序方向属性”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        public System.ComponentModel.ListSortDirection SortDirection”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        {”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
            get { return _sortDir; }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
            set { _sortDir = value; }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        //实现IComparer<T>接口的方法”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        public int Compare(T lhs, T rhs)”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        {”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
            int compareResult =”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
                lhs.ToString().CompareTo(rhs.ToString());”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
            // 如果是降序，则反转.”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
            if (SortDirection == ListSortDirection.Descending)”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
                compareResult *= -1;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
            return compareResult;”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    #endregion”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
}”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
public class Test”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
{”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    static void Main()”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    {”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        ReversibleSortedList<int, string> rs=new ReversibleSortedList<int, string>();”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
        Console.WriteLine(rs.Capacity);”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
    }”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
}”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u
”n‹ƒÞwww.netcsharp.cn[„Ç0¯–~u