#include <boost/mpl/min_max.hpp>
#include <boost/mpl/insert.hpp>
#include <boost/mpl/long.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/at.hpp>
#include <iostream>

template <
    typename enum_container,
    typename _tag = enum_container
>
struct CompressedEnum {
    typedef  _tag tag;
    typedef typename enum_container::E inner_type;
    const static size_t size = enum_container::size;

    template<typename storage_type, int offset>
    static int get_offset() { return offset; }

    template<typename storage_type, int offset>
    static inner_type get(const storage_type& data) {
        //std::cout << "Get>" <<
        //    " data:" << (unsigned int) data <<
        //    " size:" << size <<
        //    " offset:" << offset << std::endl;

        return (inner_type)((data / offset) % size);
    }

    template<typename storage_type, int offset>
    static void clear(storage_type& data) {
        data -= get<storage_type, offset>(data) * offset;
    }

    template<typename storage_type, int offset>
    static void set(storage_type& data, inner_type value) {
        //std::cout << "Set> (start)" << std::endl;

        clear<storage_type, offset>(data);
        data += value * offset;

        //std::cout << "Set> (done)" <<
        //    " data:" << (unsigned int) data <<
        //    " value:" << (unsigned int) value <<
        //    " offset:" << offset << std::endl;
    }

    template<typename storage_type, int offset>
    static void set_no_clear(storage_type& data, inner_type value) {
        data += value * offset;
    }

    template<typename storage_type, int offset>
    static void next(storage_type& data) {
        data += offset;
    }

    template<typename storage_type, int offset>
    static void prev(storage_type& data) {
        data -= offset;
    }
};

template <
    typename enum_container,
    int length,
    typename _tag = enum_container
>
struct CompressedEnumArray {
    template<typename T, int X, int P> struct Pow { const static T result = X*Pow<T,X,P-1>::result; };
    template<typename T, int X> struct Pow<T,X,0> { const static T result = 1; };
    template<typename T, int X> struct Pow<T,X,1> { const static T result = X; };

    typedef  _tag tag;
    typedef typename enum_container::E inner_type;
    const static size_t size = Pow<unsigned, enum_container::size, length>::result;

    template<typename storage_type, int offset>
    static int i_offset(int i) { // TODO, make more efficient
        int o = offset;          // TODO, check range
        for (int j = 0; j < i; j++)
            o *= enum_container::size;
        return o;
    }

    template<typename storage_type, int offset>
    static inner_type get(const storage_type& data, int i) {
        return (inner_type)((data / i_offset(i)) % enum_container::size);
    }

    template<typename storage_type, int offset>
    static void clear(storage_type& data, int i) {
        data -= get(data) * i_offset(i);
    }

    template<typename storage_type, int offset>
    static void set(storage_type& data, int i, inner_type value) {
        clear(data); data += value * i_offset(i);
    }

    template<typename storage_type, int offset>
    static void set_no_clear(storage_type& data, int i, inner_type value) {
        data += value * i_offset(i);
    }

    template<typename storage_type, int offset>
    static void next(storage_type& data, int i) {
        data += i_offset(i);
    }

    template<typename storage_type, int offset>
    static void prev(storage_type& data, int i) {
        data -= i_offset(i);
    }

    template<typename storage_type, int offset, int N>
    static inner_type get(const storage_type& data) {
        return (inner_type)
            ((data / (offset * Pow<int, enum_container::size, N>::result) )
             % enum_container::size);
    }

    template<typename storage_type, int offset, int N>
    static void clear(storage_type& data) {
        data -= get<storage_type, offset, N>(data) *
            (offset * Pow<int, enum_container::size, N>::result);
    }

    template<typename storage_type, int offset, int N>
    static void set(storage_type& data, inner_type value) {
        clear<storage_type, offset, N>(data);
        data += value * (offset * Pow<int, enum_container::size, N>::result);
    }

    template<typename storage_type, int offset, int N>
    static void set_no_clear(storage_type& data, inner_type value) {
        data += value * offset * Pow<int, enum_container::size, N>::result;
    }

    template<typename storage_type, int offset, int N>
    static void next(storage_type& data) {
        data += offset * Pow<int, enum_container::size, N>::result;
    }

    template<typename storage_type, int offset, int N>
    static void prev(storage_type& data) {
        data -= offset * Pow<int, enum_container::size, N>::result;
    }
};

template<int _size, int _offset, typename t>
struct Conf {
    static const size_t size = _size;
    static const size_t offset = _offset;
    typedef t type;
};

template < int prev_size,
           int prev_offset,
           typename prev_map,
           typename head,
           typename... tail
>
struct StructModel_r :
    public
    StructModel_r <
        head::size, // size
        prev_offset * prev_size, // offset

        typename boost::mpl::insert < // map
            prev_map,
            boost::mpl::pair<
                typename head::tag,
                Conf<head::size, // size
                     prev_offset * prev_size, // offset
                     head
                >
            >
        >::type,

        tail...
> {
    typedef StructModel_r <
            head::size, // size
            prev_offset * prev_size, // offset

            typename boost::mpl::insert < // map
                prev_map,
                boost::mpl::pair<
                    typename head::tag,
                    Conf<head::size, // size
                         prev_offset * prev_size, // offset
                         head
                    >
                >
            >::type,
            tail...
    > _tail;

    static const size_t size = head::size * _tail::size;

    typedef typename _tail::type_map type_map;
};

template < int prev_size,
           int prev_offset,
           typename prev_map,
           typename head
>
struct StructModel_r<
    prev_size,
    prev_offset,
    prev_map,
    head
> {
    static const size_t size = head::size;

    typedef typename boost::mpl::insert < // map
        prev_map,
        boost::mpl::pair<
            typename head::tag,
            Conf<head::size, // size
                 prev_offset * prev_size, // offset
                 head
            >
        >
    >::type type_map;
};

template < typename... args >
struct StructModel :
public StructModel_r <
    1,
    1,
    boost::mpl::map<>,  args...
> {
    typedef StructModel_r < 1, 1, boost::mpl::map<>,  args...> _tail;
    typedef typename _tail::type_map type_map;
};

template < typename head, typename... tail >
struct UnionModel : private UnionModel< tail... > {
    typedef UnionModel< tail... > _tail;

    static const size_t size = head::size > _tail::size ? head::size : _tail::size;

    typedef typename boost::mpl::insert <
        typename _tail::type_map,
        boost::mpl::pair<
            typename head::tag,
            Conf< head::size,
                  1, // local offset in union is always 1
                  head
            >
        >
    >::type type_map;
};

template < typename head >
struct UnionModel<head> {
    typedef boost::mpl::map<
        boost::mpl::pair<
            typename head::tag,
            Conf< head::size,
                  1, // local offset in union is always 1
                  head
            >
        >
    > type_map;

    static const size_t size = head::size;
};

template < template <typename...> class model,
           typename... args>
struct Walker: public model< args...> {
    typedef typename model< args...>::type_map type_map;

    template<typename tag>
    struct Mapped_scope {
        typedef typename boost::mpl::at<type_map, tag>::type type;
    };

    template<int offset, typename map, typename head_tag, typename... tail_tag>
    struct Mapped_scope_deep_r :
        public
            Mapped_scope_deep_r<
                boost::mpl::at<
                    map,
                    head_tag
                >::type::offset,
                typename boost::mpl::at<
                    map,
                    head_tag
                >::type::type::type_map,
                tail_tag...
        > {

        typedef Mapped_scope_deep_r<
            boost::mpl::at<
                map,
                head_tag
            >::type::offset,
            typename boost::mpl::at<
                map,
                head_tag
            >::type::type::type_map,
            tail_tag...
        > _tail;

        typedef Conf<
            _tail::type::size,
            offset * _tail::type::offset,
            typename _tail::type::type
        > type;
    };

    template<int offset, typename map, typename head_tag>
    struct Mapped_scope_deep_r<offset, map, head_tag> {
        typedef typename boost::mpl::at<map, head_tag>::type _type;

        typedef Conf<
            _type::size,
            offset * _type::offset,
            typename _type::type
        > type;
    };

    template<typename... Tags>
    struct Mapped_scope_deep :
        public Mapped_scope_deep_r<1, type_map, Tags...> {
        typedef typename Mapped_scope_deep_r<
            1,
            type_map,
            Tags...
        >::type type;
    };
};

template < typename _tag,
           typename... args>
struct EnumStruct : public Walker< StructModel, args...> {
    typedef _tag tag;
    typedef Walker< StructModel, args...> walker;
    typedef typename walker::type_map type_map;

    static const size_t size = walker::size;
};

template < typename _tag,
           typename... args>
struct EnumUnion : public Walker< UnionModel, args...> {
    typedef _tag tag;
    typedef Walker< UnionModel, args...> walker;
    typedef typename walker::type_map type_map;

    static const size_t size = walker::size;
};

template < typename storage_type, typename... args>
struct CompressedEnums : public Walker< StructModel, args... > {
    typedef Walker< StructModel, args... > W;
#define SCOPE W::template Mapped_scope_deep<tags...>::type::
#define METHOD W::template Mapped_scope_deep<tags...>::type::type:: template
#define INNER_TYPE typename W::template Mapped_scope_deep<tags...>::type::type::inner_type
#define OFFSET SCOPE offset

    template<typename... tags> int
    get_offset() const {
        return SCOPE offset;
    }

    template<typename... tags> int
    get_size() const {
        return SCOPE size;
    }

    // Regular enum access methods
    template<typename... tags> INNER_TYPE
    get() const {
        return METHOD get<storage_type, OFFSET>(data);
    }

    template<typename... tags> void
    set(INNER_TYPE value) {
        METHOD set<storage_type, OFFSET>(data, value);
    }

    template<typename... tags> void
    set_no_clear(INNER_TYPE value) {
        METHOD set_no_clear<storage_type, OFFSET>(data, value);
    }

    template<typename... tags> void
    clear() {
        METHOD clear<storage_type, OFFSET>(data);
    }

    template<typename... tags> void
    next() {
        METHOD next<storage_type, OFFSET>(data);
    }

    template<typename... tags> void
    prev() {
        METHOD prev<storage_type, OFFSET>(data);
    }

    // Regular enum-array access methods, compile time index
    template<int N, typename... tags> INNER_TYPE
    get() const {
        return METHOD get<storage_type, OFFSET, N>(data);
    }

    template<int N, typename... tags> void
    set(INNER_TYPE value) {
        METHOD set<storage_type, OFFSET, N>(data, value);
    }

    template<int N, typename... tags> void
    set_no_clear(INNER_TYPE value) {
        METHOD set_no_clear<storage_type, OFFSET, N>(data, value);
    }

    template<int N, typename... tags> void
    clear() {
        METHOD clear<storage_type, OFFSET, N>(data);
    }

    template<int N, typename... tags> void
    next() {
        METHOD next<storage_type, OFFSET, N>(data);
    }

    template<int N, typename... tags> void
    prev() {
        METHOD prev<storage_type, OFFSET, N>(data);
    }

#undef SCOPE
#undef METHOD
#undef INNER_TYPE
#undef OFFSET
    storage_type data;
};


// tests starts here
struct e1{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e2{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e3{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e4{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };

struct e21{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e22{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e23{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };

struct e31{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e32{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e33{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };

struct e321{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e322{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e323{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };

struct e3221{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e3222{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e3223{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };
struct e3224{ static const size_t size = 2; static const size_t max = 1; enum E { e0 = 0, E1 = 1 }; };

struct Abc {
    static const size_t size = 3;
    static const size_t max = 2;
    enum E { A = 0, B = 1, C = 2 };
};
struct YesNoMaby {
    static const size_t size = 3;
    static const size_t max = 2;
    enum E { Yes = 0, No = 1, Maby = 2 };
};

std::ostream& operator<<(std::ostream& o, Abc::E e){
    switch(e){
        case Abc::A: o << "A"; return o;
        case Abc::B: o << "B"; return o;
        case Abc::C: o << "C"; return o;
    }
}

std::ostream& operator<<(std::ostream& o, YesNoMaby::E e){
    switch(e){
        case YesNoMaby::Yes:  o << "Yes"; return o;
        case YesNoMaby::No:   o << "No"; return o;
        case YesNoMaby::Maby: o << "Maby"; return o;
    }
}

#define print_size_offset(var, leaf, ...) \
    std::cout << leaf #var "<" #__VA_ARGS__ ">" " = (" << \
        var.get_size<__VA_ARGS__>() << ", " << \
        var.get_offset<__VA_ARGS__>() << ")" << std::endl

int main(int argc, const char *argv[])
{
    using namespace std;

    CompressedEnums<
        unsigned,
        CompressedEnum<e1>,
        CompressedEnum<e2>,
        CompressedEnum<e3>,
        CompressedEnum<e4>
    > ce1;

    print_size_offset(ce1, "*", e1);
    print_size_offset(ce1, "*", e2);
    print_size_offset(ce1, "*", e3);
    print_size_offset(ce1, "*", e4);
    std::cout << "-------------------" << std::endl;

    CompressedEnums<
        unsigned,
        CompressedEnum<e1>,
        EnumStruct<e2,
            CompressedEnum<e21>,
            CompressedEnum<e22>,
            CompressedEnum<e23>
        >,
        CompressedEnum<e3>,
        CompressedEnum<e4>
    > ce2;

    ce2.set<e1>(e1::E1);
    e1::E ee = ce2.get<e1>();
    std::cout << ee << std::endl;

    print_size_offset(ce2, "*", e1);
    print_size_offset(ce2, " ", e2);
    print_size_offset(ce2, "*", e2, e21);
    print_size_offset(ce2, "*", e2, e22);
    print_size_offset(ce2, "*", e2, e23);
    print_size_offset(ce2, "*", e3);
    print_size_offset(ce2, "*", e4);
    std::cout << "-------------------" << std::endl;

    CompressedEnums<
        unsigned,
        CompressedEnum<e1>,
        EnumStruct<e2,
            CompressedEnum<e21>,
            CompressedEnum<e22>,
            CompressedEnum<e23>
        >,
        EnumStruct<e3,
            CompressedEnum<e31>,
            EnumStruct<e32,
                CompressedEnum<e321>,
                CompressedEnum<e322>,
                CompressedEnum<e323>
            >,
            CompressedEnum<e33>
        >,
        CompressedEnum<e4>
    > ce3;

    print_size_offset(ce3, "*", e1);
    print_size_offset(ce3, " ", e2);
    print_size_offset(ce3, "*", e2, e21);
    print_size_offset(ce3, "*", e2, e22);
    print_size_offset(ce3, "*", e2, e23);
    print_size_offset(ce3, " ", e3);
    print_size_offset(ce3, "*", e3, e31);
    print_size_offset(ce3, " ", e3, e32);
    print_size_offset(ce3, "*", e3, e32, e321);
    print_size_offset(ce3, "*", e3, e32, e322);
    print_size_offset(ce3, "*", e3, e32, e323);
    print_size_offset(ce3, "*", e3, e33);
    print_size_offset(ce3, "*", e4);
    std::cout << "-------------------" << std::endl;

    CompressedEnums<
        unsigned,
        CompressedEnum<e1>,
        EnumStruct<e2,
            CompressedEnum<e21>,
            CompressedEnum<e22>,
            CompressedEnum<e23>
        >,
        EnumStruct<e3,
            CompressedEnum<e31>,
            EnumStruct<e32,
                CompressedEnum<e321>,
                EnumStruct<e322,
                    CompressedEnum<e3221>,
                    CompressedEnum<e3222>,
                    CompressedEnum<e3223>,
                    CompressedEnum<e3224>
                >,
                CompressedEnum<e323>
            >,
            CompressedEnum<e33>
        >,
        CompressedEnum<e4>
    > ce4;

    print_size_offset(ce4, "*", e1);
    print_size_offset(ce4, " ", e2);
    print_size_offset(ce4, "*", e2, e21);
    print_size_offset(ce4, "*", e2, e22);
    print_size_offset(ce4, "*", e2, e23);
    print_size_offset(ce4, " ", e3);
    print_size_offset(ce4, "*", e3, e31);
    print_size_offset(ce4, " ", e3, e32);
    print_size_offset(ce4, "*", e3, e32, e321);
    print_size_offset(ce4, " ", e3, e32, e322);
    print_size_offset(ce4, "*", e3, e32, e322, e3221);
    print_size_offset(ce4, " ", e3, e32, e322, e3222);
    print_size_offset(ce4, " ", e3, e32, e322, e3223);
    print_size_offset(ce4, " ", e3, e32, e322, e3224);
    print_size_offset(ce4, " ", e3, e32, e323);
    print_size_offset(ce4, "*", e3, e33);
    print_size_offset(ce4, "*", e4);
    std::cout << "-------------------" << std::endl;

    CompressedEnums<
        unsigned,
        CompressedEnum<e1>,
        EnumStruct<e2,
            CompressedEnum<e1>,
            CompressedEnum<e2>,
            CompressedEnum<e3>
        >,
        EnumStruct<e3,
            CompressedEnum<e1>,
            EnumStruct<e2,
                CompressedEnum<e1>,
                EnumStruct<e2,
                    CompressedEnum<e1>,
                    CompressedEnum<e2>,
                    CompressedEnum<e3>,
                    CompressedEnum<e4>
                >,
                CompressedEnum<e3>
            >,
            CompressedEnum<e3>
        >,
        CompressedEnum<e4>
    > ce5;

    print_size_offset(ce5, "*", e1);
    print_size_offset(ce5, " ", e2);
    print_size_offset(ce5, "*", e2, e1);
    print_size_offset(ce5, "*", e2, e2);
    print_size_offset(ce5, "*", e2, e3);
    print_size_offset(ce5, " ", e3);
    print_size_offset(ce5, "*", e3, e1);
    print_size_offset(ce5, " ", e3, e2);
    print_size_offset(ce5, "*", e3, e2, e1);
    print_size_offset(ce5, " ", e3, e2, e2);
    print_size_offset(ce5, "*", e3, e2, e2, e1);
    print_size_offset(ce5, " ", e3, e2, e2, e2);
    print_size_offset(ce5, " ", e3, e2, e2, e3);
    print_size_offset(ce5, " ", e3, e2, e2, e4);
    print_size_offset(ce5, " ", e3, e2, e3);
    print_size_offset(ce5, "*", e3, e3);
    print_size_offset(ce5, "*", e4);
    std::cout << "-------------------" << std::endl;

    ce5.set<e1>(e1::E1);
    std::cout << ce5.get<e1>() << std::endl;

    ce5.set<e2, e2>(e2::E1);
    std::cout << ce5.get<e2, e2>() << std::endl;

    ce5.set<e3, e2, e1>(e1::E1);
    std::cout << ce5.get<e3, e2, e1>() << std::endl;

    ce5.set<e3, e2, e2, e3>(e3::E1);
    std::cout << ce5.get<e3, e2, e2, e3>() << std::endl;

    CompressedEnums<
        unsigned,
        CompressedEnum<e1>,
        CompressedEnumArray<Abc, 5>,
        CompressedEnum<e3>
    > ce6;

    print_size_offset(ce6, "*", e1);
    print_size_offset(ce6, "*", Abc);
    print_size_offset(ce6, "*", e3);

    ce6.set<0, Abc>(Abc::A);
    ce6.set<1, Abc>(Abc::B);
    ce6.set<2, Abc>(Abc::C);
    ce6.set<3, Abc>(Abc::B);
    std::cout << ce6.get<0, Abc>() << std::endl;
    std::cout << ce6.get<1, Abc>() << std::endl;
    std::cout << ce6.get<2, Abc>() << std::endl;
    std::cout << ce6.get<3, Abc>() << std::endl;
    cout << "---" << endl;

    ce6.set<0, Abc>(Abc::B);
    ce6.set<1, Abc>(Abc::C);
    ce6.set<2, Abc>(Abc::A);
    ce6.set<3, Abc>(Abc::A);
    std::cout << ce6.get<0, Abc>() << std::endl;
    std::cout << ce6.get<1, Abc>() << std::endl;
    std::cout << ce6.get<2, Abc>() << std::endl;
    std::cout << ce6.get<3, Abc>() << std::endl;
    cout << "---" << endl;

    ce6.data = 0;
    for (int i = 0; i < ce6.get_size<Abc>(); i++) {
        std::cout << ce6.get<4, Abc>() <<
                     ce6.get<3, Abc>() <<
                     ce6.get<2, Abc>() <<
                     ce6.get<1, Abc>() <<
                     ce6.get<0, Abc>() <<
                     std::endl;
        ce6.next<0, Abc>();
    }
    cout << "---" << endl;

    CompressedEnums<
        unsigned,
        CompressedEnum<e1>,

        EnumUnion<e2,
            CompressedEnum<e1>,
            CompressedEnum<Abc>,
            CompressedEnum<YesNoMaby>
        >,
        CompressedEnum<e3>
    > ce7;

    print_size_offset(ce7, "*", e1);
    print_size_offset(ce7, "*", e2);
    print_size_offset(ce7, "*", e2, e1);
    print_size_offset(ce7, "*", e2, Abc);
    print_size_offset(ce7, "*", e2, YesNoMaby);
    print_size_offset(ce7, "*", e3);

    cout << "---" << endl;
    ce7.set<e2, Abc>(Abc::B);
    cout << ce7.get<e2, e1>() << " " << ce7.get<e2, Abc>() << " " << ce7.get<e2, YesNoMaby>() << endl;
    ce7.set<e2, Abc>(Abc::A);
    cout << ce7.get<e2, e1>() << " " << ce7.get<e2, Abc>() << " " << ce7.get<e2, YesNoMaby>() << endl;
    ce7.set<e2, YesNoMaby>(YesNoMaby::Maby);
    cout << ce7.get<e2, e1>() << " " << ce7.get<e2, Abc>() << " " << ce7.get<e2, YesNoMaby>() << endl;

    return 0;
}