#include <memory>
#include <functional>

struct StandardDelete {
  template<typename T>
  void operator()(T* ptr) {
    delete ptr;
  }
};

struct Deleter {
  virtual void destroy(void*) = 0;
  virtual void deallocate(void*) = 0;
  virtual ~Deleter() {}
};

template<class T, class Allocator>
struct ObjectManagerBlock : Deleter {
  Allocator allocator_;
  ObjectManagerBlock(const Allocator& allocator) : allocator_(allocator) {}

  void destroy(void* ptr) override {
    using ConstructAllocator = typename std::allocator_traits<Allocator>::template rebind_alloc<T>;
    using ConstructAllocatorTraits = typename std::allocator_traits<ConstructAllocator>;
    ConstructAllocator construct_allocator = allocator_;

    ConstructAllocatorTraits::destroy(construct_allocator, static_cast<T*>(ptr));
  }
  void deallocate(void* ptr) override {
    using MemoryAllocator = typename std::allocator_traits<Allocator>::template rebind_alloc<uint8_t>;
    using MemoryAllocatorTraits = typename std::allocator_traits<MemoryAllocator>;
    MemoryAllocator memory_allocator = allocator_;

    MemoryAllocatorTraits::deallocate(memory_allocator,
                                      reinterpret_cast<uint8_t*>(ptr),
                                      sizeof(T) + 2 * sizeof(size_t) + sizeof(Deleter));
  }
};

template<class T, class TDeleter, class Allocator>
struct DeleterWithSpecialDeleter : Deleter {
  Allocator allocator_;
  TDeleter t_deleter_;
  DeleterWithSpecialDeleter(const Allocator& allocator, const TDeleter& t_deleter)
      : allocator_(allocator), t_deleter_(t_deleter) {}
  void destroy(void* ptr) override {
    t_deleter_(reinterpret_cast<T*>(ptr));
  }
  void deallocate(void* ptr) override {
    using MemoryAllocator = typename std::allocator_traits<Allocator>::template rebind_alloc<uint8_t>;
    using MemoryAllocatorTraits = typename std::allocator_traits<MemoryAllocator>;
    MemoryAllocator memory_allocator = allocator_;
    MemoryAllocatorTraits::deallocate(memory_allocator,
                                      reinterpret_cast<uint8_t*>(ptr),
                                      2 * sizeof(size_t) + sizeof(Deleter));
  }
};

template<class T>
class WeakPtr;

template<class T>
class SharedPtr {
 private:
  template<class U>
  friend
  class SharedPtr;
  template<class U>
  friend
  class WeakPtr;
  struct TemplateConstructorTag {};

  void decrease_counter() {
    if (counter_) {
      --*counter_;
      if (*counter_ == 0) {
        deleter_->destroy(value_);
        if (*weak_counter_ == 0) {
          if (!is_block_) {
            deleter_->deallocate(counter_);
          } else {
            deleter_->deallocate(value_);
          }
        }
      }
    }
  }

  void increase_counter() {
    if (counter_) {
      ++*counter_;
    }
  }

  void reset_without_decrease() {
    value_ = nullptr;
    counter_ = nullptr;
    weak_counter_ = nullptr;
    deleter_ = nullptr;
    is_block_ = false;
  }

 public:


  ~SharedPtr() {
    decrease_counter();
  }
  SharedPtr() {}
  SharedPtr(T* ptr) : SharedPtr(ptr, StandardDelete(), std::allocator<size_t>()) {}
  template<class TDeleter, class Allocator = std::allocator<size_t>>
  SharedPtr(T* ptr, const TDeleter& deleter, Allocator allocator = Allocator()) : SharedPtr() {
    reset<Allocator, TDeleter>(ptr, allocator, deleter);
  }

  template<class Allocator = std::allocator<size_t>, class TDeleter = StandardDelete>
  void reset(T* ptr, Allocator allocator = Allocator(), const TDeleter& t_deleter = TDeleter()) {
    decrease_counter();
    value_ = ptr;
    is_block_ = false;

    using MemoryAllocator = typename std::allocator_traits<Allocator>::template rebind_alloc<uint8_t>;
    using MemoryAllocatorTraits = typename std::allocator_traits<MemoryAllocator>;
    MemoryAllocator memory_allocator = allocator;
    auto mem = MemoryAllocatorTraits::allocate(memory_allocator, 2 * sizeof(size_t) + sizeof(Deleter));

    counter_ = reinterpret_cast<size_t*>(mem);
    *counter_ = 1;
    weak_counter_ = reinterpret_cast<size_t*>(mem + sizeof(size_t));
    *weak_counter_ = 0;
    deleter_ = reinterpret_cast<Deleter*>(mem + 2 * sizeof(size_t));
    new(deleter_) DeleterWithSpecialDeleter<T, TDeleter, Allocator>(allocator, t_deleter);
  }

  void reset() {
    decrease_counter();
    reset_without_decrease();
  }

  SharedPtr(SharedPtr&& another) : SharedPtr(std::move(another), TemplateConstructorTag()) {}

  template<class U>
  SharedPtr(SharedPtr<U>&& another, TemplateConstructorTag = TemplateConstructorTag()) {
    value_ = std::move(another.value_);
    counter_ = std::move(another.counter_);
    weak_counter_ = std::move(another.weak_counter_);
    deleter_ = std::move(another.deleter_);
    is_block_ = another.is_block_;
    another.reset_without_decrease();
  }

  SharedPtr(const SharedPtr& another) : SharedPtr(another, TemplateConstructorTag()) {}

  template<class U>
  SharedPtr(const SharedPtr<U>& another, TemplateConstructorTag = TemplateConstructorTag()) {
    value_ = another.value_;
    counter_ = another.counter_;
    weak_counter_ = another.weak_counter_;
    deleter_ = another.deleter_;
    is_block_ = another.is_block_;
    increase_counter();
  }

  SharedPtr& operator=(const SharedPtr& another) {
    return operator=<T>(another);
  }

  template<class U>
  SharedPtr& operator=(const SharedPtr<U>& another) {
    SharedPtr tmp(another);
    swap(tmp);
    return *this;
  }

  SharedPtr& operator=(SharedPtr&& another) {
    return operator=<T>(std::move(another));
  }

  template<class U>
  SharedPtr& operator=(SharedPtr<U>&& another) {
    SharedPtr tmp(std::move(another));
    swap(tmp);
    return *this;
  }

  size_t use_count() const {
    return *counter_;
  }

  T* operator->() {
    return value_;
  }

  T& operator*() {
    return *value_;
  }

  const T& operator*() const {
    return *value_;
  }

  T* get() {
    return value_;
  }

  const T* get() const {
    return value_;
  }

  void swap(SharedPtr<T>& another) {
    std::swap(value_, another.value_);
    std::swap(counter_, another.counter_);
    std::swap(weak_counter_, another.weak_counter_);
    std::swap(deleter_, another.deleter_);
    std::swap(is_block_, another.is_block_);
  }
 private:
  template<class U, class... Args>
  friend SharedPtr<U> makeShared(Args&& ... args);
  template<class U, class Alloc, class... Args>
  friend SharedPtr<U> allocateShared(const Alloc& alloc, Args&& ... args);

  friend WeakPtr<T>;

  T* value_ = nullptr;
  size_t* counter_ = nullptr;
  size_t* weak_counter_ = nullptr;
  Deleter* deleter_ = nullptr;
  bool is_block_ = false;
  template<class Alloc = std::allocator<size_t>>
  SharedPtr(T* ptr, size_t* counter, size_t* weak_counter, Deleter* deleter, const Alloc& alloc) :
      value_(ptr), counter_(counter), weak_counter_(weak_counter), deleter_(deleter), is_block_(true) {
    increase_counter();
    new(deleter) ObjectManagerBlock<T, Alloc>(alloc);
  }
  SharedPtr(T* ptr, size_t* counter, size_t* weak_counter, Deleter* deleter, bool is_block) :
      value_(ptr), counter_(counter), weak_counter_(weak_counter), deleter_(deleter), is_block_(is_block) {
    increase_counter();
  }
};

template<class T>
class WeakPtr {
  template<class U>
  friend
  class WeakPtr;
  struct TemplateConstructorTag {};
 public:
  ~WeakPtr() {
    decrease_counter();
  }
  WeakPtr() {}
  WeakPtr(const SharedPtr<T>& another) : WeakPtr(another, TemplateConstructorTag()) {}
  template<class U>
  WeakPtr(const SharedPtr<U>& another, TemplateConstructorTag = TemplateConstructorTag()) {
    value_ = another.value_;
    counter_ = another.counter_;
    weak_counter_ = another.weak_counter_;
    deleter_ = another.deleter_;
    is_block_ = another.is_block_;
    increase_counter();
  }
  WeakPtr(const WeakPtr& another) : WeakPtr(another, TemplateConstructorTag()) {}
  template<class U>
  WeakPtr(const WeakPtr<U>& another, TemplateConstructorTag = TemplateConstructorTag()) {
    value_ = another.value_;
    counter_ = another.counter_;
    weak_counter_ = another.weak_counter_;
    deleter_ = another.deleter_;
    is_block_ = another.is_block_;
    increase_counter();
  }
  size_t use_count() const {
    return *counter_;
  }
  bool expired() const {
    return *counter_ == 0;
  }
  SharedPtr<T> lock() const {
    return SharedPtr<T>(value_, counter_, weak_counter_, deleter_, is_block_);
  }
  WeakPtr& operator=(const WeakPtr& another) {
    WeakPtr tmp(another);
    swap(tmp);
    return *this;
  }
  WeakPtr& operator=(WeakPtr&& another) {
    WeakPtr tmp(another);
    swap(tmp);
    return *this;
  }
  WeakPtr& operator=(const SharedPtr<T>& another) {
    WeakPtr tmp(another);
    swap(tmp);
    return *this;
  }
 private:
  void decrease_counter() {
    if (weak_counter_) {
      --*weak_counter_;
      if (*counter_ == 0 && *weak_counter_ == 0) {
        if (!is_block_) {
          deleter_->deallocate(counter_);
        } else {
          deleter_->deallocate(value_);
        }
      }
    }
  }
  void increase_counter() {
    if (weak_counter_) {
      ++*weak_counter_;
    }
  }
  void swap(WeakPtr& another) {
    std::swap(value_, another.value_);
    std::swap(counter_, another.counter_);
    std::swap(weak_counter_, another.weak_counter_);
    std::swap(deleter_, another.deleter_);
  }
  T* value_ = nullptr;
  size_t* counter_ = nullptr;
  size_t* weak_counter_ = nullptr;
  Deleter* deleter_ = nullptr;
  bool is_block_ = false;
};

template<typename T, typename Alloc, typename... Args>
SharedPtr<T> allocateShared(const Alloc& alloc, Args&& ... args) {
  using MemoryAllocator = typename std::allocator_traits<Alloc>::template rebind_alloc<uint8_t>;
  using MemoryAllocatorTraits = typename std::allocator_traits<MemoryAllocator>;
  MemoryAllocator memory_allocator = alloc;
  auto ptr = MemoryAllocatorTraits::allocate(memory_allocator, sizeof(T) + 2 * sizeof(size_t) + sizeof(Deleter));

  using ConstructAllocator = typename std::allocator_traits<Alloc>::template rebind_alloc<T>;
  using ConstructAllocatorTraits = typename std::allocator_traits<ConstructAllocator>;
  ConstructAllocator construct_allocator = alloc;

  ConstructAllocatorTraits::construct(construct_allocator, (T*) ptr, std::forward<Args>(args)...);

  *(size_t*) (ptr + sizeof(T)) = 0;
  *(size_t*) (ptr + sizeof(T) + sizeof(size_t)) = 0;
  return SharedPtr<T>((T*) ptr, (size_t*) (ptr + sizeof(T)), (size_t*) (ptr + sizeof(T) + sizeof(size_t)),
                      (Deleter*) (ptr + sizeof(T) + 2 * sizeof(size_t)), alloc);
}

template<class T, typename... Args>
SharedPtr<T> makeShared(Args&& ... args) {
  return allocateShared<T>(std::allocator<T>(), std::forward<Args>(args)...);
}