#include "meowpp/dsa/SegmentTree.h"
#include "meowpp/utility.h"

#include "meowpp.h"

#include <ctime>
#include <algorithm>

struct RangeMax{
  int value;
  //
  RangeMax(){}
  RangeMax(int _value): value(_value){ }
  RangeMax(RangeMax const& b): value(b.value){ }
  //
  RangeMax operator*(size_t n) const{ return RangeMax(value); }
  RangeMax operator|(RangeMax const& b) const{ return RangeMax(std::max(value, b.value)); }
  RangeMax operator+(RangeMax const& b) const{ return RangeMax(b.value + value); }
  bool operator==(RangeMax const& b) const{ return (value == b.value); }
};
struct RangeSum{
  int value;
  //
  RangeSum(){}
  RangeSum(int _value): value(_value){ }
  RangeSum(RangeSum const& b): value(b.value){ }
  //
  RangeSum operator*(size_t n) const{ return RangeSum(n * value); }
  RangeSum operator|(RangeSum const& b) const{ return RangeSum(value + b.value); }
  RangeSum operator+(RangeSum const& b) const{ return RangeSum(b.value + value); }
  bool operator==(RangeSum const& b) const{ return (value == b.value); }
};

meow::SegmentTree<RangeMax> s_max;
meow::SegmentTree<RangeSum> s_sum;

static int N = 1000000;

std::vector<int> array;

void override(int a, int b, int c){
  for(int i = a; i <= b; i++)
    array[i] = c;
}
void offset(int a, int b, int c){
  for(int i = a; i <= b; i++)
    array[i] += c;
}
int bmax(int a, int b){
  int ret = array[a];
  for(int i = a + 1; i <= b; i++)
    ret = std::max(ret, array[i]);
  return ret;
}
int bsum(int a, int b){
  int sum = 0;
  for(int i = a; i <= b; i++)
    sum += array[i];
  return sum;
}

void show(){
  if(N <= 20){
    printf("\n");
    printf("Me : ");
    for(int i = 0; i < N; i++){
      printf("%4d ", array[i]);
    }
    printf("\n");
    printf("Sum: ");
    for(int i = 0; i < N; i++){
      printf("%4d ", s_sum.query(i, i).value);
    }
    printf("\n");
    printf("Max: ");
    for(int i = 0; i < N; i++){
      printf("%4d ", s_max.query(i, i).value);
    }
    printf("\n");
  }
}

TEST(SegmentTree, "..."){
  s_max.reset(N);
  s_sum.reset(N);
  s_max.override(0, N - 1, RangeMax(0));
  s_sum.override(0, N - 1, RangeSum(0));
  array.resize(N, 0);

  for(int z = 0; z < 10; z++){
    meow::messagePrintf(1, "test %d", z);
    int tMe = 0, tSeg = 0, t0;
    int NN = 1 + rand() % 100;
    for(int i = 0; i < NN; i++){
      int a = rand() % N;
      int b = rand() % (N - a) + a;
      int k = rand() % 20000 - 10000;
      bool over = (rand() % 2 == 1);
      if(over){
        t0 = clock();
        s_max.override(a, b, RangeMax(k));
        s_sum.override(a, b, RangeSum(k));
        tSeg += clock() - t0;
        t0 = clock();
        override(a, b, k);
        tMe += clock() - t0;
      }else{
        t0 = clock();
        s_max.offset(a, b, RangeMax(k));
        s_sum.offset(a, b, RangeSum(k));
        tSeg = clock() - t0;
        t0 = clock();
        offset(a, b, k);
        tMe += clock() - t0;
      }
      /*
      printf("\n");
      printf("%s %d~%d with %d", over ? "override" : "offset", a, b, k);
      show();
      printf("max:"); s_max.print();
      printf("sum:"); s_sum.print();
      // */
    }
    NN = 1 + rand() % 100;
    for(int i = 0; i < NN; i++){
      int a = rand() % N;
      int b = rand() % (N - a) + a;

      t0 = clock();
      RangeMax m(s_max.query(a, b));
      RangeSum s(s_sum.query(a, b));
      tSeg += clock() - t0;
      t0 = clock();
      int mm = bmax(a, b);
      int ss = bsum(a, b);
      tMe += clock() - t0;
      if(m.value != mm){
        printf("ask %d~%d, me %d/%d   seg %d/%d\n", a, b, mm, ss, m.value, s.value);
        meow::messagePrintf(-1, "range-max query fail");
        return false;
      }
      if(s.value != ss){
        printf("ask %d~%d, max/sum = me %d/%d   seg %d/%d\n", a, b, mm, ss, m.value, s.value);
        meow::messagePrintf(-1, "range-sum query fail");
        return false;
      }
    }
    meow::messagePrintf(-1, "ok, %.3f/%.3f",
                        1.0 * tSeg / CLOCKS_PER_SEC,
                        1.0 * tMe  / CLOCKS_PER_SEC);
    s_max.reset(N);
    s_sum.reset(N);
    array.clear();
    array.resize(N, 0);
  }
  return true;
};