[Dotgnu-pnet-commits] CVS: pnetlib/runtime/System/Collections ArrayList.cs,1.12,1.13

[Rhys Weatherley <address@hidden>]

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);