#include <cassert>
#include <iostream>

#include <string>
#include <stdexcept>
using namespace std::literals;

//#define NYI throw std::runtime_error("line "s + std::to_string(__LINE__) + ": Not yet implemented"s)

//
//
//

/*
    A type that can store one of two values: one representing success
    (Ok state) and one representing failure (Err state).

    When default constructed, Result is in Ok state.

    Type is Regular if T and E are Regular.

    Type is Swappable if T and E are Swappable.

    Do not use Result value that was moved from. Assign a value to it
    first (or emplace), then use it. This is standard practice, but
    compiler can't enforce it.

    C++14 compatible.

    TODO: valueless by exception?
*/

#include <type_traits>
#include <new>
#include <initializer_list>

struct in_place_ok_t {};
constexpr in_place_ok_t const in_place_ok;

struct in_place_err_t {};
constexpr in_place_err_t const in_place_err;

template<class T, class E>
class Result {

  enum class Type { Ok, Err, None };

  using Storage = std::aligned_union_t<1, T, E>;

public: // ctor, dtor, assign

  Result()
    : m_type{Type::Ok}
  {
    new (ptr_ok()) T{};
  }

  Result(Result const& other)
    : m_type{other.m_type}
  {
    if(other.is_ok()) {
      new (ptr_ok()) T{*other.ptr_ok()};
    }
    if(other.is_err()) {
      new (ptr_err()) E{*other.ptr_err()};
    }
  }

  Result(Result&& other)
    : m_type{other.m_type}
  {
    if(other.is_ok()) {
      new (ptr_ok()) T{std::move(*other.ptr_ok())};
    }
    if(other.is_err()) {
      new (ptr_err()) E{std::move(*other.ptr_err())};
    }
    other.m_type = Type::None;
  }

  template<class ... Args>
  Result(in_place_ok_t, Args&& ... args)
    : m_type{Type::Ok}
  {
    new (ptr_ok()) T{std::forward<Args>(args)...};
  }

  template<class U, class ... Args>
  Result(in_place_ok_t, std::initializer_list<U> ls, Args&& ... args)
    : m_type{Type::Ok}
  {
    new (ptr_ok()) T{ls, std::forward<Args>(args)...};
  }

  template<class ... Args>
  Result(in_place_err_t, Args&& ... args)
    : m_type{Type::Err}
  {
    new (ptr_err()) E{std::forward<Args>(args)...};
  }

  template<class U, class ... Args>
  Result(in_place_err_t, std::initializer_list<U> ls, Args&& ... args)
    : m_type{Type::Err}
  {
    new (ptr_err()) E{ls, std::forward<Args>(args)...};
  }

  ~Result() {
    deinit();
  }

  Result& operator= (Result const& other) {
    if(this != &other) {
      deinit();
      if(other.is_ok()) {
        new (ptr_ok()) T{*other.ptr_ok()};
      }
      if(other.is_err()) {
        new (ptr_err()) E{*other.ptr_err()};
      }
      m_type = other.m_type;
      other.deinit();
    }
    return *this;
  }

  Result& operator= (Result&& other) {
    if(this != &other) {
      deinit();
      if(other.is_ok()) {
        new (ptr_ok()) T{std::move(*other.ptr_ok())};
      }
      if(other.is_err()) {
        new (ptr_err()) E{std::move(*other.ptr_err())};
      }
      m_type = other.m_type;
      other.deinit();
    }
    return *this;
  }

public: // equality comparable

  friend auto operator== (Result const& a, Result const& b) -> bool {
    bool result = false;
    if(a.m_type == b.m_type) {
      if(a.is_ok()) {
        result = *a.ptr_ok() == *b.ptr_ok();
      }
      if(a.is_err()) {
        result = *a.ptr_err() == *b.ptr_err();
      }
      // two Nones are not equal!
    }
    return result;
  }

  friend auto operator!= (Result const& a, Result const& b) -> bool {
    return !(a == b);
  }

public: // observers

  auto is_ok() const -> bool {
    return Type::Ok == m_type;
  }

  auto is_err() const -> bool {
    return Type::Err == m_type;
  }

  auto ok() & -> T& {
    assert(is_ok());
    return *ptr_ok();
  }

  auto ok() const & -> T const& {
    assert(is_ok());
    return *ptr_ok();
  }

  auto ok() && -> T&& {
    assert(is_ok());
    return std::move(*ptr_ok());
  }

  auto ok() const && -> T const&& {
    assert(is_ok());
    return std::move(*ptr_ok());
  }

  auto err() & -> E& {
    assert(is_err());
    return *ptr_err();
  }

  auto err() const & -> E const& {
    assert(is_err());
    return *ptr_err();
  }

  auto err() && -> E&& {
    assert(is_err());
    return std::move(*ptr_err());
  }

  auto err() const && -> E const&& {
    assert(is_err());
    return std::move(*ptr_err());
  }

public: //

  auto unwrap() & -> T {
    assert(is_ok());
    return *ptr_ok();
  }

  auto unwrap() const& -> T {
    assert(is_ok());
    return *ptr_ok();
  }

  auto unwrap() && -> T&& {
    assert(is_ok());
    return std::move(*ptr_ok());
  }

  auto unwrap() const&& -> T const&& {
    assert(is_ok());
    return std::move(*ptr_ok());
  }

public: // swap

  auto swap(Result& other) {
    Result<T,E> temp(std::move(other));
    other = std::move(*this);
    *this = std::move(temp);
  }

public: // modifiers

  template<class ... Args>
  auto emplace_ok(Args&& ... args) -> T&  {
    deinit();
    m_type = Type::Ok;
    new (ptr_ok()) T{std::forward<Args>(args)...};
    return *ptr_ok();
  }

  template<class U, class ... Args>
  auto emplace_ok(std::initializer_list<U> ls, Args&& ... args) -> T& {
    deinit();
    m_type = Type::Ok;
    new (ptr_ok()) T{ls, std::forward<Args>(args)...};
    return *ptr_ok();
  }

  template<class ... Args>
  auto emplace_err(Args&& ... args) -> E& {
    deinit();
    m_type = Type::Err;
    new (ptr_err()) E{std::forward<Args>(args)...};
    return *ptr_err();
  }

  template<class U, class ... Args>
  auto emplace_err(std::initializer_list<U> ls, Args&& ... args) -> E& {
    deinit();
    m_type = Type::Err;
    new (ptr_err()) E{ls, std::forward<Args>(args)...};
    return *ptr_err();
  }

private: // helpers

  auto ptr_ok() -> T* {
    return reinterpret_cast<T*>(&m_storage);
  }

  auto ptr_ok() const -> T const* {
    return reinterpret_cast<T const*>(&m_storage);
  }

  auto ptr_err() -> E* {
    return reinterpret_cast<E*>(&m_storage);
  }

  auto ptr_err() const -> E const* {
    return reinterpret_cast<E const*>(&m_storage);
  }

  auto deinit() -> void {
    if(is_ok()) {
      ptr_ok()->~T();
    }
    if(is_err()) {
      ptr_err()->~E();
    }
    m_type = Type::None;
  }

private: // fields

  Type     m_type;
  Storage  m_storage;

};

template<class T, class E>
auto swap(Result<T, E>& a, Result<T, E>& b) -> void {
  a.swap(b);
}

//
//
//
#include <vector>
#include <string>

struct Test {
  Test()
    : default_constructed{true}
  {}

  Test(Test const&)
    : copy_constructed{true}
  {}

  Test(Test&&)
    : move_constructed{true}
  {}

  ~Test() {}

  Test& operator= (Test const&) {
    copy_assigned = true;
    return *this;
  }

  Test& operator= (Test&&) {
    move_assigned = true;
    return *this;
  }

  //
  bool default_constructed{false};
  bool copy_constructed{false};
  bool move_constructed{false};
  bool copy_assigned{false};
  bool move_assigned{false};
};


auto main() -> int {

  //
  {
    Result<int, std::string> res;

    assert(res.is_ok());
    assert(!res.is_err());
  }

  //
  {
    std::vector<int> const expected = {1, 2, 3, 4, 5};
    Result<std::vector<int>, std::string> res{in_place_ok, {1, 2, 3, 4, 5}};

    assert(res.ok() == expected);
  }

  //
  {
    Result<std::vector<int>, std::string> res{in_place_err, "error"};

    assert(res.err() == "error");
  }

  {
    std::vector<int> const expected = {1, 2, 3, 4, 5};
    Result<std::vector<int>, std::string> res{in_place_ok, {1, 2, 3, 4, 5}};

    assert(std::move(res).ok() == expected);
  }

  //
  {
    Result<std::vector<int>, std::string> res{in_place_err, "error"};

    assert(std::move(res).err() == "error");
  }

  //
  {
    Result<int, int> a{in_place_ok, 42}, b{in_place_ok, 42}, c{in_place_ok, 53};

    assert(a == b);
    assert(a != c);
  }

  //
  {
    Result<int, int> res;

    assert(res.is_ok());

    res.emplace_ok(42);

    assert(res.is_ok() && res.ok() == 42);

    res.emplace_err(15);

    assert(res.is_err() && res.err() == 15);
  }

  //
  {
    Result<int, int> a{in_place_ok, 42}, b{in_place_err, 15};

    swap(a, b);

    assert(a.is_err() && a.err() == 15);
    assert(b.is_ok() && b.ok() == 42);
  }

  //
  {
    Result<Test, int> res{};

    assert(res.ok().default_constructed);

    res.emplace_ok();

    assert(res.ok().default_constructed);

    auto t1 = std::move(res).ok();

    assert(t1.move_constructed);

    res.emplace_ok();

    auto t2 = res.ok();

    assert(t2.copy_constructed);
  }

  //
  {
    Result<int, std::string> res{in_place_ok, 42};

    assert(res.unwrap() == 42);
  }

}

#if 0 // old version using variant
#include <cassert>
#include <iostream>

//
//
//
#include <variant>
#include <initializer_list>

struct in_place_t {};
constexpr in_place_t const in_place;

template<class T>
struct Ok {
    Ok() = default;
    Ok(Ok const&) = default;
    Ok(Ok&&) = default;
    ~Ok() = default;
    Ok& operator= (Ok const&) = default;
    Ok& operator= (Ok&&) = default;

    Ok(T value_)
        : value{std::move(value_)}
    {}

    template<class ... Args>
    Ok(in_place_t, Args&& ... args)
        : value{std::forward<Args>(args)...}
    {}

    template<class U, class ... Args>
    Ok(in_place_t, std::initializer_list<U> ls, Args&& ... args)
        : value{ls, std::forward<Args>(args)...}
    {}

    T value;
};

template<class T>
auto operator== (Ok<T> const& a, Ok<T> const& b) -> bool {
    return a.value == b.value;
}

template<class T>
auto operator!= (Ok<T> const& a, Ok<T> const& b) -> bool {
    return a.value != b.value;
}

template<class E>
struct Err {
    Err() = default;
    Err(Err const&) = default;
    Err(Err&&) = default;
    ~Err() = default;
    Err& operator= (Err const&) = default;
    Err& operator= (Err&&) = default;

    Err(E e)
        : reason{std::move(e)}
    {}

    template<class ... Args>
    Err(in_place_t, Args&& ... args)
        : reason{std::forward<Args>(args)...}
    {}

    template<class U, class ... Args>
    Err(in_place_t, std::initializer_list<U> ls, Args&& ... args)
        : reason{ls, std::forward<Args>(args)...}
    {}


    E reason;
};

template<class E>
auto operator== (Err<E> const& a, Err<E> const& b) -> bool {
    return a.reason == b.reason;
}

template<class E>
auto operator!= (Err<E> const& a, Err<E> const& b) -> bool {
    return a.reason != b.reason;
}

struct in_place_ok_t {};
constexpr in_place_ok_t const in_place_ok;

struct in_place_err_t {};
constexpr in_place_err_t const in_place_err;

template<class T, class E>
class Result {

    using Ok_  = Ok<T>;
    using Err_ = Err<E>;
    using Variant = std::variant< Ok_, Err_ >;

public: // ctor, dtor, assign

    Result() = default;

    Result(Result const& ) = default;

    Result(Result&& ) = default;

    template<class ... Args>
    Result(in_place_ok_t, Args&& ... args)
        : m_variant{ Ok_{ std::forward<Args>(args)... } }
    {}

    template<class U, class ... Args>
    Result(in_place_ok_t, std::initializer_list<U> ls, Args&& ... args)
        : m_variant{ Ok_{ ls, std::forward<Args>(args)... } }
    {}

    template<class ... Args>
    Result(in_place_err_t, Args&& ... args)
        : m_variant{ Err_{ E{ std::forward<Args>(args)... } } }
    {}

    template<class U, class ... Args>
    Result(in_place_err_t, std::initializer_list<U> ls, Args&& ... args)
        : m_variant{ Err_{ E{ ls, std::forward<Args>(args)... } } }
    {}

    ~Result() = default;

    Result& operator= (Result const& other) = default;

    Result& operator= (Result&& other) = default;

public: // equality comparable

    friend auto operator== (Result const& a, Result const& b) -> bool {
        return a.m_variant == b.m_variant;
    }

    friend auto operator!= (Result const& a, Result const& b) -> bool {
        return a.m_variant != b.m_variant;
    }

public: // observers

    auto is_ok() const -> bool {
        return std::holds_alternative< Ok_ >(m_variant);
    }

    auto is_err() const -> bool {
        return std::holds_alternative< Err_ >(m_variant);
    }

    auto ok() & -> T& {
        assert(is_ok());
        return std::get< Ok_ >(m_variant).value;
    }

    auto ok() const & -> T const& {
        assert(is_ok());
        return std::get< Ok_ >(m_variant).value;
    }

    auto ok() && -> T&& {
        assert(is_ok());
        return std::get< Ok_ >(std::move(m_variant)).value;
    }

    auto ok() const && -> T const&& {
        assert(is_ok());
        return std::get< Ok_ >(std::move(m_variant)).value;
    }

    auto err() & -> E& {
        assert(is_err());
        return std::get< Err_ >(m_variant).reason;
    }

    auto err() const & -> E const& {
        assert(is_err());
        return std::get< Err_ >(m_variant).reason;
    }

    auto err() && -> E&& {
        assert(is_err());
        return std::get< Err_ >(std::move(m_variant)).reason;
    }

    auto err() const && -> E const&& {
        assert(is_err());
        return std::get< Err_ >(std::move(m_variant)).reason;
    }

public: // modifiers

    template<class ... Args>
    auto emplace_ok(Args&& ... args) -> T&  {
        return m_variant.template emplace< Ok_ >( in_place, std::forward<Args>(args)... ).value;
    }

    template<class U, class ... Args>
    auto emplace_ok(std::initializer_list<U> ls, Args&& ... args) -> T& {
        return m_variant.template emplace< Ok_ >(in_place, ls, std::forward<Args>(args)... ).value;
    }

    template<class ... Args>
    auto emplace_err(Args&& ... args) -> E& {
        return m_variant.template emplace< Err_ >(in_place, std::forward<Args>(args)... ).reason;
    }

    template<class U, class ... Args>
    auto emplace_err(std::initializer_list<U> ls, Args&& ... args) -> E& {
        return m_variant.template emplace< Err_ >(in_place, ls, std::forward<Args>(args)... ).reason;
    }


private:
    Variant m_variant;
};

//
//
//
#include <vector>
#include <string>

auto main() -> int {
    //
    {
        Result<int, std::string> res;

        assert(res.is_ok());
        assert(!res.is_err());
    }

    //
    {
        std::vector<int> const expected = {1, 2, 3, 4, 5};
        Result<std::vector<int>, std::string> res{in_place_ok, {1, 2, 3, 4, 5}};

        assert(res.ok() == expected);
    }

    //
    {
        Result<std::vector<int>, std::string> res{in_place_err, "error"};

        assert(res.err() == "error");
    }

    {
        std::vector<int> const expected = {1, 2, 3, 4, 5};
        Result<std::vector<int>, std::string> res{in_place_ok, {1, 2, 3, 4, 5}};

        assert(std::move(res).ok() == expected);
    }

    //
    {
        Result<std::vector<int>, std::string> res{in_place_err, "error"};

        assert(std::move(res).err() == "error");
    }

    //
    {
        Result<int, int> a{in_place_ok, 42}, b{in_place_ok, 42}, c{in_place_ok, 53};

        assert(a == b);
        assert(a != c);
    }

    //
    {
        Result<int, int> res;

        assert(res.is_ok());

        res.emplace_ok(42);

        assert(res.is_ok() && res.ok() == 42);

        res.emplace_err(15);

        assert(res.is_err() && res.err() == 15);
    }

    //
    {
    }
}
#endif