1 #ifndef MERGEREDUCE_HPP
2 #define MERGEREDUCE_HPP
15 std::vector<std::unique_ptr<std::vector<T >> > buckets;
25 firstBucketSize(firstBucketSize)
27 buckets.push_back(std::unique_ptr < std::vector < T >> (
new std::vector<T>()));
28 buckets.reserve(firstBucketSize);
41 virtual std::unique_ptr<std::vector<T >> assemble();
48 virtual void insert(T
const & element);
53 virtual void reduce();
61 virtual void reduce(std::vector<T>
const * input,
int level, std::vector<T> * reduced) = 0;
70 virtual void merge(std::vector<T>
const * left, std::vector<T>
const * right,
int level, std::vector<T> * merged);
75 if (buckets[0]->size() >= firstBucketSize)
85 std::unique_ptr < std::vector < T >> reduced(
new std::vector<T>());
86 std::unique_ptr < std::vector < T >> merged(
new std::vector<T>());
89 if(buckets[level]->size() == 0)
92 reduce(buckets[level].
get(), level, reduced.get());
93 buckets[level]->clear();
95 while (buckets.size() >= level + 1 && buckets[level]->size() > 0)
98 merge(reduced.get(), buckets[level].get(), level, merged.get());
99 buckets[level]->clear();
101 reduce(merged.get(), level, reduced.get());
104 if (buckets.size() < level + 1)
105 buckets.push_back(std::unique_ptr < std::vector < T >> (
new std::vector<T>()));
106 buckets[level] = std::move(reduced);
114 for (
size_t i = 0; i < buckets.size(); ++i)
115 num += buckets[i]->size();
117 std::unique_ptr < std::vector < T >> assembly(
new std::vector<T>());
118 assembly->reserve(num);
120 for (
size_t i = 0; i < buckets.size(); ++i)
121 for (
size_t j = 0; j < buckets[i]->size(); ++j)
122 assembly->push_back((*buckets[i])[j]);
129 buckets[0]->push_back(element);
132 template<
typename T>
void MergeReduce<T>::merge(std::vector<T>
const * left, std::vector<T>
const * right,
int level, std::vector<T> * merged)
134 merged->insert(merged->end(), left->begin(), left->end());
135 merged->insert(merged->end(), right->begin(), right->end());