PROBI  1.0
 All Classes Functions
MergeReduce.hpp
1 #ifndef MERGEREDUCE_HPP
2 #define MERGEREDUCE_HPP
3 
4 #include <vector>
5 #include <memory>
6 
12 template<typename T> class MergeReduce
13 {
14 private:
15  std::vector<std::unique_ptr<std::vector<T >> > buckets;
16  int firstBucketSize;
17 
18 public:
19 
23  MergeReduce(int firstBucketSize) :
24  buckets(),
25  firstBucketSize(firstBucketSize)
26  {
27  buckets.push_back(std::unique_ptr < std::vector < T >> (new std::vector<T>()));
28  buckets.reserve(firstBucketSize);
29  }
30 
31  virtual ~MergeReduce()
32  {
33  }
34 
40  MergeReduce& operator<<(T const & element);
41  virtual std::unique_ptr<std::vector<T >> assemble();
42 
43 private:
48  virtual void insert(T const & element);
49 
53  virtual void reduce();
54 
61  virtual void reduce(std::vector<T> const * input, int level, std::vector<T> * reduced) = 0;
62 
70  virtual void merge(std::vector<T> const * left, std::vector<T> const * right, int level, std::vector<T> * merged);
71 };
72 
73 template<typename T> MergeReduce<T>& MergeReduce<T>::operator <<(T const & element)
74 {
75  if (buckets[0]->size() >= firstBucketSize)
76  reduce();
77  insert(element);
78 
79  return *this;
80 }
81 
82 template<typename T> void MergeReduce<T>::reduce()
83 {
84  int level = 0;
85  std::unique_ptr < std::vector < T >> reduced(new std::vector<T>());
86  std::unique_ptr < std::vector < T >> merged(new std::vector<T>());
87 
88  // Nothing to reduce
89  if(buckets[level]->size() == 0)
90  return;
91 
92  reduce(buckets[level].get(), level, reduced.get());
93  buckets[level]->clear();
94  ++level;
95  while (buckets.size() >= level + 1 && buckets[level]->size() > 0)
96  {
97  merged->clear();
98  merge(reduced.get(), buckets[level].get(), level, merged.get());
99  buckets[level]->clear();
100  reduced->clear();
101  reduce(merged.get(), level, reduced.get());
102  ++level;
103  }
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);
107 }
108 
109 template<typename T> std::unique_ptr<std::vector<T >> MergeReduce<T>::assemble()
110 {
111  reduce();
112 
113  size_t num = 0;
114  for (size_t i = 0; i < buckets.size(); ++i)
115  num += buckets[i]->size();
116 
117  std::unique_ptr < std::vector < T >> assembly(new std::vector<T>());
118  assembly->reserve(num);
119 
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]);
123 
124  return assembly;
125 }
126 
127 template<typename T> void MergeReduce<T>::insert(T const & element)
128 {
129  buckets[0]->push_back(element);
130 }
131 
132 template<typename T> void MergeReduce<T>::merge(std::vector<T> const * left, std::vector<T> const * right, int level, std::vector<T> * merged)
133 {
134  merged->insert(merged->end(), left->begin(), left->end());
135  merged->insert(merged->end(), right->begin(), right->end());
136 }
137 
138 #endif /* MERGEREDUCE_HPP */
139