//-------------------------------------
// utils::variant: Tagged union in C++
//-------------------------------------
//
//          Copyright kennytm (auraHT Ltd.) 2011.

// Boost Software License - Version 1.0 - August 17th, 2003

// Permission is hereby granted, free of charge, to any person or organization
// obtaining a copy of the software and accompanying documentation covered by
// this license (the "Software") to use, reproduce, display, distribute,
// execute, and transmit the Software, and to prepare derivative works of the
// Software, and to permit third-parties to whom the Software is furnished to
// do so, all subject to the following:

// The copyright notices in the Software and this entire statement, including
// the above license grant, this restriction and the following disclaimer,
// must be included in all copies of the Software, in whole or in part, and
// all derivative works of the Software, unless such copies or derivative
// works are solely in the form of machine-executable object code generated by
// a source language processor.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

/**

``<utils/variant.hpp>`` --- Tagged union
========================================

This module provides the :type:`utils::variant` type, which stores tagged union
of objects (also known as discriminated union or sum type).

This is mainly a rewrite of `boost::variant
<http://www.boost.org/doc/libs/1_48_0/doc/html/variant.html>`_ for C++11 support.

:type:`utils::variant` support the following features over ``boost::variant``:

* Proper move semantics
* Stricter, compile-time type checking
* Visitation using pattern-matching, in additional to the traditional
  class-based method.

but it also has some features not present in :type:`utils::variant`, and will
likely not be supported here:

* Recursive variant
* Reference members
* `Boost.MPL <http://www.boost.org/doc/libs/1_47_0/libs/mpl/doc/index.html>`_
* C++03, and support for compilers other than gcc ≥4.7 (and clang when its C++11
  support becomes better).

Synopsis
--------

::

    #include <cstdio>
    #include <vector>
    #include <utils/variant.hpp>

    int main()
    {
        std::vector<int> v {8, 9, 10, 12, 18, 24, 36, 48, 64, 72, 96};

        utils::variant<std::vector<int>, std::string> u = std::move(v);

        assert(v.is_type< std::vector<int> >());

        utills::case_of(u,
            [](const std::vector<int>& vec)
            {
                for (int val : vec)
                    printf("%d\n", val);
            },
            [](const std::string& str)
            {
                printf("[%s]\n", str.c_str());
            }
        );

        return 0;
    }

*/

#ifndef VARIANT_HPP_XMPYUK9CBNN
#define VARIANT_HPP_XMPYUK9CBNN

#include <utility>
#include <type_traits>
#include <iosfwd>
#if !defined(BOOST_NO_TYPEID)
#include <typeinfo>
#endif
#include "traits.hpp"

namespace utils {

    template <typename RT = void>
    class static_visitor
    {
    public:
        typedef RT result_type;
    };

    template <typename... T>
    class variant;

    template <typename T>
    struct is_variant { enum { value = false }; };
    template <typename... T>
    struct is_variant<variant<T...>> { enum { value = true }; };
}

#include "variant-impl.hpp"

namespace utils {

/**
Members
-------
*/

    /**
    .. type:: class utils::variant<T...> final
        :default_constructible:
        :movable:
        :copyable:

        The tagged union type.
    */
    template <typename... T>
    class variant
    {
        typedef xx_impl::union_impl<T...> union_type;

        size_t _index;
        union_type _storage;

        class init_to_visitor : public static_visitor<void>
        {
        public:
            variant<T...>* this_;

            template <typename U>
            void operator()(U&& other)
            {
                this_->init(std::forward<U>(other));
            }
        };

        template <typename U>
        void init(U&& other)
        {
            typedef xx_impl::get_index<U, xx_impl::is_constructible, T...> index_tmpl;
            static_assert(index_tmpl::found, "Constructing variant from unexpected type.");
            static_assert(!index_tmpl::ambiguous, "Constructing variant with ambiguous conversion.");
            static const size_t index_of_U = index_tmpl::index;
            _index = index_of_U;

            xx_impl::init_visitor_1<U> ctor (std::forward<U>(other));
            xx_impl::static_applier<index_of_U>()(_storage, ctor);
        }

    public:
        /**
        .. function:: variant()

            Construct a new variant type and initialize with the default value
            of the first type in *T*.
        */
        variant() : _index(0)
        {
            new(&_storage.head) decltype(_storage.head);
        }

        ~variant()
        {
            xx_impl::destroy_visitor dtor;
            apply(_storage, _index, dtor);
        }

        template <typename U>
        variant(U&& other)
        {
            this->init(std::forward<U>(other));
        }

        template <typename... TOther>
        variant(variant<TOther...>& other)
        {
            init_to_visitor ctor;
            ctor.this_ = this;
            apply(other._storage, other._index, ctor);
        }

        template <typename... TOther>
        variant(variant<TOther...>&& other)
        {
            init_to_visitor ctor;
            ctor.this_ = this;
            apply(std::move(other._storage), other._index, ctor);
        }

        variant(variant<T...>& other) : _index(other._index)
        {
            xx_impl::init_visitor_2 ctor;
            apply(_storage, other._storage, _index, ctor);
        }

        variant(const variant<T...>& other) : _index(other._index)
        {
            xx_impl::init_visitor_2 ctor;
            apply(_storage, other._storage, _index, ctor);
        }

        variant(variant<T...>&& other) : _index(other._index)
        {
            xx_impl::init_visitor_2 ctor;
            apply(_storage, std::move(other._storage), _index, ctor);
        }

    private:
        template <typename CA>
        void perform_safe_copy(bool nothrow_movable, CA copy_action)
        {
            xx_impl::destroy_visitor dtor;

            if (nothrow_movable)
            {
                apply(_storage, _index, dtor);
                copy_action();
            }
            else
            {
                struct backup_owner
                {
                    size_t index;
                    union_type* storage;

                    constexpr bool can_restore() const noexcept { return index < sizeof...(T); }

                    backup_owner() : index(sizeof...(T)), storage(new union_type) {}
                    ~backup_owner()
                    {
                        if (storage != nullptr)
                        {
                            if (this->can_restore())
                            {
                                xx_impl::destroy_visitor dtor;
                                apply(*storage, index, dtor);
                            }
                            delete storage;
                        }
                    }
                } backup;

                xx_impl::init_visitor_2 ctor2;
                xx_impl::is_nothrow_movable_checker nothrow_movable_checker;

                try
                {
                    if (xx_impl::apply(_storage, _index, nothrow_movable_checker))
                        xx_impl::apply(*backup.storage, std::move(_storage), _index, ctor2);
                    else
                        xx_impl::apply(*backup.storage, _storage, _index, ctor2);
                    backup.index = _index;

                    xx_impl::apply(_storage, _index, dtor);
                    copy_action();
                }
                catch (...)
                {
                    if (backup.can_restore())
                    {
                        if (xx_impl::apply(_storage, backup.index, nothrow_movable_checker))
                            xx_impl::apply(_storage, std::move(*backup.storage), backup.index, ctor2);
                        else
                            xx_impl::apply(_storage, *backup.storage, backup.index, ctor2);
                    }

                    throw;
                }
            }
        }

    public:
        template <typename U>
        variant<T...>& operator=(U&& other) noexcept(xx_impl::is_generic_nothrow_assignable<U>())
        {
            typedef xx_impl::get_index<U, xx_impl::is_assignable, T...> index_tmpl;
            static_assert(index_tmpl::found, "Assigning to variant from unexpected type.");
            static_assert(!index_tmpl::ambiguous, "Assigning to variant with ambiguous conversion.");
            static const size_t index_of_U = index_tmpl::index;

            if (_index == index_of_U)
            {
                xx_impl::assign_visitor_1<U> copier (std::forward<U>(other));
                xx_impl::static_applier<index_of_U>()(_storage, copier);
            }
            else
            {
                xx_impl::init_visitor_1<U> ctor (std::forward<U>(other));
                xx_impl::static_applier<index_of_U> static_applier;
                this->perform_safe_copy(xx_impl::is_generic_nothrow_assignable<U>(),
                    [&, this] { static_applier(_storage, ctor); }
                );
                _index = index_of_U;
            }
            return *this;
        }

        template <typename... TOther>
        typename std::enable_if<!xx_impl::get_index<variant<TOther...>,
                                                    xx_impl::is_same,
                                                    T...>::is_exact,
                                 variant<T...>>::type&
            operator=(variant<TOther...>& other)
        {
            xx_impl::is_same_visitor is_same;
            xx_impl::is_one_of_visitor<T...> has_same;

            auto same_type_pair = xx_impl::apply2(_storage, _index, other._storage, other._index, is_same);
            bool has_same_type = xx_impl::apply(other._storage, other._index, has_same);

            if (same_type_pair.first || (!has_same_type && same_type_pair.second))
            {
                xx_impl::assign_visitor_2 assigner;
                xx_impl::apply2(_storage, _index, other._storage, other._index, assigner);
            }
            else
            {
                xx_impl::assign_to_visitor<variant<T...>> assigner (*this);
                xx_impl::apply(other._storage, other._index, assigner);
            }
            return *this;
        }

        template <typename... TOther>
        variant<T...>& operator=(variant<TOther...>&& other)
        {
            xx_impl::is_same_visitor is_same;
            xx_impl::is_one_of_visitor<T...> has_same;

            auto same_type_pair = xx_impl::apply2(_storage, _index, other._storage, other._storage, is_same);
            bool has_same_type = xx_impl::apply(other._storage, other._index, has_same);

            if (same_type_pair.first || (!has_same_type && same_type_pair.second))
            {
                xx_impl::assign_visitor_2 assigner;
                xx_impl::apply2(_storage, _index, std::move(other._storage), other._index, assigner);
            }
            else
            {
                xx_impl::assign_to_visitor<variant<T...>> assigner (*this);
                xx_impl::apply(std::move(other._storage), other._index, assigner);
            }
            return *this;
        }

        variant<T...>& operator=(const variant<T...>& other)
        {
            if (_index == other._index)
            {
                xx_impl::assign_visitor_2 assigner;
                xx_impl::apply(_storage, other._storage, _index, assigner);
            }
            else
            {
                xx_impl::is_nothrow_copyable_checker cc;
                bool is_nothrow_copyable = xx_impl::apply(other._storage, other._index, cc);

                this->perform_safe_copy(is_nothrow_copyable,
                    [=, &other] {
                        xx_impl::init_visitor_2 ctor;
                        xx_impl::apply(_storage, other._storage, other._index, ctor);
                    }
                );
                _index = other._index;
            }
            return *this;
        }

        variant<T...>& operator=(variant<T...>& other)
        {
            const auto& other_const = other;
            return (*this = other_const);
        }

        variant<T...>& operator=(variant<T...>&& other)
        {
            if (_index == other._index)
            {
                xx_impl::assign_visitor_2 assigner;
                apply(_storage, std::move(other._storage), _index, assigner);
            }
            else
            {
                xx_impl::is_nothrow_movable_checker mc;
                bool is_nothrow_movable = xx_impl::apply(other._storage, other._index, mc);

                this->perform_safe_copy(is_nothrow_movable,
                    [=, &other] {
                        xx_impl::init_visitor_2 ctor;
                        xx_impl::apply(_storage, std::move(other._storage), other._index, ctor);
                    }
                );
                _index = other._index;
            }
            return *this;
        }

        void swap(variant& other)
        {
            if (_index == other._index)
            {
                xx_impl::swap_visitor_2 swapper;
                xx_impl::apply(_storage, other._storage, _index, swapper);
            }
            else
            {
                auto tmp = std::move(other);
                other = std::move(*this);
                *this = std::move(tmp);
            }
        }

        template <typename U>
        bool operator==(const U& other) const
        {
            typedef xx_impl::get_index<U, xx_impl::is_equatable, T...> index_tmpl;
            static_assert(index_tmpl::found, "Equating variant to unexpected type.");
            static_assert(!index_tmpl::ambiguous, "Equating variant with ambiguous conversion.");
            static const size_t index_of_U = index_tmpl::index;

            if (index_of_U != _index)
                return false;

            xx_impl::equals_visitor_1<U> eq (other);
            return xx_impl::static_applier<index_of_U>()(_storage, eq);
        }

        template <typename U>
        bool operator<(const U& other) const
        {
            typedef xx_impl::get_index<U, xx_impl::is_less_than_comparable, T...> index_tmpl;
            static_assert(index_tmpl::found, "Comparing variant with unexpected type.");
            static_assert(!index_tmpl::ambiguous, "Comparing variant with ambiguous conversion.");
            static const size_t index_of_U = index_tmpl::index;

            if (index_of_U != _index)
                return _index < index_of_U;

            xx_impl::less_than_visitor_1<U> lt (other);
            return xx_impl::static_applier<index_of_U>()(_storage, lt);
        }

        template <typename U>
        bool operator>(const U& other) const
        {
            typedef xx_impl::get_index<U, xx_impl::is_greater_than_comparable, T...> index_tmpl;
            static_assert(index_tmpl::found, "Comparing variant with unexpected type.");
            static_assert(!index_tmpl::ambiguous, "Comparing variant with ambiguous conversion.");
            static const size_t index_of_U = index_tmpl::index;

            if (index_of_U != _index)
                return _index > index_of_U;

            xx_impl::greater_than_visitor_1<U> gt (other);
            return xx_impl::static_applier<index_of_U>()(_storage, gt);
        }

        bool operator==(const variant<T...>& other) const
        {
            if (_index != other._index)
                return false;

            xx_impl::equals_visitor_2 eq;
            return xx_impl::apply(_storage, other._storage, _index, eq);
        }

        bool operator<(const variant<T...>& other) const
        {
            if (_index != other._index)
                return _index < other._index;

            xx_impl::less_than_visitor_2 lt;
            return xx_impl::apply(_storage, other._storage, _index, lt);
        }

        template <typename U>
        bool operator!=(const U& a) const { return !(*this == a); }
        template <typename U>
        bool operator>=(const U& a) const { return !(*this < a); }
        template <typename U>
        bool operator<=(const U& a) const { return !(*this > a); }

#if !defined(BOOST_NO_TYPEID)
        /**
        .. function:: const std::type_info& type() const noexcept

            Returns the typeid of the currently active member. This function
            will not be available if you define BOOST_NO_TYPEID before including
            this header.
        */
        const std::type_info& type() const noexcept
        {
            xx_impl::typeid_visitor tv;
            return xx_impl::apply(_storage, _index, tv);
        }
#endif

        /**
        .. function:: bool is_type<U>() const noexcept

            Check if the variant is currently containing the **exact type** *U*.
        */
        template <typename U>
        bool is_type() const noexcept
        {
            typedef xx_impl::get_index<U, xx_impl::is_same, T...> index_impl;
            static_assert(index_impl::is_exact, "Checking from unexpected type.");
            return index_impl::index == _index;
        }

        template <typename SV, typename V>
        friend typename SV::result_type apply_visitor(SV& visitor, V&& variant);

        template <typename SV, typename V1, typename V2>
        friend typename SV::result_type apply_visitor(SV& visitor, V1&& variant1, V2&& variant2);

        template <typename SV, typename V>
        friend typename SV::result_type apply_visitor(SV&& visitor, V&& variant);

        template <typename SV, typename V1, typename V2>
        friend typename SV::result_type apply_visitor(SV&& visitor, V1&& variant1, V2&& variant2);

        template <typename U, typename... TX>
        friend U* get(variant<TX...>* v) noexcept;

        template <typename U, typename... TX>
        friend const U* get(const variant<TX...>* v) noexcept;

        template <typename V, typename... F>
        friend typename xx_impl::common_result_type<F...>::type case_of(V&& variant, F&&... functions);

        template <typename...>
        friend class variant;
    };

    /**
    .. function:: VisitorType::result_type utils::apply_visitor<VisitorType, T...>(VisitorType visitor, const utils::variant<T...>& var)
                  VisitorType::result_type utils::apply_visitor<VisitorType, T...>(VisitorType visitor, utils::variant<T...>& var)

        Perform an operation on the variant. The *visitor* must be a function
        object that accepts every possible type of *T*, and has the same return
        type for all overloads, which must be reported as
        ``VisitorType::result_type``. You could use the
        :type:`~utils::static_visitor` to ensure this.
    */
    template <typename SV, typename V>
    typename SV::result_type apply_visitor(SV& visitor, V&& variant)
    {
        return xx_impl::apply(forward_like<V>(variant._storage), variant._index, visitor);
    }
    template <typename SV, typename V>
    typename SV::result_type apply_visitor(SV&& visitor, V&& variant)
    {
        return xx_impl::apply(forward_like<V>(variant._storage), variant._index, visitor);
    }

    /**
    .. function:: VisitorType::result_type utils::apply_visitor<VisitorType, T..., U...>(VisitorType visitor, const utils::variant<T...>& var1, const utils::variant<U...>& var2)
                  VisitorType::result_type utils::apply_visitor<VisitorType, T..., U...>(VisitorType visitor, utils::variant<T...>& var1, const utils::variant<U...>& var2)
                  VisitorType::result_type utils::apply_visitor<VisitorType, T..., U...>(VisitorType visitor, const utils::variant<T...>& var1, utils::variant<U...>& var2)
                  VisitorType::result_type utils::apply_visitor<VisitorType, T..., U...>(VisitorType visitor, utils::variant<T...>& var1, utils::variant<U...>& var2)

        Perform double visitation on a pair of variants.
    */
    template <typename SV, typename V1, typename V2>
    typename SV::result_type apply_visitor(SV& visitor, V1&& variant1, V2&& variant2)
    {
        return xx_impl::apply2(variant1._storage, variant1._index,
                               variant2._storage, variant2._index, visitor);
    }
    template <typename SV, typename V1, typename V2>
    typename SV::result_type apply_visitor(SV&& visitor, V1&& variant1, V2&& variant2)
    {
        return xx_impl::apply2(variant1._storage, variant1._index,
                               variant2._storage, variant2._index, visitor);
    }

    /**
    .. function:: auto utils::apply_visitor<VisitorType>(VisitorType visitor)

        Return a function object that will perform single or double visitation
        when called. In Boost this is known as *delayed visitation*.
    */
    template <typename SV>
    xx_impl::delayed_visitor<SV> apply_visitor(SV& visitor)
    {
        return xx_impl::delayed_visitor<SV>(visitor);
    }

    /**
    .. function:: auto utils::case_of<T..., F...>(const utils::variant<T...>& var, F&&... functions)
                  auto utils::case_of<T..., F...>(utils::variant<T...>& var, F&&... functions)

        Apply one of the functions which has compatible argument type to the
        variant, and return that result.
    */
    template <typename V, typename... F>
    typename xx_impl::common_result_type<F...>::type case_of(V&& variant, F&&... functions)
    {
        return xx_impl::apply_funcs_run(forward_like<V>(variant._storage),
                                        variant._index,
                                        std::forward<F>(functions)...);
    }

    /**
    .. function:: U* utils::get<U, T...>(utils::variant<T...>* var_ptr) noexcept
                  const U* utils::get<U, T...>(const utils::variant<T...>* var_ptr) noexcept

        Obtain a pointer to *U* if the variant's active member is really of type
        *U*. Return ``nullptr`` if not.
    */
    template <typename U, typename... T>
    U* get(variant<T...>* v) noexcept
    {
        typedef xx_impl::get_index<U, xx_impl::is_same, T...> index_impl;
        static_assert(index_impl::is_exact, "Getting from unexpected type.");
        if (index_impl::index == v->_index)
        {
            xx_impl::getter_visitor<U> getter;
            return xx_impl::static_applier<index_impl::index>()(v->_storage, getter);
        }
        else
            return nullptr;
    }

    template <typename U, typename... T>
    const U* get(const variant<T...>* v) noexcept
    {
        typedef xx_impl::get_index<U, xx_impl::is_same, T...> index_impl;
        static_assert(index_impl::is_exact, "Getting from unexpected type.");
        if (index_impl::index == v->_index)
        {
            xx_impl::getter_visitor<const U> getter;
            return xx_impl::static_applier<index_impl::index>()(v->_storage, getter);
        }
        else
            return nullptr;
    }

    /**
    .. type:: class utils::bad_get : public std::exception

        This exception is thrown when trying to :func:`~utils::get` a reference
        from a variant that does not have the required type.
    */
    class bad_get : public std::exception {
    public:
        virtual const char* what() const noexcept { return "bad_get"; }
    };

    /**
    .. function:: U& utils::get<U, T...>(utils::variant<T...>& var)
                  const U& utils::get<U, T...>(const utils::variant<T...>& var)

        Obtain a reference to *U* if the variant's active member is really of
        type *U*. Throws a :type:`~utils::bad_get` exception if not.
    */
    template <typename U, typename... T>
    U& get(variant<T...>& v)
    {
        auto res = get<U>(&v);
        if (res == nullptr)
            throw bad_get();
        return *res;
    }

    template <typename U, typename... T>
    const U& get(const variant<T...>& v)
    {
        auto res = get<U>(&v);
        if (res == nullptr)
            throw bad_get();
        return *res;
    }

    template <typename U, typename... T>
    bool operator==(const U& a, const variant<T...>& v) { return v == a; }
    template <typename U, typename... T>
    bool operator<(const U& a, const variant<T...>& v) { return v > a; }
    template <typename U, typename... T>
    bool operator>(const U& a, const variant<T...>& v) { return v < a; }
    template <typename U, typename... T>
    bool operator!=(const U& a, const variant<T...>& v) { return !(v == a); }
    template <typename U, typename... T>
    bool operator>=(const U& a, const variant<T...>& v) { return !(v > a); }
    template <typename U, typename... T>
    bool operator<=(const U& a, const variant<T...>& v) { return !(v < a); }

    template <typename... T>
    std::ostream& operator<<(std::ostream& stream, const variant<T...>& v)
    {
        xx_impl::ostream_visitor visitor (stream);
        return apply_visitor(visitor, v);
    }
}

namespace std
{
    template <typename... T>
    void swap(utils::variant<T...>& a, utils::variant<T...>& b)
    {
        a.swap(b);
    }
}

#endif