"L. Spiro Engine"

F:/My Projects/LSEngine/Modules/LSStandardLib/Src/Search/LSSTDIndexSorter.h

00001 
00018 #ifndef __LSSTD_INDEXSORTER_H__
00019 #define __LSSTD_INDEXSORTER_H__
00020 
00021 #include "../LSSTDStandardLib.h"
00022 #include "LSSTDSearch.h"
00023 
00024 namespace lsstd {
00025 
00034         template <typename _tType>
00035         class CIndexSorter {
00036         public :
00037                 // == Various constructors.
00038                 LSE_CALLCTOR                                                    CIndexSorter() :
00039                         m_pui32Indices( NULL ),
00040                         m_ui32TotalIndices( 0UL ),
00041                         m_ui32AllocIndices( 0UL ) {
00042                 }
00043                 LSE_CALLCTOR                                                    ~CIndexSorter() {
00044                         delete [] m_pui32Indices;
00045                 }
00046 
00047 
00048                 // == Operators.
00055                 CIndexSorter<_tType> & LSE_CALL                 operator = ( const CIndexSorter<_tType> &_isOther ) {
00056                         if ( _isOther.m_pui32Indices > m_pui32Indices ) {
00057                                 // Have to allocate more.
00058                                 delete [] m_pui32Indices;
00059                                 m_pui32Indices = new LSUINT32[_isOther.m_pui32Indices];
00060                                 m_ui32AllocIndices = _isOther.m_pui32Indices;
00061                         }
00062                         m_ui32TotalIndices = _isOther.m_pui32Indices;
00063                         for ( LSUINT32 I = m_ui32TotalIndices; I--; ) {
00064                                 m_pui32Indices[I] = _isOther.m_pui32Indices[I];
00065                         }
00066                         return (*this);
00067                 }
00068 
00069 
00070                 // == Functions.
00079                 CIndexSorter<_tType> & LSE_CALL                 Sort( const _tType * _ptData, LSUINT32 _ui32Total, LSBOOL _bCheckIfSorted = true ) {
00080                         PrepareFor( _ui32Total );
00081                         if ( _ui32Total <= 1UL ) { return (*this); }    // 0 or 1 items cannot be sorted.
00082 
00083                         // Temporal coherence allows us to avoid work on already-sorted data.
00084                         //      When unsorted data is passed in, usually this loop will exit very quickly, so
00085                         //      there is almost no loss when data is never sorted.
00086                         if ( _bCheckIfSorted ) {
00087                                 LSBOOL bSorted = true;
00088                                 for ( LSUINT32 I = _ui32Total - 1UL; I--; ) {
00089                                         if ( !(_ptData[I] < _ptData[I+1UL]) ) {
00090                                                 bSorted = false;
00091                                                 break;
00092                                         }
00093                                 }
00094                                 if ( bSorted ) { return (*this); }
00095                         }
00096 
00097                         // Sort it.
00098                         CSearch::MergeSort( m_pui32Indices, m_ui32TotalIndices, sizeof( LSUINT32 ),
00099                                 SortComp, static_cast<LSVOID *>(const_cast<_tType *>(_ptData)) );
00100                         return (*this);
00101                 }
00102 
00111                 CIndexSorter<_tType> & LSE_CALL                 QuickSort( const _tType * _ptData, LSUINT32 _ui32Total, LSBOOL _bCheckIfSorted = false ) {
00112                         PrepareFor( _ui32Total );
00113                         if ( _ui32Total <= 1UL ) { return (*this); }    // 0 or 1 items cannot be sorted.
00114 
00115                         // Temporal coherence allows us to avoid work on already-sorted data.
00116                         //      When unsorted data is passed in, usually this loop will exit very quickly, so
00117                         //      there is almost no loss when data is never sorted.
00118                         if ( _bCheckIfSorted ) {
00119                                 LSBOOL bSorted = true;
00120                                 for ( LSUINT32 I = _ui32Total - 1UL; I--; ) {
00121                                         if ( !(_ptData[I] < _ptData[I+1UL]) ) {
00122                                                 bSorted = false;
00123                                                 break;
00124                                         }
00125                                 }
00126                                 if ( bSorted ) { return (*this); }
00127                         }
00128 
00129                         // Sort it.
00130                         QSort( m_pui32Indices, _ptData, m_ui32TotalIndices );
00131                         return (*this);
00132                 }
00133 
00141                 CIndexSorter<_tType> & LSE_CALL                 InsertionSort( const _tType * _ptData, LSUINT32 _ui32Total ) {
00142                         PrepareFor( _ui32Total );
00143                         if ( _ui32Total <= 1UL ) { return (*this); }    // 0 or 1 items cannot be sorted.
00144 
00145                         // Sort it.
00146                         InsertionSort( m_pui32Indices, _ptData, m_ui32TotalIndices );
00147                         return (*this);
00148                 }
00149 
00155                 const LSUINT32 * LSE_CALL                               GetIndices() const { return m_pui32Indices; }
00156 
00162                 LSVOID LSE_CALL                                                 PrepareFor( LSUINT32 _ui32Total ) {
00163                         if ( _ui32Total > m_ui32AllocIndices ) {
00164                                 // Up-size the allocated amount.
00165                                 delete [] m_pui32Indices;
00166                                 m_pui32Indices = new LSUINT32[_ui32Total];
00167                                 m_ui32AllocIndices = _ui32Total;
00168                                 m_ui32TotalIndices = 0UL;
00169                         }
00170                         if ( m_ui32TotalIndices > _ui32Total ) {
00171                                 for ( LSUINT32 I = 0UL; I < _ui32Total; ++I ) {
00172                                         // Add indices that were not added before.
00173                                         m_pui32Indices[I] = I;
00174                                 }
00175                         }
00176                         else {
00177                                 for ( LSUINT32 I = m_ui32TotalIndices; I < _ui32Total; ++I ) {
00178                                         // Add indices that were not added before.
00179                                         m_pui32Indices[I] = I;
00180                                 }
00181                         }
00182                         m_ui32TotalIndices = _ui32Total;
00183                 }
00184 
00185 
00186         protected :
00187                 // == Members.
00191                 LSUINT32 *                                                              m_pui32Indices;
00192 
00196                 LSUINT32                                                                m_ui32TotalIndices;
00197 
00201                 LSUINT32                                                                m_ui32AllocIndices;
00202 
00203 
00204                 // == Functions.
00213                 static LSINT32 LSE_CCALL                                SortComp( LSVOID * _pvContext,
00214                         const LSVOID * _pvLeft, const LSVOID * _pvRight ) {
00215                         _tType * ptSrc = static_cast<_tType *>(_pvContext);
00216                         const _tType * ptLeft = &ptSrc[(*static_cast<const LSUINT32 *>(_pvLeft))];
00217                         const _tType * ptRight = &ptSrc[(*static_cast<const LSUINT32 *>(_pvRight))];
00218                         if ( (*ptLeft) < (*ptRight) ) { return -1; }
00219                         if ( (*ptLeft) == (*ptRight) ) { return 0; }
00220                         return 1;
00221                 }
00222 
00229                 template <typename _tSwapType>
00230                 static LSVOID LSE_CALL                                  ShortSwap( _tSwapType * _ptA,
00231                         _tSwapType * _ptB ) {
00232                         _tSwapType tTemp = (*_ptA);
00233                         (*_ptA) = (*_ptB);
00234                         (*_ptB) = tTemp;
00235                 }
00236 
00244                 static LSVOID LSE_CALL                                  ShortSort( LSUINT32 * _pui32Indices, const _tType * _ptValues, LSUINTPTR _uiptrTotal ) {
00245                         LSUINT32 * pui32Low = _pui32Indices;
00246                         LSUINT32 * pui32Hi = _pui32Indices + _uiptrTotal;
00247                         LSUINT32 * pui32P, * pui32Max;
00248                         // Note: In assertions below, i and j are alway inside original bounds of the
00249                         //      array to sort.
00250 
00251                         while ( pui32Hi > pui32Low ) {
00252                                 // A[i] <= A[j] for i <= j, j > hi
00253                                 pui32Max = pui32Low;
00254                                 for ( pui32P = pui32Low + 1; pui32P <= pui32Hi; ++pui32P ) {
00255                                         // A[i] <= A[pui32Max] for lo <= i < p
00256                                         if ( _ptValues[(*pui32Max)] < _ptValues[(*pui32P)] ) {
00257                                                 pui32Max = pui32P;
00258                                         }
00259                                         // A[i] <= A[pui32Max] for lo <= i <= p
00260                                 }
00261 
00262                                 // A[i] <= A[pui32Max] for lo <= i <= hi
00263                                 LSUINT32 ui32Temp = (*pui32Max);
00264                                 (*pui32Max) = (*pui32Hi);
00265                                 (*pui32Hi) = ui32Temp;
00266 
00267                                 // A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi
00268                                 --pui32Hi;
00269 
00270                                 // A[i] <= A[j] for i <= j, j > hi, loop top condition established
00271                         }
00272                         // A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
00273                         //      so array is sorted.
00274                 }
00275 
00283                 static LSVOID LSE_CALL                                  QSort( LSUINT32 * _pui32Indices, const _tType * _ptValues, LSUINTPTR _uiptrTotal ) {
00284 #define LSSTL_STACKSIZE (8UL * sizeof( LSVOID * ) - 2UL)
00285 
00286                         LSUINT32 * ptLow, * ptHigh;
00287                         LSUINT32 * ptMid;
00288                         LSUINT32 * ptLowGuy, * ptHighGuy;
00289                         LSUINTPTR uiptrSize;
00290                         LSUINT32 * ptLowStack[LSSTL_STACKSIZE], * ptHighStack[LSSTL_STACKSIZE];
00291                         LSINT32 i32StackPointer;
00292 #undef LSSTL_STACKSIZE
00293 
00294                         // Validate the parameters.
00295                         if ( !(_ptValues != NULL || _uiptrTotal == 0UL) ) { return; }
00296                         if ( _uiptrTotal < 2UL ) { return; }
00297 
00298                         // Initialize the stack.
00299                         i32StackPointer = 0;
00300 
00301                         // Initialize the limits.
00302                         ptLow = _pui32Indices;
00303                         ptHigh = _pui32Indices + (_uiptrTotal - 1UL);
00304 
00305 
00306         Recurse :
00307 
00308                         // Number of elements to sort.
00309                         uiptrSize = static_cast<LSUINTPTR>(ptHigh - ptLow) + 1;
00310 
00311                         // Below a certain size, it is faster to use an O(n^2) sorting method.
00312                         if ( uiptrSize <= 8 ) {
00313                                 ShortSort( ptLow, _ptValues, uiptrSize - 1 );
00314                         }
00315                         else {
00316                                 // First we pick a partitioning element.  The efficiency of the
00317                                 //      algorithm demands that we find one that is approximately the median
00318                                 //      of the values, but also that we select one quickly.  We choose the
00319                                 //      median of the first, middle, and last elements, to avoid bad
00320                                 //      performance in the face of already-sorted data, or data that is made
00321                                 //      up of multiple sorted runs appended together.  Testing shows that a
00322                                 //      median-of-three algorithm provides better performance than simply
00323                                 //      picking the middle element for the latter case.
00324 
00325                                 // Find the middle element.
00326                                 ptMid = ptLow + (uiptrSize >> 1);
00327 
00328                                 // Sort the first, middle, last elements into order.
00329                                 if ( _ptValues[(*ptMid)] < _ptValues[(*ptLow)] ) {
00330                                         ShortSwap( ptLow, ptMid );
00331                                 }
00332                                 if ( _ptValues[(*ptHigh)] < _ptValues[(*ptLow)] ) {
00333                                         ShortSwap( ptLow, ptHigh );
00334                                 }
00335                                 if ( _ptValues[(*ptHigh)] < _ptValues[(*ptMid)] ) {
00336                                         ShortSwap( ptMid, ptHigh );
00337                                 }
00338 
00339                                 // We now wish to partition the array into three pieces, one consisting
00340                                 //      of elements <= partition element, one of elements equal to the
00341                                 //      partition element, and one of elements > than it.  This is done
00342                                 //      below; comments indicate conditions established at every step.
00343 
00344                                 ptLowGuy = ptLow;
00345                                 ptHighGuy = ptHigh;
00346 
00347                                 // Note that ptHighGuy decreases and ptLowGuy increases on every iteration,
00348                                 //      so loop must terminate.
00349                                 for ( ; ; ) {
00350                                         // ptLow <= ptLowGuy < ptHigh, ptLow < ptHighGuy <= ptHigh,
00351                                         //      A[i] <= A[ptMid] for ptLow <= i <= ptLowGuy,
00352                                         //      A[i] > A[ptMid] for ptHighGuy <= i < ptHigh,
00353                                         //      A[ptHigh] >= A[ptMid]
00354 
00355                                         // The doubled loop is to avoid calling _psfFunc( ptMid, ptMid ), since some
00356                                         //      existing comparison functions don't work when passed the same
00357                                         //      value for both pointers.
00358                                         if ( ptMid > ptLowGuy ) {
00359                                                 do  {
00360                                                         ++ptLowGuy;
00361                                                 } while ( ptLowGuy < ptMid && (_ptValues[(*ptLowGuy)] < _ptValues[(*ptMid)] ||
00362                                                         _ptValues[(*ptLowGuy)] == _ptValues[(*ptMid)]) );
00363                                         }
00364                                         if ( ptMid <= ptLowGuy ) {
00365                                                 do  {
00366                                                         ++ptLowGuy;
00367                                                 } while ( ptLowGuy <= ptHigh && (_ptValues[(*ptLowGuy)] < _ptValues[(*ptMid)] ||
00368                                                         _ptValues[(*ptLowGuy)] == _ptValues[(*ptMid)]) );
00369                                         }
00370 
00371                                         // ptLow < ptLowGuy <= ptHigh+1, A[i] <= A[ptMid] for ptLow <= i < ptLowGuy,
00372                                         //      either ptLowGuy > ptHigh or A[ptLowGuy] > A[ptMid]
00373 
00374                                         do  {
00375                                                 --ptHighGuy;
00376                                         } while ( ptHighGuy > ptMid && 
00377                                                 _ptValues[(*ptMid)] < _ptValues[(*ptHighGuy)] );
00378 
00379                                         // ptLow <= ptHighGuy < ptHigh, A[i] > A[ptMid] for ptHighGuy < i < ptHigh,
00380                                         //      either ptHighGuy == ptLow or A[ptHighGuy] <= A[ptMid]
00381 
00382                                         if ( ptHighGuy < ptLowGuy ) {
00383                                                 break;
00384                                         }
00385 
00386                                         // if ptLowGuy > ptHigh or ptHighGuy == ptLow, then we would have exited, so
00387                                         //      A[ptLowGuy] > A[ptMid], A[ptHighGuy] <= A[ptMid],
00388                                         //      ptLowGuy <= ptHigh, ptHighGuy > ptLow
00389 
00390                                         ShortSwap( ptLowGuy, ptHighGuy );
00391 
00392                                         // If the partition element was moved, follow it.  Only need
00393                                         //      to check for ptMid == ptHighGuy, since before the swap,
00394                                         //      A[ptLowGuy] > A[ptMid] implies ptLowGuy != ptMid.
00395 
00396                                         if ( ptMid == ptHighGuy ) {
00397                                                 ptMid = ptLowGuy;
00398                                         }
00399 
00400                                         // A[ptLowGuy] <= A[ptMid], A[ptHighGuy] > A[ptMid]; so condition at top
00401                                         //      of loop is re-established.
00402                                 }
00403 
00404                                 // A[i] <= A[ptMid] for ptLow <= i < ptLowGuy,
00405                                 //      A[i] > A[ptMid] for ptHighGuy < i < ptHigh,
00406                                 //      A[ptHigh] >= A[ptMid]
00407                                 //      ptHighGuy < ptLowGuy
00408                                 //      implying:
00409                                 //      ptHighGuy == ptLowGuy-1
00410                                 //      or ptHighGuy == ptHigh - 1, ptLowGuy == ptHigh + 1, A[ptHigh] == A[ptMid]
00411 
00412                                 // Find adjacent elements equal to the partition element.  The
00413                                 //      doubled loop is to avoid calling _psfFunc( ptMid, ptMid ), since some
00414                                 //      existing comparison functions don't work when passed the same value
00415                                 //      for both pointers.
00416 
00417                                 ++ptHighGuy;
00418                                 if ( ptMid < ptHighGuy ) {
00419                                         do  {
00420                                                 --ptHighGuy;
00421                                         } while ( ptHighGuy > ptMid &&
00422                                                 _ptValues[(*ptHighGuy)] == _ptValues[(*ptMid)] );
00423                                 }
00424                                 if ( ptMid >= ptHighGuy ) {
00425                                         do  {
00426                                                 --ptHighGuy;
00427                                         } while ( ptHighGuy > ptLow &&
00428                                                 _ptValues[(*ptHighGuy)] == _ptValues[(*ptMid)] );
00429                                 }
00430 
00431                                 // Okay, now we have the following:
00432                                 //      ptHighGuy < ptLowGuy
00433                                 //      ptLow <= ptHighGuy <= ptHigh
00434                                 //      A[i] <= A[ptMid] for ptLow <= i <= ptHighGuy
00435                                 //      A[i]  == A[ptMid] for ptHighGuy < i < ptLowGuy
00436                                 //      A[i]  >  A[ptMid] for ptLowGuy <= i < ptHigh
00437                                 //      A[ptHigh] >= A[ptMid]
00438 
00439                                 // We've finished the partition; now we want to sort the subarrays
00440                                 //      [ptLow, ptHighGuy] and [ptLowGuy, ptHigh].
00441                                 //      We do the smaller one first to minimize stack usage.
00442                                 //      We only sort arrays of length 2 or more.
00443 
00444                                 if ( ptHighGuy - ptLow >= ptHigh - ptLowGuy ) {
00445                                         if ( ptLow < ptHighGuy ) {
00446                                                 ptLowStack[i32StackPointer] = ptLow;
00447                                                 ptHighStack[i32StackPointer] = ptHighGuy;
00448                                                 ++i32StackPointer;
00449                                         }
00450 
00451                                         if ( ptLowGuy < ptHigh ) {
00452                                                 ptLow = ptLowGuy;
00453                                                 goto Recurse;
00454                                         }
00455                                 }
00456                                 else {
00457                                         if ( ptLowGuy < ptHigh ) {
00458                                                 ptLowStack[i32StackPointer] = ptLowGuy;
00459                                                 ptHighStack[i32StackPointer] = ptHigh;
00460                                                 ++i32StackPointer;
00461                                         }
00462 
00463                                         if ( ptLow < ptHighGuy ) {
00464                                                 ptHigh = ptHighGuy;
00465                                                 goto Recurse;
00466                                         }
00467                                 }
00468                         }
00469 
00470                         // We have sorted the array except for any pending sorts on the stack.
00471                         //      Check if there are any and do them.
00472                         --i32StackPointer;
00473                         if ( i32StackPointer >= 0 ) {
00474                                 ptLow = ptLowStack[i32StackPointer];
00475                                 ptHigh = ptHighStack[i32StackPointer];
00476 
00477                                 // Pop array from the stack.
00478                                 goto Recurse;
00479                         }
00480                         else { return; }
00481                 }
00482 
00490                 static LSVOID LSE_CALL                                  InsertionSort( LSUINT32 * _pui32Indices, const _tType * _ptValues, LSUINTPTR _uiptrTotal ) {
00491                         if ( _uiptrTotal <= 1UL ) { return; }
00492                         LSUINT32 * pui32Cur = _pui32Indices + 1UL;
00493                         LSUINT32 * pui32End = _pui32Indices + _uiptrTotal;
00494                         while ( pui32Cur < pui32End ) {
00495                                 const _tType * ptKey = &_ptValues[(*pui32Cur)];
00496                                 for ( LSUINT32 * pui32NextDown = pui32Cur - 1UL; pui32NextDown >= _pui32Indices && (*ptKey) < _ptValues[(*pui32NextDown)]; --pui32NextDown ) {
00497                                         LSUINT32 ui32Temp = (*pui32NextDown);
00498                                         (*pui32NextDown) = pui32NextDown[1];
00499                                         pui32NextDown[1] = ui32Temp;
00500                                 }
00501                                 ++pui32Cur;
00502                         }
00503                 }
00504         };
00505 
00506 }       // namespace lsstd
00507 
00508 #endif  // __LSSTD_INDEXSORTER_H__
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator