"L. Spiro Engine"
|
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__