00001 /* 00002 ----------------------------------------------------------------------------- 00003 This source file is part of OGRE 00004 (Object-oriented Graphics Rendering Engine) 00005 For the latest info, see http://www.ogre3d.org/ 00006 00007 Copyright (c) 2000-2006 Torus Knot Software Ltd 00008 Also see acknowledgements in Readme.html 00009 00010 This program is free software; you can redistribute it and/or modify it under 00011 the terms of the GNU Lesser General Public License as published by the Free Software 00012 Foundation; either version 2 of the License, or (at your option) any later 00013 version. 00014 00015 This program is distributed in the hope that it will be useful, but WITHOUT 00016 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 00017 FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 00018 00019 You should have received a copy of the GNU Lesser General Public License along with 00020 this program; if not, write to the Free Software Foundation, Inc., 59 Temple 00021 Place - Suite 330, Boston, MA 02111-1307, USA, or go to 00022 http://www.gnu.org/copyleft/lesser.txt. 00023 00024 You may alternatively use this source under the terms of a specific version of 00025 the OGRE Unrestricted License provided you have obtained such a license from 00026 Torus Knot Software Ltd. 00027 ----------------------------------------------------------------------------- 00028 */ 00029 #ifndef __RadixSort_H__ 00030 #define __RadixSort_H__ 00031 00032 #include "OgrePrerequisites.h" 00033 00034 namespace Ogre { 00035 00082 template <class TContainer, class TContainerValueType, typename TCompValueType> 00083 class RadixSort 00084 { 00085 public: 00086 typedef typename TContainer::iterator ContainerIter; 00087 protected: 00090 int mCounters[4][256]; 00092 int mOffsets[256]; 00094 int mSortSize; 00096 int mNumPasses; 00097 00098 struct SortEntry 00099 { 00100 TCompValueType key; 00101 ContainerIter iter; 00102 SortEntry() {} 00103 SortEntry(TCompValueType k, ContainerIter it) 00104 : key(k), iter(it) {} 00105 00106 }; 00108 std::vector<SortEntry> mSortArea1; 00109 std::vector<SortEntry> mSortArea2; 00110 std::vector<SortEntry>* mSrc; 00111 std::vector<SortEntry>* mDest; 00112 TContainer mTmpContainer; // initial copy 00113 00114 00115 void sortPass(int byteIndex) 00116 { 00117 // Calculate offsets 00118 // Basically this just leaves gaps for duplicate entries to fill 00119 mOffsets[0] = 0; 00120 for (int i = 1; i < 256; ++i) 00121 { 00122 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1]; 00123 } 00124 00125 // Sort pass 00126 for (int i = 0; i < mSortSize; ++i) 00127 { 00128 unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key); 00129 (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i]; 00130 } 00131 00132 } 00133 template <typename T> 00134 void finalPass(int byteIndex, T val) 00135 { 00136 // default is to do normal pass 00137 sortPass(byteIndex); 00138 } 00139 00140 // special case signed int 00141 void finalPass(int byteIndex, int val) 00142 { 00143 int numNeg = 0; 00144 // all negative values are in entries 128+ in most significant byte 00145 for (int i = 128; i < 256; ++i) 00146 { 00147 numNeg += mCounters[byteIndex][i]; 00148 } 00149 // Calculate offsets - positive ones start at the number of negatives 00150 // do positive numbers 00151 mOffsets[0] = numNeg; 00152 for (int i = 1; i < 128; ++i) 00153 { 00154 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1]; 00155 } 00156 // Do negative numbers (must start at zero) 00157 // No need to invert ordering, already correct (-1 is highest number) 00158 mOffsets[128] = 0; 00159 for (int i = 129; i < 256; ++i) 00160 { 00161 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1]; 00162 } 00163 00164 // Sort pass 00165 for (int i = 0; i < mSortSize; ++i) 00166 { 00167 unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key); 00168 (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i]; 00169 } 00170 } 00171 00172 00173 // special case float 00174 void finalPass(int byteIndex, float val) 00175 { 00176 // floats need to be special cased since negative numbers will come 00177 // after positives (high bit = sign) and will be in reverse order 00178 // (no ones-complement of the +ve value) 00179 int numNeg = 0; 00180 // all negative values are in entries 128+ in most significant byte 00181 for (int i = 128; i < 256; ++i) 00182 { 00183 numNeg += mCounters[byteIndex][i]; 00184 } 00185 // Calculate offsets - positive ones start at the number of negatives 00186 // do positive numbers normally 00187 mOffsets[0] = numNeg; 00188 for (int i = 1; i < 128; ++i) 00189 { 00190 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1]; 00191 } 00192 // Do negative numbers (must start at zero) 00193 // Also need to invert ordering 00194 // In order to preserve the stability of the sort (essential since 00195 // we rely on previous bytes already being sorted) we have to count 00196 // backwards in our offsets from 00197 mOffsets[255] = mCounters[byteIndex][255]; 00198 for (int i = 254; i > 127; --i) 00199 { 00200 mOffsets[i] = mOffsets[i+1] + mCounters[byteIndex][i]; 00201 } 00202 00203 // Sort pass 00204 for (int i = 0; i < mSortSize; ++i) 00205 { 00206 unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key); 00207 if (byteVal > 127) 00208 { 00209 // -ve; pre-decrement since offsets set to count 00210 (*mDest)[--mOffsets[byteVal]] = (*mSrc)[i]; 00211 } 00212 else 00213 { 00214 // +ve 00215 (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i]; 00216 } 00217 } 00218 } 00219 00220 inline unsigned char getByte(int byteIndex, TCompValueType val) 00221 { 00222 #if OGRE_ENDIAN == OGRE_ENDIAN_LITTLE 00223 return ((unsigned char*)(&val))[byteIndex]; 00224 #else 00225 return ((unsigned char*)(&val))[mNumPasses - byteIndex - 1]; 00226 #endif 00227 } 00228 00229 public: 00230 00231 RadixSort() {} 00232 ~RadixSort() {} 00233 00239 template <class TFunction> 00240 void sort(TContainer& container, TFunction func) 00241 { 00242 if (container.empty()) 00243 return; 00244 00245 // Set up the sort areas 00246 mSortSize = static_cast<int>(container.size()); 00247 mSortArea1.resize(container.size()); 00248 mSortArea2.resize(container.size()); 00249 00250 // Copy data now (we need constant iterators for sorting) 00251 mTmpContainer = container; 00252 00253 mNumPasses = sizeof(TCompValueType); 00254 00255 // Counter pass 00256 // Initialise the counts 00257 int p; 00258 for (p = 0; p < mNumPasses; ++p) 00259 memset(mCounters[p], 0, sizeof(int) * 256); 00260 00261 // Perform alpha pass to count 00262 ContainerIter i = mTmpContainer.begin(); 00263 TCompValueType prevValue = func.operator()(*i); 00264 bool needsSorting = false; 00265 for (int u = 0; i != mTmpContainer.end(); ++i, ++u) 00266 { 00267 // get sort value 00268 TCompValueType val = func.operator()(*i); 00269 // cheap check to see if needs sorting (temporal coherence) 00270 if (!needsSorting && val < prevValue) 00271 needsSorting = true; 00272 00273 // Create a sort entry 00274 mSortArea1[u].key = val; 00275 mSortArea1[u].iter = i; 00276 00277 // increase counters 00278 for (p = 0; p < mNumPasses; ++p) 00279 { 00280 unsigned char byteVal = getByte(p, val); 00281 mCounters[p][byteVal]++; 00282 } 00283 00284 prevValue = val; 00285 00286 } 00287 00288 // early exit if already sorted 00289 if (!needsSorting) 00290 return; 00291 00292 00293 // Sort passes 00294 mSrc = &mSortArea1; 00295 mDest = &mSortArea2; 00296 00297 for (p = 0; p < mNumPasses - 1; ++p) 00298 { 00299 sortPass(p); 00300 // flip src/dst 00301 std::vector<SortEntry>* tmp = mSrc; 00302 mSrc = mDest; 00303 mDest = tmp; 00304 } 00305 // Final pass may differ, make polymorphic 00306 finalPass(p, prevValue); 00307 00308 // Copy everything back 00309 int c = 0; 00310 for (i = container.begin(); 00311 i != container.end(); ++i, ++c) 00312 { 00313 *i = *((*mDest)[c].iter); 00314 } 00315 } 00316 00317 }; 00318 00319 00320 } 00321 #endif 00322
Copyright © 2008 Torus Knot Software Ltd
This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.
Last modified Sun Sep 27 22:02:25 2009