// <optional> -*- C++ -*-

// Copyright (C) 2013-2018 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/>.

/** @file include/optional
 *  This is a Standard C++ Library header.
 */

#ifndef _GLIBCXX_OPTIONAL
#define _GLIBCXX_OPTIONAL 1

#pragma GCC system_header

#if __cplusplus >= 201703L

#include <utility>
#include <type_traits>
#include <stdexcept>
#include <new>
#include <initializer_list>
#include <bits/functexcept.h>
#include <bits/functional_hash.h>
#include <bits/enable_special_members.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**
   *  @addtogroup utilities
   *  @{
   */

#define __cpp_lib_optional 201603

  template<typename _Tp>
    class optional;

  /// Tag type to disengage optional objects.
  struct nullopt_t
  {
    // Do not user-declare default constructor at all for
    // optional_value = {} syntax to work.
    // nullopt_t() = delete;

    // Used for constructing nullopt.
    enum class _Construct { _Token };

    // Must be constexpr for nullopt_t to be literal.
    explicit constexpr nullopt_t(_Construct) { }
  };

  /// Tag to disengage optional objects.
  inline constexpr nullopt_t nullopt { nullopt_t::_Construct::_Token };

  /**
   *  @brief Exception class thrown when a disengaged optional object is
   *  dereferenced.
   *  @ingroup exceptions
   */
  class bad_optional_access : public exception
  {
  public:
    bad_optional_access() { }

    virtual const char* what() const noexcept override
    { return "bad optional access"; }

    virtual ~bad_optional_access() noexcept = default;
  };

  void
  __throw_bad_optional_access()
  __attribute__((__noreturn__));

  // XXX Does not belong here.
  inline void
  __throw_bad_optional_access()
  { _GLIBCXX_THROW_OR_ABORT(bad_optional_access()); }


  // Payload for optionals with non-trivial destructor.
  template <typename _Tp,
	    bool /*_HasTrivialDestructor*/ =
	      is_trivially_destructible_v<_Tp>,
	    bool /*_HasTrivialCopy */ =
	      is_trivially_copy_assignable_v<_Tp>
	      && is_trivially_copy_constructible_v<_Tp>,
	    bool /*_HasTrivialMove */ =
	      is_trivially_move_assignable_v<_Tp>
	      && is_trivially_move_constructible_v<_Tp>>
    struct _Optional_payload
    {
      constexpr _Optional_payload() noexcept : _M_empty() { }

      template <typename... _Args>
	constexpr
	_Optional_payload(in_place_t, _Args&&... __args)
	: _M_payload(std::forward<_Args>(__args)...), _M_engaged(true) { }

      template<typename _Up, typename... _Args>
	constexpr
	_Optional_payload(std::initializer_list<_Up> __il,
			  _Args&&... __args)
	: _M_payload(__il, std::forward<_Args>(__args)...),
	  _M_engaged(true)
	{ }

      constexpr
      _Optional_payload(bool __engaged, const _Optional_payload& __other)
      : _Optional_payload(__other)
      { }

      constexpr
      _Optional_payload(bool __engaged, _Optional_payload&& __other)
      : _Optional_payload(std::move(__other))
      { }

      constexpr
      _Optional_payload(const _Optional_payload& __other)
      {
	if (__other._M_engaged)
	  this->_M_construct(__other._M_payload);
      }

      constexpr
      _Optional_payload(_Optional_payload&& __other)
      {
	if (__other._M_engaged)
	  this->_M_construct(std::move(__other._M_payload));
      }

      constexpr
      _Optional_payload&
      operator=(const _Optional_payload& __other)
      {
        if (this->_M_engaged && __other._M_engaged)
          this->_M_get() = __other._M_get();
        else
	  {
	    if (__other._M_engaged)
	      this->_M_construct(__other._M_get());
	    else
	      this->_M_reset();
	  }
	return *this;
      }

      constexpr
      _Optional_payload&
      operator=(_Optional_payload&& __other)
      noexcept(__and_<is_nothrow_move_constructible<_Tp>,
		      is_nothrow_move_assignable<_Tp>>())
      {
	if (this->_M_engaged && __other._M_engaged)
	  this->_M_get() = std::move(__other._M_get());
	else
	  {
	    if (__other._M_engaged)
	      this->_M_construct(std::move(__other._M_get()));
	    else
	      this->_M_reset();
	  }
	return *this;
      }

      using _Stored_type = remove_const_t<_Tp>;

      struct _Empty_byte { };

      union {
          _Empty_byte _M_empty;
          _Stored_type _M_payload;
      };
      bool _M_engaged = false;

      ~_Optional_payload()
      {
        if (_M_engaged)
          _M_payload.~_Stored_type();
      }

      template<typename... _Args>
        void
        _M_construct(_Args&&... __args)
        noexcept(is_nothrow_constructible<_Stored_type, _Args...>())
        {
          ::new ((void *) std::__addressof(this->_M_payload))
            _Stored_type(std::forward<_Args>(__args)...);
          this->_M_engaged = true;
        }

      // The _M_get operations have _M_engaged as a precondition.
      constexpr _Tp&
      _M_get() noexcept
      { return this->_M_payload; }

      constexpr const _Tp&
      _M_get() const noexcept
      { return this->_M_payload; }

      // _M_reset is a 'safe' operation with no precondition.
      constexpr
      void
      _M_reset() noexcept
      {
	if (this->_M_engaged)
	  {
	    this->_M_engaged = false;
	    this->_M_payload.~_Stored_type();
	  }
      }
    };

  // Payload for potentially-constexpr optionals.
  template <typename _Tp>
    struct _Optional_payload<_Tp, true, true, true>
    {
      constexpr _Optional_payload() noexcept
      : _M_empty(), _M_engaged(false) { }

      template<typename... _Args>
	constexpr
	_Optional_payload(in_place_t, _Args&&... __args)
	: _M_payload(std::forward<_Args>(__args)...), _M_engaged(true)
	{ }

      template<typename _Up, typename... _Args>
	constexpr
	_Optional_payload(std::initializer_list<_Up> __il,
			  _Args&&... __args)
	: _M_payload(__il, std::forward<_Args>(__args)...),
	  _M_engaged(true)
	{ }

      constexpr
      _Optional_payload(bool __engaged, const _Optional_payload& __other)
      : _M_engaged(__engaged)
      {
	if (__engaged)
	  _M_construct(__other._M_get());
      }

      constexpr
      _Optional_payload(bool __engaged, _Optional_payload&& __other)
      : _M_engaged(__engaged)
      {
	if (__engaged)
	  _M_construct(std::move(__other._M_get()));
      }

      using _Stored_type = remove_const_t<_Tp>;

      struct _Empty_byte { };

      union {
	  _Empty_byte _M_empty;
          _Stored_type _M_payload;
      };
      bool _M_engaged;

      // The _M_get operations have _M_engaged as a precondition.
      constexpr _Tp&
      _M_get() noexcept
      { return this->_M_payload; }

      constexpr const _Tp&
      _M_get() const noexcept
      { return this->_M_payload; }
    };

  // Payload for optionals with non-trivial copy assignment.
  template <typename _Tp>
    struct _Optional_payload<_Tp, true, false, true>
    {
      constexpr _Optional_payload() noexcept
      : _M_empty(), _M_engaged(false) { }

      template<typename... _Args>
	constexpr
	_Optional_payload(in_place_t, _Args&&... __args)
	: _M_payload(std::forward<_Args>(__args)...), _M_engaged(true)
	{ }

      template<typename _Up, typename... _Args>
	constexpr
	_Optional_payload(std::initializer_list<_Up> __il,
			  _Args&&... __args)
	: _M_payload(__il, std::forward<_Args>(__args)...),
	  _M_engaged(true)
	{ }

      constexpr
      _Optional_payload(bool __engaged, const _Optional_payload& __other)
      : _M_engaged(__engaged)
      {
	if (__engaged)
	  _M_construct(__other._M_get());
      }

      constexpr
      _Optional_payload(bool __engaged, _Optional_payload&& __other)
      : _M_engaged(__engaged)
      {
	if (__engaged)
	  _M_construct(std::move(__other._M_get()));
      }

      _Optional_payload(const _Optional_payload&) = default;
      _Optional_payload(_Optional_payload&&) = default;

      constexpr
      _Optional_payload&
      operator=(const _Optional_payload& __other)
      {
        if (this->_M_engaged && __other._M_engaged)
          this->_M_get() = __other._M_get();
        else
	  {
	    if (__other._M_engaged)
	      this->_M_construct(__other._M_get());
	    else
	      this->_M_reset();
	  }
	return *this;
      }

      _Optional_payload&
      operator=(_Optional_payload&& __other) = default;

      using _Stored_type = remove_const_t<_Tp>;

      struct _Empty_byte { };

      union {
          _Empty_byte _M_empty;
          _Stored_type _M_payload;
      };
      bool _M_engaged;

      template<typename... _Args>
        void
        _M_construct(_Args&&... __args)
        noexcept(is_nothrow_constructible<_Stored_type, _Args...>())
        {
          ::new ((void *) std::__addressof(this->_M_payload))
            _Stored_type(std::forward<_Args>(__args)...);
          this->_M_engaged = true;
        }

      // The _M_get operations have _M_engaged as a precondition.
      constexpr _Tp&
      _M_get() noexcept
      { return this->_M_payload; }

      constexpr const _Tp&
      _M_get() const noexcept
      { return this->_M_payload; }

      // _M_reset is a 'safe' operation with no precondition.
      constexpr
      void
      _M_reset() noexcept
      {
	if (this->_M_engaged)
	  {
	    this->_M_engaged = false;
	    this->_M_payload.~_Stored_type();
	  }
      }
    };

  // Payload for optionals with non-trivial move assignment.
  template <typename _Tp>
    struct _Optional_payload<_Tp, true, true, false>
    {
      constexpr _Optional_payload() noexcept
      : _M_empty(), _M_engaged(false) { }

      template<typename... _Args>
	constexpr
	_Optional_payload(in_place_t, _Args&&... __args)
	: _M_payload(std::forward<_Args>(__args)...),
	  _M_engaged(true)
	{ }

      template<typename _Up, typename... _Args>
	constexpr
	_Optional_payload(std::initializer_list<_Up> __il,
			  _Args&&... __args)
	: _M_payload(__il, std::forward<_Args>(__args)...),
	  _M_engaged(true)
	{ }

      constexpr
      _Optional_payload(bool __engaged, const _Optional_payload& __other)
      : _M_engaged(__engaged)
      {
	if (__engaged)
	  _M_construct(__other._M_get());
      }

      constexpr
      _Optional_payload(bool __engaged, _Optional_payload&& __other)
      : _M_engaged(__engaged)
      {
	if (__engaged)
	  _M_construct(std::move(__other._M_get()));
      }

      _Optional_payload(const _Optional_payload&) = default;
      _Optional_payload(_Optional_payload&&) = default;

      _Optional_payload&
      operator=(const _Optional_payload& __other) = default;

      constexpr
      _Optional_payload&
      operator=(_Optional_payload&& __other)
      noexcept(__and_<is_nothrow_move_constructible<_Tp>,
		      is_nothrow_move_assignable<_Tp>>())
      {
	if (this->_M_engaged && __other._M_engaged)
	  this->_M_get() = std::move(__other._M_get());
	else
	  {
	    if (__other._M_engaged)
	      this->_M_construct(std::move(__other._M_get()));
	    else
	      this->_M_reset();
	  }
	return *this;
      }

      using _Stored_type = remove_const_t<_Tp>;

      struct _Empty_byte { };

      union {
          _Empty_byte _M_empty;
          _Stored_type _M_payload;
      };
      bool _M_engaged;

      template<typename... _Args>
        void
        _M_construct(_Args&&... __args)
        noexcept(is_nothrow_constructible<_Stored_type, _Args...>())
        {
          ::new ((void *) std::__addressof(this->_M_payload))
            _Stored_type(std::forward<_Args>(__args)...);
          this->_M_engaged = true;
        }

      // The _M_get operations have _M_engaged as a precondition.
      constexpr _Tp&
      _M_get() noexcept
      { return this->_M_payload; }

      constexpr const _Tp&
      _M_get() const noexcept
      { return this->_M_payload; }

      // _M_reset is a 'safe' operation with no precondition.
      constexpr
      void
      _M_reset() noexcept
      {
	if (this->_M_engaged)
	  {
	    this->_M_engaged = false;
	    this->_M_payload.~_Stored_type();
	  }
      }
    };

  // Payload for optionals with non-trivial copy and move assignment.
  template <typename _Tp>
    struct _Optional_payload<_Tp, true, false, false>
    {
      constexpr _Optional_payload() noexcept
      : _M_empty(), _M_engaged(false) {}

      template<typename... _Args>
	constexpr
	_Optional_payload(in_place_t, _Args&&... __args)
	: _M_payload(std::forward<_Args>(__args)...),
	  _M_engaged(true)
	{ }

      template<typename _Up, typename... _Args>
	constexpr
	_Optional_payload(std::initializer_list<_Up> __il,
			  _Args&&... __args)
	: _M_payload(__il, std::forward<_Args>(__args)...),
	  _M_engaged(true)
	{ }

      constexpr
      _Optional_payload(bool __engaged, const _Optional_payload& __other)
      : _M_engaged(__engaged)
      {
	if (__engaged)
	  _M_construct(__other._M_get());
      }

      constexpr
      _Optional_payload(bool __engaged, _Optional_payload&& __other)
      : _M_engaged(__engaged)
      {
	if (__engaged)
	  _M_construct(std::move(__other._M_get()));
      }

      _Optional_payload(const _Optional_payload&) = default;
      _Optional_payload(_Optional_payload&&) = default;

      constexpr
      _Optional_payload&
      operator=(const _Optional_payload& __other)
      {
        if (this->_M_engaged && __other._M_engaged)
          this->_M_get() = __other._M_get();
        else
	  {
	    if (__other._M_engaged)
	      this->_M_construct(__other._M_get());
	    else
	      this->_M_reset();
	  }
	return *this;
      }

      constexpr
      _Optional_payload&
      operator=(_Optional_payload&& __other)
      noexcept(__and_<is_nothrow_move_constructible<_Tp>,
		      is_nothrow_move_assignable<_Tp>>())
      {
	if (this->_M_engaged && __other._M_engaged)
	  this->_M_get() = std::move(__other._M_get());
	else
	  {
	    if (__other._M_engaged)
	      this->_M_construct(std::move(__other._M_get()));
	    else
	      this->_M_reset();
	  }
	return *this;
      }

      using _Stored_type = remove_const_t<_Tp>;

      struct _Empty_byte { };

      union {
          _Empty_byte _M_empty;
          _Stored_type _M_payload;
      };
      bool _M_engaged;

      template<typename... _Args>
        void
        _M_construct(_Args&&... __args)
        noexcept(is_nothrow_constructible<_Stored_type, _Args...>())
        {
          ::new ((void *) std::__addressof(this->_M_payload))
            _Stored_type(std::forward<_Args>(__args)...);
          this->_M_engaged = true;
        }

      // The _M_get operations have _M_engaged as a precondition.
      constexpr _Tp&
      _M_get() noexcept
      { return this->_M_payload; }

      constexpr const _Tp&
      _M_get() const noexcept
      { return this->_M_payload; }

      // _M_reset is a 'safe' operation with no precondition.
      constexpr
      void
      _M_reset() noexcept
      {
	if (this->_M_engaged)
	  {
	    this->_M_engaged = false;
	    this->_M_payload.~_Stored_type();
	  }
      }
    };

  template<typename _Tp, typename _Dp>
    class _Optional_base_impl
    {
    protected:
      using _Stored_type = remove_const_t<_Tp>;
      
      // The _M_construct operation has !_M_engaged as a precondition
      // while _M_destruct has _M_engaged as a precondition.
      template<typename... _Args>
	void
	_M_construct(_Args&&... __args)
	noexcept(is_nothrow_constructible<_Stored_type, _Args...>())
	{
	  ::new
	    (std::__addressof(static_cast<_Dp*>(this)->_M_payload._M_payload))
	    _Stored_type(std::forward<_Args>(__args)...);
	  static_cast<_Dp*>(this)->_M_payload._M_engaged = true;
	}
      
      void
      _M_destruct() noexcept
      {
	static_cast<_Dp*>(this)->_M_payload._M_engaged = false;
	static_cast<_Dp*>(this)->_M_payload._M_payload.~_Stored_type();
      }
      
      // _M_reset is a 'safe' operation with no precondition.
      constexpr
      void
      _M_reset() noexcept
      {
	if (static_cast<_Dp*>(this)->_M_payload._M_engaged)
	  static_cast<_Dp*>(this)->_M_destruct();
      }
  };

  /**
    * @brief Class template that takes care of copy/move constructors
    of optional
    *
    * Such a separate ba                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                