[Igarden-commit] Garden/source/LayoutDB MaterialCollection.cpp, 1.6.2.2, 1.6.2.3

[Jeffrey B. <jlb...@us...>]

Update of /cvsroot/igarden/Garden/source/LayoutDB
In directory sc8-pr-cvs2.sourceforge.net:/tmp/cvs-serv1028

Modified Files:
      Tag: Release_branch_v1
	MaterialCollection.cpp 
Log Message:
Change MaterialCollection sort to Quicksort

Index: MaterialCollection.cpp
===================================================================
RCS file: /cvsroot/igarden/Garden/source/LayoutDB/MaterialCollection.cpp,v
retrieving revision 1.6.2.2
retrieving revision 1.6.2.3
diff -C2 -d -r1.6.2.2 -r1.6.2.3
*** MaterialCollection.cpp	9 Dec 2006 17:45:35 -0000	1.6.2.2
--- MaterialCollection.cpp	12 Dec 2006 03:57:09 -0000	1.6.2.3
***************
*** 27,31 ****
  #include "SourceMaterialFile.h"
  
! 	enum matCollectProp_t
  	{
  	kFieldMatCollectName,
--- 27,33 ----
  #include "SourceMaterialFile.h"
  
! void QuicksortByName(XGDynArray<matCollItem_t*> &items, long left, long right);
! 
! enum matCollectProp_t
  	{
  	kFieldMatCollectName,
***************
*** 365,398 ****
  	{	
  		numItems = _items.Length();
! 		for(i = _items.Length()-1; i >= 0 && _items[i]->sortName.Length() == 0; i--)
  			_items[i]->sortName = _items[i]->mat->GetDisplayName(namePref);
  		
! 		// I know I know, but for a small number of items which should be already 
! 		// be nearly sorted, this should be enough.
! 		for (i = 0; i < (numItems - 1); ++i)
! 		{
! 			NoSwaps = true;  // Checks to see if any swaps happened
! 			
! 			for (unsigned int j = 1; j < (numItems - i); ++j)
! 			{
! 				if (_items[j - 1]->sortName > _items[j]->sortName)
! 				{
! 					intermediate = _items[j-1];
! 					_items[j-1] = _items[j];
! 					_items[j] = intermediate;
! 					
! 					// There was a swap, so set the flag false
! 					if (NoSwaps)
! 						NoSwaps = false;
! 				}
! 			}
! 			
! 			// If the sort didn't do anything (i.e. if the array is
! 			// sorted), then stop the algorithm.
! 			if (NoSwaps)
! 				break;
! 		}
  		_needsSort = false;
  		_sortType = namePref;
  	}
  }
--- 367,408 ----
  	{	
  		numItems = _items.Length();
! 		for(i = numItems-1; i >= 0 && _items[i]->sortName.Length() == 0; i--)
  			_items[i]->sortName = _items[i]->mat->GetDisplayName(namePref);
  		
! 		if(numItems >= 1)
! 			QuicksortByName(_items, 0, _items.Length()-1);
  		_needsSort = false;
  		_sortType = namePref;
  	}
  }
+ 
+ // A simple recursive quicksort
+ void QuicksortByName(XGDynArray<matCollItem_t*> &items, long left, long right)
+ {
+ 	long			i, j;
+ 	matCollItem_t	*pivot, *tmp;
+ 	
+ 	i = left;
+ 	j = right;
+ 	pivot = items[(left+right)/2];
+ 	do
+ 	{
+ 		while(items[i]->sortName < pivot->sortName)
+ 			i++;
+ 		while(pivot->sortName < items[j]->sortName)
+ 			j--;
+ 		if(i<=j)
+ 		{
+ 			tmp = items[i];
+ 			items[i] = items[j];
+ 			items[j] = tmp;
+ 			i++;
+ 			j--;
+ 		}
+ 	} while(i <= j);
+ 	if(left < j)
+ 		QuicksortByName(items, left,j);
+ 	if(i < right)
+ 		QuicksortByName(items, i,right);
+ }
+