[Mono-list] Implementation of ListWrapper.Sort

[Thong (Tum) Nguyen]

This is a multi-part message in MIME format.

------=_NextPart_000_0013_01C2FC0D.52150980
Content-Type: text/plain;
	charset="Windows-1252"
Content-Transfer-Encoding: 7bit

Can't remember if this is the place for patches or not...

^Tum

"The true measure of a man is how he treats someone who can do him
absolutely no good." - Samuel Johnson (1709-1784)



---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.461 / Virus Database: 260 - Release Date: 10/03/2003
 
  

------=_NextPart_000_0013_01C2FC0D.52150980
Content-Type: application/octet-stream;
	name="listwrapper.diff"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="listwrapper.diff"

? arraylist.diff=0A=
? listwrapper.diff=0A=
Index: 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 -r1.42 ArrayList.cs=0A=
319,320c319,321=0A=
< 			[MonoTODO]
< 			public override void Sort () {
---=0A=
> 			public override void Sort ()
> 			{
> 				QuickSort(this, 0, count - 1, Comparer.Default);
323,324c324,326=0A=
< 			[MonoTODO]
< 			public override void Sort (IComparer comparer) {
---=0A=
> 			public override void Sort (IComparer comparer)
> 			{
> 				QuickSort(this, 0, count - 1, comparer);
327,328c329,423=0A=
< 			[MonoTODO]
< 			public override void Sort (int index, int count, IComparer =
comparer) {
---=0A=
> 			public override void Sort (int index, int count, IComparer =
comparer)
> 			{
> 				QuickSort(this, index, index + count, comparer);
> 			}
>=20
> 			/// <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;
> 			}
>=20
> 			/// <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;
> 				}
>=20
> 				// Pick the pivot using the median-of-three strategy.
>=20
> 				middle =3D (left + right) / 2;
>=20
> 				if (comparer.Compare(list[middle], list[left]) < 0)
> 				{
> 					Swap(list, middle, left);
> 				}
>=20
> 				if (comparer.Compare(list[right], list[left]) < 0)
> 				{
> 					Swap(list, right, left);
> 				}
>=20
> 				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.
>=20
> 				Swap(list, right - 1, middle);
>=20
> 				// List should look like:
> 				//
> 				// [Small] ..Numbers.. [Middle] ..Numbers.. [Pivot][Large]
>=20
> 				pivot =3D list[right - 1];
>=20
> 				// Sort from (left + 1) to (right - 2).
>=20
> 				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;
> 					}
> 				}
>=20
> 				// Put pivot into the right position (real middle).
>=20
> 				Swap(list, right - 1, i);
>=20
> 				// Recursively sort the left and right sub lists.
>=20
> 				QuickSort(list, left, i - 1, comparer);
> 				QuickSort(list, i + 1, right, comparer);	=09
Index: ChangeLog=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/ChangeLog,v=0A=
retrieving revision 1.66=0A=
diff -r1.66 ChangeLog=0A=
0a1,3=0A=
> 2003-04-06  Thong Nguyen <tum@veridicus.com>=0A=
> 	* ArrayList.cs:  Added implementation for ListWrapper.Sort.=0A=
> =0A=

------=_NextPart_000_0013_01C2FC0D.52150980--