#ifndef SSO_STR_H
#define SSO_STR_H

#include <limits>
#include <utility>
#include <algorithm>
#include <iterator>
#include <cassert>
#include <cstring>
#include <type_traits>
#include <string_view>
#include <variant>

template <class C>
constexpr auto string_length(std::basic_string_view<C> s) {
   return s.size();
}

namespace v0 {
   template <class C>
   class basic_sso_str {
   public:
      using char_type = C;
      using value_type = C;
      using size_type = std::size_t;
   private:
      class big_data {
         size_type nelems{}, cap{};
         char_type *elems{};
      public:
         using iterator = char_type *;
         using const_iterator = const char_type *;
         size_type size() const noexcept {
            return nelems;
         }
         size_type capacity() const noexcept {
            return cap;
         }
         bool full() const noexcept {
            return size() == capacity();
         }
         iterator begin() noexcept {
            return elems;
         }
         const_iterator begin() const noexcept {
            return elems;
         }
         iterator end() noexcept {
            return begin() + size();
         }
         const_iterator end() const noexcept {
            return begin() + size();
         }
         big_data() = default;
         template <int N>
         big_data(const char_type(&arr)[N])
            : nelems{ N }, cap{ N }, elems{ new char_type[N] } {
            std::copy(std::begin(arr), std::end(arr), begin());
         }
         template <class It>
         big_data(It b, It e, size_type newcap = {}) {
            nelems = std::distance(b, e);
            cap = std::max(newcap, size());
            elems = new char_type[capacity()];
            std::copy(b, e, begin());
         }
         big_data(const big_data &org)
            : nelems{ org.size() }, cap{ org.size() } {
            elems = new char_type[capacity()];
            std::copy(std::begin(org), std::end(org), begin());
         }
         big_data(const big_data &org, size_type cap)
            : nelems{ org.size() }, cap{ cap } {
            elems = new char_type[capacity()];
            std::copy(std::begin(org), std::end(org), begin());
         }
         big_data(big_data &&org) noexcept
            : nelems{ std::exchange(org.nelems, 0) },
            cap{ std::exchange(org.cap, 0) },
            elems{ std::exchange(org.elems, nullptr) } {
         }
         void swap(big_data &other) noexcept {
            using std::swap;
            swap(elems, other.elems);
            swap(nelems, other.nelems);
            swap(cap, other.cap);
         }
         big_data &operator=(const big_data &other) {
            big_data{ other }.swap(*this);
            return *this;
         }
         big_data &operator=(big_data &&other) noexcept {
            if (&other == this) return *this;
            delete[] elems;
            elems = std::exchange(other.elems, nullptr);
            nelems = std::exchange(other.nelems, 0);
            cap = std::exchange(other.cap, 0);
            return *this;
         }
         ~big_data() {
            delete[] elems;
         }
         void add(char_type c) {
            assert(!full());
            elems[size()] = c;
            ++nelems;
         }
      };
      static constexpr auto bits_in_byte =
         std::numeric_limits<unsigned char>::digits;
      static constexpr auto smallness_mark_bit =
         static_cast<std::size_t>(1) << (static_cast<std::size_t>(sizeof(size_type) * bits_in_byte - 1));
      static_assert(
         sizeof(smallness_mark_bit) == sizeof(size_type)
         );
      class small_data {
      public:
         using size_type = std::size_t;
      private:
         char_type data_[sizeof(big_data) / sizeof(char_type)];
         auto to_char_rep() {
            return std::begin(data_);
         }
         auto to_char_rep() const {
            return std::begin(data_);
         }
         decltype(auto) to_size_rep() {
            return *reinterpret_cast<size_type *>(std::begin(data_));
         }
         decltype(auto) to_size_rep() const {
            return *reinterpret_cast<const size_type *>(std::begin(data_));
         }
      public:
         static constexpr auto max_chars =
            sizeof(big_data) - sizeof(size_type);
         using iterator = char_type *;
         using const_iterator = const char_type *;
         iterator begin() noexcept {
            return to_char_rep() + sizeof(size_type);
         }
         const_iterator begin() const noexcept {
            return to_char_rep() + sizeof(size_type);
         }
         iterator end() noexcept {
            return begin() + size();
         }
         const_iterator end() const noexcept {
            return begin() + size();
         }
         size_type size() const noexcept {
            return remove_smallness_mark(to_size_rep());
         }
         constexpr size_type capacity() const noexcept {
            return (sizeof(data_) - sizeof(size_type)) / sizeof(char_type);
         }
         bool full() const noexcept {
            return size() == capacity();
         }
         template <class It>
         small_data(It b, It e, size_type = 0) {
            to_size_rep() =
               add_smallness_mark(std::distance(b, e));
            assert(size() <= max_chars);
            std::copy(b, e, begin());
         }
         small_data() {
            to_size_rep() = add_smallness_mark(0);
         }
         template <int N>
         small_data(const char_type(&arr)[N]) {
            static_assert(N && N - 1 <= max_chars);
            to_size_rep() = add_smallness_mark(N - 1);
            std::copy(std::begin(arr), std::prev(std::end(arr)), begin());
         }
         void add(char_type c) {
            assert(!full());
            *(begin() + size()) = c;
            to_size_rep() = add_smallness_mark(
               remove_smallness_mark(to_size_rep()) + 1
            );
         }
         static bool has_smallness_mark(size_type n) {
            return (n & smallness_mark_bit) != 0;
         }
         static size_type add_smallness_mark(size_type n) {
            return n | smallness_mark_bit;
         }
         static size_type remove_smallness_mark(size_type n) {
            return n & ~smallness_mark_bit;
         }
      };
      // this could be a static_assert that the two are equal, really
      static constexpr auto data_size =
         std::max(sizeof(small_data), sizeof(big_data))/* / sizeof(char_type)*/;
      char_type data[data_size]{};
      static constexpr bool is_big(size_type n) noexcept {
         return n > small_data::max_chars / sizeof(char_type);
      }
      bool is_big() const noexcept {
         return !small_data::has_smallness_mark(
            *reinterpret_cast<const size_type *>(data + 0)
         );
      }
      big_data &to_big_data() noexcept {
         return *reinterpret_cast<big_data *>(data);
      }
      const big_data &to_big_data() const noexcept {
         return *reinterpret_cast<const big_data *>(data);
      }
      small_data &to_small_data() noexcept {
         return *reinterpret_cast<small_data *>(data);
      }
      const small_data &to_small_data() const noexcept {
         return *reinterpret_cast<const small_data *>(data);
      }
      size_type capacity() const noexcept {
         return is_big() ? to_big_data().capacity() :
            to_small_data().capacity();
      }
      bool full() const noexcept {
         return size() == capacity();
      }
      template <class Pol>
      void resize(Pol policy) {
         char_type new_data[data_size]{ };
         size_type newcap = policy(capacity());
         assert(newcap >= capacity());
         assert(!small_data::has_smallness_mark(newcap));
         const bool was_big = is_big(capacity());
         if (is_big(newcap))
            new (new_data) big_data{ begin(), end(), newcap };
         else
            new (new_data) small_data{ begin(), end(), newcap };
         if (was_big)
            to_big_data().~big_data();
         else
            to_small_data().~small_data();
         if (is_big(newcap))
            new (static_cast<void *>(data)) big_data{ *reinterpret_cast<big_data *>(new_data), newcap };
         else
            new (static_cast<void *>(data)) small_data{ *reinterpret_cast<small_data *>(new_data) };
      }
   public:
      using iterator = char_type *;
      using const_iterator = const char_type *;
      iterator begin() noexcept {
         return is_big() ? to_big_data().begin() :
            to_small_data().begin();
      }
      const_iterator begin() const noexcept {
         return is_big() ? to_big_data().begin() :
            to_small_data().begin();
      }
      iterator end() noexcept {
         return begin() + size();
      }
      const_iterator end() const noexcept {
         return begin() + size();
      }
      size_type size() const noexcept {
         return is_big() ? to_big_data().size() : to_small_data().size();
      }
      basic_sso_str() {
         new (data) small_data;
      }
      basic_sso_str(const basic_sso_str &other) {
         if (other.is_big())
            new (data) big_data(other.to_big_data());
         else
            new (data) small_data(other.to_small_data());
      }
      basic_sso_str &operator=(const basic_sso_str &other) {
         if (this != &other) {
            char_type new_data[data_size]{ };
            if (other.is_big())
               new (new_data) big_data(other.to_big_data());
            else
               new (new_data) small_data(other.to_small_data());
            if (is_big())
               to_big_data().~big_data();
            else
               to_small_data().~small_data();
            if (other.is_big())
               new (data) big_data{ *reinterpret_cast<big_data *>(new_data) };
            else
               new (data) small_data{ *reinterpret_cast<small_data *>(new_data) };
         }
         return *this;
      }
      template <int N>
      basic_sso_str(const char_type(&p)[N]) {
         if constexpr (is_big(N * sizeof(char_type)))
            new (data) big_data(p);
         else
            new (data) small_data(p);
      }
      ~basic_sso_str() {
         if (is_big())
            to_big_data().~big_data();
         else
            to_small_data().~small_data();
      }
      void push_back(char_type c) {
         auto resizer = [](size_type oldcap) {
            static constexpr auto resize_fac = 2;
            return oldcap ? static_cast<size_type>(oldcap * resize_fac) : data_size;
         };
         if (full())
            resize(resizer);
         if (is_big())
            to_big_data().add(c);
         else
            to_small_data().add(c);
      }
   };
}

namespace v1 {
   template <class C>
   class basic_sso_str {
   public:
      using char_type = C;
      using value_type = C;
      using size_type = std::size_t;
   private:
      static constexpr auto data_size = 16;
      union {
         value_type small[data_size];
         char_type *ptr;
      } rep;
      size_type nelems{}, cap{ data_size };
   public:
      size_type size() const noexcept {
         return nelems;
      }
      size_type capacity() const noexcept {
         return cap;
      }
      bool full() const noexcept {
         return size() == capacity();
      }
      using iterator = char_type *;
      using const_iterator = const char_type *;
      iterator begin() noexcept {
         return uses_small_rep() ? std::begin(rep.small) : rep.ptr;
      }
      const_iterator begin() const noexcept {
         return uses_small_rep() ? std::begin(rep.small) : rep.ptr;
      }
      iterator end() noexcept {
         return begin() + size();
      }
      const_iterator end() const noexcept {
         return begin() + size();
      }
   private:
      template <class Pol>
      void resize(Pol policy) {
         using namespace std;
         size_type newcap = policy(capacity());
         assert(newcap >= capacity());
         if (newcap > data_size) {
            auto p = new char_type[newcap];
            copy(begin(), end(), p);
            if (!uses_small_rep()) delete[] rep.ptr;
            rep.ptr = p;
            cap = newcap;
         }
      }
      bool uses_small_rep() const {
         return capacity() == data_size;
      }
   public:
      basic_sso_str() = default;
      basic_sso_str(const basic_sso_str &other)
         : nelems{ other.size() }, cap{ other.uses_small_rep() ? data_size : other.size() } {
         if (!uses_small_rep())
            rep.ptr = new char_type[capacity()];
         std::copy(other.begin(), other.end(), begin());
      }
      void swap(basic_sso_str &other) {
         using std::swap;
         swap(nelems, other.nelems);
         swap(cap, other.cap);
         swap(rep, other.rep);
      }
      basic_sso_str &operator=(const basic_sso_str &other) {
         basic_sso_str{ other }.swap(*this);
         return *this;
      }
      template <int N>
      basic_sso_str(const char_type(&p)[N]) {
         assert(!p[N - 1]);
         if constexpr (N > data_size) {
            rep.ptr = new char_type[N];
            cap = N;
         }
         nelems = N - 1;
         std::copy(std::begin(p), std::end(p) - 1, begin());
      }
      ~basic_sso_str() {
         if (!uses_small_rep()) delete rep.ptr;
      }
      void push_back(char_type c) {
         if (full()) resize([](auto n) { return n * 2; }); // no need for the 0 capacity case
         if (uses_small_rep()) {
            rep.small[size()] = c;
         }
         else {
            rep.ptr[size()] = c;
         }
         ++nelems;
      }
   };
}

namespace v2 {
   template <class C>
   class basic_sso_str {
   public:
      using char_type = C;
      using value_type = C;
      using size_type = std::size_t;
      using iterator = char_type *;
      using const_iterator = const char_type *;
   private:
      static constexpr auto data_size = 16;
      class small {
         value_type data[data_size / sizeof(value_type)];
         size_type nelems{};
         bool full() const noexcept { return size() == capacity(); }
      public:
         small() = default;
         template <class It>
         small(It debut, It fin) : nelems(std::distance(debut, fin)) {
            assert(size() < capacity());
            std::copy(debut, fin, begin());
         }
         auto size() const noexcept { return nelems; }
         auto capacity() const noexcept { return std::size(data); }
         iterator begin() noexcept { return std::begin(data); }
         const_iterator begin() const noexcept { return std::begin(data); }
         iterator end() noexcept { return begin() + size(); }
         const_iterator end() const noexcept { return begin() + size(); }
         void push_back(value_type c) {
            assert(!full());
            data[size()] = c;
            ++nelems;
         }
      };
      class big {
         value_type *data;
         size_type nelems{}, cap{ };
         bool full() const noexcept { return size() == capacity(); }
      public:
         big(size_type cap) : data{ new value_type[cap] }, cap{ cap } {
         }
         template <class It>
         big(It debut, It fin) : nelems(std::distance(debut, fin)) {
            cap = size();
            data = new value_type[capacity()];
            std::copy(debut, fin, begin());
         }
         // prudence : le choix de dupliquer la capacité est délibéré ici
         big(const big &other)
            : data{ new value_type[other.capacity()] }, nelems{ other.size() }, cap{ other.capacity() } {
            std::copy(other.begin(), other.end(), begin());
         }
         big(big &&other) noexcept
            : data{ std::exchange(other.data, nullptr) },
            nelems{ std::exchange(other.nelems, 0) },
            cap{ std::exchange(other.cap, 0) } {
         }
         void swap(big &other) noexcept {
            using std::swap;
            swap(data, other.data);
            swap(nelems, other.nelems);
            swap(cap, other.cap);
         }
         big &operator=(const big &other) {
            big{ other }.swap(*this);
            return *this;
         }
         big &operator=(big &&other) noexcept {
            if (this != &other) {
               delete[] data;
               data = std::exchange(other.data, nullptr);
               nelems = std::exchange(other.nelems, 0);
               cap = std::exchange(other.cap, 0);
            }
            return *this;
         }
         template <class It>
         void assign(It debut, It fin) {
            size_type n = std::distance(debut, fin);
            assert(n <= capacity());
            std::copy(debut, fin, begin());
            nelems = n;
         }
         auto size() const noexcept { return nelems; }
         auto capacity() const noexcept { return cap; }
         iterator begin() noexcept { return data; }
         const_iterator begin() const noexcept { return data; }
         iterator end() noexcept { return begin() + size(); }
         const_iterator end() const noexcept { return begin() + size(); }
         void push_back(value_type c) {
            assert(!full());
            data[size()] = c;
            ++nelems;
         }
      };
      std::variant<small, big> rep{}; // initializes small
   public:
      size_type size() const noexcept {
         return visit([](const auto &rep) { return rep.size(); }, rep);
      }
      size_type capacity() const noexcept {
         return visit([](const auto &rep) { return rep.capacity(); }, rep);
      }
      bool full() const noexcept {
         return size() == capacity();
      }
      iterator begin() noexcept {
         return visit([](auto &rep) { return rep.begin(); }, rep);
      }
      const_iterator begin() const noexcept {
         return visit([](const auto &rep) { return rep.begin(); }, rep);
      }
      iterator end() noexcept {
         return visit([](auto &rep) { return rep.end(); }, rep);
      }
      const_iterator end() const noexcept {
         return visit([](const auto &rep) { return rep.end(); }, rep);
      }
   private:
      template <class Pol>
      void resize(Pol policy) {
         using namespace std;
         size_type newcap = policy(capacity());
         assert(newcap >= capacity());
         big s(newcap);
         s.assign(begin(), end());
         rep = s;
      }
   public:
      basic_sso_str() = default;
      template <int N>
      basic_sso_str(const char_type(&p)[N]) {
         assert(!p[N - 1]);
         if constexpr (N < data_size / sizeof(char_type)) {
            rep = small{ std::begin(p), std::end(p) };
         }
         else {
            rep = big{ std::begin(p), std::end(p) };
         }
      }
      void push_back(char_type c) {
         if (full()) resize([](auto n) { return n * 2; }); // no need for the 0 capacity case
         visit([c](auto &rep) { rep.push_back(c); }, rep);
      }
   };
}

using v0::basic_sso_str;

template <class C>
std::basic_ostream<C> &
operator<<(std::basic_ostream<C> &os, const basic_sso_str<C> &s) {
   for (auto c : s)
      os << c;
   return os;
}

using sso_str = basic_sso_str<char>;
using wsso_str = basic_sso_str<wchar_t>;

#endif