当前位置导航:炫浪网>>网络学院>>网页制作>>XML/WebService教程

构建可反转排序泛型字典类(2)--排序方向

2. 排序方向

你希望ReversibleSortedList类中的元素是以TKey(键)的顺序进行存储的,并且它即可以从小排到大,也可以从大排到小。当然,最佳方式就是在添加元素时找到合适的位置插入,插入后元素就已经按顺序排好。在一个有序数组中查找合适的插入点这样的算法并不困难,但FCL已经帮我们实现了,而且是采用速度最快的二分查找法(在MSDN中被称为“二进制搜索法”)。太棒了!它就是:静态方法Array.BinarySearch。下面我们来看MSDN中对它的介绍。

Array.BinarySearch一共有8个重载版本,最后一个是我们需要的:


public static int BinarySearch (
T[] array, //要搜索的从零开始的一维排序 Array
int index, //要搜索的范围的起始索引。
int length, //要搜索的范围的长度。
T value, //要搜索的对象。
IComparer comparer //比较元素时要使用的 IComparer 实现。
)

其中,T表示数组元素的类型。对返回值的介绍是:如果找到 value,则为指定 array 中的指定 value 的索引。如果找不到 value 且 value 小于 array 中的一个或多个元素,则为一个负数,该负数是大于 value 的第一个元素的索引的按位求补。如果找不到 value 且 value 大于 array 中的任何元素,则为一个负数,该负数是最后一个元素的索引加 1的按位求补。

我们的ReversibleSortedList不能插入重复的键值。当返回值大于或等于0时,表明不能插入。当返回值小于零时,表明没有找到重复键,而且这时返回值还带有插入位置的信息。考虑得可真周到啊,赞一个!

求补是什么呢?就是把二进制数的0变成1,1变成0。对于int来说,由于它是有符号整数,求补会把正数变为负数,把负数变为正数。对一个数进行两次求补运算就会得到原来的数。哈哈,如果反回值小于0,对它求补就可以得到插入位置信息了。真是得来全不费工夫!

现在的问题是需要一个实现了IComparer接口的类。可以在ReversibleSortedList声明一个嵌套类以解决这个问题。当然,在实现IComparer接口的Compare方法时在里面做些手脚就可以实现正向和反向排序了。这时需要一个能表示正向和反向排序的东西,FCL里有现成的,它就是System.ComponentModel命名空间下的 ListSortDirection枚举。它有两个值:Ascending表示升序,Descending表示降序。下面的代码在1.0版本的基础上添加了实现IComparer接口的内部类:SortDirectionComparer。代码可直接拷贝运行,运行它纯粹是为了检查是否有错误,没有什么看得见的效果。


ReversibleSortedList 0.2版本:添加了实现IComparer接口的内部类


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

public class ReversibleSortedList
{
#region 成员变量
private TKey[] keys=new TKey[0]; //键数组
private TValue[] values; //值数组
private static TKey[] emptyKeys;
private static TValue[] emptyValues;
#endregion
#region 构造方法
//类型构造器
static ReversibleSortedList()
{
ReversibleSortedList.emptyKeys = new TKey[0];
ReversibleSortedList.emptyValues = new TValue[0];
}
public ReversibleSortedList()
{
this.keys = ReversibleSortedList.emptyKeys;
this.values = ReversibleSortedList.emptyValues;
}
#endregion
#region 公有属性
public int Capacity //容量属性
{
get
{
return this.keys.Length;
}
}
#endregion
#region SortDirectionComparer类定义
public class SortDirectionComparer : IComparer
{ //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接口的方法
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 rs=new ReversibleSortedList();
Console.WriteLine(rs.Capacity);
}
}

相关内容
赞助商链接