[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Dotgnu-pnet-commits] CVS: pnetlib/runtime/System/Collections ArrayList
From: |
Rhys Weatherley <address@hidden> |
Subject: |
[Dotgnu-pnet-commits] CVS: pnetlib/runtime/System/Collections ArrayList.cs,1.12,1.13 |
Date: |
Mon, 14 Apr 2003 01:23:35 -0400 |
Update of /cvsroot/dotgnu-pnet/pnetlib/runtime/System/Collections
In directory subversions:/tmp/cvs-serv8904/runtime/System/Collections
Modified Files:
ArrayList.cs
Log Message:
Use quicksort for sorting Array and ArrayList instances.
Index: ArrayList.cs
===================================================================
RCS file: /cvsroot/dotgnu-pnet/pnetlib/runtime/System/Collections/ArrayList.cs,v
retrieving revision 1.12
retrieving revision 1.13
diff -C2 -r1.12 -r1.13
*** ArrayList.cs 21 Feb 2003 03:12:54 -0000 1.12
--- ArrayList.cs 14 Apr 2003 05:23:33 -0000 1.13
***************
*** 658,773 ****
}
! // Inner version of "Sort". Based on the Quicksort implementation
! // described in R. Sedgewick, "Algorithms in C++", Addison-Wesley, 1992.
public void InnerSort(int lower, int upper, IComparer comparer)
{
! // Temporary hack - use a dumb sort until I can
figure
! // out what is wrong with the Quicksort code --
Rhys.
! int i, j, cmp;
! Object valuei;
! Object valuej;
! for(i = lower; i < upper; ++i)
{
! for(j = i + 1; j <= upper; ++j)
{
! valuei = this[i];
! valuej = this[j];
! if(comparer != null)
{
! cmp =
comparer.Compare(valuei, valuej);
}
! else
{
! cmp =
((IComparable)valuei).CompareTo(valuej);
}
! if(cmp > 0)
{
! this[i] = valuej;
! this[j] = valuei;
}
}
! }
! #if false
! int i, j, cmp;
! Object testKey;
! Object valuei;
! Object valuej;
! if(lower < upper)
! {
! // If this[lower] > this[upper], then
swap. This
! // helps to make the loops below
terminate predictably.
! testKey = this[upper];
! valuei = this[lower];
! if(comparer != null)
{
! cmp = comparer.Compare(valuei,
testKey);
}
else
{
! cmp =
((IComparable)valuei).CompareTo(testKey);
! }
! if(cmp > 0)
! {
! this[upper] = valuei;
! this[lower] = testKey;
! testKey = valuei;
! }
!
! // Partition the array.
! i = lower - 1;
! j = upper;
! for(;;)
! {
! for(;;)
! {
! ++i;
! valuei = this[i];
! if(comparer != null)
! {
! cmp =
comparer.Compare(valuei, testKey);
! }
! else
! {
! cmp =
((IComparable)valuei).CompareTo(testKey);
! }
! if(cmp >= 0 || i ==
upper)
! {
! break;
! }
! }
! for(;;)
! {
! --j;
! valuej = this[j];
! if(comparer != null)
! {
! cmp =
comparer.Compare(valuej, testKey);
! }
! else
! {
! cmp =
((IComparable)valuej).CompareTo(testKey);
! }
! if(cmp <= 0 || j ==
lower)
! {
! break;
! }
! }
! if(i >= j)
{
! break;
}
! this[i] = valuej;
! this[j] = valuei;
}
- valuei = this[i];
- valuej = this[upper];
- this[i] = valuej;
- this[upper] = valuej;
-
- // Sort the sub-partitions.
- InnerSort(lower, i - 1, comparer);
- InnerSort(i + 1, upper, comparer);
}
! #endif
}
--- 658,726 ----
}
! // Inner version of "Sort".
public 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
{
! // Find two values to be
swapped.
! while(comparer.Compare(this[i],
pivot) < 0)
{
! ++i;
! }
! while(comparer.Compare(this[j],
pivot) > 0)
! {
! --j;
}
! if(i > j)
{
! break;
}
!
! // Swap the values.
! if(i < j)
{
! temp = this[i];
! this[i] = this[j];
! this[j] = temp;
}
+ ++i;
+ --j;
}
! while(i <= j);
!
! // Sort the partitions.
! if((j - lower) <= (upper - i))
{
! if(lower < j)
! {
! InnerSort(lower, j,
comparer);
! }
! lower = i;
}
else
{
! if(i < upper)
{
! InnerSort(i, upper,
comparer);
}
! upper = j;
}
}
! while(lower < upper);
}
***************
*** 775,782 ****
public virtual void Sort()
{
! InnerSort(0, Count - 1, null);
}
public virtual void Sort(IComparer comparer)
{
InnerSort(0, Count - 1, comparer);
}
--- 728,739 ----
public virtual void Sort()
{
! InnerSort(0, Count - 1, Comparer.Default);
}
public virtual void Sort(IComparer comparer)
{
+ if(comparer == null)
+ {
+ comparer = Comparer.Default;
+ }
InnerSort(0, Count - 1, comparer);
}
***************
*** 796,799 ****
--- 753,760 ----
{
throw new
ArgumentException(_("Arg_InvalidArrayRange"));
+ }
+ if(comparer == null)
+ {
+ comparer = Comparer.Default;
}
InnerSort(index, index + count - 1, comparer);
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Dotgnu-pnet-commits] CVS: pnetlib/runtime/System/Collections ArrayList.cs,1.12,1.13,
Rhys Weatherley <address@hidden> <=