aboutsummaryrefslogtreecommitdiffstats
path: root/meowpp.test/src/SplayTree_Range.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'meowpp.test/src/SplayTree_Range.cpp')
-rw-r--r--meowpp.test/src/SplayTree_Range.cpp561
1 files changed, 0 insertions, 561 deletions
diff --git a/meowpp.test/src/SplayTree_Range.cpp b/meowpp.test/src/SplayTree_Range.cpp
deleted file mode 100644
index e6d857b..0000000
--- a/meowpp.test/src/SplayTree_Range.cpp
+++ /dev/null
@@ -1,561 +0,0 @@
-#include "meowpp/dsa/SplayTree.h"
-#include "meowpp/utility.h"
-
-#include "dsa.h"
-
-#include <algorithm>
-#include <utility>
-#include <map>
-#include <cstdlib>
-#include <cmath>
-
-static int min_sum;
-struct Double{
- double k;
- Double(): k(0){ }
- Double(double _k): k(0){ }
- bool operator==(const Double& b) const{ return fabs(k - b.k) <= 1e-9; }
- bool operator!=(const Double& b) const{ return fabs(k - b.k) > 1e-9; }
- bool operator<(const Double& b) const{ return k < b.k; }
- Double operator+(const Double& b) const{ return Double(k + b.k); }
- Double operator*(size_t& b) const{
- if(min_sum == 0) return Double(k);
- else return Double(k * b);
- }
- Double operator|(const Double& b) const{
- if(min_sum == 0) return Double(std::min(k, b.k));
- else return Double(k + b.k);
- }
-};
-
-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_Range<int, Double>::Element IterS;
-
-static std::vector< std::map <int, Double> > normal;
-static std::vector<meow::SplayTree_Range<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.k);
- }
- 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.k);
- }
- 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.k,
- (b == splay[i].end()) ? 0 : b->second.k);
- 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.k == b->second.k);
-}
-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.k,
- (b == splay [i].end()) ? 0 : b->second.k);
- 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.k == b->second.k);
-}
-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.k,
- (b == splay[i].end()) ? 0 : b->second.k);
- 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.k == b->second.k);
-}
-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.k,
- (b == splay[i].end()) ? 0 : b->second.k);
- 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.k == b->second.k);
-}
-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.k,
- (b == splay[i].end()) ? 0 : b->second.k);
- 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.k == b->second.k);
-}
-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.k,
- (b == splay[i].end()) ? 0 : b->second.k);
- 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.k == b->second.k);
-}
-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.k,
- (b == splay[i].end()) ? 0 : b->second.k);
- if((a == normal[i].end()) != (b == splay[i].end())) return false;
- if( a == normal[i].end());
- else{
- if((a->first == b->first && a->second.k == b->second.k) == 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.k,
- (b == splay[i].end()) ? 0 : b->second.k);
- if((r == normal[i].rend()) != (b == splay[i].end())) return false;
- if(r == normal[i].rend());
- else{
- if((r->first == b->first && r->second.k == b->second.k) == 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.k));
- }
- (*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.k);
- t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0;
- t0 = clock();
- for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
- it->second = it->second + delta;
- }
- (*tN) += clock() - t0;
- show(detail_fg);
- return true;
-}
-static bool valueOverride(int i, Double value, size_t* tN, size_t* tS){
- size_t t0;
- detail_fg && printf("============= valueOverride(%d, %f)\n", i, value.k);
- t0 = clock(); splay[i].valueOverride(value); (*tS) += clock() - t0;
- t0 = clock();
- for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
- it->second.k = value.k;
- }
- (*tN) += clock() - t0;
- show(detail_fg);
- return true;
-}
-static bool query(int i, int a, int b, size_t* tN, size_t* tS){
- size_t t0;
- detail_fg && printf("============= query(%d, %d, %d)\n", i, a, b);
- Double ans1, ans2 = 0;
- if((rand() & 3) == 3){
- t0 = clock(); ans1 = splay[i].query(); (*tS) += clock() - t0;
- t0 = clock();
- for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
- ans2 = ans2 | it->second.k;
- }
- }else{
- t0 = clock(); ans1 = splay[i].query(a, b); (*tS) += clock() - t0;
- t0 = clock();
- for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
- if(a <= it->first && it->first <= b)
- ans2 = ans2 | it->second.k;
- }
- }
- detail_fg && printf(">>get %f %f\n", ans1.k, ans2.k);
- 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.k != splay[i].order(j)->second.k)
- return false;
- }
- }
- return true;
-}
-
-TEST(SplayTree_Range, "..."){
- 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;
- min_sum = rand() & 1;
- meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op);
- while(op--){
- int wh = rand() % 100;
- 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 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 + 1, &tn, &tm) == false){
- meow::messagePrintf(-1, "fail(%s)", "insert");
- 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:
- if(valueOverride(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){
- meow::messagePrintf(-1, "fail(%s)", "valueOffset");
- show(true);
- return false;
- }
- break;
- case 60:
- case 61:
- case 62:
- case 63:
- case 64:
- case 65:
- case 66:
- if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){
- meow::messagePrintf(-1, "fail(%s)", "valueOffset");
- show(true);
- return false;
- }
- break;
- default:
- if(query(i1, rand() % 200 - 100, rand() % 200 - 100, &tn, &tm) == false){
- meow::messagePrintf(-1, "fail(%s)", "query");
- 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 08:06:02 +0800