1 files changed, 91 insertions, 28 deletions

diff --git a/exp_3.cpp b/exp_3.cpp
index b7598e9..bda5681 100644
--- a/exp_3.cpp
+++ b/exp_3.cpp
@@ -3,58 +3,119 @@
 #include <cmath>
 #include <cstdio>
 #include <set>
+#include <tuple>
 #include <vector>
 
 constexpr size_t length = 1048576;
 constexpr size_t sample_length = 1000;
 
-int main() {
+#define CALC_HEIGHT
+
+#ifdef CALC_HEIGHT
+constexpr int block_size = 2;
+unsigned trailing_zeroes(size_t index) {
+  unsigned bits = 0;
+  unsigned x = index / block_size;
+
+  if (x) {
+    while (x % block_size == 0) {
+      ++bits;
+      x /= block_size;
+    }
+  }
+  return bits;
+}
+
+unsigned int getHeight(long loc) {
+  if (loc % block_size == 0) {
+    auto level = trailing_zeroes(loc) + 1;
+    return level - 1;
+  }
+
+  return 0;
+}
+#else
+unsigned int getHeight(long loc) { return loc; }
+#endif
+
+std::vector<long long> population_vector, sample_vector;
+
+void initialize(const std::vector<long long> &input_population,
+                const std::vector<long long> &input_sample) {
+  population_vector = input_population;
+  std::sort(population_vector.begin(), population_vector.end());
+  sample_vector = input_sample;
+  std::sort(sample_vector.begin(), sample_vector.end());
+}
+
+long double sample_cdf(long double x) {
+  auto it = lower_bound(sample_vector.begin(), sample_vector.end(), x);
+  if (it == sample_vector.end()) {
+    return 1;
+  }
+  if (it == sample_vector.begin()) {
+    return 0;
+  }
+  auto it_prev = it - 1;
+  return ((long double)(it_prev - sample_vector.begin()) +
+          (long double)(x - *it_prev) / (*it - *it_prev)) /
+         (long double)(sample_vector.size() - 1);
+}
+
+int infer_offset(double x) {
+  return int(sample_cdf(x) * double(population_vector.size()));
+}
 
-  std::vector<long long> vector1, vector2;
+// const double M_SQRT1_2 = sqrt(0.5);
+constexpr long long s_avg = 2147483648;
+constexpr long long s_stddev = 2147483648;
+
+double goal_cdf(double x) { return erfc(-x * M_SQRT1_2) * 0.5; }
+double stat_cdf(double x) { return goal_cdf((x - s_avg) / s_stddev); }
+
+int main() {
 
-  std::vector<long double> E;
+  std::vector<long long> original_vector;
 
   std::set<long long> set1, set2;
 
+  typedef std::tuple<int, int, long double> element_type;
+
+  std::vector<element_type> location;
+
   FILE *file = fopen("normal_distribution.txt", "r");
   for (long long i; fscanf(file, "%lld ", &i) != EOF;
-       vector1.push_back(i), set1.insert(i))
+       original_vector.push_back(i), set1.insert(i))
     ;
   fclose(file);
 
-  assert(vector1.size() == set1.size());
-  assert(vector1.size() == length);
+  assert(original_vector.size() == set1.size());
+  assert(original_vector.size() >= length);
 
-  auto it = vector1.begin();
+  auto it = original_vector.begin();
   for (int i = 1; i <= sample_length; i++) {
     auto element = *it;
     auto ret = set2.insert(element);
     if (ret.second) {
-      vector2.push_back(element);
+      sample_vector.push_back(element);
       // printf("%lld\n", element);
     }
     it++;
   }
 
-  assert(vector2.size() == sample_length);
+  assert(sample_vector.size() == sample_length);
 
-  auto it2 = set2.begin();
-  int cnt = 0;
-  for (long long it1 : set1) {
-    while (it1 > *it2 && it2 != set2.end())
-      it2++, cnt++;
-    // printf("%d ", cnt);
-  }
+  initialize(original_vector, sample_vector);
 
-  auto it1 = set1.begin();
-  cnt = 0;
-  for (it2 = set2.begin(); it2 != set2.end(); it2++) {
-    while (*it2 > *it1 && it1 != set1.end())
-      it1++, cnt++;
-    // printf("%d ", cnt);
+  for (auto iter = population_vector.begin(); iter != population_vector.end();
+       iter++) {
+    printf("%d,%d ", getHeight(infer_offset(*iter)),
+           getHeight(iter - population_vector.begin()));
   }
+  puts("");
+  return 0;
 
-  auto ita = set2.begin(), itb = set2.begin();
+  /*auto ita = set2.begin(), itb = set2.begin();
   itb++;
   long double dx = (*itb - *ita);
   int cnt1 = 0, cnt2 = 0;
@@ -77,14 +138,16 @@ int main() {
     // printf("%lld %lld %lld ", *ita, *it, *itb);
     long double res = (cnt2 + (*iter - *ita) / dx) / (sample_length - 1);
     auto single_e = std::abs(res - (long double)cnt1 / (length - 1));
-    E.push_back(single_e);
+    auto real_cnt2 = res * (length - 1) + 1;
+    location.emplace_back(getHeight(cnt1),
+                          getHeight((int)std::round(real_cnt2)), single_e);
     e += single_e;
     printf("%.4Lf ", res * 100);
   }
-  printf("\n%.4Lf", e);
-  for (auto element : E) {
-    printf("%.8Lf ", element);
+  printf("\n%.4Lf\n", e);
+  for (auto element : location) {
+    printf("%d,%d ", std::get<0>(element), std::get<1>(element));
   }
   puts("");
-  return 0;
+  return 0;*/
 }
\ No newline at end of file