CrystalSpace

Public API Reference

csutil/radixsort.h

Go to the documentation of this file.
00001 /*
00002   Crystal Space Radix Sort
00003   Copyright (C) 2006 by Marten Svanfeldt
00004 
00005   This library is free software; you can redistribute it and/or
00006   modify it under the terms of the GNU Library General Public
00007   License as published by the Free Software Foundation; either
00008   version 2 of the License, or (at your option) any later version.
00009 
00010   This library is distributed in the hope that it will be useful,
00011   but WITHOUT ANY WARRANTY; without even the implied warranty of
00012   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013   Library General Public License for more details.
00014 
00015   You should have received a copy of the GNU Library General Public
00016   License along with this library; if not, write to the Free
00017   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018 */
00019 
00020 #ifndef __CSUTIL_RADIX_SORT_H__
00021 #define __CSUTIL_RADIX_SORT_H__
00022 
00027 #include "csextern.h"
00028 
00029 // Hack: Work around problems caused by #defining 'new'.
00030 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00031 # undef new
00032 #endif
00033 #include <new>
00034 
00040 class CS_CRYSTALSPACE_EXPORT csRadixSorter
00041 {
00042 public:
00043   csRadixSorter();
00044   ~csRadixSorter();
00045 
00051   void Sort(uint32* array, size_t size);
00052 
00058   void Sort(int32* array, size_t size);
00059 
00065   void Sort(float* array, size_t size);
00066 
00070   inline size_t* GetRanks() const
00071   {
00072     return ranks1;
00073   }
00074 
00078   template<class T>
00079   void ReorderInplace (T* source, size_t size)
00080   {
00081     if(size*sizeof(T) < 0x4000) //Max out to 16kb
00082     {
00083       //Stack-allocated temp-array
00084       CS_ALLOC_STACK_ARRAY(uint8, tmpStorage, size*sizeof(T));
00085       T* dest = (T*)tmpStorage;
00086       for(size_t i = 0; i < size; i++)
00087       {
00088         new (&dest[i]) T(source[ranks1[i]]); //to make sure it is initialized
00089       }
00090       for(size_t i = 0; i < size; i++)
00091       {
00092         source[i] = dest[i];
00093         dest[i].~T();
00094       }
00095     }
00096     else
00097     {
00098       //Heap-allocated
00099       uint8* tmpStorage = (uint8*)cs_malloc(size*sizeof(T));
00100       T* dest = (T*)tmpStorage;
00101       for(size_t i = 0; i < size; i++)
00102       {
00103         new (&dest[i]) T(source[ranks1[i]]); //to make sure it is initialized
00104       }
00105       for(size_t i = 0; i < size; i++)
00106       {
00107         source[i] = dest[i];
00108         dest[i].~T();
00109       }
00110       cs_free(tmpStorage);
00111     }
00112   }
00113 
00118   template<class T>
00119   bool Reorder(const T* source, T* dest, size_t size)
00120   {
00121     //make sure ranges don't overlap
00122 #ifdef _DEBUG
00123     if((source + size - dest > 0 && dest - source < size) ||
00124        (dest + size - source > 0 && source - dest < size))
00125        return false;
00126 #endif
00127 
00128     for(size_t i = 0; i < size; i++)
00129     {
00130       dest[i] = source[ranks1[i]];
00131     }
00132     return true;
00133   }
00134 
00135 private:
00136   // Resize the rank arrays
00137   void Resize(size_t size);
00138 
00139   //Helper-function to create histograms. Returns true if values are already sorted
00140   template<class T>
00141   bool CreateHistogram(T* data, size_t size, uint32* histogram);
00142 
00143   // Check if pass should be performed
00144   template<class T>
00145   bool DoPass(size_t pass, T* data, size_t size, uint32* histogram);
00146 
00147   size_t currentSize;
00148   size_t* ranks1;
00149   size_t* ranks2;
00150 
00151   bool ranksValid;
00152 };
00153 
00154 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00155 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00156 #endif
00157 
00158 #endif

Generated for Crystal Space 1.0.2 by doxygen 1.4.7