# include <type_traits>
# include <cmath>
# include <cassert>
# include <iterator>
# include <sstream>
# include <algorithm>
#include <iostream>

namespace digits
{   
    // Default base type traits, infer base size from the number of character
    template <char... Chars>
    struct base_char_traits
    {
        // Mandatory for the digits container, maybe someone want to make
        // another traits with  wchar ?
        typedef char value_type;

        // Size of the base, computed from the number of characters passed
        static constexpr size_t size = sizeof...(Chars);

        // Array of characters use to print the output
        static constexpr value_type characters[sizeof...(Chars)]  = { Chars... };
    };

    // **sigh**
    // Instantiation of the array of character; otherwise there will be a link
    // error
    template <char... Chars>
    constexpr typename base_char_traits<Chars...>::value_type base_char_traits<Chars...>::characters[sizeof...(Chars)];

    // All your bases are belong to us !
    struct base2_traits : public base_char_traits<'0', '1'> { };
    struct base8_traits : public base_char_traits<'0', '1', '2', '3', '4', '5', '6', '7'> { };
    struct base10_traits : public base_char_traits<'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'> { };
    struct base12_traits : public base_char_traits<'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b'> { };
    struct base16_traits : public base_char_traits<'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'> { };


    // The digit container with the base traits and the type as template
    // parameter.
    //     
    // It is a read only container that allows you to iterate on the digit in 
    // the base given as template parameter.
    template <typename BaseTraits, typename T = unsigned long>
    class digits
    {
    public:

        // Assert that T fullfil our criteria
        static_assert(std::is_integral<T>(), "T must be integral");
        static_assert(std::is_unsigned<T>(), "T must be unsigned");        

        // Value type is defined by the base traits to allow the use of more
        // complicated digit type (here we only handle char)
        typedef typename BaseTraits::value_type value_type;

        // Reference type is defined to be the same as value type because this is an immutable container
        typedef typename BaseTraits::value_type reference;

        // The size type of the container, i.e. the type that will be used to
        // express a digit position
        typedef size_t size_type;

        // Iterator class allowing one to walk through the number's digit from 
        // the lowest to the highest 
        class iterator 
        { 
        public:

            // Type used to return iterator substraction result
            typedef size_t difference_type;

            // type used by algorithms (e.g. find)
            typedef typename digits::reference reference;

            // type used by algorithms (e.g. find)
            typedef typename digits::reference pointer;

            // type returned by operator*
            typedef typename digits::value_type value_type;

            // Iterator category, here we can randomly walk in the digit
            typedef std::random_access_iterator_tag iterator_category;

            // Mandatory default constructor, initialize to an invalid iterator
            iterator()
            {
                _current_digit = 0;
                _digits = nullptr;
            }

            // Build an iterator other a digits container starting at digit
            iterator(const digits* digits, size_type digit)
            {
                _current_digit = digit;
                _digits = digits;
            }

            iterator(const iterator& it) :
            iterator(it._digits, it._current_digit)
            {
                
            }

            // Move using swap idiom
            iterator(iterator&& it) :
            iterator()
            {
                swap(*this, it);
            }

            ~iterator()
            {
                _digits = nullptr;
            }

            // assignment iterator using swap idiom
            iterator& operator=(iterator it)
            {
                swap(*this, it);
                return *this;
            }

            // Comparison operators
            bool operator==(const iterator& it) const
            {
                assert(_digits == it._digits);
                return (_current_digit == it._current_digit);
            }

            bool operator!=(const iterator& it) const
            {
                return !(operator==(it));
            }

            bool operator<(const iterator& it) const
            {
                assert(_digits == it._digits);
                return (_current_digit < it._current_digit);
            }

            bool operator>(const iterator& it) const
            {
                assert(_digits == it._digits);
                return (_current_digit > it._current_digit);
            }

            bool operator<=(const iterator& it) const
            {
                assert(_digits == it._digits);
                return (_current_digit <= it._current_digit);
            }

            bool operator>=(const iterator& it) const
            {
                assert(_digits == it._digits);
                return (_current_digit >= it._current_digit);
            }

            // Moving the iterator
            iterator& operator++()
            {
                ++_current_digit;
                return *this;
            }

            iterator operator++(int)
            {
                iterator it(*this);
                operator++();
                return it;
            }

            iterator& operator--()
            {
                --_current_digit;
                return  *this;
            }

            iterator operator--(int)
            {
                iterator it(*this);
                operator--();
                return it;
            }

            iterator& operator+=(size_type increment)
            {
                _current_digit += increment;
                return *this;
            }

            iterator operator+(size_type increment) const
            {
                iterator it(*this);
                return (it += increment);
            }

            friend iterator operator+(size_type increment, const iterator& it)
            {
                return (it + increment);
            }

            iterator& operator-=(size_type decrement)
            {
                _current_digit -= decrement;
                return *this;
            }

            iterator operator-(size_type decrement) const
            {
                iterator it(*this);
                return (it - decrement);
            }

            difference_type operator-(const iterator& it) const
            {
                assert(_digits == it._digits);
                return (_current_digit - it._current_digit);
            }

            value_type operator*() const
            {
                assert(nullptr != _digits);

                return _digits->digit(_current_digit);
            }           

            friend void swap(iterator& first, iterator& second)
            {
                std::swap(first._digits, second._digits); 
                std::swap(first._current_digit, second._current_digit);
            }
            
        private:

            // The current digit we will be printing when calling operator*().
            // From 0 to (digits.size() - 1)
            size_t _current_digit;

            // The digit container we're working on.
            const digits* _digits;
        };      
        
        // Define the reverse iterator, that will allow to iterator from the
        // highest digit to the lowest (more printing friendly)
        typedef std::reverse_iterator<iterator> reverse_iterator;

        // Default constructor use 0 as a number
        digits() 
        {
            _number = 0;
        }

        // Build a container over a number given as parameter
        digits(T number) 
        {
            _number = number;
        }

        digits(const digits& copy) :
        digits(copy._number)
        {            
        }

        // Move constructor using swap idiom
        digits(digits&& move) :
        digits()
        {
            swap(*this, move);
        }

        ~digits()
        {
        }

        // Retrieve the digit character
        value_type digit(size_t digit) const
        {
            assert(digit < size());
            constexpr size_t base = BaseTraits::size;

            // @warning
            // llround is mandatory because of a double to unsigned long problem
            T modul = static_cast<T>(llround(std::pow(base, digit + 1)));
            T div =  static_cast<T>(llround(std::pow(base, digit)));
            T digit_index = (_number % modul) / div;         

            return BaseTraits::characters[digit_index];
        }

        // Assignment using swap idiom
        digits& operator=(digits assign)
        {
            swap(_number, assign._number);
        }

        // Comparison operator
        bool operator==(const digits& comp) const
        {
            return (_number == comp._number);
        }

        bool operator!=(const digits& comp) const
        {
            return !(operator==(comp));
        }       

        // Iterators creation
        iterator begin() const
        {
            return iterator(this, static_cast<size_type>(0));
        }

        iterator cbegin() const
        {
            return begin();
        }

        iterator end() const
        {
            return iterator(this, size());
        }

        iterator cend() const
        {
            return end();
        }

        reverse_iterator rbegin() const
        {
            return reverse_iterator(end());
        }

        reverse_iterator crbegin() const
        {
            return reverse_iterator(cend());
        }

        reverse_iterator rend() const
        {
            return reverse_iterator(begin());
        }

        reverse_iterator crend() const
        {
            return reverse_iterator(cbegin());
        }

        // swap function
        friend void swap(digits& first, digits& second)
        {
            std::swap(first._number, second._number);
        }

        // cast to string
        operator std::string () const
        {
            std::ostringstream stream;

            // print from high to low
            std::copy(rbegin(), rend(), 
                      std::ostream_iterator<value_type>(stream, ""));
            return stream.str();
        }

        // The number of digits of this _number
        size_type size() const
        {            
            const double log_number = std::log(_number);
            constexpr double log_base = std::log(BaseTraits::size);
            return  std::ceil(log_number / log_base);
        }

        // The maximum nulber of digits this type can have
        size_type max_size() const
        {
            constexpr double max_number = std::pow(2, sizeof(T) * 8);
            constexpr double log_max_number = std::log(max_number);
            constexpr double log_base = std::log(BaseTraits::size);
            return  log_max_number / log_base;
        }

    private:

        // The number we will iterate over the digits
        T _number;
    };
}

template <typename Iterator>
void find_and_print(Iterator begin, Iterator end, char value)
{
    auto it = std::find(begin, end, value);
    if (end == it)
    {
        std::cout << "Digit " << value << " not found" << std::endl;
    }
    else
    {
        std::cout << *it << " digit found at place " 
            << std::distance(begin, it)
            << std::endl;
        auto it2 = it;

        if (it2 == it)
        {
            std::cout << *it2 << " ==  " << *it << std::endl;
        }

    }
}

int main(int argc, char const *argv[])
{
    digits::digits<digits::base16_traits> dig(123456);
    digits::digits<digits::base2_traits> dig3(123456);
    digits::digits<digits::base10_traits> dig4(123456);
    auto dig2 = dig;

    for (auto digit: dig)
    {
        std::cout << "Digit: " << digit << std::endl;
    }

    std::copy(dig2.rbegin(), dig2.rend(), std::ostream_iterator<char>(std::cout, " "));
    std::cout << std::endl;
    std::copy(dig3.begin(), dig3.end(), std::ostream_iterator<char>(std::cout, " "));
    std::cout << std::endl;

    find_and_print(dig.begin(), dig.end(), 'e');
    find_and_print(dig2.begin(), dig2.end(), '0');
    find_and_print(dig3.rbegin(), dig3.rend(), '0');

    std::cout << "Dig: " << static_cast<std::string>(dig) << std::endl;
    std::cout << "Dig3: " << static_cast<std::string>(dig3) << std::endl;
    std::cout << "Dig4: " << static_cast<std::string>(dig4) << std::endl;
    return 0;
}