source: OGRE/trunk/ogrenew/OgreMain/include/OgreRadixSort.h @ 692

Revision 692, 9.4 KB checked in by mattausch, 19 years ago (diff)

adding ogre 1.2 and dependencies

Line 
1/*
2-----------------------------------------------------------------------------
3This source file is part of OGRE
4    (Object-oriented Graphics Rendering Engine)
5For the latest info, see http://www.ogre3d.org/
6
7Copyright (c) 2000-2005 The OGRE Team
8Also see acknowledgements in Readme.html
9
10This program is free software; you can redistribute it and/or modify it under
11the terms of the GNU Lesser General Public License as published by the Free Software
12Foundation; either version 2 of the License, or (at your option) any later
13version.
14
15This program is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
18
19You should have received a copy of the GNU Lesser General Public License along with
20this program; if not, write to the Free Software Foundation, Inc., 59 Temple
21Place - Suite 330, Boston, MA 02111-1307, USA, or go to
22http://www.gnu.org/copyleft/lesser.txt.
23-----------------------------------------------------------------------------
24*/
25#ifndef __RadixSort_H__
26#define __RadixSort_H__
27
28#include "OgrePrerequisites.h"
29
30namespace Ogre {
31
32        /** Class for performing a radix sort (fast comparison-less sort based on
33                byte value) on various standard STL containers.
34        @remarks
35                A radix sort is a very fast sort algorithm. It doesn't use comparisons
36                and thus is able to break the theoretical minimum O(N*logN) complexity.
37                Radix sort is complexity O(k*N), where k is a constant. Note that radix
38                sorting is not in-place, it requires additional storage, so it trades
39                memory for speed. The overhead of copying means that it is only faster
40                for fairly large datasets, so you are advised to only use it for collections
41                of at least a few hundred items.
42        @par
43                This is a template class to allow it to deal with a variety of containers,
44                and a variety of value types to sort on. In addition to providing the
45                container and value type on construction, you also need to supply a
46                functor object which will retrieve the value to compare on for each item
47                in the list. For example, if you had an std::vector of by-value instances
48                of an object of class 'Bibble', and you wanted to sort on
49                Bibble::getDoobrie(), you'd have to firstly create a functor
50                like this:
51        @code
52                struct BibbleSortFunctor
53                {
54                        float operator()(const Bibble& val) const
55                        {
56                                return val.getDoobrie();
57                        }
58                }
59        @endcode
60                Then, you need to declare a RadixSort class which names the container type,
61                the value type in the container, and the type of the value you want to
62                sort by. You can then call the sort function. E.g.
63        @code
64                RadixSort<BibbleList, Bibble, float> radixSorter;
65                BibbleSortFunctor functor;
66
67                radixSorter.sort(myBibbleList, functor);
68        @endcode
69                You should try to reuse RadixSort instances, since repeated allocation of the
70                internal storage is then avoided.
71        @note
72                Radix sorting is often associated with just unsigned integer values. Our
73                implementation can handle both unsigned and signed integers, as well as
74                floats (which are often not supported by other radix sorters). doubles
75                are not supported; you will need to implement your functor object to convert
76                to float if you wish to use this sort routine.
77        */
78        template <class TContainer, class TContainerValueType, typename TCompValueType>
79        class RadixSort
80        {
81        public:
82                typedef typename TContainer::iterator ContainerIter;
83        protected:
84                /// Alpha-pass counters of values (histogram)
85                /// 4 of them so we can radix sort a maximum of a 32bit value
86                int mCounters[4][256];
87                /// Beta-pass offsets
88                int mOffsets[256];
89                /// Sort area size
90                int mSortSize;
91                /// Number of passes for this type
92                int mNumPasses;
93
94                struct SortEntry
95                {
96                        TCompValueType key;
97                        ContainerIter iter;
98                        SortEntry() {}
99                        SortEntry(TCompValueType k, ContainerIter it)
100                                : key(k), iter(it) {}
101
102                };
103                /// Temp sort storage
104                std::vector<SortEntry> mSortArea1;
105                std::vector<SortEntry> mSortArea2;
106                std::vector<SortEntry>* mSrc;
107                std::vector<SortEntry>* mDest;
108                TContainer mTmpContainer; // initial copy
109
110
111                void sortPass(int byteIndex)
112                {
113                        // Calculate offsets
114                        // Basically this just leaves gaps for duplicate entries to fill
115                        mOffsets[0] = 0;
116                        for (int i = 1; i < 256; ++i)
117                        {
118                                mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
119                        }
120
121                        // Sort pass
122                        for (int i = 0; i < mSortSize; ++i)
123                        {
124                                unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key);
125                                (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
126                        }
127
128                }
129                template <typename T>
130                void finalPass(int byteIndex, T val)
131                {
132                        // default is to do normal pass
133                        sortPass(byteIndex);
134                }
135               
136                // special case signed int
137                void finalPass(int byteIndex, int val)
138                {
139                        int numNeg = 0;
140                        // all negative values are in entries 128+ in most significant byte
141                        for (int i = 128; i < 256; ++i)
142                        {
143                                numNeg += mCounters[byteIndex][i];
144                        }
145                        // Calculate offsets - positive ones start at the number of negatives
146                        // do positive numbers
147                        mOffsets[0] = numNeg;
148                        for (int i = 1; i < 128; ++i)
149                        {
150                                mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
151                        }
152                        // Do negative numbers (must start at zero)
153                        // No need to invert ordering, already correct (-1 is highest number)
154                        mOffsets[128] = 0;
155                        for (int i = 129; i < 256; ++i)
156                        {
157                                mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
158                        }
159
160                        // Sort pass
161                        for (int i = 0; i < mSortSize; ++i)
162                        {
163                                unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key);
164                                (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
165                        }
166                }
167               
168
169                // special case float
170                void finalPass(int byteIndex, float val)
171                {
172                        // floats need to be special cased since negative numbers will come
173                        // after positives (high bit = sign) and will be in reverse order
174                        // (no ones-complement of the +ve value)
175                        int numNeg = 0;
176                        // all negative values are in entries 128+ in most significant byte
177                        for (int i = 128; i < 256; ++i)
178                        {
179                                numNeg += mCounters[byteIndex][i];
180                        }
181                        // Calculate offsets - positive ones start at the number of negatives
182                        // do positive numbers normally
183                        mOffsets[0] = numNeg;
184                        for (int i = 1; i < 128; ++i)
185                        {
186                                mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
187                        }
188                        // Do negative numbers (must start at zero)
189                        // Also need to invert ordering
190                        // In order to preserve the stability of the sort (essential since
191                        // we rely on previous bytes already being sorted) we have to count
192                        // backwards in our offsets from
193                        mOffsets[255] = mCounters[byteIndex][255];
194                        for (int i = 254; i > 127; --i)
195                        {
196                                mOffsets[i] = mOffsets[i+1] + mCounters[byteIndex][i];
197                        }
198
199                        // Sort pass
200                        for (int i = 0; i < mSortSize; ++i)
201                        {
202                                unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key);
203                                if (byteVal > 127)
204                                {
205                                        // -ve; pre-decrement since offsets set to count
206                                        (*mDest)[--mOffsets[byteVal]] = (*mSrc)[i];
207                                }
208                                else
209                                {
210                                        // +ve
211                                        (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
212                                }
213                        }
214                }
215
216                inline unsigned char getByte(int byteIndex, TCompValueType val)
217                {
218#if OGRE_ENDIAN == OGRE_ENDIAN_LITTLE
219                        return ((unsigned char*)(&val))[byteIndex];
220#else
221                        return ((unsigned char*)(&val))[mNumPasses - byteIndex - 1];
222#endif
223                }
224
225        public:
226
227                RadixSort() {}
228                ~RadixSort() {}
229
230                /** Main sort function
231                @param container A container of the type you declared when declaring
232                @param func A functor which returns the value for comparison when given
233                        a container value
234                */
235                template <class TFunction>
236                void sort(TContainer& container, TFunction func)
237                {
238                        if (container.empty())
239                                return;
240
241                        // Set up the sort areas
242                        mSortSize = static_cast<int>(container.size());
243                        mSortArea1.resize(container.size());
244                        mSortArea2.resize(container.size());
245
246                        // Copy data now (we need constant iterators for sorting)
247                        mTmpContainer = container;
248
249                        mNumPasses = sizeof(TCompValueType);
250
251                        // Counter pass
252                        // Initialise the counts
253                        int p;
254                        for (p = 0; p < mNumPasses; ++p)
255                                memset(mCounters[p], 0, sizeof(int) * 256);
256
257                        // Perform alpha pass to count
258                        ContainerIter i = mTmpContainer.begin();
259                        TCompValueType prevValue = func.operator()(*i);
260                        bool needsSorting = false;
261                        for (int u = 0; i != mTmpContainer.end(); ++i, ++u)
262                        {
263                                // get sort value
264                                TCompValueType val = func.operator()(*i);
265                                // cheap check to see if needs sorting (temporal coherence)
266                                if (!needsSorting && val < prevValue)
267                                        needsSorting = true;
268
269                                // Create a sort entry
270                                mSortArea1[u].key = val;
271                                mSortArea1[u].iter = i;
272
273                                // increase counters
274                                for (p = 0; p < mNumPasses; ++p)
275                                {
276                                        unsigned char byteVal = getByte(p, val);
277                                        mCounters[p][byteVal]++;
278                                }
279
280                                prevValue = val;
281
282                        }
283
284                        // early exit if already sorted
285                        if (!needsSorting)
286                                return;
287
288
289                        // Sort passes
290                        mSrc = &mSortArea1;
291                        mDest = &mSortArea2;
292
293                        for (p = 0; p < mNumPasses - 1; ++p)
294                        {
295                                sortPass(p);
296                                // flip src/dst
297                                std::vector<SortEntry>* tmp = mSrc;
298                                mSrc = mDest;
299                                mDest = tmp;
300                        }
301                        // Final pass may differ, make polymorphic
302                        finalPass(p, prevValue);
303
304                        // Copy everything back
305                        int c = 0;
306                        for (i = container.begin();
307                                i != container.end(); ++i, ++c)
308                        {
309                                *i = *((*mDest)[c].iter);
310                        }
311                }
312
313        };
314
315
316}
317#endif
318
Note: See TracBrowser for help on using the repository browser.