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, 561 insertions, 0 deletions
diff --git a/meowpp.test/src/SplayTree_Range.cpp b/meowpp.test/src/SplayTree_Range.cpp
new file mode 100644
index 0000000..085b5bf
--- /dev/null
+++ b/meowpp.test/src/SplayTree_Range.cpp
@@ -0,0 +1,561 @@
+#include "meowpp/dsa/SplayTree_Range.h"
+#include "meowpp/utility.h"
+
+#include "meowpp.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-25 14:13:17 +0800