File indexing completed on 2024-04-06 12:20:16
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))
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 };