[Mono-list] System.Collections.ArrayList Patch

Thong (Tum) Nguyen tum@veridicus.com
Sun, 4 May 2003 13:16:05 +1200


This is a multi-part message in MIME format.

------=_NextPart_000_0010_01C3123F.53D7D840
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit

Oops :D

Regards,

^Tum

> -----Original Message-----
> From: mono-list-admin@lists.ximian.com [mailto:mono-list-
> admin@lists.ximian.com] On Behalf Of Nick Drochak
> Sent: Sunday, 4 May 2003 1:25 a.m.
> To: Thong (Tum) Nguyen
> Cc: 'Piers Haken'; 'Ben Maurer'; 'Mono List'
> Subject: RE: [Mono-list] System.Collections.ArrayList Patch
> 
> On Sat, 2003-05-03 at 14:00, Thong (Tum) Nguyen wrote:
> > My patch is attached.
> 
> Seems like you forgot the attachment.
> 
> Nick D.
> 
> _______________________________________________
> Mono-list maillist  -  Mono-list@lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-list

------=_NextPart_000_0010_01C3123F.53D7D840
Content-Type: application/octet-stream;
	name="arraylist.diff"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="arraylist.diff"

Index: class/corlib/System.Collections/ArrayList.cs=0A=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=0A=
RCS file: /mono/mcs/class/corlib/System.Collections/ArrayList.cs,v=0A=
retrieving revision 1.42=0A=
diff -u -r1.42 ArrayList.cs=0A=
--- class/corlib/System.Collections/ArrayList.cs	9 Feb 2003 04:22:24 =
-0000	1.42=0A=
+++ class/corlib/System.Collections/ArrayList.cs	6 Apr 2003 09:09:18 =
-0000=0A=
@@ -4,7 +4,8 @@=0A=
 // Author:
 //    Vladimir Vukicevic (vladimir@pobox.com)
 //    Duncan Mak (duncan@ximian.com)
-//		Patrik Torstensson (totte@crepundia.net)
+//    Patrik Torstensson (totte@crepundia.net)
+//    Thong Nguyen (tum@veridicus.com)
 //
 // (C) 2001 Vladimir Vukicevic
 // (C) 2002 Ximian, Inc.
@@ -143,189 +144,403 @@=0A=
 		}
=20
 		[Serializable]
-		private class ListWrapper : ArrayList {
+		private class ListWrapper : ArrayList
+		{
 			IList list;
=20
-			public ListWrapper (IList list) {
+			public ListWrapper (IList list)
+			{
 				if (null =3D=3D list)
+				{
 					throw new ArgumentNullException();
+				}
=20
 				this.list =3D list;
-				count =3D ((ICollection) list).Count;
 			}
 		=09
-			// ArrayList
-			[MonoTODO]
-			public override int Capacity {
+			public override int Capacity
+			{
 				get { return list.Count; }
 				set { throw new NotSupportedException (); }
 			}
-
-			[MonoTODO]
-			public override void AddRange (ICollection collection) {
+		=09
+			public override void AddRange(ICollection collection)
+			{
 				if (collection =3D=3D null)
-					throw new ArgumentNullException ("colllection");
+					throw new ArgumentNullException ("collection");
+
 				if (IsFixedSize || IsReadOnly)
 					throw new NotSupportedException ();
+
+				foreach (object value in collection)
+				{
+					Add(value);
+				}
 			}
=20
 			[MonoTODO]
-			public override int BinarySearch (object value) {
+			public override int BinarySearch (object value)
+			{
 				throw new NotImplementedException ();
 			}
=20
 			[MonoTODO]
-			public override int BinarySearch (object value, IComparer comparer) =
{
+			public override int BinarySearch (object value, IComparer comparer)
+			{
 				throw new NotImplementedException ();
 			}
=20
 			[MonoTODO]
 			public override int BinarySearch (int index, int count, object =
value,
-				IComparer comparer) {
+				IComparer comparer)
+			{
 				throw new NotImplementedException ();
 			}
=20
-			public override void CopyTo (Array array) {
+			public override void CopyTo (Array array)
+			{
 				if (null =3D=3D array)
 					throw new ArgumentNullException("array");
+
 				if (array.Rank > 1)
 					throw new ArgumentException("array cannot be multidimensional");
=20
 				CopyTo (array, 0);
 			}
=20
-			[MonoTODO]
 			public override void CopyTo (int index, Array array,
-				int arrayIndex, int count) {
+				int arrayIndex, int count)
+			{
 				if (array =3D=3D null)
 					throw new ArgumentNullException ();
+
 				if (index < 0 || arrayIndex < 0 || count < 0)
 					throw new ArgumentOutOfRangeException ();
+
 				if (array.Rank > 1 || index >=3D Count || Count > (array.Length - =
arrayIndex))
 					throw new ArgumentException ();
-				// FIXME: handle casting error here
+			=09
+				for (int i =3D arrayIndex; i < count; i++)
+				{
+					array.SetValue(this[i - arrayIndex], arrayIndex);
+				}
 			}
=20
-			public override ArrayList GetRange (int index, int count) {
+			public override ArrayList GetRange (int index, int count)
+			{
 				if (index < 0 || count < 0)
 					throw new ArgumentOutOfRangeException ();
-				if (Count < (index + count))
+
+				if (this.Count < (index + count))
 					throw new ArgumentException ();
 			=09
 				ArrayList result =3D new ArrayList (count);
=20
 				for (int i =3D 0; i < count; i++)
+				{
 					result.Add (list [i]);
+				}
=20
 				return result;
 			}
+		=09
+			public override void InsertRange (int index, ICollection collection)
+			{
+				int x;
=20
-			[MonoTODO]
-			public override void InsertRange (int index, ICollection col) {
-				if (col =3D=3D null)
+				if (collection =3D=3D null)
 					throw new ArgumentNullException ();
+
 				if (index < 0 || index > Count)
 					throw new ArgumentOutOfRangeException ();
+
 				if (IsReadOnly || IsFixedSize)
 					throw new NotSupportedException ();
=20
-				if (index =3D=3D Count) {
-					foreach (object element in col)
-						list.Add (element);
+				if (index =3D=3D this.Count)
+				{
+					foreach (object element in collection)
+					{
+						list.Add(element);
+					}
+				}
+				else
+				{
+					IEnumerator enumerator;
+
+					enumerator =3D collection.GetEnumerator();
+
+					// Room in list from insertion point to the end.
+
+					x =3D list.Count - index;
+
+					// Add bits from collection that don't fit into list.
+
+					if (collection.Count > x)
+					{
+						for (int i =3D 0; i <=3D x; i++)
+						{
+							enumerator.MoveNext();
+						}
+
+						do
+						{
+							list.Add(enumerator.Current);
+						}
+						while (enumerator.MoveNext());
+
+						// Move items from original list=20
+
+						for (int i =3D index; i <=3D x; i++)
+						{
+							list.Add(list[i]);
+						}
=20
-				} //else if ((index + count) < Count) {
-				// 					for (int i =3D index; i < (index + count); i++)
-				// 						list [i] =3D col [i];
+						enumerator.Reset();
+						enumerator.MoveNext();
=20
-				// 				} else {
-				// 					int added =3D Count - (index + count);
-				// 					for (int i =3D index; i < Count; i++)
-				// 						list [i] =3D col [i];
-				// 					for (int i =3D 0; i < added; i++)
-				// 						list.Add (col [Count +i]);
-				// 				}
+						// Copy first part of collection over.
+
+						for (int i =3D 0; i <=3D x; i++)
+						{
+							list[index + i] =3D enumerator.Current;
+							enumerator.MoveNext();
+						}
+					}
+					else
+					{
+						int y;
+						x =3D list.Count;
+
+						y =3D list.Count - index - collection.Count;
+
+						// Add the elements that sit after collection but which don't =
fit.
+
+						for (int i =3D 0; i < collection.Count; i++)
+						{
+							list.Add(list[x - collection.Count + i]);
+						}
+
+						// Move the elements that sit after collection.
+
+						for (int i =3D y; i >=3D 0; i--)
+						{
+							list[i + index + collection.Count] =3D list[i + index];
+						}					=09
+
+						// Put the collection in.
+
+						x =3D index;
+
+						foreach (object value in collection)
+						{
+							list[x++] =3D value;
+						}
+					}
+				}
 			}
=20
-			public override int LastIndexOf (object value) {
-				return LastIndexOf (value, Count, 0);
+			public override int LastIndexOf (object value)
+			{
+				return LastIndexOf (value, this.Count, 0);
 			}
=20
-			public override int LastIndexOf (object value, int startIndex) {
+			public override int LastIndexOf (object value, int startIndex)
+			{
 				return LastIndexOf (value, startIndex, 0);
 			}
=20
-			public override int LastIndexOf (object value, int startIndex, int =
count) {
-				if (null =3D=3D value){
+			public override int LastIndexOf (object value, int startIndex, int =
count)
+			{
+				if (null =3D=3D value)
+				{
 					return -1;
 				}
=20
-				if (startIndex > Count || count < 0 || (startIndex + count > =
Count))
+				if (startIndex > this.Count || count < 0 || (startIndex + count > =
this.Count))
 					throw new ArgumentOutOfRangeException ();
 			=09
 				int length =3D startIndex - count + 1;
=20
 				for (int i =3D startIndex; i >=3D length; i--)
+				{
 					if (list [i] =3D=3D value)
+					{
 						return i;
+					}
+				}
+
 				return -1;
 			}
=20
-			public override void RemoveRange (int index, int count) {
+			public override void RemoveRange (int index, int count)
+			{
 				if ((index < 0) || (count < 0))
 					throw new ArgumentOutOfRangeException ();
+
 				if ((index > Count) || (index + count) > Count)
 					throw new ArgumentException ();
+
 				if (IsReadOnly || IsFixedSize)
 					throw new NotSupportedException ();
=20
 				for (int i  =3D 0; i < count; i++)
+				{
 					list.RemoveAt (index);
+				}
 			}
=20
-			public override void Reverse () {
-				Reverse (0, Count);
+			public override void Reverse ()
+			{
+				Reverse (0, this.Count);
 			}
=20
-			public override void Reverse (int index, int count) {
+			public override void Reverse (int index, int count)
+			{
 				if ((index < 0) || (count < 0))
 					throw new ArgumentOutOfRangeException ();
+
 				if ((index > Count) || (index + count) > Count)
 					throw new ArgumentException ();
+
 				if (IsReadOnly)
 					throw new NotSupportedException ();
=20
 				object tmp =3D null;
=20
-				for (int i =3D index; i < count; i++) {
-					tmp =3D list [i];
-					list [i] =3D list [count - i];
-					list [count - i] =3D tmp;
+				for (int i =3D 0; i < count / 2; i++)
+				{
+					tmp =3D list[i + index];
+					list[i + index] =3D list[index + count - i - 1];
+					list[index + count - i - 1] =3D tmp;
 				}
 			}
=20
-			public override void SetRange (int index, ICollection col) {
+			public override void SetRange (int index, ICollection col)
+			{
 				if (index < 0 || (index + col.Count) > Count)
 					throw new ArgumentOutOfRangeException ();
+
 				if (col =3D=3D null)
 					throw new ArgumentNullException ();
+
 				if (IsReadOnly)
 					throw new NotSupportedException ();
=20
 				for (int i =3D index; i < col.Count; i++)
+				{
 					foreach (object o in col)
-						list [i] =3D o;
+					{
+						list[i] =3D o;
+					}
+				}
 			}
=20
-			[MonoTODO]
-			public override void Sort () {
+			public override void Sort ()
+			{
+				QuickSort(this, 0, this.Count - 1, Comparer.Default);
 			}
=20
-			[MonoTODO]
-			public override void Sort (IComparer comparer) {
+			public override void Sort (IComparer comparer)
+			{
+				QuickSort(this, 0, this.Count - 1, comparer);
 			}
=20
-			[MonoTODO]
-			public override void Sort (int index, int count, IComparer comparer) =
{
+			public override void Sort (int index, int count, IComparer comparer)
+			{
+				QuickSort(this, index, index + this.Count, comparer);
+			}
+
+			/// <summary>
+			/// Swaps two items in a list at the specified indexes.
+			/// </summary>
+			private static void Swap(IList list, int x, int y)
+			{
+				object tmp;
+			=09
+				tmp =3D list[x];
+				list[x] =3D list[y];
+				list[y] =3D tmp;
+			}
+
+			/// <summary>
+			/// Quicksort for lists.
+			/// </summary>
+			/// <remarks>
+			/// This function acts as both qsort() and partition().
+			/// </remarks>
+			private static void QuickSort(IList list, int left, int right, =
IComparer comparer)
+			{
+				int i, j, middle;
+				object pivot;
+				=09
+				if (left >=3D right)
+				{
+					return;
+				}
+
+				// Pick the pivot using the median-of-three strategy.
+
+				middle =3D (left + right) / 2;
+
+				if (comparer.Compare(list[middle], list[left]) < 0)
+				{
+					Swap(list, middle, left);
+				}
+
+				if (comparer.Compare(list[right], list[left]) < 0)
+				{
+					Swap(list, right, left);
+				}
+
+				if (comparer.Compare(list[right], list[middle]) < 0)
+				{
+					Swap(list, right, middle);
+				}
+	=09
+				if (right - left + 1 <=3D 3)
+				{
+					return;
+				}
+	=09
+				// Put the pivot in right - 1.
+
+				Swap(list, right - 1, middle);
+
+				// List should look like:
+				//
+				// [Small] ..Numbers.. [Middle] ..Numbers.. [Pivot][Large]
+
+				pivot =3D list[right - 1];
+
+				// Sort from (left + 1) to (right - 2).
+
+				i =3D left;
+				j =3D right - 1;		=09
+	=09
+				for (;;)
+				{
+					while (comparer.Compare(list[++i], pivot) < 0);
+					while (comparer.Compare(list[--j], pivot) > 0);
+		=09
+					if (i < j)
+					{
+						Swap(list, i, j);
+					}
+					else
+					{
+						break;
+					}
+				}
+
+				// Put pivot into the right position (real middle).
+
+				Swap(list, right - 1, i);
+
+				// Recursively sort the left and right sub lists.
+
+				QuickSort(list, left, i - 1, comparer);
+				QuickSort(list, i + 1, right, comparer);	=09
 			}
=20
 			public override object [] ToArray () {
@@ -389,8 +604,9 @@=0A=
 			}
=20
 			// ICollection		=09
-			public override int Count {
-				get { return count; }
+			public override int Count
+			{
+				get { return list.Count; }
 			}
=20
 			public override bool IsSynchronized {

------=_NextPart_000_0010_01C3123F.53D7D840--