#include <gtest/gtest.h>
#include <iostream>
#include <random>
#include <vector>
#include "map.hpp"

TEST(BasicTests, GTestItSelf) {
  // Expect two strings not to be equal.
  EXPECT_STRNE("hello", "world");
  // Expect equality.
  EXPECT_EQ(7 * 6, 42);
}

TEST(BasicTests, ConstructorAndEmptySize) {
  sjtu::map<int, int> map;
  EXPECT_EQ(map.empty(), true);
  EXPECT_EQ(map.size(), 0);
}

TEST(BasicTests, BasicOperatorInsert) {
  sjtu::map<int, int> map1;
  map1[1] = 2;
  EXPECT_EQ(map1.empty(), false);
  EXPECT_EQ(map1.size(), 1);
  EXPECT_EQ(map1[1], 2);
  auto it = map1.find(1);
  EXPECT_EQ(it->second, 2);
  sjtu::map<int, int> map2;
  auto ret = map2.insert(sjtu::pair<int, int>(1, 2));
  EXPECT_EQ(ret.second, true);
  EXPECT_EQ(ret.first->first, 1);
  EXPECT_EQ(ret.first->second, 2);
}

TEST(BasicTests, MassiveOperatorInsert) {
  std::mt19937 rnd(2333);
  sjtu::map<int, int> map;
  std::map<int, int> standard_map;
  int nodes = 1000;
  for (int i = 0; i < nodes; ++i) {
    int key = rnd() % 10000;
    int value = rnd() % 10000;
    // std::cerr << "writing " << key << " " << value << "\n";
    map[key] = value;
#ifndef NDEBUG
    EXPECT_TRUE(map.RedBlackTreeStructureCheck());
#endif
    standard_map[key] = value;
  }
  auto mp_it = map.begin();
  auto st_it = standard_map.begin();
  EXPECT_EQ(map.size(), standard_map.size());
  for (; mp_it != map.end(); mp_it++, st_it++) {
    EXPECT_EQ(mp_it->first, st_it->first);
    EXPECT_EQ(mp_it->second, st_it->second);
  }
  mp_it = map.end();
  st_it = standard_map.end();
  for (int i = 0; i < map.size(); ++i) {
    mp_it--;
    st_it--;
    EXPECT_EQ(mp_it->first, st_it->first);
    EXPECT_EQ(mp_it->second, st_it->second);
  }
}

TEST(BasicTests, BasicOperationErase) {
  sjtu::map<int, int> mp;
  mp[1] = 2;
  mp[3] = 4;
  mp[5] = 7;
  mp[9] = 11;
  auto it = mp.find(3);
  mp.erase(it);
  EXPECT_EQ(mp.size(), 3);
  it = mp.begin();
  EXPECT_EQ(it->first, 1);
  EXPECT_EQ(it->second, 2);
  it++;
  EXPECT_EQ(it->first, 5);
  EXPECT_EQ(it->second, 7);
  it++;
  EXPECT_EQ(it->first, 9);
  EXPECT_EQ(it->second, 11);
}

TEST(BasicTests, MassiveOperationErase) {
  std::mt19937 rnd(2333333);
  sjtu::map<int, int> map;
  std::map<int, int> standard_map;
  int nodes = 7, range = 7;
  for (int i = 0; i < nodes; ++i) {
    int key = rnd() % range;
    int value = rnd() % range;
    map[key] = value;
    standard_map[key] = value;
    std::cerr << "inserting " << key << " " << value << "\n";
  }
  std::vector<int> keys;
  for (auto items : standard_map) keys.push_back(items.first);
  for (int i = 0; i < nodes / 2; ++i) {
    int kid = rnd() % keys.size();
    int key = keys[kid];
    std::cerr << "erasing " << key << "\n";
    map.erase(map.find(key));
    standard_map.erase(key);
    keys.erase(keys.begin() + kid);
#ifndef NDEBUG
    EXPECT_TRUE(map.RedBlackTreeStructureCheck());
#endif
  }
  auto mp_it = map.begin();
  auto st_it = standard_map.begin();
  EXPECT_EQ(map.size(), standard_map.size());
  for (; mp_it != map.end(); mp_it++, st_it++) {
    EXPECT_EQ(mp_it->first, st_it->first);
    EXPECT_EQ(mp_it->second, st_it->second);
  }
  mp_it = map.end();
  st_it = standard_map.end();
  for (int i = 0; i < map.size(); ++i) {
    mp_it--;
    st_it--;
    EXPECT_EQ(mp_it->first, st_it->first);
    EXPECT_EQ(mp_it->second, st_it->second);
  }
}