#include "meowpp/dsa/SplayTree.h"
#include "meowpp/utility.h"
#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());
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;
};
