[Anyedit-cvs]AnyEditv2 SortedArray.h,1.2,1.3

[<moo...@us...>]

Update of /cvsroot/anyedit/AnyEditv2
In directory sc8-pr-cvs1:/tmp/cvs-serv17674

Modified Files:
	SortedArray.h 
Log Message:
CSortedArray template caused Stack Overflows
Changed the sorting algorithm to Heapsort.
This doesn't use recursion at a small speed penalty,
but doesn't cause stack overflows.

Index: SortedArray.h
===================================================================
RCS file: /cvsroot/anyedit/AnyEditv2/SortedArray.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** SortedArray.h	8 May 2003 12:00:56 -0000	1.2
--- SortedArray.h	8 Dec 2003 08:01:04 -0000	1.3
***************
*** 8,11 ****
--- 8,17 ----
           PJN / 22-02-2000 Fixed a problem in CSortedArray::Find when there are no items in the array
           PJN / 29-02-2000 Fixed a problem in CSortedArray::Sort when there are no items in the array
+ 
+ 		 Leon Wennekers, 4 December 2003, Change for AnyEdit.
+ 		 Because sorting an CString SortedArray with 7 CString caused a stack overflow,
+ 		 I rewrote the Sort routine. It now uses the Heap Sort algorithm, which is a
+ 		 little bit slower then the old routine, but if you'll notice sorting is slow,
+ 		 it's time to use a database.
   
  Copyright (c) 1999 - 2000 by PJ Naughter.  
***************
*** 60,63 ****
--- 66,70 ----
      LPCOMPARE_FUNCTION m_lpfnCompareFunction;
      void swap(ARG_TYPE element1, ARG_TYPE element2);
+     void SortHelper(int root, int bottom);
  };
  
***************
*** 245,250 ****
  
  
  
! template
  <class TYPE, class ARG_TYPE>
  void CSortedArray<TYPE, ARG_TYPE>::Sort(int nLowIndex, int nHighIndex)
--- 252,258 ----
  
  
+ // (LW) If you like the old routine. Here it still is.
  
! /*template
  <class TYPE, class ARG_TYPE>
  void CSortedArray<TYPE, ARG_TYPE>::Sort(int nLowIndex, int nHighIndex)
***************
*** 284,288 ****
--- 292,377 ----
      Sort(left, last-1);
      Sort(last+1, right);
+ }*/
+ 
+ // (LW) Here is the new Heap Sort routines. Split in two function.
+ //      It's slower than merge or quick sort, but it doesn't use
+ //      recursion. So less change we get a stack overflow.
+ 
+ template
+ <class TYPE, class ARG_TYPE>
+ void CSortedArray<TYPE, ARG_TYPE>::SortHelper( int root, int bottom)
+ {
+ 	int done;
+ 	int maxChild;
+ 	TYPE temp;
+ 
+ 	done = 0;
+ 	while( (root*2 <= bottom ) && (!done) )
+ 	{
+ 		if( root*2 == bottom )
+ 			maxChild = root * 2;
+ 		else if( m_lpfnCompareFunction(ElementAt(root*2), ElementAt(root*2+1)) == 1 )
+ 			maxChild = root * 2;
+ 		else
+ 			maxChild = root * 2 + 1;
+ 
+ 		if( m_lpfnCompareFunction(ElementAt(root), ElementAt(maxChild)) == -1 )
+ 		{
+ 			temp = ElementAt(root);
+ 			SetAt( root, ElementAt(maxChild) );
+ 			SetAt( maxChild, temp );
+ 			root = maxChild;
+ 		}
+ 		else
+ 			done = 1;
+ 	}
  }
  
+ template
+ <class TYPE, class ARG_TYPE>
+ void CSortedArray<TYPE, ARG_TYPE>::Sort(int nLowIndex, int nHighIndex)
+ {
+     ASSERT(m_lpfnCompareFunction != NULL); //Did you forget to call SetCompareFunction prior to calling this function
+ 
+     //If there are no items in the array, then return immediately
+     if (GetSize() == 0)
+         return;
+ 
+  //   int left = nLowIndex;
+  //   int right = nHighIndex;
+ 	int index;
+ 	TYPE temp;
+ 
+     if (nHighIndex == -1)
+         nHighIndex = GetUpperBound();
+ 
+     if (nHighIndex-nLowIndex <= 0) //Do nothing if fewer than 2 elements are to be sorted
+         return;
+ 
+     // (not really needed, just to optimize)
+     if (nHighIndex-nLowIndex == 1)  //Do a simple comparison if only 2 elements
+     {
+         if (m_lpfnCompareFunction(ElementAt(nHighIndex), ElementAt(nLowIndex)) == -1)
+ 		{
+          //   swap(ElementAt(nLowIndex), ElementAt(nHighIndex));
+ 			temp = ElementAt(nLowIndex);
+ 			SetAt( nLowIndex, ElementAt(nHighIndex) );
+ 			SetAt( nHighIndex, temp );
+ 		}	
+         return;
+     }
+ 
+ 	for( index = ( nHighIndex - nLowIndex ) / 2; index >= 0; -- index )
+ 	{
+ 		SortHelper( index, nHighIndex - nLowIndex );
+ 	}
+ 
+ 	for( index = nHighIndex - nLowIndex; index >= 1; -- index )
+ 	{
+ 		temp = ElementAt(0);
+ 		SetAt( 0, ElementAt(index) );
+ 		SetAt( index, temp );
+ 		SortHelper( 0, index - 1 );
+ 	}
+ }
  #endif //__SORTEDARRAY_H__