构建可反转排序的泛型字典类(3)--实现元素添加及自动扩展

admin - 2008-6-16 18:38:00

3. 实现元素添加及自动扩展您是一单位CEO，单位占地50亩，这几年在你的带领下，公司不断发展壮大，原来50亩地已经不够用。公司急需扩大地盘，这个现实问题摆在你面前，该怎么办？到旁边单位抢地？不行，现在是法制社会。有两个解决方案，第一是买一块50亩的地，这样你的公司就有两个办公地点，缺点是不能统一管理，两个地点的员工交流不顺畅。第二是买一块100亩的地，把原来的地卖掉，公司全部搬到新地点。这样做的缺点是重建费用太大。
我们要构建的ReversibleSortedList集合也面临着这样的问题，由于使用数组存放数据，数组的空间一旦确定就不能再改变。这一次我们选择了第二种方案，原因很简单，内存间成片数据的拷贝速度非常快，不耗费什么成本。既然搬家费用不高，有什么理由把公司一分为二呢？
ReversibleSortedList中的方案是，初始空间为0，当有元素添加时，空间增长为4，每当添加新元素时，如果现有空间已满，则另开辟一块大小为原来2倍的空间，把原来的数据拷贝到新空间后再添加新元素。当然，原来存放数据的空间这时就变成了待回收的垃圾。
由于数组的长度只能代表ReversibleSortedList的存储空间，并不能表示当前元素个数，所以需要使用一个成员变量来表示当前元素个数：

private int _size; //表示元素个数

public int Count //属性，表示当前元素个数
{
get
{
return this._size;
}
}

前面声明的SortDirectionComparer<T>内部类也需要进行初始化：
private SortDirectionComparer<TKey> _sortDirectionComparer = null;
注意，这里把TKey做为类型参数传递给SortDirectionComparer<T>，TKey本身也是一个类型参数。
在无参实例构造方法中对它们进行初始化：
this._size = 0;

this._sortDirectionComparer = new SortDirectionComparer<TKey>();
剩下的就是插入数据的方法，共有1个公方法：Add，3个私有方法：Insert、EnsureCapacity、InternalSetCapacity。具体的方法代码请参考稍后的ReversibleSortedList 0.3版本。关于以上几个方法的算法及作用，请参考代码中的注释。这里讲一下添加数据的过程，如图1所示，首先利用Array.BinarySearch查找到插入点，然后把插入点及其后元素向后移动一个位置，最后在插入点插入数据。这里有一点需要明确，任何时候，数据在内存中都是以有序的方法排列的。
为了对程序进行测试，添加了一个Print方法用于打印数组中的元素。代码测试成功后可以把它删除。并且在Main()方法中依次添加9个元素并在期间打印数组元素进行观察。

ReversibleSortedList 0.3版本：添加数据（以下代码可直接拷贝并运行）

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;
private SortDirectionComparer<TKey> _sortDirectionComparer = null;
private int _size; //表示元素个数
#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;
this._size = 0;
this._sortDirectionComparer = new SortDirectionComparer<TKey>();
}
#endregion
#region 公有属性
public int Capacity //容量属性
{
get
{
return this.keys.Length;
}
}
public int Count //当前元素个数
{
get
{
return this._size;
}
}
#endregion
#region 公有方法
//添加元素
public void Add(TKey key, TValue value)
{
if (key.Equals(null))
{
throw new ArgumentNullException("key");
}
//使用二分查找法搜索将插入的键
int num1 = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this._sortDirectionComparer);
if (num1 >= 0) //如果数组中已存在将插入的键
{
throw new ArgumentException("尝试添加重复值！");
}
this.Insert(~num1, key, value); //在插入点插入键和值
}
public void Print() //只用于测试
{
for(int i=0;i<_size;i++)
{
Console.WriteLine("key:{0} value:{1}",keys,values);
}
}
#endregion
#region 私有方法
private void Insert(int index, TKey key, TValue value)
{ //在指定索引入插入数据
if (this._size == this.keys.Length)
{
this.EnsureCapacity(this._size + 1);
}
if (index < this._size)
{ //当插入元素不是添加在未尾时，移动插入点后面的元素
Array.Copy(this.keys, index, this.keys, (int)(index + 1),
(int)(this._size - index));
Array.Copy(this.values, index, this.values, (int)(index + 1),
(int)(this._size - index));
}
this.keys[index] = key; //在插入点插入键
this.values[index] = value; //在插入点插入值
this._size++;
}
private void EnsureCapacity(int min) //确保当前容量
{ //如果当前容量为，则增长为，否则翻倍
int num1 = (this.keys.Length == 0) ? 4 : (this.keys.Length * 2);
if (num1 < min)
{
num1 = min;
}
this.InternalSetCapacity(num1);
}
private void InternalSetCapacity(int value)
{ //调整容量
if (value != this.keys.Length)
{
if (value < this._size)
{
throw new ArgumentOutOfRangeException(
"value", "要调整的容量值太小");
}
if (value > 0)
{ //重新开辟一块内存空间用来存放集合中的值
TKey[] localArray1 = new TKey[value];
TValue[] localArray2 = new TValue[value];
if (this._size > 0)
{ //数据搬家
Array.Copy(this.keys, 0, localArray1, 0, this._size);
Array.Copy(this.values, 0, localArray2, 0, this._size);
}
this.keys = localArray1;
this.values = localArray2;
}
else
{ //设置容量为
this.keys = ReversibleSortedList<TKey, TValue>.emptyKeys;
this.values = ReversibleSortedList<TKey, TValue>.emptyValues;
}
}
}
#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
// SortDirectionComparer
}
public class Test
{
static void Main()
{
ReversibleSortedList<int, string> rs=new ReversibleSortedList<int, string>();
rs.Add(3,"a");
rs.Add(1,"b");
rs.Add(2,"c");
rs.Add(6,"d");
rs.Print();
Console.WriteLine("当前容量为："+rs.Capacity+"元素个数为："+rs.Count);
rs.Add(5,"e");
rs.Add(4,"f");
rs.Print();
Console.WriteLine("当前容量为："+rs.Capacity+"元素个数为："+rs.Count);
rs.Add(8,"g");
rs.Add(7,"h");
rs.Add(9,"i");
rs.Print();
Console.WriteLine("当前容量为："+rs.Capacity+"元素个数为："+rs.Count);
}
}

运行结果：
key：1
value：b
key：2
value：c
key：3
value：a
key：4
value：d
当前容量为：4 元素个数为：4
key：1
value：b
key：2
value：c
key：3
value：a
key：4
value：f
key：5
value：e
key：6
value：d
当前容量为：8 元素个数为：6
key：1
value：b
key：2
value：c
key：3
value：a
key：4
value：f
key：5
value：e
key：6
value：d
key：7
value：h
key：8
value：g
key：9
value：i
当前容量为：16 元素个数为：9
从运行结果可以得知：刚开始插入了4个元素后，容量为4，接下来再插2个元素，容量自动扩展为8。最后再插入3个元素，容量自动扩展为16。并且，元素是按key的顺序进行排列的，完全符合我们之前的预想。终于可以点鞭炮庆祝一下了，但不要高兴得太早，百里长征大概才走了几里地。随着代码越来越复杂，要走的路会变得更艰难。

星辰.Net技术社区论坛