#include "meowpp/dsa/DisjointSet.h"

#include "dsa.h"

#include <vector>


TEST(DisjointSet, "..."){
  int N = 10000000;
  meow::DisjointSet dsj(N);
  
  meow::messagePrintf(1, "merge(0, 1) merge(0, 2) merge(0, 3) ... (N = %d)", N);
  for(int i = 1; i < N; i++){
    dsj.merge(0, i);
  }
  int root = dsj.root(0);
  for(int i = 1; i < N; i++){
    if(root != (int)dsj.root(i)){
      meow::messagePrintf(-1, "fail");
      return false;
    }
  }
  meow::messagePrintf(-1, "ok");
  //
  
  dsj.reset(N);
  meow::messagePrintf(1, "merge(0, 1) merge(1, 2) merge(2, 3) ... (N = %d)", N);
  for(int i = 1; i < N; i++){
    dsj.merge(i - 1, i);
  }
  root = dsj.root(0);
  for(int i = 1; i < N; i++){
    if(root != (int)dsj.root(i)){
      meow::messagePrintf(-1, "fail");
      return false;
    }
  }
  meow::messagePrintf(-1, "ok");
  //
  
  int M = 1000;
  N = 1000000;
  dsj.reset(N);
  std::vector<int> used(N, -1);
  std::vector<std::vector<int> > nums(M);
  
  meow::messagePrintf(1, "random test (N = %d)", N);
  for(int i = 0; i < N / 10; i++){
    int grp = rand() % M;
    int who;
    while(used[who = rand() % N] != -1);
    nums[grp].push_back(who);
    used[who] = grp;
  }
  meow::messagePrintf(0, "data created");
  for(int i = 0; i < M; i++){
    for(int k = 0; k < 100; k++){
      int j1 = rand() % nums[i].size();
      int j2 = rand() % nums[i].size();
      dsj.merge(nums[i][j1], nums[i][j2]);
    }
    for(size_t j = 1; j < nums[i].size(); j++){
      dsj.merge(nums[i][0], nums[i][j]);
    }
  }
  for(int i = 0; i < N; i++){
    bool ok = false;
    if((int)used[i] == -1 && (int)dsj.root(i) == i){
      ok = true;
    }else{
      if(dsj.root(i) == dsj.root(nums[used[i]][0])){
        ok = true;
      }
    }
    if(!ok){
      meow::messagePrintf(-1, "fail");
      return false;
    }
  }
  meow::messagePrintf(-1, "ok");
  return true;
}