鸟语天空

C#动态数组原理

作者：追风剑情 发布于：2014-5-23 14:38 分类：C#

以下代码摘自NGUI 2.7

using System;
using System.Collections.Generic;

/// <summary>
/// 这是改进版的System.Collections.Generic.List
/// </summary>

public class BetterList<T>
{
	/// <summary>
	/// 缓冲区
	/// </summary>

	public T[] buffer;

	/// <summary>
	/// 缓冲区大小
	/// </summary>

	public int size = 0;

	/// <summary>
	/// 数组迭代器
	/// </summary>

	public IEnumerator<T> GetEnumerator ()
	{
		if (buffer != null)
		{
			for (int i = 0; i < size; ++i)
			{
				yield return buffer[i];
			}
		}
	}
	
	/// <summary>
	/// 索引器
	/// </summary>
	
	public T this[int i]
	{
		get { return buffer[i]; }
		set { buffer[i] = value; }
	}

	/// <summary>
	/// 动态增加数组长度
	/// </summary>

	void AllocateMore ()
	{
		T[] newList = (buffer != null) ? new T[Math.Max(buffer.Length << 1, 32)] : new T[32];
		if (buffer != null && size > 0) buffer.CopyTo(newList, 0);
		buffer = newList;
	}

	/// <summary>
    /// 去除不必要的内存
	/// </summary>

	void Trim ()
	{
		if (size > 0)
		{
			if (size < buffer.Length)
			{
				T[] newList = new T[size];
				for (int i = 0; i < size; ++i) newList[i] = buffer[i];
				buffer = newList;
			}
		}
		else buffer = null;
	}

	/// <summary>
    /// 清除数组中的项
	/// </summary>

	public void Clear () { size = 0; }

	/// <summary>
	/// 清除数组中的项，并释放内存
	/// </summary>

	public void Release () { size = 0; buffer = null; }

	/// <summary>
	/// 添加项
	/// </summary>

	public void Add (T item)
	{
		if (buffer == null || size == buffer.Length) AllocateMore();
		buffer[size++] = item;
	}

	/// <summary>
	/// 在数组的指定位置插入一项
	/// </summary>

	public void Insert (int index, T item)
	{
		if (buffer == null || size == buffer.Length) AllocateMore();

		if (index < size)
		{
			for (int i = size; i > index; --i) buffer[i] = buffer[i - 1];
			buffer[index] = item;
			++size;
		}
		else Add(item);
	}

	/// <summary>
	/// 检查数组中是否存在指定项 true:存在  false:不存在
	/// </summary>

	public bool Contains (T item)
	{
		if (buffer == null) return false;
        for (int i = 0; i < size; ++i)
        {
            if (buffer[i] == null)
                continue;
            if (buffer[i].Equals(item))
                return true;
        }
		return false;
	}

	/// <summary>
	/// 移除指定项
	/// </summary>

	public bool Remove (T item)
	{
		if (buffer != null)
		{
			EqualityComparer<T> comp = EqualityComparer<T>.Default;

			for (int i = 0; i < size; ++i)
			{
				if (comp.Equals(buffer[i], item))
				{
					--size;
					buffer[i] = default(T);
					for (int b = i; b < size; ++b) buffer[b] = buffer[b + 1];
					return true;
				}
			}
		}
		return false;
	}

	/// <summary>
	/// 移除指定索引的项
	/// </summary>

	public void RemoveAt (int index)
	{
		if (buffer != null && index < size)
		{
			--size;
			buffer[index] = default(T);
			for (int b = index; b < size; ++b) buffer[b] = buffer[b + 1];
		}
	}

	/// <summary>
	/// 移除数组中最后一项
	/// </summary>

	public T Pop ()
	{
		if (buffer != null && size != 0)
		{
			T val = buffer[--size];
			buffer[size] = default(T);
			return val;
		}
		return default(T);
	}

	/// <summary>
	/// 返回一个长度为size的数组
	/// </summary>

	public T[] ToArray () { Trim(); return buffer; }

	/// <summary>
	/// 排序方法.
	/// </summary>

	public void Sort (System.Comparison<T> comparer)
	{
		bool changed = true;

		while (changed)
		{
			changed = false;

			for (int i = 1; i < size; ++i)
			{
				if (comparer.Invoke(buffer[i - 1], buffer[i]) > 0)
				{
					T temp = buffer[i];
					buffer[i] = buffer[i - 1];
					buffer[i - 1] = temp;
					changed = true;
				}
			}
		}
	}
}