interface/common/bitonic_sort_ref.h

0001 #ifndef BITONIC_NEW_H
0002 #define BITONIC_NEW_H
0003
0004 #include <algorithm>
0005 #include <cassert>
0006
0007 #include "L1Trigger/Phase2L1ParticleFlow/interface/dbgPrintf.h"
0008
0009 inline unsigned int PowerOf2LessThan(unsigned int n) {
0010   unsigned int i = 1;
0011   unsigned int prev = 1;
0012   if (n <= 1)
0013     return n;
0014   while (i < n) {
0015     i <<= 1;
0016     if (i < n) {
0017       prev = i;
0018     } else {
0019       return prev;
0020     }
0021   }
0022   // shouldn't happen
0023   assert(false);
0024 }
0025
0026 template <typename T>
0027 void bitonicMerge(T in[], int InSize, T out[], int OutSize, bool dir) {
0028   //printDebug;
0029
0030   // size == 1 -> pass through
0031   if (InSize <= 1) {
0032     for (int i = 0; i < std::min(InSize, OutSize); ++i)
0033       out[i] = in[i];
0034     return;
0035   }
0036
0037   if (InSize > 1) {
0038     int LowerSize = PowerOf2LessThan(InSize);  //-- LowerSize >= Size / 2
0039     int UpperSize = InSize - LowerSize;        //-- UpperSize < LowerSiz
0040
0041     assert(UpperSize >= 0);
0042     assert(UpperSize <= LowerSize);
0043
0044     for (int i = 0; i < UpperSize; ++i) {
0045       if ((in[i] > in[i + LowerSize]) == dir) {
0046         // this checks should refer to the comments, "just needs to be long enough"
0047         if (i < OutSize)
0048           out[i] = in[i + LowerSize];
0049         if (i + LowerSize < OutSize)
0050           out[i + LowerSize] = in[i];
0051       } else {
0052         if (i < OutSize)
0053           out[i] = in[i];
0054         if (i + LowerSize < OutSize)
0055           out[i + LowerSize] = in[i + LowerSize];
0056       }
0057     }
0058
0059     // Copy the residual at the end. This limits the sorting in the overall descending direction (if out != in).
0060     if (LowerSize > UpperSize) {
0061       for (int i = UpperSize; i < LowerSize; ++i) {
0062         if (i < OutSize)
0063           out[i] = in[i];
0064       }
0065     }
0066
0067     T out2[LowerSize];
0068     bitonicMerge(out, LowerSize, out2, LowerSize, dir);
0069
0070     T out3[UpperSize];
0071     bitonicMerge(out + LowerSize, UpperSize, out3, UpperSize, dir);
0072
0073     // copy back to out; direction dependent.
0074     if (dir)  // ascending -- Copy up to OutSize
0075     {
0076       for (int i = 0; i < OutSize; ++i) {
0077         if (i < UpperSize)
0078           out[OutSize - i - 1] = out3[UpperSize - i - 1];
0079         else
0080           out[OutSize - i - 1] = out2[LowerSize - i - 1 + UpperSize];
0081       }
0082
0083     } else {  //descending
0084       for (int i = 0; i < LowerSize; ++i) {
0085         if (i < OutSize)
0086           out[i] = out2[i];
0087       }
0088       for (int i = LowerSize; i < OutSize; ++i)
0089         out[i] = out3[i - LowerSize];
0090     }
0091
0092   }  // InSize>1
0093
0094 }  // bitonicMerge
0095
0096 template <typename T>
0097 void bitonicSort(const T in[], int Start, int InSize, T out[], int OutSize, bool dir) {
0098   assert(OutSize > 0);
0099   if (InSize <= 1)  // copy in-> out and exit
0100   {
0101     for (int i = 0; i < std::min(InSize, OutSize); ++i)
0102       out[i] = in[i + Start];
0103     return;
0104   }
0105
0106   int LowerInSize = InSize / 2;
0107   int UpperInSize = InSize - LowerInSize;  //-- UpperSize >= LowerSize
0108
0109   int LowerOutSize = std::min(OutSize, LowerInSize);
0110   int UpperOutSize = std::min(OutSize, UpperInSize);
0111
0112   // sorted output
0113   T OutTmp[LowerOutSize + UpperOutSize];
0114
0115   // sort first half
0116   bitonicSort(in,
0117               Start,
0118               LowerInSize,
0119               OutTmp,
0120               LowerOutSize,
0121               not dir);  // the not dir enforce the sorting in overall descending direction.
0122
0123   // sort second half
0124   bitonicSort(in, Start + LowerInSize, UpperInSize, OutTmp + LowerOutSize, UpperOutSize, dir);
0125
0126   // create a temporary output vector "large enough" and then copy back
0127   int OutSize2 = LowerOutSize + UpperOutSize;
0128   T outTmp2[OutSize2];
0129   bitonicMerge(OutTmp, LowerOutSize + UpperOutSize, outTmp2, OutSize2, dir);
0130   //copy back to out the first OutSize
0131   for (int i = 0; i < OutSize; ++i) {
0132     if (dir) {  //ascending
0133       out[OutSize - 1 - i] = outTmp2[OutSize2 - 1 - i];
0134     } else {  //descending
0135       out[i] = outTmp2[i];
0136     }
0137   }
0138 }
0139
0140 template <typename T>
0141 void bitonic_sort_and_crop_ref(unsigned int nIn, unsigned int nOut, const T in[], T out[]) {  // just an interface
0142   bitonicSort(in, 0, nIn, out, nOut, 0);
0143 }
0144 #endif