/*
   +----------------------------------------------------------------------+
   | HipHop for PHP                                                       |
   +----------------------------------------------------------------------+
   | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   +----------------------------------------------------------------------+
   | This source file is subject to version 3.01 of the PHP license,      |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | http://www.php.net/license/3_01.txt                                  |
   | If you did not receive a copy of the PHP license and are unable to   |
   | obtain it through the world-wide-web, please send a note to          |
   | license@php.net so we can mail you a copy immediately.               |
   +----------------------------------------------------------------------+
*/
#include "hphp/util/sparse-id-containers.h"
#include <gtest/gtest.h>

#include <cstdint>
#include <initializer_list>
#include <vector>
#include <stdexcept>

#include <folly/ScopeGuard.h>

namespace HPHP {

namespace {

//////////////////////////////////////////////////////////////////////

constexpr uint16_t kTestUniverseSize = 4096;

sparse_id_set<uint16_t> make_test_set(std::initializer_list<uint16_t> vals) {
  auto ret = sparse_id_set<uint16_t>{kTestUniverseSize};
  for (auto v : vals) ret.insert(v);
  return ret;
}

using IntMap = sparse_id_map<uint32_t,uint32_t>;

IntMap make_test_map(
    std::initializer_list<std::pair<uint32_t,uint32_t>> vals) {
  auto ret = IntMap{kTestUniverseSize};
  for (auto v : vals) ret.insert(v);
  return ret;
}

struct LiveCount {
  static uint32_t count;

  LiveCount() { ++count; }
  LiveCount(const LiveCount&) { ++count; }
  ~LiveCount() { --count; }
};
uint32_t LiveCount::count = 0;

struct CopyThrower {
  static uint32_t throw_plan;
  static uint32_t current_count;
  static void plan_throw(uint32_t when) {
    throw_plan = when;
    current_count = 0;
  }

  CopyThrower() = default;
  CopyThrower(const CopyThrower&) {
    if (++current_count == throw_plan) {
      throw std::runtime_error("ok");
    }
  }

  LiveCount counter;
};
uint32_t CopyThrower::throw_plan;
uint32_t CopyThrower::current_count;

//////////////////////////////////////////////////////////////////////

}

TEST(SparseIdSet, Basic) {
  sparse_id_set<uint16_t> set(2048);

  EXPECT_FALSE(set.contains(2));
  EXPECT_FALSE(set.contains(0));
  EXPECT_FALSE(set.contains(8));

  set.insert(2);
  set.insert(2);
  set.insert(8);
  set.insert(2);
  set.insert(0);

  EXPECT_TRUE(set.contains(2));
  EXPECT_TRUE(set.contains(8));
  EXPECT_TRUE(set.contains(0));
  EXPECT_EQ(3, set.size());
  set.erase(8);
  EXPECT_FALSE(set.contains(8));
  EXPECT_EQ(2, set.size());
}

TEST(SparseIdSet, Unions) {
  auto const a = make_test_set({1, 42, 1234, 1, 234, 2, 2, 3});
  auto const b = make_test_set({500, 600, 700, 800});
  auto const manual_union = make_test_set({
    1, 42, 1234, 1, 234, 2, 2, 3,
    500, 600, 700, 800
  });

  auto tmpSet = a;
  tmpSet |= b;

  EXPECT_EQ(tmpSet, manual_union);
}

TEST(SparseIdSet, Intersect) {
  auto const a = make_test_set({1, 2, 3, 4, 5, 6});
  auto const b = make_test_set({2, 3, 4, 5});

  auto c = a;
  c &= b;
  EXPECT_EQ(make_test_set({2,3,4,5}), c);

  c &= make_test_set({3});
  EXPECT_TRUE(c.contains(3));
  EXPECT_FALSE(c.contains(2));
  EXPECT_EQ(make_test_set({3}), c);
}

TEST(SparseIdSet, IterationOrder) {
  sparse_id_set<uint16_t> set(kTestUniverseSize);
  auto vec = std::vector<sparse_id_set<uint16_t>::value_type>{};

  for (auto i = uint16_t{0}; i < 1024; ++i) {
    auto val = std::rand() % kTestUniverseSize;
    if (!set.contains(val)) {
      set.insert(val);
      vec.push_back(val);
    }
  }

  auto iter = set.begin();
  for (auto t : vec) {
    EXPECT_TRUE(iter != set.end());
    if (iter == set.end()) break;
    EXPECT_EQ(t, *iter);
    ++iter;
  }
}

TEST(SparseIdSet, EraseBack) {
  sparse_id_set<uint16_t> set(kTestUniverseSize);

  EXPECT_TRUE(set.empty());

  set.insert(10);
  set.insert(2);
  set.insert(5);
  for (auto i = 0; i < 999; ++i) {
    set.insert(6);
  }

  EXPECT_FALSE(set.empty());
  EXPECT_TRUE(set.contains(6));
  EXPECT_EQ(6, set.back());
  EXPECT_EQ(10, set.front());
  EXPECT_EQ(4, set.size());

  set.erase(6);
  EXPECT_EQ(3, set.size());
  EXPECT_EQ(5, set.back());
  EXPECT_FALSE(set.contains(6));

  set.erase(5);
  EXPECT_EQ(2, set.size());
  EXPECT_EQ(2, set.back());
  EXPECT_FALSE(set.contains(5));
  EXPECT_FALSE(set.contains(6));
  EXPECT_TRUE(set.contains(2));
  EXPECT_TRUE(set.contains(10));

  set.erase(2);
  EXPECT_EQ(1, set.size());
  EXPECT_EQ(10, set.back());
  EXPECT_EQ(set.front(), set.back());
  EXPECT_TRUE(set.contains(10));
  EXPECT_FALSE(set.contains(5));
  EXPECT_FALSE(set.contains(6));
  EXPECT_FALSE(set.contains(2));

  set.erase(10);
  EXPECT_TRUE(set.empty());
}

TEST(SparseIdSet, Clear) {
  auto x = make_test_set({1234, 124, 1234, 5});
  EXPECT_EQ(3 /* no duplicate above */, x.size());
  x.clear();
  EXPECT_TRUE(x.empty());
  EXPECT_EQ(0, x.size());
}

TEST(SparseIdSet, Show) {
  auto x = make_test_set({55, 34, 12});
  EXPECT_EQ("55 34 12", show(x));
}

TEST(SparseIdSet, MoveAssign) {
  auto x = make_test_set({55, 34, 12});
  sparse_id_set<uint16_t> tmp(kTestUniverseSize);
  tmp = std::move(x);
  sparse_id_set<uint16_t> tmp2(0);
  tmp2 = std::move(tmp);
}

//////////////////////////////////////////////////////////////////////

TEST(SparseIdMap, Basic) {
  sparse_id_map<uint32_t,std::string> map(2048);

  EXPECT_TRUE(map.empty());

  map[1024] = "ok";
  EXPECT_FALSE(map.contains(0));
  map[0] = "hi";

  EXPECT_EQ("ok", map[1024]);
  EXPECT_EQ("hi", map[0]);
  EXPECT_EQ(std::string("ok"), map.front().second);
  EXPECT_EQ(std::string("hi"), map.back().second);

  EXPECT_TRUE(map.contains(0));
  EXPECT_TRUE(map.contains(1024));

  EXPECT_EQ(2, map.size());
  map.erase(1024);
  EXPECT_EQ(1, map.size());
}

TEST(SparseIdMap, Dtors) {
  SCOPE_EXIT { EXPECT_EQ(0, LiveCount::count); };
  sparse_id_map<uint32_t,LiveCount> map(4096);

  EXPECT_EQ(0, LiveCount::count);
  map[12] = LiveCount();
  EXPECT_EQ(1, LiveCount::count);
  map[12] = LiveCount();
  EXPECT_EQ(1, LiveCount::count);
  map[0] = LiveCount();
  EXPECT_EQ(2, LiveCount::count);
  map.clear();
  EXPECT_EQ(0, LiveCount::count);

  sparse_id_map<uint32_t,LiveCount> another(2048);
  for (auto i = uint32_t{0}; i < 10; ++i) {
    another[i] = LiveCount{};
  }
  EXPECT_EQ(10, LiveCount::count);
  map = std::move(another);
  EXPECT_EQ(10, LiveCount::count);
  EXPECT_EQ(10, map.size());
  auto idx = uint32_t{0};
  for (auto& kv : map) {
    EXPECT_EQ(idx, kv.first);
    ++idx;
  }
}

TEST(SparseIdMap, Erases) {
  auto test = make_test_map({{10, 10}, {24, 24}, {32, 32}});
  EXPECT_EQ(3, test.size());
  EXPECT_EQ(10, test.front().first);
  EXPECT_EQ(32, test.back().first);
  test.erase(24);
  EXPECT_EQ(2, test.size());
  EXPECT_EQ(10, test.front().first);
  EXPECT_EQ(32, test.back().first);

  for (auto i = uint32_t{0}; i < 1024; ++i) {
    test[i + 1024] = i + 1024;
  }
  EXPECT_EQ(1024 * 2 - 1, test.back().first);

  auto sz = 1024 + 2;
  do {
    EXPECT_EQ(sz, test.size());
    test.erase(test.front().first);
    --sz;
  } while (!test.empty());
}

TEST(SparseIdMap, Compare) {
  auto testa = make_test_map({{1, 1}, {2, 2}});
  auto testb = make_test_map({{2, 2}, {1, 1}});
  auto testc = make_test_map({{2, 1}, {1, 1}});
  EXPECT_EQ(testa, testa);
  EXPECT_EQ(testb, testb);
  EXPECT_EQ(testa, testb);
  EXPECT_NE(testa, testc);
  EXPECT_NE(testb, testc);
  EXPECT_EQ(testc, testc);
}

TEST(SparseIdMap, ExceptionCleanup) {
  using M = sparse_id_map<uint32_t,CopyThrower>;

  bool caught{true};
  for (auto plan_counter = uint32_t{0}; caught; ++plan_counter) {
    CopyThrower::plan_throw(plan_counter);
    caught = false;
    try {
      M thing(kTestUniverseSize);
      for (auto i = uint32_t{0}; i < 15; ++i) {
        thing.insert(std::make_pair(i, CopyThrower()));
      }
      M thing2 = thing;
      M thing3(0);
      thing3 = thing2;
    } catch (...) {
      EXPECT_EQ(0, LiveCount::count);
      caught = true;
    }
  }

  EXPECT_EQ(0, LiveCount::count);
}

TEST(SparseIdMap, Merge) {
  struct Foo {
    bool operator==(Foo f) const { return value == f.value; }
    uint32_t value;
  };

  sparse_id_map<uint32_t,Foo> a(1024);
  sparse_id_map<uint32_t,Foo> b(1024);

  a[0] = Foo { 0 };
  a[7] = Foo { 7 };
  for (auto i = uint32_t{0}; i < 200; ++i) {
    a[30 + i] = Foo { 30 + i };
  }
  a[7] = Foo { 3 };
  b[2] = Foo { 10 };
  b[7] = Foo { 70 };
  b[1] = Foo { 10 };
  b[0] = Foo { 10 };

  EXPECT_EQ(202, a.size());
  EXPECT_EQ(4, b.size());

  auto merge_calls = uint32_t{0};
  auto merge_fn = [&] (Foo& dst, const Foo& src) {
    auto const old = dst.value;
    dst.value = std::max(dst.value, src.value);
    ++merge_calls;
    return old != dst.value;
  };

  EXPECT_TRUE(a.merge(b, merge_fn));
  EXPECT_EQ(2, merge_calls);

  EXPECT_EQ(2, a.size());

  EXPECT_EQ(10, a[0].value);
  EXPECT_EQ(70, a[7].value);

  // Merge a back into b.  They should be the same now.
  EXPECT_EQ(4, b.size());
  merge_calls = 0;
  EXPECT_EQ(2, a.size());
  EXPECT_TRUE(b.merge(a, merge_fn));
  EXPECT_EQ(2, merge_calls);
  EXPECT_EQ(a.size(), b.size());
  EXPECT_EQ(a, b);

  // Now they shouldn't change either direction:
  EXPECT_FALSE(a.merge(b, merge_fn));
  EXPECT_FALSE(b.merge(a, merge_fn));
}

//////////////////////////////////////////////////////////////////////

TEST(SparseId, StructyLookups) {
  struct StrongerTypedId {
    uint32_t id;
    /* implicit */ operator uint32_t() { return id; }
  };

  sparse_id_map<uint32_t,int,StrongerTypedId> map(12);
  map[StrongerTypedId{0}] = 2;
  EXPECT_EQ(1, map.size());
  map.erase(StrongerTypedId{0});
  EXPECT_EQ(0, map.size());

  sparse_id_set<uint32_t,StrongerTypedId> set(12);
  set.insert(StrongerTypedId{2});
  EXPECT_EQ(1, set.size());
  set.erase(StrongerTypedId{0});
  EXPECT_EQ(1, set.size());
  set.erase(StrongerTypedId{2});
  EXPECT_EQ(0, set.size());
}

TEST(SparseId, PointeryLookups) {
  struct SSATmp {
    uint32_t id() const { return m_id; }
    uint32_t m_id;
  };

  struct IDEx {
    uint32_t operator()(SSATmp* tmp) const { return tmp->id(); }
  };

  SSATmp one { 1 };
  SSATmp two { 2 };
  SSATmp three { 3 };

  sparse_id_map<uint32_t,int,SSATmp*,IDEx> map(5);

  map[&one] = 2;
  map[&two] = 3;
  map[&three] = 4;

  EXPECT_EQ(3, map.size());
}

//////////////////////////////////////////////////////////////////////

}
