#include <istream>
#include <ostream>
#include <string>
#include <stdexcept>

#include <boost/numeric/ublas/matrix.hpp>

namespace BefungeInterpreter
{
        struct InterpreteException : public std::logic_error
        {
                InterpreteException(std::string const& w):
                        std::logic_error(w){}
        };

        boost::numeric::ublas::matrix<char> toMatrix(std::string const&);

        void process(boost::numeric::ublas::matrix<char>&, std::ostream&, std::istream&);
}

#include <ostream>

namespace BefungeInterpreter
{
        namespace Miscellaneous
        {
                enum class Direction
                {
                        right,
                        left,
                        up,
                        down
                };

                inline std::string toString(Direction const d)
                {
                #define makro(C) if(d == Direction::C) return #C;
                        makro(down)
                        makro(right)
                        makro(left)
                        makro(up)
                #undef makro
                }
        }
}

#include <boost/lexical_cast.hpp>

#include <iterator>
#include <vector>
#include <stack>

#define get_from_stack(C) auto C = stack.top();\
                          stack.pop();


boost::numeric::ublas::matrix<char> BefungeInterpreter::toMatrix(std::string const& s)
{
        boost::numeric::ublas::matrix<char> rval(1, 1);
        size_t X = 0, Y = 0;
        for(auto c : s)
                if(c == '\n')
                {
                        X = 0;
                        ++Y;
                        rval.resize(rval.size1(), Y + 1);
                }
                else
                {
                        if(X == rval.size1())
                                rval.resize(X + 1, rval.size2());
                        rval(X++, Y) = c;
                }

        return rval;
}

void makeStepNCheck(size_t &X, size_t &Y, BefungeInterpreter::Miscellaneous::Direction const dir, size_t const righter_bound, size_t const lower_bound)
{
        using BefungeInterpreter::Miscellaneous::Direction;

        size_t const before_x = X,
                     before_y = Y;

        bool failure = false;
        switch(dir)
        {
                case Direction::down:  failure = ++Y >= lower_bound; break;
                case Direction::right: failure = ++X >= righter_bound; break;
                case Direction::left:  failure = X-- == 0; break;
                case Direction::up:    failure = Y-- == 0; break;
                default: break;
        }
        if(failure)
        {
                throw BefungeInterpreter::InterpreteException("Reached end of direction - no instructions!\n"
                                                              "Position: (" + boost::lexical_cast<std::string>(before_x) + "|" + boost::lexical_cast<std::string>(before_y) + ")\n"
                                                              "Direction: " + toString(dir) + "\n"
                                                              "Bounds: (" + boost::lexical_cast<std::string>(righter_bound) + "|" + boost::lexical_cast<std::string>(lower_bound) + ")");
        }
}

void BefungeInterpreter::process(boost::numeric::ublas::matrix<char>& matrix, std::ostream& os, std::istream& is)
{
        using BefungeInterpreter::Miscellaneous::Direction;

        size_t X = 0,
               Y = 0;

        Direction direction{Direction::right};

        typedef unsigned long long stack_t;
        std::stack<stack_t> stack;

        bool string_mode = false;

        auto makeStepNCheck = std::bind(::makeStepNCheck,
                                        std::ref(X),
                                        std::ref(Y),
                                        std::cref(direction),
                                        std::placeholders::_1,
                                        std::placeholders::_2);

        for(bool exit = false;!exit;exit ? (void)0 : makeStepNCheck(matrix.size1(), matrix.size2()))
        {
                char const ch = matrix(X, Y);

#ifdef DEBUG
                std::cout << "Position: (" + boost::lexical_cast<std::string>(X) + "|" + boost::lexical_cast<std::string>(Y) + ") '" + std::string{ch} + "'\n";
#endif

                if(ch == '"')
                {
                        string_mode = !string_mode;
                        continue;
                }

                if(string_mode)
                        stack.push(ch);

                else
                        switch(ch)
                        {
                                /// MISCELLANEOUS *************************************************************
                                case '@':
                                        exit = true;
                                        break;

                                case ':':
                                        stack.push(stack.top());
                                        break;

                                case ' ':
                                        break;

                                case '#':
                                        makeStepNCheck(matrix.size1(), matrix.size2());
                                        break;

                                case '0':case '1':case '2':
                                case '3':case '4':case '5':
                                case '6':case '7':case '8':
                                case '9':

                                        stack.push(ch - '0');
                                        break;

                                case 'g':
                                {
                                        get_from_stack(y)
                                        get_from_stack(x)

                                        stack.push(matrix(x, y));
                                        break;
                                }
                                case 'p':
                                {
                                        get_from_stack(y)
                                        get_from_stack(x)
                                        get_from_stack(v)

                                        matrix(x, y) = v;
                                        break;
                                }

                                /// INPUT OPERATIONS ****
                                case '&': stack.push(*std::istream_iterator<stack_t>(is)); break;
                                case '~': stack.push(*std::istream_iterator<char>(is)); break;

                                /// DIRECTION OPERATIONS (not qualified ops!) *********************************

                                case '>': {direction = Direction::right; break;}
                                case '<': {direction = Direction::left; break;}
                                case 'v': {direction = Direction::down; break;}
                                case '^': {direction = Direction::up; break;}
                                case '?':
                                {
                                        std::vector<Direction> s;
                                        if(X) s.push_back(Direction::left);
                                        if(Y) s.push_back(Direction::up);
                                        if(Y < matrix.size2() - 1) s.push_back(Direction::down);
                                        if(X < matrix.size1() - 1) s.push_back(Direction::right);

                                        direction = s[rand() % s.size()];
                                        break;
                                }

                                /// BINARY OPERATIONS *********************************************************
                                case '+':
                                case '-':
                                case '*':
                                case '/':
                                case '%':
                                case '\\':
                                case '`':
                                {
                                        get_from_stack(a)
                                        get_from_stack(b)

                                        switch(ch)
                                        {
                                                case '+': stack.push(a + b); break;
                                                case '-': stack.push(b - a); break;
                                                case '*': stack.push(a * b); break;
                                                case '/': stack.push(a / b); break;
                                                case '%': stack.push(a % b); break;
                                                case '\\': stack.push(a); stack.push(b); break;
                                                case '`': stack.push(b > a ? 1 : 0);
                                                default:  break;
                                        }
                                        break;
                                }

                                /// UNARY OPERATIONS **********************************************************
                                case '!':
                                case '_':
                                case '|':
                                case '.':
                                case ',':
                                case '$':
                                {
                                        get_from_stack(a)

                                        switch(ch)
                                        {
                                                case '!': stack.push(a ? 0 : 1); break;
                                                case '_': direction = (a ? Direction::left : Direction::right); break;
                                                case '|': direction = (a ? Direction::up : Direction::down); break;
                                                case '.': os << a; break;
                                                case ',': os << static_cast<char>(a); break;
                                                default: break;
                                        }
                                        break;
                                }


                                default:
                                        throw InterpreteException("Unknown character in code!\n"
                                                                  "Character (ASCII): " + boost::lexical_cast<std::string>((int)ch) + "\n"
                                                                  "Character        : " + std::string(1, ch));
                        }
        }
}

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <sstream>
#include <fstream>

int main() try
{
        srand(time(nullptr));

        std::ostringstream stream;
        stream << ">25*\"!dlrow ,olleH\":v  \n"
                  "                 v:,_@ \n"
                  "                 >  ^    ";

        auto m = BefungeInterpreter::toMatrix(stream.str());
        BefungeInterpreter::process(m, std::cout, std::cin);
}
catch(BefungeInterpreter::InterpreteException const& b)
{
        std::cerr << "An interprete exception occured!\n"
                  << b.what();
}
catch(std::exception const& e)
{
        std::cerr << "A standard exception occured!\n"
                  << e.what() << '\n'
                  << "Terminating!";
        std::exit(-1);
}
catch(...)
{
        std::cerr << "An unknown exception occured!\n"
                     "Terminating!";
        std::exit(-2);
}