add BIT

9 files changed, 1301 insertions, 26 deletions

diff --git a/_test/meowpp.cpp b/_test/meowpp.cpp
index e03edaa..805f459 100644
--- a/_test/meowpp.cpp
+++ b/_test/meowpp.cpp
@@ -1,32 +1,72 @@
-#include "dsa/KD_Tree.h"
-#include "Usage.h"
+#include "meowpp.h"
 
-bool testColors(){
-}
-bool testDisjointSet(){
-}
-bool testMergeableHeap(){
-}
+#include <string>
+#include <cstdlib>
+#include <ctime>
+
+////////////////////////////
+meow::Usage usg("meowpp"), usg2;
+int count = 0;
+TestFunctions tests;
+////////////////////////
 
 int main(int argc, char** argv){
-  Usage usg("meowpp"), usg2;
-  usg .addOption('h', "Display this help document");
-  usg2.addOption('t',
-                 "Test the i-th part of the meowpp and then quit",
-                 "<number>", "",
-                 false);
+  //srand(time(NULL));
+  usg.addOption('h', "Display this help document");
+  usg.addUsageBegin("<name> is a little test program to check whether"
+                    "the data structures in the template is correct by"
+                    "random generate lots of data to test");
+  usg.addUsageEnd  ("zzzzzzzzzzzzzzz....");
+  usg.import(usg2);
   
-      KD_Tree();
-      KD_Tree(size_t _dimension);
-      ~KD_Tree();
-      //
-      void   insert(Keys const& key, Value value);
-      void   build();
-      //
-      Value  query     (Keys const& point, int k) const;
-      Values rangeQuery(Keys const& point, int k) const;
-      //
-      void   clear();
-      void   reset(size_t _dimension);
+  std::string err;
+  if(usg.setArguments(argc, argv, &err) == false){
+    printf("%s\n\n%s\n", err.c_str(), usg.getUsage().c_str());
+    return 1;
+  }else if(usg.hasOptionSetup('h')){
+    printf("%s", usg.getUsage().c_str());
+    return 0;
+  }else{
+    usg2.update(usg);
+    if(usg2.getOptionValuesCount('t') > 0){
+      for(int i = 0, I = usg2.getOptionValuesCount('t'); i < I; i++){
+        int id = atoi(usg2.getOptionValue('t', i).c_str());
+        TestFunction* f = (TestFunction*)tests.getImplement(id);
+        if(f->run() == false){
+          printf("error occure on %s\n", f->name().c_str());
+          return 1;
+        }else{
+          printf("%s success\n", f->name().c_str());
+        }
+      }
+    }else{
+      std::vector<int> ids = tests.getIdentifys();
+      while(true){
+        for(int i = 0, I = ids.size(); i < I; i++){
+          TestFunction* f = (TestFunction*)tests.getImplement(i);
+          printf("    %d) %s\n", ids[i], f->name().c_str());
+        }
+        printf("please select(EOF to quit): ");
+        int id;
+        if(!~scanf("%d", &id)){
+          break;
+        }
+        printf("\n");
+        TestFunction* f = (TestFunction*)tests.getImplement(id);
+        if(f == NULL){
+          printf("Bad value!\n\n");
+          continue;
+        }
+        if(f->run() == false){
+          printf("error occure on %s\n\n", f->name().c_str());
+          return 1;
+        }else{
+          printf("%s success\n\n", f->name().c_str());
+        }
+      }
+      printf("\n");
+    }
+    return 0;
+  }
   return 0;
 }
diff --git a/_test/meowpp.h b/_test/meowpp.h
new file mode 100644
index 0000000..ca6c224
--- /dev/null
+++ b/_test/meowpp.h
@@ -0,0 +1,64 @@
+#ifndef   __meowpp_h__
+#define   __meowpp_h__
+
+#include "Usage.h"
+#include "utility.h"
+#include "colors/RGB.h"
+#include "colors/YUV.h"
+#include "colors/HSL.h"
+#include "colors/HSV.h"
+#include "dsa/DisjointSet.h"
+#include "dsa/KD_Tree.h"
+#include "dsa/VP_Tree.h"
+#include "dsa/SegmentTree.h"
+#include "dsa/BinaryIndexTree.h"
+#include "dsa/MergeableHeap.h"
+#include "dsa/SplayTree.h"
+#include "dsa/SplayTree_Range.h"
+#include "oo/Register_Implement.h"
+
+extern meow::Usage usg, usg2;
+extern int count;
+//////////////////////////////////
+class TestFunctions: public meow::RegisterInterface<int>{
+  public:
+    TestFunctions(): RegisterInterface(){
+      usg2.addOption('t',
+                     "Specify which part of the template to test",
+                     "name", "",
+                     false);
+    }
+    bool regImplement(meow::ImplementInterface<int>* imp,
+                      std::string const& str){
+      usg2.addOptionValueAccept('t',
+                                meow::stringPrintf("%d", imp->identify()),
+                                str);
+      return RegisterInterface::regImplement(imp);
+    }
+};
+extern TestFunctions tests;
+////////////////////////
+class TestFunction: public meow::ImplementInterface<int>{
+  private:
+    std::string _name;
+  public:
+    TestFunction(std::string const& __name):
+    ImplementInterface(count++), _name("testing code about " + __name){
+      tests.regImplement(this, _name);
+    }
+    virtual ~TestFunction(){ }
+    virtual bool run() = 0;
+    std::string name() const{ return _name; }
+};
+////////////////////////
+
+#define concat(a,b) a##b
+#define TEST(a) \
+class Test_##a: public TestFunction{ \
+  public: \
+          Test_##a(): TestFunction(#a){ } \
+  bool run();\
+} __test_##a; bool Test_##a::run()
+
+
+#endif // meowpp_h__
diff --git a/_test/meowpp_BinaryIndexTree.cpp b/_test/meowpp_BinaryIndexTree.cpp
new file mode 100644
index 0000000..3841a84
--- /dev/null
+++ b/_test/meowpp_BinaryIndexTree.cpp
@@ -0,0 +1,54 @@
+#include "meowpp.h"
+
+#include <vector>
+
+static int N = 100000;
+
+static std::vector<int> array;
+
+inline int sum(int k){
+  int x = 0;
+  for(int i = 0; i <= k; i++){
+    x += array[i];
+  }
+  return x;
+}
+
+static meow::BinaryIndexTree<int> bit;
+
+TEST(BinaryIndexTree){
+  size_t tMe = 0, tBi = 0, t0;
+  for(int z = 0; z < 10; z++){
+    meow::messagePrintf(1, "test %d", z);
+    bit.reset(N, 0);
+    array.clear();
+    array.resize(N, 0);
+    
+    int NN = rand() % 10000;
+    for(int i = 0; i < NN; i++){
+      int index = rand() % N;
+      if(rand() & 1){
+        int val = rand() % 1000;
+        t0 = clock(); array[i] += val; tMe += clock() - t0;
+        t0 = clock(); bit.update(i, val); tBi += clock() - t0;
+      }else{
+        if(sum(index) != bit.query(index)){
+          meow::messagePrintf(-1, "range-sum query fail");
+          return false;
+        }
+      }
+    }
+    int s = 0;
+    for(int i = 0; i < N; i++){
+      s += array[i];
+      if(s != bit.query(i)){
+        meow::messagePrintf(-1, "range-sum query fail");
+        return false;
+      }
+    }
+    meow::messagePrintf(-1, "ok %.3f/%.3f",
+                        tBi * 1.0 / CLOCKS_PER_SEC,
+                        tMe * 1.0 / CLOCKS_PER_SEC);
+  }
+  return true;
+};
diff --git a/_test/meowpp_Colors.cpp b/_test/meowpp_Colors.cpp
new file mode 100644
index 0000000..847f838
--- /dev/null
+++ b/_test/meowpp_Colors.cpp
@@ -0,0 +1,124 @@
+#include "meowpp.h"
+
+TEST(Colors){
+  meow::RGBf rgb, rgb2;
+  meow::YUVf yuv, yuv2;
+  meow::HSLf hsl, hsl2;
+  meow::HSVf hsv, hsv2;
+  bool ok = true;
+  double eps;
+  eps = 1e-8;
+  meow::messagePrintf(1, "rgb ---> hsl ---> rgb ---> hsl (eps = %e)", eps);
+  for(int i = 0; ok && i < 100000; i++){
+    rgb.r(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax()));
+    rgb.g(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax()));
+    rgb.b(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax()));
+    meow::RGB_to_HSL(rgb , &hsl );
+    meow::HSL_to_RGB(hsl , &rgb2);
+    meow::RGB_to_HSL(rgb2, &hsl2);
+    if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 ||
+       meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 ||
+       meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false;
+    if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 ||
+       meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 ||
+       meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false;
+  }
+  if(ok) meow::messagePrintf(-1, "ok!");
+  else{  meow::messagePrintf(-1, "fail"); return false; }
+  //
+  eps = 1e-8;
+  meow::messagePrintf(1, "rgb ---> hsv ---> rgb ---> hsv (eps = %e)", eps);
+  for(int i = 0; ok && i < 100000; i++){
+    rgb.r(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax()));
+    rgb.g(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax()));
+    rgb.b(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax()));
+    meow::RGB_to_HSV(rgb , &hsv );
+    meow::HSV_to_RGB(hsv , &rgb2);
+    meow::RGB_to_HSV(rgb2, &hsv2);
+    if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 ||
+       meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 ||
+       meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false;
+    if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 ||
+       meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 ||
+       meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false;
+  }
+  if(ok) meow::messagePrintf(-1, "ok!");
+  else{  meow::messagePrintf(-1, "fail"); return false; }
+  //
+  /*
+  eps = 1e-3;
+  meow::messagePrintf(1, "yuv ---> hsl ---> yuv ---> hsl");
+  for(int i = 0; ok && i < 100000; i++){
+    yuv.y(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.yMin(), yuv.yMax()));
+    yuv.u(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.uMin(), yuv.uMax()));
+    yuv.v(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.vMin(), yuv.vMax()));
+    meow::YUV_to_HSL(yuv , &hsl );
+    meow::HSL_to_YUV(hsl , &yuv2);
+    meow::YUV_to_HSL(yuv2, &hsl2);
+    if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 ||
+       meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 ||
+       meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false;
+    if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 ||
+       meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 ||
+       meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false;
+  }
+  if(ok) meow::messagePrintf(-1, "ok!");
+  else{  meow::messagePrintf(-1, "fail"); return false; }
+  // */
+  /*
+  meow::messagePrintf(1, "yuv ---> hsv ---> yuv ---> hsv");
+  for(int i = 0; ok && i < 100000; i++){
+    yuv.y(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.yMin(), yuv.yMax()));
+    yuv.u(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.uMin(), yuv.uMax()));
+    yuv.v(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.vMin(), yuv.vMax()));
+    meow::YUV_to_HSV(yuv , &hsv );
+    meow::HSV_to_YUV(hsv , &yuv2);
+    meow::YUV_to_HSV(yuv2, &hsv2);
+    if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 ||
+       meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 ||
+       meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false;
+    if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 ||
+       meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 ||
+       meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false;
+  }
+  if(ok) meow::messagePrintf(-1, "ok!");
+  else{  meow::messagePrintf(-1, "fail"); return false; }
+  // */
+  eps = 1e-3;
+  meow::messagePrintf(1, "rgb ---> yuv ---> rgb ---> yuv (eps = %e)", eps);
+  for(int i = 0; ok && i < 100000; i++){
+    rgb.r(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax()));
+    rgb.g(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax()));
+    rgb.b(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax()));
+    meow::RGB_to_YUV(rgb , &yuv );
+    meow::YUV_to_RGB(yuv , &rgb2);
+    meow::RGB_to_YUV(rgb2, &yuv2);
+    if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 ||
+       meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 ||
+       meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false;
+    if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 ||
+       meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 ||
+       meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false;
+  }
+  if(ok) meow::messagePrintf(-1, "ok!");
+  else{  meow::messagePrintf(-1, "fail"); return false; }
+  eps = 1e-8;
+  meow::messagePrintf(1, "hsl ---> hsv ---> hsl ---> hsv (eps = %e)", eps);
+  for(int i = 0; ok && i < 100000; i++){
+    hsl.h(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, hsl.hMin(), hsl.hMax()));
+    hsl.s(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, hsl.sMin(), hsl.sMax()));
+    hsl.l(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, hsl.lMin(), hsl.lMax()));
+    meow::HSL_to_HSV(hsl , &hsv );
+    meow::HSV_to_HSL(hsv , &hsl2);
+    meow::HSL_to_HSV(hsl2, &hsv2);
+    if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 ||
+       meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 ||
+       meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false;
+    if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 ||
+       meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 ||
+       meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false;
+  }
+  if(ok) meow::messagePrintf(-1, "ok!");
+  else{  meow::messagePrintf(-1, "fail"); return false; }
+  return true;
+};
diff --git a/_test/meowpp_DisjointSet.cpp b/_test/meowpp_DisjointSet.cpp
new file mode 100644
index 0000000..b871c4d
--- /dev/null
+++ b/_test/meowpp_DisjointSet.cpp
@@ -0,0 +1,79 @@
+#include "meowpp.h"
+
+#include <vector>
+
+TEST(DisjointSet){
+  int N = 10000000;
+  meow::DisjointSet dsj(N);
+  
+  meow::messagePrintf(1, "merge(0, 1) merge(0, 2) merge(0, 3) ... (N = %d)", N);
+  for(int i = 1; i < N; i++){
+    dsj.merge(0, i);
+  }
+  int root = dsj.root(0);
+  for(int i = 1; i < N; i++){
+    if(root != dsj.root(i)){
+      meow::messagePrintf(-1, "fail");
+      return false;
+    }
+  }
+  meow::messagePrintf(-1, "ok");
+  //
+  
+  dsj.reset(N);
+  meow::messagePrintf(1, "merge(0, 1) merge(1, 2) merge(2, 3) ... (N = %d)", N);
+  for(int i = 1; i < N; i++){
+    dsj.merge(i - 1, i);
+  }
+  root = dsj.root(0);
+  for(int i = 1; i < N; i++){
+    if(root != dsj.root(i)){
+      meow::messagePrintf(-1, "fail");
+      return false;
+    }
+  }
+  meow::messagePrintf(-1, "ok");
+  //
+  
+  int M = 1000;
+  N = 1000000;
+  dsj.reset(N);
+  std::vector<int> used(N, -1);
+  std::vector<int> nums[M];
+  
+  meow::messagePrintf(1, "random test (N = %d)", N);
+  for(int i = 0; i < N / 10; i++){
+    int grp = rand() % M;
+    int who;
+    while(used[who = rand() % N] != -1);
+    nums[grp].push_back(who);
+    used[who] = grp;
+  }
+  meow::messagePrintf(0, "data created");
+  for(int i = 0; i < M; i++){
+    for(int k = 0; k < 100; k++){
+      int j1 = rand() % nums[i].size();
+      int j2 = rand() % nums[i].size();
+      dsj.merge(nums[i][j1], nums[i][j2]);
+    }
+    for(size_t j = 1; j < nums[i].size(); j++){
+      dsj.merge(nums[i][0], nums[i][j]);
+    }
+  }
+  for(int i = 0; i < N; i++){
+    bool ok = false;
+    if(used[i] == -1 && dsj.root(i) == i){
+      ok = true;
+    }else{
+      if(dsj.root(i) == dsj.root(nums[used[i]][0])){
+        ok = true;
+      }
+    }
+    if(!ok){
+      meow::messagePrintf(-1, "fail");
+      return false;
+    }
+  }
+  meow::messagePrintf(-1, "ok");
+  return true;
+};
diff --git a/_test/meowpp_KD_Tree.cpp b/_test/meowpp_KD_Tree.cpp
new file mode 100644
index 0000000..dcbda5f
--- /dev/null
+++ b/_test/meowpp_KD_Tree.cpp
@@ -0,0 +1,186 @@
+#include "meowpp.h"
+
+#include <vector>
+
+#include <cmath>
+#include <cstdlib>
+#include <algorithm>
+#include <ctime>
+#include <queue>
+
+static int N = 10000;
+static int D = 5;
+
+static double dist2(std::vector<double> const& v1, std::vector<double> const& v2){
+  double ret = 0;
+  for(int i = 0; i < D; i++){
+    ret += meow::squ(v1[i] - v2[i]);
+  }
+  return ret;
+}
+
+static std::vector< std::vector<double> > data;
+static std::vector<             double  > dist;
+static std::vector<             int     > order;
+
+
+struct Answer{
+  double dist;
+  int    id;
+  Answer(double _dist, int _id): dist(_dist), id(_id){ }
+  bool operator<(Answer const& b) const{
+    if(dist != b.dist) return (dist < b.dist);
+    return (id < b.id);
+  }
+};
+
+
+static void find(std::vector<double> const& v, int k){
+  std::priority_queue<Answer> qu;
+  for(int i = 0; i < k; i++){
+    qu.push(Answer(dist2(v, data[i]), i));
+  }
+  for(int i = k; i < N; i++){
+    qu.push(Answer(dist2(v, data[i]), i));
+    qu.pop();
+  }
+  order.resize(k);
+  for(int i = qu.size() - 1; i >= 0; i--){
+    order[i] = qu.top().id;
+    qu.pop();
+  }
+}
+
+static std::vector<double> v;
+
+static bool sf(const int& a, const int& b){
+  if(dist[a] != dist[b])
+    return (dist[a] < dist[b]);
+  return (a < b);
+}
+
+static void show(std::vector<double> const& ask, std::vector<int> kd, std::vector<int> me, int k){
+  if(N <= 30 && D <= 3){
+    printf("\nData:\n");
+    for(int i = 0; i < N; i++){
+      printf("  %2d) <", i);
+      for(int j = 0; j < D; j++){
+        printf("%.7f", data[i][j]);
+        if(j < D - 1) printf(", ");
+        else          printf(">");
+      }
+      printf("\n");
+    }
+    printf("Ask  <");
+    for(int j = 0; j < D; j++){
+      printf("%.7f", ask[j]);
+      if(j < D - 1) printf(", ");
+      else          printf(">");
+    }
+    printf("\n");
+    printf("MyAnswer: ");
+    for(int i = 0; i < k; i++) printf("%d ", me[i]);
+    printf("\n");
+    printf("KdAnswer: ");
+    for(int i = 0; i < k; i++) printf("%d ", kd[i]);
+    printf("\n");
+    order.resize(N);
+    dist .resize(N);
+    for(int i = 0; i < N; i++){
+      dist [i] = dist2(ask, data[i]);
+      order[i] = i;
+    }
+    std::sort(order.begin(), order.end(), sf);
+    printf("Sorted:\n");
+    for(int i = 0; i < N; i++){
+      printf("  %2d) <", order[i]);
+      for(int j = 0; j < D; j++){
+        printf("%.7f", data[order[i]][j]);
+        if(j < D - 1) printf(", ");
+        else          printf(">");
+      }
+      printf(" ((%.7f))", dist[order[i]]);
+      printf("\n");
+    }
+  }
+}
+
+struct Node{
+  std::vector<double> v;
+  int id;
+  double& operator[](size_t d)       { return v[d]; }
+  double  operator[](size_t d) const { return v[d]; }
+  bool operator<(Node const& n) const{ return (id < n.id); }
+};
+
+TEST(KD_Tree){
+  
+  int t0, t1, t2;
+  
+  meow::KD_Tree<Node, double> tree(D);
+  
+  meow::messagePrintf(1, "Create data (N = %d, D = %d)", N, D);
+  data.resize(N);
+  for(int i = 0; i < N; i++){
+    data[i].resize(D);
+    Node nd;
+    nd.v.resize(D);
+    nd.id = i;
+    for(int j = 0; j < D; j++){
+      data[i][j] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3);
+      nd[j] = data[i][j];
+    }
+    tree.insert(nd);
+  }
+  meow::messagePrintf(-1, "ok");
+  meow::messagePrintf(1, "build");
+  t0 = clock();
+  tree.build();
+  meow::messagePrintf(-1, "ok, %.3f seconds", (clock() - t0) * 1.0 / CLOCKS_PER_SEC);
+  
+  meow::messagePrintf(1, "query...");
+  v.resize(D);
+  meow::KD_Tree<Node, double>::Vectors ret;
+  int id;
+  for(int k = 1; k <= std::min(100, N); k++){
+    meow::messagePrintf(1, "range k = %d", k);
+    t1 = t2 = 0;
+    for(int i = 0; i < 10; i++){
+      Node nd;
+      nd.v.resize(D);
+      for(int d = 0; d < D; d++){
+        v[d] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3);
+        nd[d] = v[d];
+      }
+      t0 = clock();
+      tree.build();
+      ret = tree.query(nd, k, true);
+      t1 += clock() - t0;
+      
+      t0 = clock();
+      find(v, k);
+      t2 += clock() - t0;
+      if(ret.size() != std::min(k, N)){
+        meow::messagePrintf(-1, "(%d)query fail, size error", i);
+        meow::messagePrintf(-1, "fail");
+        return false;
+      }
+      for(int kk = 1; kk <= k; kk++){
+        if(order[kk - 1] != ret[kk - 1].id){
+          //show(v, ret, order, k);
+          meow::messagePrintf(-1, "(%d)query fail", i);
+          meow::messagePrintf(-1, "fail");
+          return false;
+        }
+      }
+    }
+    meow::messagePrintf(-1, "ok %.3f/%.3f",
+                        t1 * 1.0 / CLOCKS_PER_SEC,
+                        t2 * 1.0 / CLOCKS_PER_SEC
+                        );
+  }
+  meow::messagePrintf(-1, "ok");
+  
+  
+  return true;
+};
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;
+};
diff --git a/_test/meowpp_SegmentTree.cpp b/_test/meowpp_SegmentTree.cpp
new file mode 100644
index 0000000..777ca9d
--- /dev/null
+++ b/_test/meowpp_SegmentTree.cpp
@@ -0,0 +1,154 @@
+#include "meowpp.h"
+
+#include <ctime>
+#include <algorithm>
+
+struct RangeMax{
+  int value;
+  //
+  RangeMax(){}
+  RangeMax(int _value): value(_value){ }
+  RangeMax(RangeMax const& b): value(b.value){ }
+  //
+  RangeMax operator*(size_t n) const{ return RangeMax(value); }
+  RangeMax operator|(RangeMax const& b) const{ return RangeMax(std::max(value, b.value)); }
+  RangeMax operator+(RangeMax const& b) const{ return RangeMax(b.value + value); }
+  bool operator==(RangeMax const& b) const{ return (value == b.value); }
+};
+struct RangeSum{
+  int value;
+  //
+  RangeSum(){}
+  RangeSum(int _value): value(_value){ }
+  RangeSum(RangeSum const& b): value(b.value){ }
+  //
+  RangeSum operator*(size_t n) const{ return RangeSum(n * value); }
+  RangeSum operator|(RangeSum const& b) const{ return RangeSum(value + b.value); }
+  RangeSum operator+(RangeSum const& b) const{ return RangeSum(b.value + value); }
+  bool operator==(RangeSum const& b) const{ return (value == b.value); }
+};
+
+meow::SegmentTree<RangeMax> s_max;
+meow::SegmentTree<RangeSum> s_sum;
+
+static int N = 1000000;
+
+std::vector<int> array;
+
+void override(int a, int b, int c){
+  for(int i = a; i <= b; i++)
+    array[i] = c;
+}
+void offset(int a, int b, int c){
+  for(int i = a; i <= b; i++)
+    array[i] += c;
+}
+int bmax(int a, int b){
+  int ret = array[a];
+  for(int i = a + 1; i <= b; i++)
+    ret = std::max(ret, array[i]);
+  return ret;
+}
+int bsum(int a, int b){
+  int sum = 0;
+  for(int i = a; i <= b; i++)
+    sum += array[i];
+  return sum;
+}
+
+void show(){
+  if(N <= 20){
+    printf("\n");
+    printf("Me : ");
+    for(int i = 0; i < N; i++){
+      printf("%4d ", array[i]);
+    }
+    printf("\n");
+    printf("Sum: ");
+    for(int i = 0; i < N; i++){
+      printf("%4d ", s_sum.query(i, i).value);
+    }
+    printf("\n");
+    printf("Max: ");
+    for(int i = 0; i < N; i++){
+      printf("%4d ", s_max.query(i, i).value);
+    }
+    printf("\n");
+  }
+}
+
+TEST(SegmentTree){
+  s_max.reset(N);
+  s_sum.reset(N);
+  s_max.override(0, N - 1, RangeMax(0));
+  s_sum.override(0, N - 1, RangeSum(0));
+  array.resize(N, 0);
+
+  for(int z = 0; z < 10; z++){
+    meow::messagePrintf(1, "test %d", z);
+    int tMe = 0, tSeg = 0, t0;
+    int NN = 1 + rand() % 100;
+    for(int i = 0; i < NN; i++){
+      int a = rand() % N;
+      int b = rand() % (N - a) + a;
+      int k = rand() % 20000 - 10000;
+      bool over = (rand() % 2 == 1);
+      if(over){
+        t0 = clock();
+        s_max.override(a, b, RangeMax(k));
+        s_sum.override(a, b, RangeSum(k));
+        tSeg += clock() - t0;
+        t0 = clock();
+        override(a, b, k);
+        tMe += clock() - t0;
+      }else{
+        t0 = clock();
+        s_max.offset(a, b, RangeMax(k));
+        s_sum.offset(a, b, RangeSum(k));
+        tSeg = clock() - t0;
+        t0 = clock();
+        offset(a, b, k);
+        tMe += clock() - t0;
+      }
+      /*
+      printf("\n");
+      printf("%s %d~%d with %d", over ? "override" : "offset", a, b, k);
+      show();
+      printf("max:"); s_max.print();
+      printf("sum:"); s_sum.print();
+      // */
+    }
+    NN = 1 + rand() % 100;
+    for(int i = 0; i < NN; i++){
+      int a = rand() % N;
+      int b = rand() % (N - a) + a;
+
+      t0 = clock();
+      RangeMax m(s_max.query(a, b));
+      RangeSum s(s_sum.query(a, b));
+      tSeg += clock() - t0;
+      t0 = clock();
+      int mm = bmax(a, b);
+      int ss = bsum(a, b);
+      tMe += clock() - t0;
+      if(m.value != mm){
+        printf("ask %d~%d, me %d/%d   seg %d/%d\n", a, b, mm, ss, m.value, s.value);
+        meow::messagePrintf(-1, "range-max query fail");
+        return false;
+      }
+      if(s.value != ss){
+        printf("ask %d~%d, max/sum = me %d/%d   seg %d/%d\n", a, b, mm, ss, m.value, s.value);
+        meow::messagePrintf(-1, "range-sum query fail");
+        return false;
+      }
+    }
+    meow::messagePrintf(-1, "ok, %.3f/%.3f",
+                        1.0 * tSeg / CLOCKS_PER_SEC,
+                        1.0 * tMe  / CLOCKS_PER_SEC);
+    s_max.reset(N);
+    s_sum.reset(N);
+    array.clear();
+    array.resize(N, 0);
+  }
+  return true;
+};
diff --git a/_test/meowpp_SplayTree.cpp b/_test/meowpp_SplayTree.cpp
new file mode 100644
index 0000000..0d1e2f2
--- /dev/null
+++ b/_test/meowpp_SplayTree.cpp
@@ -0,0 +1,503 @@
+#include "meowpp.h"
+
+#include <algorithm>
+#include <utility>
+#include <map>
+#include <cstdlib>
+
+static int N;
+
+static bool detail_fg;
+
+typedef typename  std::map      <int, double>::        iterator IterN;
+typedef typename  std::map      <int, double>::reverse_iterator IterR;
+typedef typename meow::SplayTree<int, double>::Element          IterS;
+
+static std::vector< std::map      <int, double> > normal;
+static std::vector<meow::SplayTree<int, double> > splay;
+
+static void show(bool fg = false){
+  if(fg){
+    for(int i = 0; i < N; i++){
+      printf("normal %d-%lu: ", i, normal[i].size());
+      for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+        printf("%d/%.2f ", it->first, it->second);
+      }
+      printf("\n");
+      printf("splay  %d-%lu: ", i, splay[i].size());
+      bool bye = false;
+      for(int j = 0; j < splay[i].size(); j++){
+        IterS it = splay[i].order(j);
+        printf("%d/%.2f ", it->first, it->second);
+      }
+      printf("\n");
+    }
+    printf("\n");
+  }
+}
+
+static bool lowerBound(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= lowerBound(%d, %d)\n", i, key);
+  t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0;
+  t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second,
+                      (b == splay[i].end()) ? 0 : b->second);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second == b->second);
+}
+static bool upperBound(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= upperBound(%d, %d)\n", i, key);
+  t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0;
+  t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay [i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second,
+                      (b == splay [i].end()) ? 0 : b->second);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second == b->second);
+}
+static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key);
+  t0 = clock(); IterS b =   splay [i].rLowerBound(key); (*tS) += clock() - t0;
+  t0 = clock();
+  IterN a, z;
+  if(normal[i].size() == 0 || normal[i].begin()->first > key){
+    a = normal[i].end();
+  }else{
+    for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){
+      if(z->first > key){
+        break;
+      }
+    }
+  }
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second,
+                      (b == splay[i].end()) ? 0 : b->second);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second == b->second);
+}
+static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key);
+  t0 = clock(); IterS b =   splay [i].rUpperBound(key); (*tS) += clock() - t0;
+  t0 = clock();
+  IterN a, z;
+  if(normal[i].begin() == normal[i].end()){
+    a = normal[i].end();
+  }else{
+    if(normal[i].begin()->first >= key) a = normal[i].end();
+    else{
+      for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){
+        if(z->first >= key)
+          break;
+      }
+    }
+  }
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second,
+                      (b == splay[i].end()) ? 0 : b->second);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second == b->second);
+}
+static bool find(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= find(%d, %d)\n", i, key);
+  t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0;
+  t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second,
+                      (b == splay[i].end()) ? 0 : b->second);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second == b->second);
+}
+static bool order(int i, int order, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= order(%d, %d)\n", i, order);
+  t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0;
+  t0 = clock();
+  IterN a = normal[i].begin();
+  for(int k = 0; k < order; k++) a++;
+  (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second,
+                      (b == splay[i].end()) ? 0 : b->second);
+  show(detail_fg);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end()) return true;
+  return (a->first == b->first && a->second == b->second);
+}
+static bool first_last(int i, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= first_last(%d)\n", i);
+  IterN a;
+  t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0;
+  t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (a == normal[i].end()) ? 0 : a->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (a == normal[i].end()) ? 0 : a->second,
+                      (b == splay[i].end()) ? 0 : b->second);
+  if((a == normal[i].end()) != (b == splay[i].end())) return false;
+  if( a == normal[i].end());
+  else{
+    if((a->first == b->first && a->second == b->second) == false){
+      return false;
+    }
+  }
+  t0 = clock(); b = splay[i].last   (); (*tS) += clock() - t0;
+  t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0;
+  detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+                      (r == normal[i].rend()) ? 0 : r->first,
+                      (b == splay[i].end()) ? 0 : b->first,
+                      (r == normal[i].rend()) ? 0 : r->second,
+                      (b == splay[i].end()) ? 0 : b->second);
+  if((r == normal[i].rend()) != (b == splay[i].end())) return false;
+  if(r == normal[i].rend());
+  else{
+    if((r->first == b->first && r->second == b->second) == false){
+      return false;
+    }
+  }
+  return true;
+}
+static bool insert(int i, int key, double val, size_t* tN, size_t* tS){
+  size_t t0;
+  if(rand() & 1){
+    t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0;
+    t0 = clock(); normal[i].insert(std::pair<int, double>(key, val)); (*tN) += clock() - t0;
+  }else{
+    t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0;
+    t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0;
+  }
+  detail_fg && printf("============= insert(%d, %d)\n", i, key);
+  show(detail_fg);
+  return true;
+}
+static bool split(int i, int j, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  if(i == j){
+    return true;
+  }
+  detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key);
+  t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0;
+  t0 = clock();
+  normal[j].clear();
+  for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){
+    normal[j].insert(*it);
+    normal[i].erase(it);
+  }
+  *tN += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+static bool merge(int i, int j, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  if(i == j){
+    return true;
+  }
+  if(rand() & 1){
+    t0 = clock();
+    if(splay[i].size() > 0)
+      while(splay[j].size() > 0 &&
+            splay[j].first()->first <= splay[i].last()->first){
+        splay[j].erase(splay[j].first()->first);
+      }
+    *tS += clock() - t0;
+    t0 = clock();
+    if(normal[i].size() > 0)
+      while(normal[j].size() > 0 &&
+            normal[j].begin()->first <= normal[i].rbegin()->first)
+        normal[j].erase(normal[j].begin());
+    *tN += clock() - t0;
+  }
+  t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0;
+  t0 = clock();
+  if(normal[i].size() == 0 || normal[j].size() == 0 ||
+      normal[i].rbegin()->first < normal[j].begin()->first ||
+      normal[j].rbegin()->first < normal[i].begin()->first
+  ){
+    for(IterN it = normal[j].begin(); it != normal[j].end(); it++){
+      normal[i].insert(*it);
+    }
+    normal[j].clear();
+  }
+  *tN += clock() - t0;
+  detail_fg && printf("============= merge(%d, %d)\n", i, j, key);
+  show(detail_fg);
+  return true;
+}
+static bool erase(int i, int key, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= erase(%d, %d)\n", i, key);
+  t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0;
+  t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta);
+  t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0;
+  t0 = clock();
+  std::map<int, double> tmp = normal[i];
+  normal[i].clear();
+  for(IterN it = tmp.begin(); it != tmp.end(); it++){
+    normal[i].insert(std::pair<int, double>(it->first + delta, it->second));
+  }
+  (*tN) += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+/*
+static bool valueOffset(int i, double delta, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta);
+  t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0;
+  t0 = clock();
+  for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+    it->second += delta;
+  }
+  (*tN) += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+// */
+static bool copy(int i, int j, size_t* tN, size_t* tS){
+  size_t t0;
+  detail_fg && printf("copy(%d, %d)\n", i, j);
+  t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0;
+  t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0;
+  show(detail_fg);
+  return true;
+}
+
+static bool check(){
+  for(int i = 0; i < N; i++){
+    if(normal[i].size() != splay[i].size()) return false;
+    int j = 0;
+    for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){
+      if(it->first  != splay[i].order(j)->first ||
+         it->second != splay[i].order(j)->second)
+        return false;
+    }
+  }
+  return true;
+}
+
+TEST(SplayTree){
+  detail_fg = false;
+  N = 5;
+  for(int i = 0; i < 10; i++){
+    normal.clear();
+    splay .clear();
+    normal.resize(N);
+    splay .resize(N);
+    size_t tn = 0, tm = 0;
+    int op = 1 + rand() % 2000000;
+    meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op);
+    while(op--){
+      int wh = rand() % 60;
+      int i1 = rand() % N, i2, k = rand() % 60;
+      while((i2 = rand() % N) == i1);
+      switch(wh){
+        case  0:
+          if(lowerBound(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "lowerBound");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  1:
+          if(rUpperBound(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "rUpperBound");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  2:
+          if(rLowerBound(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "rLowerBound");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  3:
+          if(upperBound(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "upperBound");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  4:
+        case  5:
+        case  6:
+          if(find(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "find");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case  7:
+        case  8:
+        case  9:
+          if(normal[i1].size() > 0){
+            if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){
+              meow::messagePrintf(-1, "fail(%s)", "order");
+              //for(int z = 0; z < N; z++){ splay[z].print(); }
+              show(true);
+              return false;
+            }
+            break;
+          }
+        case 10:
+          if(first_last(i1, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "first_last");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 11:
+        case 12:
+        case 13:
+        case 14:
+        case 15:
+        case 16:
+        case 17:
+        case 18:
+        case 19:
+        case 20:
+          if(insert(i1, k, rand() * 1.0 / RAND_MAX * 50, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "insert");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 21:
+        case 22:
+        case 23:
+        case 24:
+        case 25:
+        case 26:
+          if(split(i1, i2, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "split");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 27:
+        case 28:
+        case 29:
+        case 30:
+        case 31:
+        case 32:
+        case 33:
+        case 34:
+        case 35:
+        case 36:
+          if(merge(i1, i2, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "merge");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 37:
+        case 38:
+        case 39:
+        case 40:
+          if(erase(i1, k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "erase");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 41:
+        case 42:
+        case 43:
+        case 44:
+        case 45:
+        case 46:
+        case 47:
+        case 48:
+        case 49:
+          if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "keyOffset");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 50:
+        case 51:
+        case 52:
+          if(copy(i1, i2, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "copy");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+        case 53:
+        case 54:
+        case 55:
+        case 56:
+        case 57:
+        case 58:
+        case 59:
+          op++;
+          /*
+          if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100, &tn, &tm) == false){
+            meow::messagePrintf(-1, "fail(%s)", "valueOffset");
+            //for(int z = 0; z < N; z++){ splay[z].print(); }
+            show(true);
+            return false;
+          }
+          break;
+          // */
+      }
+    }
+    if(!check()){
+      meow::messagePrintf(-1, "fail");
+      show(true);
+      return false;
+    }
+    meow::messagePrintf(-1, "ok %.3f/%.3f",
+                        tm * 1.0 / CLOCKS_PER_SEC,
+                        tn * 1.0 / CLOCKS_PER_SEC);
+  }
+  return true;
+};