// dynarray -*- C++ -*-

// Copyright (C) 2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

#ifndef _DYNARRAY
#define _DYNARRAY

#if __cplusplus <= 201103L
# include <bits/c++14_warning.h>
#else

#include <algorithm>
#include <iterator>
#include <initializer_list>
#include <bits/unique_ptr.h>
#include <bits/functexcept.h>
#include <bits/uses_allocator.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  template <typename _Tp>
    class dynarray
    {
    public:
      // types:
      typedef _Tp value_type;
      typedef _Tp& reference;
      typedef const _Tp& const_reference;
      typedef _Tp* pointer;
      typedef const _Tp* const_pointer;
      typedef _Tp* iterator;
      typedef const _Tp* const_iterator;
      typedef std::reverse_iterator<iterator> reverse_iterator;
      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
      typedef size_t size_type;
      typedef ptrdiff_t difference_type;

      // 23.3.4.2 construct/copy/destroy:

      explicit
      dynarray(size_type __c) : _M_size(__c)
      {
	_M_allocate();
	for (size_type __i = 0; __i < __c; ++__i)
	  ::new (static_cast<void*>(_M_data + __i)) _Tp; // default-init
      }

      template <typename _Alloc>
        dynarray(allocator_arg_t, const _Alloc& __alloc, size_type __c)
	: _M_size(__c)
        { _M_init_val_a(__alloc); }

      dynarray(size_type __c, const _Tp& __v) : _M_size(__c)
      { _M_init_val(__v); }

      template <typename _Alloc>
        dynarray(allocator_arg_t, const _Alloc& __alloc, size_type __c,
		 const _Tp& __v)
        : _M_size(__c)
        { _M_init_val_a(__alloc, __v); }

      dynarray(const dynarray& __d) : _M_size(__d.size())
      { _M_init_range(__d.begin(), __d.end()); }

      template <typename _Alloc>
	dynarray(allocator_arg_t, const _Alloc& __alloc, const dynarray& __d)
	: _M_size(__d._M_size)
	{ _M_init_range_a(__alloc, __d.begin(), __d.end()); }

      dynarray(initializer_list<_Tp> __il) : _M_size(__il.size())
      { _M_init_range(__il.begin(), __il.end()); }

      template <typename _Alloc>
        dynarray(allocator_arg_t, const _Alloc& __alloc,
		 initializer_list<_Tp> __il)
        : _M_size(__il.size())
        { _M_init_range_a(__alloc, __il.begin(), __il.end()); }

      ~dynarray()
      {
	std::_Destroy(begin(), end());
	delete[] reinterpret_cast<char*>(_M_data);
      }

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

      // iterators:
      iterator begin() noexcept { return _M_data; }
      const_iterator begin() const noexcept { return _M_data; }
      const_iterator cbegin() const noexcept { return _M_data; }

      iterator end() noexcept { return _M_data + _M_size; }
      const_iterator end() const noexcept { return _M_data + _M_size; }
      const_iterator cend() const noexcept { return _M_data + _M_size; }

      reverse_iterator
      rbegin() noexcept { return reverse_iterator(end()); }

      const_reverse_iterator
      rbegin() const noexcept { return const_reverse_iterator(end()); }

      const_reverse_iterator
      crbegin() const noexcept { return const_reverse_iterator(end()); }

      reverse_iterator
      rend() noexcept { return reverse_iterator(begin()); }

      const_reverse_iterator
      rend() const noexcept { return const_reverse_iterator(begin()); }

      const_reverse_iterator
      crend() const noexcept { return const_reverse_iterator(begin()); }

      // capacity:
      size_type size() const noexcept { return _M_size; }
      size_type max_size() const noexcept { return _M_size; }
      bool empty() const noexcept { return _M_size == 0; }

      // element access:

      reference operator[](size_type __n) { return _M_data[__n]; }
      const_reference operator[](size_type __n) const { return _M_data[__n]; }

      reference front() { return _M_data[0]; }
      const_reference front() const { return _M_data[0]; }
      reference back() { return _M_data[_M_size-1]; }
      const_reference back() const { return _M_data[_M_size-1]; }

      reference
      at(size_type __n) { _M_check(__n); return _M_data[__n]; }

      const_reference
      at(size_type __n) const { _M_check(__n); return _M_data[__n]; }

      // 23.3.4.3 data access:
      _Tp* data() noexcept { return _M_data; }
      const _Tp* data() const noexcept { return _M_data; }

      // 23.3.4.4 mutating member functions:
      void fill(const _Tp& __v) { std::fill_n(begin(), size(), __v); }

    private:

      template<typename... _Arg>
	void
	_S_constr(__uses_alloc0 __a, void* __ptr, const _Arg&... __arg)
	{
	  ::new (__ptr) _Tp(__arg...);
	}

      template<typename _Alloc, typename... _Arg>
	void
	_S_constr(__uses_alloc1<_Alloc> __a, void* __ptr, const _Arg&... __arg)
	{
	  ::new (__ptr) _Tp(allocator_arg, *__a._M_a, __arg...);
	}

      template<typename _Alloc, typename... _Arg>
	void
	_S_constr(__uses_alloc2<_Alloc> __a, void* __ptr, const _Arg&... __arg)
	{
	  ::new (__ptr) _Tp(__arg..., *__a._M_a);
	}

      template<typename _Alloc, typename... _Arg>
	void
	_S_construct(const _Alloc& __a, _Tp* __ptr, const _Arg&... __arg)
	{
	  _S_constr(__use_alloc<_Tp, _Alloc, const _Arg&...>(__a), __ptr,
		    __arg...);
        }

      void
      _M_check(size_type __n) const
      {
	if (__n >= _M_size)
	  __throw_out_of_range("dynarray::at");
      }

      void
      _M_allocate()
      {
	_M_data = reinterpret_cast<_Tp*>(new char[_M_size * sizeof(_Tp)]);
      }

      template<typename _Iter>
	void
	_M_init_range(_Iter __first, _Iter __last)
	{
	  _M_allocate();
	  std::uninitialized_copy(__first, __last, _M_data);
	}

      template<typename _Alloc, typename _Iter>
	void
	_M_init_range_a(const _Alloc& __a, _Iter __first, _Iter __last)
	{
	  _M_allocate();
	  auto __data = _M_data;
	  while (__first != __last)
	    _S_construct(__a, __data++, *__first++);
	}

      template<typename _Up>
        void
	_M_init_val(const _Up& __val)
	{
	  _M_allocate();
	  std::uninitialized_fill_n(_M_data, _M_size, __val);
	}

      template<typename _Alloc, typename... _Up>
        void
	_M_init_val_a(const _Alloc& __a, const _Up&... __val)
	{
	  _M_allocate();
	  for (size_type __i = 0; __i < _M_size; ++__i)
	    _S_construct(__a, _M_data + __i, __val...);
	}

      const size_t _M_size;
      _Tp*	   _M_data;
    };

  template <typename _Tp, typename _Alloc>
    struct uses_allocator<dynarray<_Tp>, _Alloc> : true_type { };

  template <typename _Tp>
    inline bool
    operator==(const dynarray<_Tp>& __x, const dynarray<_Tp>& __y)
    { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); }

  template <typename _Tp>
    inline bool
    operator<(const dynarray<_Tp>& __x, const dynarray<_Tp>& __y)
    {
      return std::lexicographical_compare(__x.begin(), __x.end(),
					  __y.begin(), __y.end());
    }

  template <typename _Tp>
    inline bool
    operator!=(const dynarray<_Tp>& __x, const dynarray<_Tp>& __y)
    { return !(__x == __y); }

  template <typename _Tp>
    inline bool
    operator>(const dynarray<_Tp>& __x, const dynarray<_Tp>& __y)
    { return __y < __x; }

  template <typename _Tp>
    inline bool
    operator>=(const dynarray<_Tp>& __x, const dynarray<_Tp>& __y)
    { return !(__x < __y); }

  template <typename _Tp>
    inline bool
    operator<=(const dynarray<_Tp>& __x, const dynarray<_Tp>& __y)
    { return !(__x > __y); }

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std

#endif
#endif