test...

1 files changed, 0 insertions, 477 deletions

diff --git a/meowpp.test/src/SplayTree.cpp b/meowpp.test/src/SplayTree.cpp
deleted file mode 100644
index ea24fb8..0000000
--- a/meowpp.test/src/SplayTree.cpp
+++ /dev/null
@@ -1,477 +0,0 @@
-#include "meowpp/dsa/SplayTree.h"
-#include "meowpp/utility.h"
-
-#include "dsa.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());
-      for(size_t 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);
-  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, "Seems buggy"){
-  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");
-            show(true);
-            return false;
-          }
-          break;
-        case  1:
-          if(rUpperBound(i1, k, &tn, &tm) == false){
-            meow::messagePrintf(-1, "fail(%s)", "rUpperBound");
-            show(true);
-            return false;
-          }
-          break;
-        case  2:
-          if(rLowerBound(i1, k, &tn, &tm) == false){
-            meow::messagePrintf(-1, "fail(%s)", "rLowerBound");
-            show(true);
-            return false;
-          }
-          break;
-        case  3:
-          if(upperBound(i1, k, &tn, &tm) == false){
-            meow::messagePrintf(-1, "fail(%s)", "upperBound");
-            show(true);
-            return false;
-          }
-          break;
-        case  4:
-        case  5:
-        case  6:
-          if(find(i1, k, &tn, &tm) == false){
-            meow::messagePrintf(-1, "fail(%s)", "find");
-            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");
-              show(true);
-              return false;
-            }
-            break;
-          }
-        case 10:
-          if(first_last(i1, &tn, &tm) == false){
-            meow::messagePrintf(-1, "fail(%s)", "first_last");
-            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");
-            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");
-            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");
-            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");
-            show(true);
-            return false;
-          }
-          break;
-        case 50:
-        case 51:
-        case 52:
-          if(copy(i1, i2, &tn, &tm) == false){
-            meow::messagePrintf(-1, "fail(%s)", "copy");
-            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");
-            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;
-}