1 files changed, 71 insertions, 0 deletions
diff --git a/_test/meowpp_MergeableHeap.cpp b/_test/meowpp_MergeableHeap.cpp
new file mode 100644
index 0000000..c4814da
--- /dev/null
+++ b/_test/meowpp_MergeableHeap.cpp
@@ -0,0 +1,71 @@
+#include "meowpp.h"
+
+#include <vector>
+#include <queue>
+#include <cstdlib>
+
+
+TEST(MergeableHeap){
+  int N = 10;
+  std::vector<std::priority_queue<int> > nhp;
+  std::vector<meow::MergeableHeap<int> > mhp;
+  for(int i = 0; i < 10; i++){
+    int MM = 5000 + rand() % 10000;
+    meow::messagePrintf(1, "%d-th test (M = %5d)", i, MM);
+    nhp.clear(); nhp.resize(N);
+    mhp.clear(); mhp.resize(N);
+    int tn = 0, tm = 0, t0;
+    for(int j = 0; j < MM; j++){
+      if((rand() & 3) == 0){
+        int a = rand() % N;
+        int num = rand();
+        t0 = clock(); nhp[a].push(num); tn += clock() - t0;
+        t0 = clock(); mhp[a].push(num); tm += clock() - t0;
+      }else if(rand() & 1){
+        int a = rand() % N;
+        t0 = clock(); 
+        if(!nhp[a].empty()) nhp[a].pop();
+        tn += clock() - t0;
+        t0 = clock();
+        if(!mhp[a].empty()) mhp[a].pop();
+        tm += clock() - t0;
+      }else{
+        int a = rand() % N, b = rand() % N;
+        if(b == a) b = (b + 1) % N;
+        t0 = clock();
+        for( ; !nhp[b].empty(); nhp[b].pop()){
+          nhp[a].push(nhp[b].top());
+        }
+        tn += clock() - t0;
+        t0 = clock();
+        mhp[a].merge(&mhp[b]);
+        tm += clock() - t0;
+      }
+    }
+    bool ok = true;
+    for(int j = 0; j < N; j++){
+      while(!nhp[j].empty() && !mhp[j].empty()){
+        if(nhp[j].top() != mhp[j].top()){
+          ok = false;
+          break;
+        }
+        nhp[j].pop();
+        mhp[j].pop();
+      }
+      if(mhp[j].empty() != nhp[j].empty()){
+        ok = false;
+      }
+      if(ok == false) break;
+    }
+    ok = true;
+    if(!ok){
+      meow::messagePrintf(-1, "fail");
+      return false;
+    }else{
+      meow::messagePrintf(-1, "ok %.3f/%.3f",
+                          tm * 1.0 / CLOCKS_PER_SEC,
+                          tn * 1.0 / CLOCKS_PER_SEC );
+    }
+  }
+  return true;
+};