4.8 反轉Sorted List裡的內容
問題
您希望在數組和列表類型中可以反轉sorted list裡的內容同時又維持SortedList和SortedList<T>類原來的功能。無論是SortedList還是泛型SortedList<T>類都直接提供了完成這個功能的方法而又不需要重填列表。
解決方案
ReversibleSortedList<TKey, TValue>類提供了這些功能，它基於SortedList<TKey, TValue>類，所以擁有相同的功能，它提供了額外的功能是很容易反轉已排序的列表。
在實例化ReversibleSortedList<TKey, TValue>之後，鍵是整數類型，值是字符串類型，一連串無序的數字和它們的文本表達被插入到列表中。這些項目是這樣顯示的：
ReversibleSortedList<int, string> rsl = new ReversibleSortedList<int, string>();
rsl.Add(2, "2");
rsl.Add(5, "5");
rsl.Add(3, "3");
rsl.Add(1, "1");
foreach (KeyValuePair<int, string> kvp in rsl)
{
Debug.WriteLine("\t" + kvp.Key + "\t" + kvp.Value);
}
列表輸出顯示為按升序排序（默認）：
1 1 2 2 3 3 5 5
現在排列順序通過設置ReversibleSortedList的SortDirection屬性被反轉為降序。為了重新排序需要調用Sort()方法。結果如下：
// 轉換排序方向.
rsl.Comparer.SortDirection = ListSortDirection.Descending;
// 重排列表.
rsl.Sort();
foreach (KeyValuePair<int, string> kvp in rsl)
{
Debug.WriteLine("\t" + kvp.Key + "\t" + kvp.Value);
}
這一次，輸出為降序：
5 5 3 3 2 2 1 1
當把一個新項添加進列表，它將按當前的排列順序被添加進去,但在添加完所有項後馬上進行反轉，就可以保持列表中元素的順序。
rsl.Add(4, "4");
foreach (KeyValuePair<int, string> kvp in rsl)
{
Debug.WriteLine("\t" + kvp.Key + "\t" + kvp.Value);
}
// 轉換排序方向.
rsl.Comparer.SortDirection = ListSortDirection.Ascending;
// 重排列表.
rsl.Sort();
foreach (KeyValuePair<int, string> kvp in rsl)
{
Debug.WriteLine("\t" + kvp.Key + "\t" + kvp.Value);
}
可以看到新項即按降序也按升序排列：
5 5 4 4 3 3 2 2 1 1 1 1 2 2 3 3 4 4 5 5
ReversibleSortedList<TKey, TValue>包含一個實現了IComparer<T>接口的嵌套類SortDirectionComparer<T>。這個類可以在“討論”這一節中的ReversibleSortedList<TKey, TValue>代碼中看到。一個實現了IComparer<T>接口的類可以做為ReversibleSortedList<TKey, TValue>構造方法的參數來改變默認的排序。IComparer<T>接口實現了Compare方法：
class Program
{
public int Compare(T lhs, T rhs)
{
int compareResult =
lhs.ToString().CompareTo(rhs.ToString());
// 如果為降序, 則反轉
if (SortDirection == ListSortDirection.Descending)
compareResult *= -1;
return compareResult;
}
}
Compare方法使用了SortDirectionComparer<T>類的SortDirection屬性來決定項的排序。這個屬性在ReversibleSortedList<TKey, TValue>的內部類SortDirectionComparer<T>實例中被設置。SortDirection屬性是在構造方法中被設置的，代碼如下：
public ReversibleSortedList()
{
this.keys = ReversibleSortedList<TKey, TValue>.emptyKeys;
this.values = ReversibleSortedList<TKey, TValue>.emptyValues;
this._size = 0;
this._sortDirectionComparer = new SortDirectionComparer<TKey>();
this._currentSortDirection = this._sortDirectionComparer.SortDirection;
}
這允許它在指定時間內反轉排列順序，但並沒有重排列表中已存在的項。為了實現這個功能，需要在Reversible-SortedList<TKey, TValue>類中添加一個新的Sort()方法以重排列表。代碼如下：
public void Sort()
{
//檢查是否跟現有排序方向相同.
if (this._currentSortDirection != this._sortDirectionComparer.SortDirection)
{
// 如果不同，則進行反轉.
Array.Reverse(this.keys, 0, this._size);
Array.Reverse(this.values, 0, this._size);
// 設置當前排序.
this._currentSortDirection = this._sortDirectionComparer.SortDirection;
}
}
討論
例4-3是ReversibleSortedList<TKey, TValue>類的所有代碼：
(譯者注：這個類的代碼很恐怖，接近1300行，不過代碼很規范，感覺應該是商業代碼，非常值得借鑒。將來有時間我會專門寫文章分析它。請關注：我的博客：http://cgbluesky.blog.163.com/)
例4-3 ReversibleSortedList類
[Serializable, ComVisible(false), DebuggerDisplay("Count = {Count}")]
public class ReversibleSortedList<TKey, TValue> :
IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>,
IEnumerable<KeyValuePair<TKey, TValue>>,
IDictionary, ICollection, IEnumerable
{
SortDirectionComparer類定義#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 order is DESC, reverse this comparison.
if (SortDirection == ListSortDirection.Descending)
compareResult *= -1;
return compareResult;
}
}
#endregion // SortDirectionComparer
構造方法#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>();
this._currentSortDirection = this._sortDirectionComparer.SortDirection;
}
//用於指定排序方向的構造方法
public ReversibleSortedList(SortDirectionComparer<TKey> comparer)
: this()
{
if (comparer != null)
{
this._sortDirectionComparer = comparer;
this._currentSortDirection = _sortDirectionComparer.SortDirection;
}
}
//用於指定字典的構造方法
public ReversibleSortedList(IDictionary<TKey, TValue> dictionary)
: this(dictionary, (SortDirectionComparer<TKey>)null)
{
}
//用於指定列表容量的構造方法
public ReversibleSortedList(int capacity)
{
if (capacity < 0)
{
throw new ArgumentOutOfRangeException(
"capacity", "Non-negative number required");
}
this.keys = new TKey[capacity];
this.values = new TValue[capacity];
this._sortDirectionComparer = new SortDirectionComparer<TKey>();
this._currentSortDirection = _sortDirectionComparer.SortDirection;
}
//用於指定字典和排序方向的構造方法
public ReversibleSortedList(IDictionary<TKey, TValue> dictionary,
SortDirectionComparer<TKey> comparer)
: this((dictionary != null) ? dictionary.Count : 0, comparer)
{
if (dictionary == null)
{
throw new ArgumentNullException("dictionary");
}
dictionary.Keys.CopyTo(this.keys, 0);
dictionary.Values.CopyTo(this.values, 0);
Array.Sort<TKey, TValue>(this.keys, this.values,
this._sortDirectionComparer);
this._size = dictionary.Count;
}
//用於指定容量和排序方向的構造方法
public ReversibleSortedList(int capacity, SortDirectionComparer<TKey> comparer)
: this(comparer)
{
this.Capacity = capacity;
}
#endregion //CTORS
公有方法#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("Attempting to add duplicate");
}
this.Insert(~num1, key, value);
}
//ICollection<KeyValuePair<TKey, TValue>>接口方法實現
public void Clear()
{
this.version++;
Array.Clear(this.keys, 0, this._size);
Array.Clear(this.values, 0, this._size);
this._size = 0;
}
//判斷是否包含指定鍵
public bool ContainsKey(TKey key)
{
return (this.IndexOfKey(key) >= 0);
}
//判斷是否包含指定值
public bool ContainsValue(TValue value)
{
return (this.IndexOfValue(value) >= 0);
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
return new ReversibleSortedList<TKey, TValue>.Enumerator<TKey, TValue>(
this);
}
//查找指定鍵
public int IndexOfKey(TKey key)
{
if (key.Equals(null))
{
throw new ArgumentNullException("key");
}
int num1 = Array.BinarySearch<TKey>(this.keys, 0, this._size, key,
this._sortDirectionComparer);
if (num1 < 0)
{
return -1;
}
return num1;
}
//查找指定值
public int IndexOfValue(TValue value)
{
return Array.IndexOf<TValue>(this.values, value, 0, this._size);
}
//IDictionary<TKey, TValue>接口方法實現
public bool Remove(TKey key)
{
int num1 = this.IndexOfKey(key);
if (num1 >= 0)
{
this.RemoveAt(num1);
}
return (num1 >= 0);
}
//移除指定索引元素
public void RemoveAt(int index)
{
if ((index < 0) || (index >= this._size))
{
throw new ArgumentOutOfRangeException("index", "Index out of range");
}
this._size--;
if (index < this._size)
{
Array.Copy(this.keys, (int)(index + 1), this.keys, index,
(int)(this._size - index));
Array.Copy(this.values, (int)(index + 1), this.values, index,
(int)(this._size - index));
}
this.keys[this._size] = default(TKey);
this.values[this._size] = default(TValue);
this.version++;
}
//排序
public void Sort()
{
// 檢查是否跟現有排序方向相同.
if (this._currentSortDirection !=
this._sortDirectionComparer.SortDirection)
{
// 如果不同，則進行反轉.
Array.Reverse(this.keys, 0, this._size);
Array.Reverse(this.values, 0, this._size);
// 設置當前排序.
this._currentSortDirection = this._sortDirectionComparer.SortDirection;
}
}
//剪除多余空間
public void TrimExcess()
{
int num1 = (int)(this.keys.Length * 0.9);
if (this._size < num1)
{
this.Capacity = this._size;
}
}
//獲取指定鍵的值
public bool TryGetValue(TKey key, out TValue value)
{
int num1 = this.IndexOfKey(key);
if (num1 >= 0)
{
value = this.values[num1];
return true;
}
value = default(TValue);
return false;
}
#endregion // Public Methods
