L1TCalorimeter/interface/AccumulatingSort.h

0001 #include <vector>
0002 #include <list>
0003 #include <cstdint>
0004
0005 template <typename T>
0006 class AccumulatingSort {
0007 private:
0008   std::vector<std::list<T> > mSortArrays;
0009   uint32_t mSize;
0010
0011 private:
0012   void AccumulatorUnit(const std::list<T>& aInput, T& aAcc, std::list<T>& aTail) {
0013     aTail.clear();
0014
0015     bool lAccInserted(false);
0016
0017     for (typename std::list<T>::const_iterator lIt(aInput.begin()); lIt != aInput.end(); ++lIt) {
0018       if (!lAccInserted and
0019           !(*lIt >
0020             aAcc))  // Accumulator greater than or equal to new entry and not previously inserted -> Reinsert accumulator
0021       {
0022         aTail.push_back(aAcc);
0023         lAccInserted = true;
0024       }
0025       aTail.push_back(*lIt);
0026     }
0027
0028     aAcc = *aTail.begin();
0029     aTail.erase(aTail.begin());
0030   }
0031
0032 public:
0033   AccumulatingSort(const uint32_t& aSize) : mSortArrays(aSize + 1, std::list<T>(aSize)), mSize(aSize) {}
0034
0035   void Merge(const std::vector<T>& aInput, std::vector<T>& aOutput) {
0036     aOutput.resize(mSize);
0037
0038     mSortArrays[0].clear();
0039     mSortArrays[0].insert(mSortArrays[0].begin(), aInput.begin(), aInput.end());
0040
0041     for (uint32_t i(0); i != mSize; ++i)
0042       AccumulatorUnit(mSortArrays[i], aOutput[i], mSortArrays[i + 1]);
0043   }
0044 };