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[i],values[i]);
}
}
#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的順序進行排列的，完全符合我們之前的預想。終於可以點鞭炮慶祝一下了，但不要高興得太早，百裡長征大概才走了幾裡地。隨著代碼越來越復雜，要走的路會變得更艱難。
