#ifndef CXSTRING_INCLUDED
#define CXSTRING_INCLUDED

// Copyright (c) 2012 Faisal Vali
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// 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 AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

// Original code:
// http://sourceforge.net/projects/constexprstr/

// Notes:
// - 30/03/2013:
//      Modified by myself to follow the coding style of the rest of the project,
//      and to use more correct C++:
//       - use of unsigned integers for sizes and indices,
//       - use of namespaces instead of structs when possible,
//       - perfer 'using T = U;' instead of 'typedef U T;',
//       - added 'operator !=',
//       - removed useless 'size' member value of 'string',
//       - added 'c_str', 'str', 'front', 'back', 'begin', 'end', 'substr',
//         'append' and 'prepend' methods to 'string',
//       - removed explicit dependence on std::ostream,
//       - removed useless 'substring' class,
//       - fixed const-correctness of some member functions,
//       - made the character type of 'string' a template parameter.

#include <memory>
#include <string>

namespace cxstring {
    using std::size_t;

    namespace int_pack {
        template<size_t ... N>
        struct pack {};

        template<typename pack, size_t N>
        struct append_t;

        template<size_t ... L, size_t R>
        struct append_t<pack<L...>, R> {
            using type = pack<L..., R>;
        };

        template<typename pack, size_t N>
        using append = typename append_t<pack, N>::type;

        template<size_t begin, size_t end>
        struct range_t;

        template<size_t begin>
        struct range_t<begin, begin> {
            using type = pack<>;
        };

        template<size_t begin, size_t end>
        struct range_t {
            using type = append<typename range_t<begin, end-1>::type, end-1>;
        };

        template<size_t begin, size_t end>
        using range = typename range_t<begin, end>::type;
    }

    template<size_t N>
    struct num {};

    struct tail_op {};
    struct append_op {};
    struct prepend_op {};
    struct empty_array {};

    template<typename T, size_t N>
    struct array {
        T data[N];

        // We use pointers to array - since using a reference does not work because of bug in gcc 4.6.1
        template<size_t ... I, size_t M, template<size_t ...> class TT>
        constexpr array(const T (*s)[M], TT<I...>) : data{(*s)[I]...} {}

        template<size_t ... I, size_t M, template<size_t ...> class TT>
        constexpr array(const T (*s)[M], TT<I...>, T c, append_op) : data{(*s)[I]..., c} {}

        template<size_t ... I, template<size_t ...> class TT>
        constexpr array(const empty_array*, TT<I...>, T c, append_op) : data{c} {}

        template<size_t ... I1, size_t ... I2, size_t M1, size_t M2,
            template<size_t ...> class TT1, template<size_t ...> class TT2>
        constexpr array(const T (*s1)[M1], TT1<I1...>,
                        const T (*s2)[M2], TT2<I2...>,
                        append_op) : data{(*s1)[I1]..., (*s2)[I2]...} {}

        template<size_t ... I, size_t M, template<size_t ...> class TT>
        constexpr array(const T (*s)[M], TT<I...>, T c, prepend_op) : data{c, (*s)[I]...} {}

        template<size_t ... I, template<size_t ...> class TT>
        constexpr array(const empty_array*, TT<I...>, T c, prepend_op) : data{c} {}

        template<size_t ... I1, size_t ... I2, size_t M1, size_t M2,
            template<size_t ...> class TT1, template<size_t ...> class TT2>
        constexpr array(const T (*s1)[M1], TT1<I1...>,
                        const T (*s2)[M2], TT2<I2...>,
                        prepend_op) : data{(*s2)[I1]..., (*s1)[I2]...} {}

        constexpr size_t size() const {
            return N;
        }

        constexpr T operator [] (size_t idx) {
           return idx >= N ? throw "Bad Index" : data[idx];
        }
    };

    template<typename T, size_t N>
    struct string;

    template<typename T, size_t Begin, size_t End, size_t N>
    constexpr string<T,End-Begin> substr(const string<T,N>& cs);

    template<typename T, size_t N>
    struct string {
        array<T,N> data;

        constexpr string(const T (&null_carray)[N+1]) :
            data(&null_carray, int_pack::range<0,N>()) {}

        constexpr string(const string<T,N>& s) :
            data(&s.data.data, int_pack::range<0,N>()) {}

        constexpr string(const string<T,N+1>& s, tail_op) :
            data(&s.data.data, int_pack::range<1,N+1>()) {}

        constexpr string(const string<T,N-1>& s, T c, append_op a) :
            data(&s.data.data, int_pack::range<0,N-1>(), c, a) {}

        template<size_t M>
        constexpr string(const string<T,M>& s1, const string<T,N-M>& s2, append_op a) :
            data(&s1.data.data, int_pack::range<0,M>(), &s2.data.data, int_pack::range<0,N-M>(), a) {}

        constexpr string(const string<T,N-1>& s, T c, prepend_op a) :
            data(&s.data.data, int_pack::range<0,N-1>(), c, a) {}

        template<size_t M>
        constexpr string(const string<T,M>& s1, const string<T,N-M>& s2, prepend_op a) :
            data(&s1.data.data, int_pack::range<0,M>(), &s2.data.data, int_pack::range<0,N-M>(), a) {}

        constexpr size_t length() const {
            return N;
        }

        constexpr size_t size() const {
            return N;
        }

        constexpr T front() const {
            return data.data[0];
        }

        constexpr T back() const {
            return data.data[N-1];
        }

        constexpr const T* begin() const {
            return data.data;
        }

        constexpr const T* end() const {
            return data.data + N;
        }

        template<typename U>
        constexpr auto append(const U& t) -> decltype(append(*this, t)) {
            return append(*this, t);
        }

        template<typename U>
        constexpr auto prepend(const U& t) -> decltype(prepend(*this, t)) {
            return prepend(*this, t);
        }

        template<size_t Begin, size_t End>
        constexpr auto substr() -> decltype(substr<Begin, End>(*this)) {
            return substr<Begin, End>(*this);
        }

        constexpr const T* c_str() const {
            return string<T,N+1>(*this, 0, append_op{}).data.data;
        }

        std::string str() const {
            return std::string(data.data, N);
        }

        constexpr T operator [] (size_t idx) const {
            return data[idx];
        }

        template<typename O>
        friend O& operator << (O& stream, const string& s) {
            stream.write(s.data.data, N);
            return stream;
        }
    };

    template<typename T>
    struct string<T,0> {
        struct {
            empty_array data;
        } data;

        constexpr string() = default;
        constexpr string(const T (&)[1]) {}

        constexpr size_t length() const { return 0; }
        constexpr size_t size() const { return 0; }
        constexpr T front() const { return 0; }
        constexpr T back() const { return 0; }
        constexpr const T* begin() const { return 0; }
        constexpr const T* end() const { return 0; }

        template<typename U>
        constexpr auto append(const U& t) -> decltype(append(*this, t)) {
            return append(*this, t);
        }

        template<typename U>
        constexpr auto prepend(const U& t) -> decltype(prepend(*this, t)) {
            return prepend(*this, t);
        }

        template<size_t Begin, size_t End>
        constexpr string substr() {
            return *this;
        }

        constexpr const T* c_str() const { return {0}; }

        template<typename O>
        friend O& operator << (O& stream, const string& s) {
            return stream;
        }
    };

    // cstr
    // --------
    template<typename T, size_t N>
    constexpr string<T,N-1> cstr(const T (&s)[N]) {
        return string<T,N-1>{s};
    }

    // tail
    // --------
    template<typename T>
    constexpr string<T,0> tail(const string<T,0>& s) {
        return s;
    }

    template<typename T>
    constexpr string<T,0> tail(const string<T,1>& s) {
        return string<T,0>();
    }

    template<typename T, size_t N, typename enable = typename std::enable_if<N != 0>::type>
    constexpr string<T,N-1> tail(const string<T,N>& s) {
        return string<T,N-1>(s, tail_op());
    }

    template<typename T, size_t N>
    constexpr string<T,N-2> tail(const T (&ca)[N]) {
        return tail(cstr(ca));
    }

    // append
    // --------
    template<typename T, size_t N>
    constexpr string<T,N+1> append(const string<T,N>& s, T c) {
        return string<T,N+1>(s, c, append_op());
    }

    template<typename T, size_t N>
    constexpr string<T,N> append(const string<T,N>& s1, const string<T,0>& s2) {
        return s1;
    }

    template<typename T, size_t N, size_t M>
    constexpr string<T,N+M> append(const string<T,N>& s1, const string<T,M>& s2) {
        return string<T,N+M>(s1, s2, append_op());
    }

    template<typename T, size_t N, size_t M>
    constexpr string<T,N+M-1> append(const string<T,N>& s1, const T (&s2)[M]) {
        return append(s1, cstr(s2));
    }

    template<typename T, size_t N, size_t M>
    constexpr string<T,N+M-2> append(const T (&s1)[N], const T (&s2)[M]) {
        return append(cstr(s1), cstr(s2));
    }

    // prepend
    // --------
    template<typename T, size_t N>
    constexpr string<T,N> prepend(const string<T,N>& s1, const string<T,0>& s2) {
        return s1;
    }

    template<typename T, size_t N>
    constexpr string<T,N+1> prepend(const string<T,N>& s, T c) {
        return string<T,N+1>(s, c, prepend_op());
    }

    template<typename T, size_t N, size_t M>
    constexpr string<T,N+M> prepend(const string<T,N>& s1, const string<T,M>& s2) {
        return string<T,N+M>(s1, s2, prepend_op());
    }

    template<typename T, size_t N, size_t M>
    constexpr string<T,N+M-1> prepend(const string<T,N>& s1, const T (&s2)[M]) {
        return prepend(s1, cstr(s2));
    }

    template<typename T, size_t N, size_t M>
    constexpr string<T,N+M-2> prepend(const T (&s1)[N], const T (&s2)[M]) {
        return prepend(cstr(s1), cstr(s2));
    }

    // substr
    // --------
    namespace impl {
        template<typename T, size_t N, size_t Begin, size_t End>
        struct extractor;

        // Base case when there is nothing to extract
        template<typename T, size_t N>
        struct extractor<T,N,0,0> {
            static_assert(0 <= N, "End must be <= N");

            static constexpr string<T,0> extract(const string<T,N> &s) {
                return string<T,0>();
            }
        };

        // Base case when we are done extracting
        template<typename T, size_t N>
        struct extractor<T,N,0,1> {
            static_assert(1 <= N, "End must be <= N");

            static constexpr string<T,1> extract(const string<T,N> &s) {
                return string<T,1>((s[0]));
            }
        };

        // Base case to start extracting
        template<typename T, size_t N, size_t End>
        struct extractor<T,N,0,End> {
            static_assert(End <= N, "End must be <= N");

            static constexpr string<T,End> extract(const string<T,N> &s) {
                // Start extracting and prepending until we get to the onepastendidx
                return prepend(extractor<T, N-1, 0, End-1>::extract(tail(s)), s[0]);
            }
        };

        // Recursive case
        template<typename T, size_t N, size_t Begin, size_t End>
        struct extractor {
            static_assert(End <= N,     "End must be <= N");
            static_assert(End >= Begin, "End must be >=  Begin");

            static constexpr string<T,End-Begin> extract(const string<T,N> &s) {
                // Do nothing until we get to the Begin
                return extractor<T, N-1, Begin-1, End-1>::extract(tail(s));
            }
        };
    }

    template<typename T, size_t Begin, size_t End, size_t N>
    constexpr string<T,End-Begin> substr(const string<T,N>& cs) {
        return impl::extractor<T, N, Begin, End>::extract(cs);
    }

    template<typename T, size_t Begin, size_t End, size_t N>
    constexpr string<T,End-Begin> substr(const T (&cs)[N]) {
        return substr<T, Begin, End>(cstr(cs));
    }

    // resize
    // --------
    namespace impl {
        template<typename T, size_t N, typename enable = typename std::enable_if<N!=0>::type>
        constexpr string<T,N> blank_string(num<N>) {
            return append(blank_string<T,N-1>(), 0);
        }

        template<typename T>
        constexpr string<T,0> blank_string(num<0>) {
            return string<T,0>({0});
        }

        template<typename T, size_t N, size_t M, bool shrink>
        struct resize_helper;

        template<typename T, size_t N, size_t M>
        struct resize_helper<T,N,M,true> {
            static constexpr string<T,N> call(const string<T,M>& s) {
                return substr<T,0,N>(s);
            }
        };

        template<typename T, size_t N, size_t M>
        struct resize_helper<T,N,M,false> {
            static constexpr string<T,N> call(const string<T,M>& s) {
                return append(s, blank_string<T>(num<N-M>()));
            }
        };
    }

    template<typename T, size_t N, size_t M, typename enable = typename std::enable_if<(N!=M)>::type>
    constexpr string<T,N> resize(const string<T,M>& s) {
        return impl::resize_helper<T,N,M,(N<M)>::call(s);
    }

    template<typename T, size_t N>
    constexpr string<T,N> resize(const string<T,N>& s) {
        return s;
    }

    // operator +
    // --------
    template<typename T, size_t N>
    constexpr string<T,N+1> operator + (const string<T,N>& s, T c) {
        return append(s, c);
    }

    template<typename T, size_t N>
    constexpr string<T,N+1> operator + (T c, const string<T,N>& s) {
        return prepend(s, c);
    }

    template<typename T, size_t N, size_t M>
    constexpr string<T,N+M> operator + (const string<T,N>& s1, const string<T,M>& s2) {
        return append(s1, s2);
    }

    template<typename T, size_t N, size_t M>
    constexpr string<T,N+M-1> operator + (const string<T,N>& s1, const T (&s2)[M]) {
        return append(s1, cstr(s2));
    }

    template<typename T, size_t N, size_t M>
    constexpr string<T,N+M-1> operator + (const T (&s2)[M], const string<T,N>& s1) {
        return append(cstr(s2), s1);
    }

    // operator ==
    // --------
    template<typename T, size_t N, size_t M>
    constexpr bool operator == (const string<T,N>& s1, const string<T,M>& s2) {
        return false;
    }

    template<typename T>
    constexpr bool operator == (const string<T,0>& s1, const string<T,0>& s2) {
        return true;
    }

    template<typename T, size_t N>
    constexpr bool operator == (const string<T,N>& s1, const string<T,N>& s2) {
        return s1[0] == s2[0] && tail(s1) == tail(s2);
    }

    template<typename T, size_t N, size_t M>
    constexpr bool operator == (const string<T,N>& s1, const T (&s2)[M]) {
        return s1 == cstr(s2);
    }

    template<typename T, size_t N, size_t M>
    constexpr bool operator == (const T (&s1)[N], const string<T,M> &s2) {
        return cstr(s1) == s2;
    }

    // operator !=
    // --------
    template<typename T, size_t N, size_t M>
    constexpr bool operator != (const string<T,N>& s1, const string<T,M>& s2) {
        return true;
    }

    template<typename T>
    constexpr bool operator != (const string<T,0>& s1, const string<T,0>& s2) {
        return false;
    }

    template<typename T, size_t N>
    constexpr bool operator != (const string<T,N>& s1, const string<T,N>& s2) {
        return s1[0] != s2[0] || tail(s1) != tail(s2);
    }

    template<typename T, size_t N, size_t M>
    constexpr bool operator != (const string<T,N>& s1, const T (&s2)[M]) {
        return s1 != cstr(s2);
    }

    template<typename T, size_t N, size_t M>
    constexpr bool operator != (const T (&s1)[N], const string<T,M> &s2) {
        return cstr(s1) != s2;
    }
}

// Test suite
// All the code that follows must compile, and all the tests should output 1 at runtime.

/*
#include <iostream>

template<size_t N> struct eval { enum { val = N, val_half = N/2 }; };

void cxstring_test() {
    using namespace cxstring;

    #define SDUMP(...) std::cout << #__VA_ARGS__ << " => " << (__VA_ARGS__)  << std::endl; \
      static_assert( !!eval<__VA_ARGS__>::val, ""); static_assert(__VA_ARGS__, #__VA_ARGS__)

    SDUMP(cstr("abc")[0] == 'a');
    constexpr string<3> ca = cstr("abc");
    SDUMP(ca[0] == 'a');
    constexpr string<2> cat = tail(ca);
    SDUMP(tail(ca)[0] == 'b');
    constexpr string<4> caa = append(ca, 'd');
    SDUMP(append(ca, tail(ca))[0] == 'a');
    SDUMP(append(ca, tail(ca))[3] == 'b');
    SDUMP(append(cstr("abc"), cstr("def")) == cstr("abcdef"));
    SDUMP(append("abc", "def") == "abcdef");
    SDUMP(cstr("abc") == "abc");
    SDUMP(substr<1,3>("help") == "el");

    #undef SDUMP
}
*/

#endif
