L1TCalorimeter/interface/BitonicSort.h

0001 #ifndef BitonicSort_h
0002 #define BitonicSort_h
0003
0004 #include <cstdint>
0005 #include <vector>
0006
0007 enum sort_direction { up, down };
0008
0009 // DECLARE!
0010 template <typename T>
0011 void BitonicSort(sort_direction aDir,
0012                  typename std::vector<T>::iterator& aDataStart,
0013                  typename std::vector<T>::iterator& aDataEnd);
0014 template <typename T>
0015 void BitonicMerge(sort_direction aDir,
0016                   typename std::vector<T>::iterator& aDataStart,
0017                   typename std::vector<T>::iterator& aDataEnd);
0018 //DEFINE!
0019
0020 //SORT
0021 template <typename T>
0022 void BitonicSort(sort_direction aDir,
0023                  typename std::vector<T>::iterator& aDataStart,
0024                  typename std::vector<T>::iterator& aDataEnd) {
0025   uint32_t lSize(aDataEnd - aDataStart);
0026   if (lSize > 1) {
0027     typename std::vector<T>::iterator lMidpoint(aDataStart + (lSize >> 1));
0028     if (aDir == down) {
0029       BitonicSort<T>(up, aDataStart, lMidpoint);
0030       BitonicSort<T>(down, lMidpoint, aDataEnd);
0031     } else {
0032       BitonicSort<T>(down, aDataStart, lMidpoint);
0033       BitonicSort<T>(up, lMidpoint, aDataEnd);
0034     }
0035     BitonicMerge<T>(aDir, aDataStart, aDataEnd);
0036   }
0037 }
0038
0039 //MERGE
0040 template <typename T>
0041 void BitonicMerge(sort_direction aDir,
0042                   typename std::vector<T>::iterator& aDataStart,
0043                   typename std::vector<T>::iterator& aDataEnd) {
0044   uint32_t lSize(aDataEnd - aDataStart);
0045   if (lSize > 1) {
0046     uint32_t lPower2(1);
0047     while (lPower2 < lSize)
0048       lPower2 <<= 1;
0049
0050     typename std::vector<T>::iterator lMidpoint(aDataStart + (lPower2 >> 1));
0051     typename std::vector<T>::iterator lFirst(aDataStart);
0052     typename std::vector<T>::iterator lSecond(lMidpoint);
0053
0054     for (; lSecond != aDataEnd; ++lFirst, ++lSecond) {
0055       if (((*lFirst) > (*lSecond)) == (aDir == up)) {
0056         std::swap(*lFirst, *lSecond);
0057       }
0058     }
0059
0060     BitonicMerge<T>(aDir, aDataStart, lMidpoint);
0061     BitonicMerge<T>(aDir, lMidpoint, aDataEnd);
0062   }
0063 }
0064
0065 #endif