arraylist.cs

来自「没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没」· CS 代码 · 共 2,722 行 · 第 1/4 页

/*
 * ArrayList.cs - Implementation of the "System.Collections.ArrayList" class.
 *
 * Copyright (C) 2001, 2002, 2003  Southern Storm Software, Pty Ltd.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

namespace System.Collections
{

using System;
using System.Private;

public class ArrayList : ICloneable, ICollection, IEnumerable, IList
{
	// Internal state.
	private int count;
	private Object[] store;
	private int generation;

	// Simple constructors.
	public ArrayList()
			{
				count = 0;
				store = new Object [16];
				generation = 0;
			}
	public ArrayList(int capacity)
			{
				if(capacity < 0)
				{
					throw new ArgumentOutOfRangeException
						("capacity", _("ArgRange_NonNegative"));
				}
				count = 0;
				store = new Object [capacity];
				generation = 0;
			}

	// Construct an array list from the contents of a collection.
	public ArrayList(ICollection c)
			{
				IEnumerator enumerator;
				int index;
				if(c == null)
				{
					throw new ArgumentNullException("c");
				}
				count = c.Count;
				store = new Object [count];
				enumerator = c.GetEnumerator();
				for(index = 0; enumerator.MoveNext(); ++index)
				{
					store[index] = enumerator.Current;
				}
				generation = 0;
			}

	// Reallocate the array to accomodate "n" new entries at "index".
	// This leaves "count" unchanged.
	private void Realloc(int n, int index)
			{
				if((count + n) <= store.Length)
				{
					// The current capacity is sufficient, so just
					// shift the contents of the array upwards.
					int posn = count - 1;
					while(posn >= index)
					{
						store[posn + n] = store[posn];
						--posn;
					}
				}
				else
				{
					// We need to allocate a new array.
					int newCapacity = (((count + n) + 31) & ~31);
					int newCapacity2 = count * 2;
					if(newCapacity2 > newCapacity)
					{
						newCapacity = newCapacity2;
					}
					Object[] newStore = new Object [newCapacity];
					if(index != 0)
					{
						Array.Copy(store, 0, newStore, 0, index);
					}
					if(count != index)
					{
						Array.Copy(store, index, newStore, index + n,
								   count - index);
					}
					store = newStore;
				}
			}

	// Delete "n" entries from the list at "index".
	// This modifies "count".
	private void Delete(int n, int index)
			{
				while((index + n) < count)
				{
					store[index] = store[index + n];
					++index;
				}
				count -= n;
			}

	// Implement the IList interface.
	public virtual int Add(Object value)
			{
				if(count >= store.Length)
				{
					Realloc(1, count);
				}
				store[count] = value;
				++generation;
				return count++;
			}
	public virtual void Clear()
			{
				Array.Clear(store, 0, count);
				count = 0;
				++generation;
			}
	public virtual bool Contains(Object item)
			{
				int index;
				if(item != null)
				{
					for(index = 0; index < count; ++index)
					{
						if(item.Equals(store[index]))
						{
							return true;
						}
					}
					return false;
				}
				else
				{
					for(index = 0; index < count; ++index)
					{
						if(store[index] == null)
						{
							return true;
						}
					}
					return false;
				}
			}
	public virtual int IndexOf(Object value)
			{
				if(Count <= 0) return -1;

				return IndexOf(value, 0, Count);
			}
	public virtual void Insert(int index, Object value)
			{
				if(index < 0 || index > count)
				{
					throw new ArgumentOutOfRangeException
						("index", _("ArgRange_Array"));
				}
				Realloc(1, index);
				store[index] = value;
				++count;
				++generation;
			}
	public virtual void Remove(Object value)
			{
				int index = Array.IndexOf(store, value, 0, count);
				if(index != -1)
				{
					Delete(1, index);
					++generation;
				}
			}
	public virtual void RemoveAt(int index)
			{
				if(index < 0 || index > count)
				{
					throw new ArgumentOutOfRangeException
						("index", _("ArgRange_Array"));
				}
				Delete(1, index);
				++generation;
			}
	public virtual bool IsFixedSize
			{
				get
				{
					return false;
				}
			}
	public virtual bool IsReadOnly
			{
				get
				{
					return false;
				}
			}
	public virtual Object this[int index]
			{
				get
				{
					if(index < 0 || index >= count)
					{
						throw new ArgumentOutOfRangeException
							("index", _("ArgRange_Array"));
					}
					return store[index];
				}
				set
				{
					if(index < 0 || index >= count)
					{
						throw new ArgumentOutOfRangeException
							("index", _("ArgRange_Array"));
					}
					store[index] = value;
					++generation;
				}
			}

	// Add the contents of a collection as a range.
	public virtual void AddRange(ICollection c)
			{
				int cCount;
				IEnumerator enumerator;
				if(c == null)
				{
					throw new ArgumentNullException("c");
				}
				cCount = c.Count;
				if((count + cCount) > store.Length)
				{
					Realloc(cCount, count);
				}
				enumerator = c.GetEnumerator();
				while(enumerator.MoveNext())
				{
					store[count++] = enumerator.Current;
				}
				++generation;
			}

	// Insert the contents of a collection as a range.
	public virtual void InsertRange(int index, ICollection c)
			{
				int cCount;
				IEnumerator enumerator;
				if(c == null)
				{
					throw new ArgumentNullException("c");
				}
				if(index < 0 || index > count)
				{
					throw new ArgumentOutOfRangeException
						("index", _("ArgRange_Array"));
				}
				cCount = c.Count;
				Realloc(cCount, index);
				enumerator = c.GetEnumerator();
				while(enumerator.MoveNext())
				{
					store[index++] = enumerator.Current;
				}
				count += cCount;
				++generation;
			}

	// Remove a range of elements from an array list.
	public virtual void RemoveRange(int index, int count)
			{
				if(index < 0)
				{
					throw new ArgumentOutOfRangeException
						("index", _("ArgRange_Array"));
				}
				if(count < 0)
				{
					throw new ArgumentOutOfRangeException
						("count", _("ArgRange_Array"));
				}
				if((this.count - index) < count)
				{
					throw new ArgumentException(_("Arg_InvalidArrayRange"));
				}
				Delete(count, index);
				++generation;
			}

	// Perform a binary search on an array list.
	public virtual int BinarySearch(Object value)
			{
				return BinarySearch(0, Count, value, null);
			}
	public virtual int BinarySearch(Object value, IComparer comparer)
			{
				return BinarySearch(0, Count, value, comparer);
			}
	public virtual int BinarySearch(int index, int count,
								    Object value, IComparer comparer)
			{
				// Validate the arguments.
				if(index < 0)
				{
					throw new ArgumentOutOfRangeException
						("index", _("ArgRange_Array"));
				}
				if(count < 0)
				{
					throw new ArgumentOutOfRangeException
						("count", _("ArgRange_Array"));
				}
				if((Count - index) < count)
				{
					throw new ArgumentException(_("Arg_InvalidArrayRange"));
				}

				// Perform the binary search.
				int left, right, middle, cmp;
				Object elem;
				IComparable icmp;
				left = index;
				right = index + count - 1;
				while(left <= right)
				{
					middle = (left + right) / 2;
					elem = this[middle];
					if(elem != null && value != null)
					{
						if(comparer != null)
						{
							cmp = comparer.Compare(value, elem);
						}
						else if((icmp = (elem as IComparable)) != null)
						{
							cmp = -(icmp.CompareTo(value));
						}
						else if((icmp = (value as IComparable)) != null)
						{
							cmp = icmp.CompareTo(elem);
						}
						else
						{
							throw new ArgumentException
								(_("Arg_SearchCompare"));
						}
					}
					else if(elem != null)
					{
						cmp = -1;
					}
					else if(value != null)
					{
						cmp = 1;
					}
					else
					{
						cmp = 0;
					}
					if(cmp == 0)
					{
						return middle;
					}
					else if(cmp < 0)
					{
						right = middle - 1;
					}
					else
					{
						left = middle + 1;
					}
				}
				return ~left;
			}

	// Implement the ICloneable interface.
	public virtual Object Clone()
			{
				ArrayList clone = new ArrayList(count);
				clone.count = count;
				clone.generation = generation;
				Array.Copy(store, 0, clone.store, 0, count);
				return clone;
			}

	// Implement the ICollection interface.
	public virtual void CopyTo(Array array, int arrayIndex)
			{
				Array.Copy(store, 0, array, arrayIndex, count);
			}
	public virtual int Count
			{
				get
				{
					return count;
				}
			}
	public virtual bool IsSynchronized
			{
				get
				{
					return false;
				}
			}
	public virtual Object SyncRoot
			{
				get
				{
					return this;
				}
			}

	// Copy from this array list to another array.
	public virtual void CopyTo(Array array)
			{
				Array.Copy(store, 0, array, 0, count);
			}
	public virtual void CopyTo(int index, Array array,
							   int arrayIndex, int count)
			{
				// Validate the parameters.
				if(index < 0)
				{
					throw new ArgumentOutOfRangeException
						("index", _("ArgRange_Array"));
				}
				if(count < 0)
				{
					throw new ArgumentOutOfRangeException
						("count", _("ArgRange_Array"));
				}
				if((Count - index) < count)
				{
					throw new ArgumentException(_("Arg_InvalidArrayRange"));
				}

				// Perform the copy.
				if(GetType() == typeof(ArrayList))
				{
					// We can use a short-cut because we know that
					// the list elements are in "store".
					Array.Copy(store, index, array, arrayIndex, count);
				}
				else
				{
					// The list elements may be elsewhere.
					while(count > 0)
					{
						array.SetValue(this[index], arrayIndex);
						++index;
						++arrayIndex;
						--count;
					}
				}
			}

	// Get the index of a value within an array list.
	public virtual int IndexOf(Object value, int startIndex)
			{
				int count = Count;
				if(startIndex < 0 || startIndex >= count)
				{
					throw new ArgumentOutOfRangeException
						("startIndex", _("ArgRange_Array"));
				}
				return IndexOf(value, startIndex, count - startIndex);
			}
	public virtual int IndexOf(Object value, int startIndex, int count)
			{
				// Validate the parameters.
				int thisCount = Count;
				if(startIndex < 0 || startIndex >= thisCount)
				{
					throw new ArgumentOutOfRangeException
						("startIndex", _("ArgRange_Array"));
				}
				if(count < 0)
				{
					throw new ArgumentOutOfRangeException
						("count", _("ArgRange_Array"));
				}
				if((thisCount - startIndex) < count)
				{
					throw new ArgumentException(_("Arg_InvalidArrayRange"));
				}

				// Perform the search.
				Object elem;
				while(count > 0)
				{
					elem = this[startIndex];
					if(elem != null && value != null)
					{
						if(value.Equals(elem))
						{
							return startIndex;
						}
					}
					else if(elem == value && value == null)
					{
						return startIndex;
					}
					++startIndex;
					--count;
				}
				return -1;
			}

	// Get the last index of a value within an array list.
	public virtual int LastIndexOf(Object value)
			{
				int count = Count;
				return LastIndexOf(value, count - 1, count);
			}
	public virtual int LastIndexOf(Object value, int startIndex)
			{
				int count = Count;
				if(startIndex < 0 || startIndex >= count)
				{
					throw new ArgumentOutOfRangeException
						("startIndex", _("ArgRange_Array"));
				}
				return LastIndexOf(value, startIndex, startIndex + 1);
			}
	public virtual int LastIndexOf(Object value, int startIndex, int count)
			{
				// Validate the parameters.
				if(startIndex < 0 || startIndex >= Count)
				{
					throw new ArgumentOutOfRangeException
						("startIndex", _("ArgRange_Array"));
				}
				if(count < 0)
				{
					throw new ArgumentOutOfRangeException
						("count", _("ArgRange_Array"));
				}
				if(count > (startIndex + 1))
				{
					throw new ArgumentException(_("Arg_InvalidArrayRange"));
				}

				// Perform the search.
				Object elem;
				while(count > 0)
				{
					elem = this[startIndex];
					if(elem != null && value != null)
					{
						if(value.Equals(elem))
						{
							return startIndex;
						}
					}
					else if(elem == value && value == null)
					{
						return startIndex;
					}
					--startIndex;
					--count;
				}
				return -1;
			}

	// Construct an array list with repeated copies of the same element.
	public static ArrayList Repeat(Object value, int count)
			{
				ArrayList list;
				int index;
				if(count < 0)
				{
					throw new ArgumentOutOfRangeException
						("count", _("ArgRange_NonNegative"));
				}
				if(count < 16)
				{
					list = new ArrayList();
				}
				else
				{
					list = new ArrayList(count);
				}
				list.Realloc(count, 0);
				for(index = 0; index < count; ++index)
				{
					list.store[index] = value;
				}
				list.count = count;
				return list;
			}

	// Reverse the contents of this array list.
	public virtual void Reverse()
			{
				Array.Reverse(store, 0, count);
				++generation;
			}
	public virtual void Reverse(int index, int count)
			{
				if(index < 0)
				{
					throw new ArgumentOutOfRangeException
						("index", _("ArgRange_Array"));
				}
				if(count < 0)
				{
					throw new ArgumentOutOfRangeException
						("count", _("ArgRange_Array"));
				}
				if((this.count - index) < count)
				{
					throw new ArgumentException(_("Arg_InvalidArrayRange"));
				}
				Array.Reverse(store, index, count);
				++generation;
			}

	// Set a range of array list elements to the members of a collection.
	public virtual void SetRange(int index, ICollection c)
			{
				int count;
				IEnumerator enumerator;
				if(c == null)
				{
					throw new ArgumentNullException("c");
				}
				if(index < 0)
				{
					throw new ArgumentOutOfRangeException
						("index", _("ArgRange_Array"));
				}
				count = c.Count;
				if((this.count - index) < count)
				{
					throw new ArgumentException(_("Arg_InvalidArrayRange"));
				}
				enumerator = c.GetEnumerator();
				while(enumerator.MoveNext())
				{
					store[index++] = enumerator.Current;
				}
				++generation;
			}

	// Inner version of "Sort".
	private void InnerSort(int lower, int upper, IComparer comparer)
			{
				int i, j;
				Object pivot, temp;
				if((upper - lower) < 1)
				{
					// Zero or one elements - this partition is already sorted.
					return;
				}
				do
				{
					// Pick the middle of the range as the pivot value.
					i = lower;
					j = upper;
					pivot = this[i + ((j - i) / 2)];
		
					// Partition the range.
					do
					{