aboutsummaryrefslogtreecommitdiffstats
path: root/_test/meowpp_SplayTree.cpp
diff options
context:
space:
mode:
Diffstat (limited to '_test/meowpp_SplayTree.cpp')
-rw-r--r--_test/meowpp_SplayTree.cpp503
1 files changed, 503 insertions, 0 deletions
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;
+};
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-26 06:49:39 +0800