#ifndef STL_MEMORY
#define STL_MEMORY

#include "cstddef"
#include "iterator"
#include "utility"
#include "type_traits"
#include "stdlib.h"

namespace std
{
// Minimal allocator implementation
template <typename T>
class allocator
{
public:
  typedef T value_type;
  typedef T *pointer;
  typedef const T *const_pointer;
  typedef T &reference;
  typedef const T &const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

  template <typename U>
  struct rebind
  {
    typedef allocator<U> other;
  };

  allocator() = default;

  template <typename U>
  allocator(const allocator<U> &)
  {
  }

  pointer allocate(size_type n)
  {
    return static_cast<pointer>(malloc(n * sizeof(T)));
  }

  void deallocate(pointer ptr, size_type)
  {
    free(ptr);
  }

  template <typename U, typename... Args>
  void construct(U *ptr, Args &&...args)
  {
    new (ptr) U(args...);
  }

  template <typename U>
  void destroy(U *ptr)
  {
    ptr->~U();
  }

  size_type max_size() const
  {
    return size_t(-1) / sizeof(T);
  }

  bool operator==(const allocator &) const
  {
    return true;
  }
  bool operator!=(const allocator &) const
  {
    return false;
  }
};

template <class X>
class auto_ptr
{
  X *ptr;

public:
  explicit auto_ptr(X *p = 0) throw()
  {
    ptr = p;
    //model
  }
  auto_ptr(auto_ptr &a) throw()
  {
    //model
  }
  template <class Y>
  auto_ptr(auto_ptr<Y> &a) throw()
  {
    //model
  }
  X *operator->() const throw()
  {
    //model
    return ptr;
  }
  X &operator*() const throw()
  {
    //model
    X &ptr2 = *ptr;
    return ptr2;
  }
  auto_ptr &operator=(auto_ptr &a) throw();
  template <class Y>
  auto_ptr &operator=(auto_ptr<Y> &a) throw();
  X *release() throw();
  void reset(X *p = 0) throw();
  template <class Y>
  operator auto_ptr<Y>() throw();
};

template <class T>
pair<T *, ptrdiff_t> get_temporary_buffer(ptrdiff_t n);

template <class T>
void return_temporary_buffer(T *p);

template <class InputIterator, class ForwardIterator, class OutputIterator>
OutputIterator
copy(InputIterator first, InputIterator last, ForwardIterator result)
{
  for (; first != last; ++result, ++first)
    new (static_cast<void *>(&*result))
      typename iterator_traits<ForwardIterator>::value_type(*first);
  return result;
}

#if __cplusplus >= 201103L // Check if C++11 or later is being used

template <class T>
struct default_delete
{
  constexpr default_delete() noexcept = default;

  // Converting constructor: allows default_delete<U> -> default_delete<T>
  // when U* is implicitly convertible to T* (e.g. Derived* -> Base*).
  template <class U>
  default_delete(const default_delete<U> &) noexcept
  {
  }

  void operator()(T *ptr) const
  {
    delete ptr;
  }
};

// Partial specialization of default_delete for array types
template <class T>
struct default_delete<T[]>
{
  constexpr default_delete() noexcept = default;

  void operator()(T *ptr) const
  {
    delete[] ptr;
  }
};

template <class T, class D = default_delete<T>>
class unique_ptr
{
  T *ptr;
  D deleter;

public:
  explicit unique_ptr(T *p = nullptr, D del = D()) : ptr(p), deleter(del)
  {
  }

  unique_ptr(const unique_ptr &) = delete;
  unique_ptr &operator=(const unique_ptr &) = delete;

  unique_ptr(unique_ptr &&other) noexcept
    : ptr(other.ptr), deleter(std::move(other.deleter))
  {
    other.ptr = nullptr;
  }

  unique_ptr &operator=(unique_ptr &&other) noexcept
  {
    if (this != &other)
    {
      deleter(ptr);

      ptr = other.ptr;
      deleter = std::move(other.deleter);
      other.ptr = nullptr;
    }
    return *this;
  }

  // Converting move constructor: allows unique_ptr<U> -> unique_ptr<T>
  // when U* is implicitly convertible to T* (e.g. Derived* -> Base*).
  template <class U, class E>
  unique_ptr(unique_ptr<U, E> &&other) noexcept
    : ptr(other.release()), deleter(std::move(other.get_deleter()))
  {
  }

  // Converting move assignment: allows unique_ptr<U> -> unique_ptr<T>
  // when U* is implicitly convertible to T* (e.g. Derived* -> Base*).
  // No self-assignment check needed: U != T guarantees different objects.
  template <class U, class E>
  unique_ptr &operator=(unique_ptr<U, E> &&other) noexcept
  {
    if (ptr)
      deleter(ptr);
    ptr = other.release();
    deleter = std::move(other.get_deleter());
    return *this;
  }

#if 0
  // TODO: fix remove goto sideeffect
  ~unique_ptr()
  {
    deleter(ptr);
  }
#endif

  T *operator->() const
  {
    return ptr;
  }

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

  T *release()
  {
    T *temp = ptr;
    ptr = nullptr;
    return temp;
  }

  void reset(T *p = nullptr)
  {
    if (ptr != p)
    {
      deleter(ptr);
      ptr = p;
    }
  }

  T *get() const
  {
    return ptr;
  }

  D &get_deleter()
  {
    return deleter;
  }

  const D &get_deleter() const
  {
    return deleter;
  }

  explicit operator bool() const noexcept
  {
    return ptr != nullptr;
  }

  void swap(unique_ptr &other) noexcept
  {
    std::swap(ptr, other.ptr);
    std::swap(deleter, other.deleter);
  }
};

// Partial specialization for arrays: unique_ptr<T[]>
// Stores T* internally; provides operator[] instead of operator* and operator->
template <class T, class D>
class unique_ptr<T[], D>
{
  T *ptr;
  D deleter;

public:
  explicit unique_ptr(T *p = nullptr, D del = D()) : ptr(p), deleter(del)
  {
  }

  unique_ptr(const unique_ptr &) = delete;
  unique_ptr &operator=(const unique_ptr &) = delete;

  unique_ptr(unique_ptr &&other) noexcept
    : ptr(other.ptr), deleter(std::move(other.deleter))
  {
    other.ptr = nullptr;
  }

  unique_ptr &operator=(unique_ptr &&other) noexcept
  {
    if (this != &other)
    {
      deleter(ptr);
      ptr = other.ptr;
      deleter = std::move(other.deleter);
      other.ptr = nullptr;
    }
    return *this;
  }

  // Converting move constructor: allows unique_ptr<U[]> -> unique_ptr<T[]>
  // when U* is implicitly convertible to T* (e.g. Derived* -> Base*).
  template <class U, class E>
  unique_ptr(unique_ptr<U[], E> &&other) noexcept
    : ptr(other.release()), deleter(std::move(other.get_deleter()))
  {
  }

  // Converting move assignment: allows unique_ptr<U[]> -> unique_ptr<T[]>.
  template <class U, class E>
  unique_ptr &operator=(unique_ptr<U[], E> &&other) noexcept
  {
    if (ptr)
      deleter(ptr);
    ptr = other.release();
    deleter = std::move(other.get_deleter());
    return *this;
  }

  T &operator[](size_t i) const
  {
    return ptr[i];
  }

  T *get() const
  {
    return ptr;
  }

  T *release()
  {
    T *temp = ptr;
    ptr = nullptr;
    return temp;
  }

  void reset(T *p = nullptr)
  {
    if (ptr != p)
    {
      deleter(ptr);
      ptr = p;
    }
  }

  D &get_deleter()
  {
    return deleter;
  }

  const D &get_deleter() const
  {
    return deleter;
  }

  explicit operator bool() const noexcept
  {
    return ptr != nullptr;
  }

  void swap(unique_ptr &other) noexcept
  {
    std::swap(ptr, other.ptr);
    std::swap(deleter, other.deleter);
  }
};

template <class T, class D>
bool operator==(const unique_ptr<T, D> &x, std::nullptr_t) noexcept
{
  return x.get() == nullptr;
}

template <class T, class D>
bool operator==(std::nullptr_t, const unique_ptr<T, D> &x) noexcept
{
  return x.get() == nullptr;
}

template <class T, class D>
bool operator!=(const unique_ptr<T, D> &x, std::nullptr_t) noexcept
{
  return x.get() != nullptr;
}

template <class T, class D>
bool operator!=(std::nullptr_t, const unique_ptr<T, D> &x) noexcept
{
  return x.get() != nullptr;
}

template <class T, class D>
bool operator==(const unique_ptr<T, D> &x, const T *ptr) noexcept
{
  return x.get() == ptr;
}

template <class T, class D>
bool operator!=(const unique_ptr<T, D> &x, const T *ptr) noexcept
{
  return x.get() != ptr;
}

template <class T, class D>
bool operator==(const T *ptr, const unique_ptr<T, D> &x) noexcept
{
  return x.get() == ptr;
}

template <class T, class D>
bool operator!=(const T *ptr, const unique_ptr<T, D> &x) noexcept
{
  return x.get() != ptr;
}

template <class T, class D>
bool operator<(const unique_ptr<T, D> &x, const unique_ptr<T, D> &y) noexcept
{
  return x.get() < y.get();
}

template <class T, class D>
bool operator<=(const unique_ptr<T, D> &x, const unique_ptr<T, D> &y) noexcept
{
  return !(y < x);
}

template <class T, class D>
bool operator>(const unique_ptr<T, D> &x, const unique_ptr<T, D> &y) noexcept
{
  return y < x;
}

template <class T, class D>
bool operator>=(const unique_ptr<T, D> &x, const unique_ptr<T, D> &y) noexcept
{
  return !(x < y);
}

template <class T, class D>
void swap(unique_ptr<T, D> &x, unique_ptr<T, D> &y) noexcept
{
  x.swap(y);
}
#endif

#if __cplusplus >= 201402L
template <
  class T,
  class... Args,
  class = typename enable_if<!is_array<T>::value>::type>
unique_ptr<T> make_unique(Args &&...args)
{
  return unique_ptr<T>(new T(std::forward<Args>(args)...));
}

template <
  class T,
  class = typename enable_if<is_array<T>::value && extent<T>::value == 0>::type>
unique_ptr<T> make_unique(size_t n)
{
  return unique_ptr<T>(new remove_extent_t<T>[n]());
}
#endif

#if 0
template <class OutputIterator, class T>
class raw_storage_iterator :
public iterator<output_iterator_tag,void,void,void,void>
{
protected:
	OutputIterator iter;

public:
	explicit raw_storage_iterator (OutputIterator x) : iter(x) {}
	raw_storage_iterator<OutputIterator,T>& operator* ()
	{	return *this;}
	raw_storage_iterator<OutputIterator,T>& operator= (const T& element)
	{	new (static_cast<void*>(&*iter)) T (element); return *this;}
	raw_storage_iterator<OutputIterator,T>& operator++ ()
	{	++iter; return *this;}
	raw_storage_iterator<OutputIterator,T> operator++ (int)
	{	raw_storage_iterator<OutputIterator,T> tmp = *this; ++iter; return tmp;}
};
#endif

} // namespace std

#endif
