#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <cassert>
#include <chrono>
#include <memory>
#include <string.h>

using namespace std;

using Stamp = int32_t;

template<typename T>
class Pool;

template<typename T>
class Handle {
private:
  friend class Pool<T>;
  int32_t mIndex { 0 };
  Stamp mStamp { 0 };
  Handle(int32_t index, Stamp stamp) : mIndex(index), mStamp(stamp) { }
public:
  Handle() { }
};

template<typename T>
class PoolRecord final {
private:
  friend class Pool<T>;
  Stamp mStamp { 0 };
public:
  T mObject;
  template<typename... Args>
  PoolRecord(int stamp, Args&&... args) : mStamp(stamp), mObject(args...) {
  }
  bool IsValid() const noexcept {
    return mStamp != 0;
  }
  const T * operator -> () const {
    return &mObject;
  }
  T * operator -> () {
    return &mObject;
  }
};

template<typename T>
class Pool final {
private:
  size_t mSpawnedCount { 0 };
  Stamp mGlobalStamp { 1 };
  PoolRecord<T> * mRecords;
  size_t mRecordCount;
  size_t mCapacity;
public:
  Pool() {

  }
  ~Pool() {
    for (size_t i = 0; i < mRecordCount; ++i) {
      mRecords[i].~PoolRecord();
    }
  }
  template<typename... Args>
  Handle<T> Spawn(Args&&... args) {
    // Find free object
    for (size_t i = 0; i < mRecordCount; ++i ) {
      auto & rec = mRecords[i];
      if (rec.mStamp == 0) {
        rec.mStamp = mGlobalStamp++;
        // Reconstruct object via placement new
        new(&rec.mObject) T(args...);
        ++mSpawnedCount;
        return Handle<T>{static_cast<int32_t>(i), rec.mStamp};
      }
    }
    // No free objects, grow pool
    if (mRecordCount >= mCapacity) {
      int oldCapacity = mCapacity;
      if (mCapacity == 0) {
        mCapacity = 1;
      } else {
        mCapacity *= 2;
      }
      PoolRecord<T> * old = mRecords;
      mRecords = reinterpret_cast<PoolRecord<T>*>(malloc(sizeof(PoolRecord<T>) * mCapacity));
      memcpy(mRecords, old, oldCapacity * sizeof(PoolRecord<T>));
      free(old);
    }
    // Obtain new record
    auto & rec = mRecords[mRecordCount];
    rec.mStamp = mGlobalStamp++;
    // Invoke placement new to construct object
    new(&rec.mObject) T(args...);
    ++mSpawnedCount;
    ++mRecordCount;
    return Handle<T>{static_cast<int32_t>(mRecordCount - 1), rec.mStamp};
  }
  void Return(const Handle<T> & handle) {
    if (static_cast<size_t>(handle.mIndex) >= mRecordCount) {
      throw runtime_error("Handle has invalid index!");
    }
    auto & rec = mRecords[handle.mIndex];
    rec.mObject.~T(); // destruct
    rec.mStamp = 0;
    --mSpawnedCount;
  }
  bool IsValid(const Handle<T> & handle) {
    if (static_cast<size_t>(handle.mIndex) >= mRecordCount) {
      throw runtime_error("Handle has invalid index!");
    }
    return handle.mStamp == mRecords[handle.mIndex].mStamp;
  }
  T & operator[](const Handle<T> & handle) const {
    return mRecords[handle.mIndex].mObject;
  }
  size_t GetSize() const noexcept {
    return mRecordCount;
  }
  size_t GetSpawnedCount() const noexcept {
    return mSpawnedCount;
  }
  size_t GetCapacity() const noexcept {
    return mCapacity;
  }
  PoolRecord<T> * GetRecords() noexcept {
    return mRecords;
  }
  // range-based for
  PoolRecord<T> * begin() {
    return mRecords;
  }
  PoolRecord<T> * end() {
    return mRecords + mRecordCount;
  }
  // Use this only to obtain handle by 'this' pointer inside class method
  // Do not rely on pointers to objects in pool, they can suddenly become invalid
  // this pointer can be used, because it is always valid
  Handle<T> HandleByPointer(const T * ptr) const {
    for (size_t i = 0; i < mRecordCount; ++i) {
      if (&mRecords[i].mObject == ptr) {
        return Handle<T>(static_cast<int32_t>(i), mRecords[i].mStamp);
      }
    }
  }
};

class PoolableNode {
private:
  string mName;
  Handle<PoolableNode> mParent;
  vector<Handle<PoolableNode>> mChildren;
  // pointer to pool always valid, since node allocated inside the pool
  Pool<PoolableNode> * mPool { nullptr };
public:
  PoolableNode(Pool<PoolableNode> * pool) : mPool(pool) {

  }
  virtual ~PoolableNode() {
    for(int i = 0; i < mChildren.size(); ++i) {
      mPool->Return(mChildren[i]);
    }
  }
  void SetName(const string & name) {
    mName = name;
  }
  void AttachTo(const Handle<PoolableNode> & parentHandle) {
    auto & parent = (*mPool)[parentHandle];
    mParent = parentHandle;
    parent.mChildren.push_back(mPool->HandleByPointer(this));
  }
};

class OrdinaryNode : public enable_shared_from_this<OrdinaryNode> {
private:
  string mName;
  weak_ptr<OrdinaryNode> mParent;
  vector<shared_ptr<OrdinaryNode>> mChildren;
public:
  OrdinaryNode() {

  }
  virtual ~OrdinaryNode() {

  }
  void SetName(const string & name) {
    mName = name;
  }
  void AttachTo(const shared_ptr<OrdinaryNode> & parent) {
    parent->mChildren.push_back(shared_from_this());
    mParent = parent;
  }
};

int main(int argc, char **argv) {
  // Sanity tests
  {
    Pool<PoolableNode> pool;

    auto handle = pool.Spawn(&pool);
    assert(pool.IsValid(handle));
    assert(pool.GetSize() == 1);

    pool.Return(handle);
    assert(!pool.IsValid(handle));
    assert(pool.GetSize() == 1);
    assert(pool.GetSpawnedCount() == 0);

    auto newHandle = pool.Spawn(&pool);
    assert(pool.IsValid(newHandle));
    assert(pool.GetSpawnedCount() == 1);
    pool.Return(newHandle);
  }

  // Performance test
  {
    constexpr int count = 10000;

    // PoolableNode
    {
      Pool<PoolableNode> pool;

      auto lastTime = chrono::high_resolution_clock::now();
      for (int i = 0; i < count; ++i) {
        auto parent = pool.Spawn(&pool);
        pool[parent].SetName("Parent");
        auto child = pool.Spawn(&pool);
        pool[child].SetName("Child");
        pool[child].AttachTo(parent);
        pool.Return(parent);
      }

      cout << "PoolableNode: " << chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - lastTime).count() << " microseconds" << endl;
    }

    // OrdinaryNode
    {
      auto lastTime = chrono::high_resolution_clock::now();

      for (int i = 0; i < count; ++i) {
        auto parent = make_shared<OrdinaryNode>();
        parent->SetName("Parent");
        auto child = make_shared<OrdinaryNode>();
        child->SetName("Child");
        child->AttachTo(parent);
        parent.reset();
      }

      cout << "OrdinaryNode: " << chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - lastTime).count() << " microseconds" << endl;
    }
  }


  system("pause");
  return 0;
}