diff options
author | cathook <b01902109@csie.ntu.edu.tw> | 2014-06-01 14:16:38 +0800 |
---|---|---|
committer | cathook <b01902109@csie.ntu.edu.tw> | 2014-06-01 14:16:38 +0800 |
commit | c60dba253906a30d3042f1dc4e9b7fe38f053fbe (patch) | |
tree | 57018f05908f0edef30cba255d46688ebfd5cd85 /meowpp.test/src/SplayTree.cpp | |
parent | 8bc9f2e8496c0c021b80eb0fb21e828f5900f08d (diff) | |
download | meow-c60dba253906a30d3042f1dc4e9b7fe38f053fbe.tar meow-c60dba253906a30d3042f1dc4e9b7fe38f053fbe.tar.gz meow-c60dba253906a30d3042f1dc4e9b7fe38f053fbe.tar.bz2 meow-c60dba253906a30d3042f1dc4e9b7fe38f053fbe.tar.lz meow-c60dba253906a30d3042f1dc4e9b7fe38f053fbe.tar.xz meow-c60dba253906a30d3042f1dc4e9b7fe38f053fbe.tar.zst meow-c60dba253906a30d3042f1dc4e9b7fe38f053fbe.zip |
add test...
Diffstat (limited to 'meowpp.test/src/SplayTree.cpp')
-rw-r--r-- | meowpp.test/src/SplayTree.cpp | 477 |
1 files changed, 477 insertions, 0 deletions
diff --git a/meowpp.test/src/SplayTree.cpp b/meowpp.test/src/SplayTree.cpp new file mode 100644 index 0000000..ea24fb8 --- /dev/null +++ b/meowpp.test/src/SplayTree.cpp @@ -0,0 +1,477 @@ +#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; +} |