構建可反轉排序的泛型字典類(2)--排序方向

2. 排序方向

你希望ReversibleSortedList類中的元素是以TKey（鍵）的順序進行存儲的，並且它即可以從小排到大，也可以從大排到小。當然，最佳方式就是在添加元素時找到合適的位置插入，插入後元素就已經按順序排好。在一個有序數組中查找合適的插入點這樣的算法並不困難，但FCL已經幫我們實現了，而且是采用速度最快的二分查找法（在MSDN中被稱為“二進制搜索法”）。太棒了！它就是：靜態方法Array.BinarySearch。下面我們來看MSDN中對它的介紹。

Array.BinarySearch一共有8個重載版本，最後一個是我們需要的：

public static int BinarySearch<T> (
　　T[] array, //要搜索的從零開始的一維排序 Array
　　int index, //要搜索的范圍的起始索引。
　　int length, //要搜索的范圍的長度。
　　T value, //要搜索的對象。
　　IComparer<T> comparer //比較元素時要使用的 IComparer 實現。
)

其中，T表示數組元素的類型。對返回值的介紹是：如果找到 value，則為指定 array 中的指定 value 的索引。如果找不到 value 且 value 小於 array 中的一個或多個元素，則為一個負數，該負數是大於 value 的第一個元素的索引的按位求補。如果找不到 value 且 value 大於 array 中的任何元素，則為一個負數，該負數是最後一個元素的索引加 1的按位求補。

我們的ReversibleSortedList不能插入重復的鍵值。當返回值大於或等於0時，表明不能插入。當返回值小於零時，表明沒有找到重復鍵，而且這時返回值還帶有插入位置的信息。考慮得可真周到啊，贊一個！

求補是什麼呢？就是把二進制數的0變成1，1變成0。對於int來說，由於它是有符號整數，求補會把正數變為負數，把負數變為正數。對一個數進行兩次求補運算就會得到原來的數。哈哈，如果反回值小於0，對它求補就可以得到插入位置信息了。真是得來全不費工夫！

現在的問題是需要一個實現了IComparer<T>接口的類。可以在ReversibleSortedList聲明一個嵌套類以解決這個問題。當然，在實現IComparer<T>接口的Compare方法時在裡面做些手腳就可以實現正向和反向排序了。這時需要一個能表示正向和反向排序的東西，FCL裡有現成的，它就是System.ComponentModel命名空間下的 ListSortDirection枚舉。它有兩個值：Ascending表示升序，Descending表示降序。下面的代碼在1.0版本的基礎上添加了實現IComparer<T>接口的內部類：SortDirectionComparer<T>。代碼可直接拷貝運行，運行它純粹是為了檢查是否有錯誤，沒有什麼看得見的效果。

ReversibleSortedList 0.2版本：添加了實現IComparer<T>接口的內部類

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;

public class ReversibleSortedList<TKey, TValue>
{
　　#region 成員變量
　　private TKey[] keys=new TKey[0]; //鍵數組
　　private TValue[] values; //值數組
　　private static TKey[] emptyKeys;
　　private static TValue[] emptyValues;
　　#endregion
　　#region 構造方法
　　//類型構造器
　　static ReversibleSortedList()
　　{
　　　　ReversibleSortedList<TKey, TValue>.emptyKeys = new TKey[0];
　　　　ReversibleSortedList<TKey, TValue>.emptyValues = new TValue[0];
　　}
　　public ReversibleSortedList()
　　{
　　　　this.keys = ReversibleSortedList<TKey, TValue>.emptyKeys;
　　　　this.values = ReversibleSortedList<TKey, TValue>.emptyValues;
　　}
　　#endregion
　　#region 公有屬性
　　public int Capacity //容量屬性
　　{
　　　　get
　　　　{
　　　　　　return this.keys.Length;
　　　　}
　　}
　　#endregion
　　#region SortDirectionComparer類定義
　　public class SortDirectionComparer<T> : IComparer<T>
　　{　 //ListSortDirection 枚舉，有兩個值：
　　　　//Ascending按升序排列，Descending按降序排列
　　　　private System.ComponentModel.ListSortDirection _sortDir;
　　　　//構造方法
　　　　public SortDirectionComparer()
　　　　{　 //默認為升序
　　　　　　_sortDir = ListSortDirection.Ascending;
　　　　}
　　　　//可指定排序方向的構造方法
　　　　public SortDirectionComparer(ListSortDirection sortDir)
　　　　{
　　　　　　_sortDir = sortDir;
　　　　}
　　　　//排序方向屬性
　　　　public System.ComponentModel.ListSortDirection SortDirection
　　　　{
　　　　　　get { return _sortDir; }
　　　　　　set { _sortDir = value; }
　　　　}
　　　　//實現IComparer<T>接口的方法
　　　　public int Compare(T lhs, T rhs)
　　　　{
　　　　　　int compareResult =
　　　　　　　　lhs.ToString().CompareTo(rhs.ToString());
　　　　　　// 如果是降序，則反轉.
　　　　　　if (SortDirection == ListSortDirection.Descending)
　　　　　　　　compareResult *= -1;
　　　　　　return compareResult;
　　　　}
　　}
　　#endregion
}
public class Test
{
　　static void Main()
　　{
　　　　ReversibleSortedList<int, string> rs=new ReversibleSortedList<int, string>();
　　　　Console.WriteLine(rs.Capacity);
　　}
}