1 files changed, 44 insertions, 9 deletions

@@ -3,18 +3,53 @@
 
 #include <map>
 #include <string>
+#include <random>
+#include <iostream>
 
 template <class T>
 class histogram {
-  public:
-    void add(const T& inst);
-    void compile();
-    const T& next() const;
-    void print() const;
-    
-  private:
-    std::map<T, int> freqtable;
-    std::map<int, T> distribution;
+public:
+
+  void add(const T& inst)
+  {
+    freqtable_[inst]++;
+  }
+
+  void compile()
+  {
+    distribution_.clear();
+
+    int max = 0;
+    for (auto& it : freqtable_)
+    {
+      max += it.second;
+      distribution_.emplace(max, it.first);
+    }
+
+    freqtable_.clear();
+  }
+
+  const T& next(std::mt19937& rng) const
+  {
+    int max = distribution_.rbegin()->first;
+    std::uniform_int_distribution<int> randDist(0, max - 1);
+    int r = randDist(rng);
+
+    return distribution_.upper_bound(r)->second;
+  }
+
+  void print() const
+  {
+    for (auto& freqpair : freqtable_)
+    {
+      std::cout << freqpair.first << ": " << freqpair.second << std::endl;
+    }
+  }
+
+private:
+
+  std::map<T, int> freqtable_;
+  std::map<int, T> distribution_;
 };
 
 #endif /* end of include guard: HISTOGRAM_H_24094D97 */