path: root/_test/meowpp_SplayTree_Range.cpp

#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{ fabs(k - b.k) <= 1e-9; }
  bool operator!=(const Double& b) const{ 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());
      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.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, 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.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");
            //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 + 1, &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:
          if(valueOverride(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){
            meow::messagePrintf(-1, "fail(%s)", "valueOffset");
            //for(int z = 0; z < N; z++){ splay[z].print(); }
            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");
            //for(int z = 0; z < N; z++){ splay[z].print(); }
            show(true);
            return false;
          }
          break;
        default:
          if(query(i1, rand() % 200 - 100, rand() % 200 - 100, &tn, &tm) == false){
            meow::messagePrintf(-1, "fail(%s)", "query");
            //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;
};