[Mono-list] System.Collections.ArrayList Patch
Thong (Tum) Nguyen
tum@veridicus.com
Sun, 4 May 2003 13:16:23 +1200
This is a multi-part message in MIME format.
------=_NextPart_000_0014_01C3123F.5E23CCF0
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_0014_01C3123F.5E23CCF0
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_0014_01C3123F.5E23CCF0--