/* 
* File:   main.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 15:21
*/

#include <iostream>
#include <valarray>
#include <string>
#include <locale>
#include "Machine.h"

/*
* 
*/

// Печатает состояние машины на каждом шаге
void printState(const State& state);

int main(int argc, char** argv)
{
	// Программа взятая с википедии для вычитания двух чисел
	std::string prg_str[] = {
		"1 x",
		"2 >",
		"3 ? 4,5",
		"4 !",
		"5 <",
		"6 ? 5,7",
		"7 x",
		"8 >",
		"9 ? 8,1"
	};

	std::valarray<std::string> prg(prg_str,sizeof(prg_str)/sizeof(prg_str[0]));

	try
	{
		std::locale::global(std::locale(""));
		// Создание машины и запуск
		Machine(prg, "00111110111000", 8).Run(printState);
	}
	catch (std::exception& ex)
	{
		std::cout << ex.what() << std::endl;
	}

	system("pause");
	return 0;
}

void printState(const State& state)
{
	std::cout << state << std::endl;
}

/* 
 * File:   SyntaxMachineException.h
 * Author:
 *
 * Created on 12 Июнь 2013 г., 7:50
 */

#ifndef SYNTAXMACHINEEXCEPTION_H
#define	SYNTAXMACHINEEXCEPTION_H

#include "MachineException.h"

// Исключение при синтаксической ошибке программы
class SyntaxMachineException : public MachineException {
public:
    SyntaxMachineException(const std::string& msg);
    virtual ~SyntaxMachineException() throw();
private:

};

#endif	/* SYNTAXMACHINEEXCEPTION_H */

/* 
 * File:   SyntaxMachineException.cpp
 * Author:
 * 
 * Created on 12 Июнь 2013 г., 7:50
 */

#include "SyntaxMachineException.h"

SyntaxMachineException::SyntaxMachineException(const std::string& msg)
: MachineException(msg)
{
}

SyntaxMachineException::~SyntaxMachineException() throw()
{
}

/* 
 * File:   StopMachine.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 23:39
 */

#ifndef STOPMACHINE_H
#define	STOPMACHINE_H

#include "MachineException.h"

// Исключение при нормальном завершении программы

class StopMachineException : public MachineException {
public:
    StopMachineException();
    virtual ~StopMachineException() throw();
private:

};

#endif	/* STOPMACHINE_H */

/* 
 * File:   StopMachine.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 23:39
 */

#include "StopMachineException.h"

StopMachineException::StopMachineException()
: MachineException("Останов программы")
{
}

StopMachineException::~StopMachineException() throw()
{
}

/* 
 * File:   ExitCommand.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 23:20
 */

#ifndef EXITCOMMAND_H
#define	EXITCOMMAND_H

#include "Command.h"

// Комманда останов программы

class StopCommand : public Command {
public:
    StopCommand(size_t line);
    virtual ~StopCommand();
    virtual void execute(State& state) const;
    virtual std::string toString() const;
private:

};

#endif	/* EXITCOMMAND_H */

/* 
 * File:   ExitCommand.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 23:20
 */

#include <sstream>
#include "StopCommand.h"
#include "StopMachineException.h"

StopCommand::StopCommand(size_t cur)
: Command(cur, STOP)
{
}

StopCommand::~StopCommand()
{
}

void StopCommand::execute(State& state) const
{
    state.last = state.line;
    throw StopMachineException();
}

std::string StopCommand::toString() const
{
    std::stringstream sstr;
    sstr << _line << ' ' << static_cast<char> (_op);
    return sstr.str();
}

/* 
 * File:   State.h
 * Author:
 *
 * Created on 12 Июнь 2013 г., 0:09
 */

#ifndef STATE_H
#define	STATE_H

#include <cstddef>
#include <deque>
#include <string>
#include <iostream>
#include "MachineException.h"

typedef std::deque<bool> tape_t;

class Program;

// Состояние машины

struct State {
    State(tape_t::size_type pos, const tape_t& data, size_t line, Program* program = 0);
    // Можно задать данные ввиде строки, состоящей из '0' и '1'
    State(tape_t::size_type pos, const std::string& data, size_t line, Program* program = 0);
    // "Бесконечная" лента
    tape_t tape;
    // Позиция указателя
    tape_t::size_type pos;
    // Текущая инструкция и предыдущая
    size_t line, last;
    // Номер шага
    size_t step;
    // Указатель на программу, если нужна
    Program * program;
};

std::ostream& operator<<(std::ostream& out, const State& state);

#endif	/* STATE_H */

#include "State.h"
#include "Program.h"

State::State(tape_t::size_type pos, const tape_t& data, size_t line, Program* program)
: pos(pos)
, tape(data)
, line(line)
, last(0)
, step(0)
, program(program)
{
};

State::State(tape_t::size_type pos, const std::string& data, size_t line, Program* program)
: pos(pos)
, line(line)
, last(0)
, step(0)
, program(program)
{
    for (std::string::size_type i = 0, end = data.length(); i < end; ++i)
    {
        switch (data[i])
        {
        case '0':
            tape.push_back(false);
            break;
        case '1':
            tape.push_back(true);
            break;
        default:
            throw MachineException("Входные данные должны состоять из нулей и единиц");
        }
    }
}

std::ostream& operator<<(std::ostream& out, const State& state)
{
    out << "Шаг: " << state.step << std::endl;
    out << std::string(state.pos, ' ') << 'V' << std::endl;
    for (tape_t::size_type i = 0, end = state.tape.size(); i < end; ++i)
    {
        out << state.tape[i];
    }
    if (state.program)
    {
        out << "   |   " << (*state.program)[state.line]->toString() << std::endl;
    }
    return out;
}

/* 
 * File:   MoveCommand.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 22:55
 */

#ifndef MOVECOMMAND_H
#define	MOVECOMMAND_H

#include "Command.h"

// Комманды типа a op b

class SimpleCommand : public Command {
public:
    SimpleCommand(size_t line, commands op, size_t to);
    virtual ~SimpleCommand();
    virtual void execute(State& state) const;
    virtual std::string toString() const;
    // Инструкция, на которую переходит выполнение после комманды
    size_t to() const;
protected:
    size_t _to;
};

#endif	/* MOVECOMMAND_H */

/* 
 * File:   MoveCommand.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 22:55
 */

#include <sstream>
#include "SimpleCommand.h"

SimpleCommand::SimpleCommand(size_t cur, commands op, size_t to)
: Command(cur, op)
, _to(to)
{
}

SimpleCommand::~SimpleCommand()
{
}

size_t SimpleCommand::to() const
{
    return _to;
}

void SimpleCommand::execute(State& state) const
{
    state.last = state.line;
    state.line = this->_to;
}

std::string SimpleCommand::toString() const
{
    std::stringstream sstr;
    sstr << _line << ' ' << static_cast<char> (_op) << ' ' << _to;
    return sstr.str();
}

/* 
 * File:   SetCommand.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 23:09
 */

#ifndef SETCOMMAND_H
#define	SETCOMMAND_H

#include "SimpleCommand.h"

// Комманда установки метки

class SetCommand : public SimpleCommand {
public:
    SetCommand(size_t line, size_t to);
    virtual ~SetCommand();
    virtual void execute(State& state) const;
private:
};

#endif	/* SETCOMMAND_H */

/* 
 * File:   SetCommand.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 23:09
 */

#include "SetCommand.h"
#include "RuntimeMachineException.h"

SetCommand::SetCommand(size_t cur, size_t to)
: SimpleCommand(cur, SET, to)
{
}

SetCommand::~SetCommand()
{
}

void SetCommand::execute(State& state) const
{
    if (state.tape[state.pos])
    {
        throw RuntimeMachineException("Нельзя записать в помеченное поле", state);
    }
    state.tape[state.pos] = true;
    SimpleCommand::execute(state);
}

/* 
 * File:   RuntimeMachineException.h
 * Author:
 *
 * Created on 12 Июнь 2013 г., 7:50
 */

#ifndef RUNTIMEMACHINEEXCEPTION_H
#define	RUNTIMEMACHINEEXCEPTION_H

#include "MachineException.h"
#include "State.h"

// Исключение времени выполнения для машины

class RuntimeMachineException : public MachineException {
public:
    RuntimeMachineException(const std::string& msg, const State& state);
    virtual ~RuntimeMachineException() throw();
    // Возвращает состояние машины
    State state() const;
private:
    State _state;
};

#endif	/* RUNTIMEMACHINEEXCEPTION_H */

/* 
 * File:   RuntimeMachineException.cpp
 * Author:
 * 
 * Created on 12 Июнь 2013 г., 7:50
 */

#include "RuntimeMachineException.h"

RuntimeMachineException::RuntimeMachineException(const std::string& msg, const State& state)
: MachineException(msg)
, _state(state)
{
}

RuntimeMachineException::~RuntimeMachineException() throw()
{
}

State RuntimeMachineException::state() const
{
    return _state;
}

/* 
 * File:   program.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 16:39
 */

#ifndef PROGRAM_H
#define	PROGRAM_H

#include <valarray>
#include <memory>
#include "Command.h"

// Программа. Содержит список инструкций. Где каждая комманда представлена своим класом

class Program {
public:
    // Конструктор. принимает массив строк программы
    Program(const std::valarray<std::string>& prog);
    virtual ~Program();
    // Возвращает указатель на комманду по номеру строки
    const Command* operator [](size_t line) const;
private:
    Program(const Program& orig);
    Command* createCommand(const std::string& cmd) const;
    template<class T> T convert(const std::string& str) const;
    std::valarray<std::shared_ptr<Command > > _commands;
};

#endif	/* PROGRAM_H */

/* 
* File:   program.cpp
* Author:
* 
* Created on 11 Июнь 2013 г., 16:39
*/

#include <sstream>
#include <typeinfo>
#include <regex>
#include "MachineException.h"
#include "SyntaxMachineException.h"
#include "MoveLeftCommand.h"
#include "MoveRightCommand.h"
#include "IfCommand.h"
#include "SetCommand.h"
#include "ClearCommand.h"
#include "StopCommand.h"
#include "Program.h"

Program::Program(const std::valarray<std::string>& prog_str)
	: _commands(prog_str.size())
{
	for (size_t i = 0, end = prog_str.size(); i < end; ++i)
	{
		auto ptr = std::shared_ptr<Command>(createCommand(prog_str[i]));
		if (ptr->line() != i + 1)
		{
			throw SyntaxMachineException(std::string("Неверный номер строки программы(нумерация не по порядку): ") + prog_str[i]);
		}
		_commands[i] = ptr;
	}
}

Program::~Program()
{
}

const Command* Program::operator [](size_t line) const
{
	if (line < 1 || line > _commands.size())
	{
		std::stringstream sstr;
		sstr<<line;
		throw MachineException(std::string("Неверный номер строки: ") + sstr.str());
	}
	return _commands[line - 1].get();
}

Command* Program::createCommand(const std::string& cmd) const
{
	// Регулярные выражения для проверки синтаксиса
	static const std::regex simpleCommand("^\\s*(\\d{1,5})\\s*([VvXx<>])\\s*(\\d{1,5}){0,1}\\s*$");
	static const std::regex ifCommand("^\\s*(\\d{1,5})\\s+(\\?)\\s+(\\d{1,5})\\s*,\\s*(\\d{1,5})\\s*$");
	static const std::regex stopCommand("^\\s*(\\d{1,5})\\s*!\\s*$");
	std::smatch m;
	if (std::regex_match(cmd, m, simpleCommand))
	{
		std::string currentStr = m[1],
			commandStr = m[2],
			toStr = m[3];
		unsigned int current = convert<unsigned int>(currentStr),
			to = toStr.empty()?current+1:convert<unsigned int>(toStr);
		switch (commandStr[0])
		{
		case 'V':
		case 'v':
			return new SetCommand(current, to);
		case 'X':
		case 'x':
			return new ClearCommand(current, to);
		case '<':
			return new MoveLeftCommand(current, to);
		case '>':
			return new MoveRightCommand(current, to);
			break;
		}
	}
	else if (std::regex_match(cmd, m, ifCommand))
	{
		std::string currentStr = m[1],
			commandStr = m[2],
			falseNoStr = m[3],
			trueNoStr = m[4];
		size_t current = convert<size_t>(currentStr),
			falseLine = convert<size_t>(falseNoStr),
			trueLine = convert<size_t>(trueNoStr);
		return new IfCommand(current, falseLine, trueLine);
	}
	else if (std::regex_match(cmd, m, stopCommand))
	{
		std::string currentStr = m[1];
		size_t current = convert<size_t>(currentStr);
		return new StopCommand(current);
	}
	else
	{
		throw SyntaxMachineException(std::string("Неверная комманда: '") + cmd + "'");
	}
	return 0;
}

template<class T> T Program::convert(const std::string& str) const
{
	std::istringstream sstr(str);
	T result;
	sstr >> result;
	if (sstr.fail())
	{
		throw MachineException(std::string("Ошибка конвертации('") + str + "' в " + typeid (T).name() + ")");
	}
	return result;
}

/* 
 * File:   MoveRightCommand.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 23:05
 */

#ifndef MOVERIGHTCOMMAND_H
#define	MOVERIGHTCOMMAND_H

#include "SimpleCommand.h"

// Класс-комманда сдвига вправо

class MoveRightCommand : public SimpleCommand {
public:
    MoveRightCommand(size_t line, size_t to);
    virtual ~MoveRightCommand();
    virtual void execute(State& state) const;
private:

};

#endif	/* MOVERIGHTCOMMAND_H */

/* 
 * File:   MoveRightCommand.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 23:05
 */

#include "MoveRightCommand.h"

MoveRightCommand::MoveRightCommand(size_t cur, size_t to)
: SimpleCommand(cur, RIGHT, to)
{
}

MoveRightCommand::~MoveRightCommand()
{
}

void MoveRightCommand::execute(State& state) const
{
    if (++state.pos == state.tape.size())
    {
        state.tape.push_back(false);
    }
    SimpleCommand::execute(state);
}

/* 
 * File:   MoveLeftCommand.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 22:15
 */

#ifndef MOVELEFTCOMMAND_H
#define	MOVELEFTCOMMAND_H

#include "SimpleCommand.h"

// Класс-комманда сдвига влево

class MoveLeftCommand : public SimpleCommand {
public:
    MoveLeftCommand(size_t line, size_t to);
    virtual ~MoveLeftCommand();
    virtual void execute(State& state) const;
private:

};

#endif	/* MOVELEFTCOMMAND_H */

/* 
 * File:   MoveLeftCommand.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 22:15
 */

#include "MoveLeftCommand.h"
#include "RuntimeMachineException.h"

MoveLeftCommand::MoveLeftCommand(size_t cur, size_t to)
: SimpleCommand(cur, LEFT, to)
{
}

MoveLeftCommand::~MoveLeftCommand()
{
}

void MoveLeftCommand::execute(State& state) const
{
    if (!state.pos)
    {
        state.tape.push_front(false);
    }
    else
    {
        --state.pos;
    }
    SimpleCommand::execute(state);
}

/* 
 * File:   machine_error.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 15:28
 */

#ifndef MACHINE_ERROR_H
#define	MACHINE_ERROR_H

#include <exception>
#include <string>

// Базовый класс-исключение для работы машины

class MachineException : public std::exception {
public:
    MachineException(const std::string& msg);
    virtual ~MachineException() throw();
    virtual const char* what() const throw();
private:
    std::string message;
};

#endif	/* MACHINE_ERROR_H */

/* 
 * File:   machine_error.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 15:28
 */

#include "MachineException.h"

MachineException::MachineException(const std::string& msg)
:message(msg)
{
}

MachineException::~MachineException() throw()
{
}

const char* MachineException::what() const throw()
{
    return message.c_str();
}

/* 
 * File:   machine.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 16:11
 */

#ifndef MACHINE_H
#define	MACHINE_H

#include <valarray>
#include <string>
#include "State.h"
#include "Program.h"

// Машина

class Machine {
public:
    // Тип для функции обратного вызова
    typedef void (*callback)(const State& state);
    Machine(const std::valarray<std::string>& program, const std::string& data, std::string::size_type pos);
    virtual ~Machine();
    // Запускает машину на выполнение. Если в качестве аргумента передана функция то вызывает ее на каждом шаге
    State Run(callback func = 0);
private:
    // Состояние машины
    State _state;
    // Программа
    Program _program;
};

#endif	/* MACHINE_H */

/* 
 * File:   machine.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 16:11
 */

#include "StopMachineException.h"
#include "RuntimeMachineException.h"
#include "Machine.h"

Machine::Machine(const std::valarray<std::string>& program, const std::string& data, std::string::size_type pos)
: _program(program)
, _state(pos, data, 1, &_program)
{
}

Machine::~Machine()
{
}

State Machine::Run(callback func)
{
    try
    {
        if (func)
        {
            func(_state);
        }
        // Цикл выполнения. Выход по исключению
        while (true)
        {
            _program[_state.line]->execute(_state);
            ++_state.step;
            if (func)
            {
                func(_state);
            }
        }
    }
    catch (StopMachineException&)
    {
        // В случае нормального завершения программы
    }
    catch (MachineException& ex)
    {
        throw RuntimeMachineException(ex.what(), _state);
    }
    catch (...)
    {
        throw;
    }
    return _state;
}

/* 
 * File:   IfCommand.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 23:16
 */

#ifndef IFCOMMAND_H
#define	IFCOMMAND_H

#include "Command.h"

// Класс-комманда условного перехода

class IfCommand : public Command {
public:
    IfCommand(size_t cur, size_t falseLine, size_t trueLine);
    virtual ~IfCommand();
    // Строка перехода если нет метки
    size_t falseLine() const;
    // Строка перехода если есть метка
    size_t trueLine() const;
    virtual void execute(State& state) const;
    virtual std::string toString() const;
private:
    size_t _falseLine, _trueLine;
};

#endif	/* IFCOMMAND_H */

/* 
 * File:   IfCommand.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 23:16
 */

#include <sstream>
#include "IfCommand.h"

IfCommand::IfCommand(size_t cur, size_t falseLine, size_t trueLine)
: Command(cur, IF)
, _falseLine(falseLine)
, _trueLine(trueLine)
{
}

IfCommand::~IfCommand()
{
}

void IfCommand::execute(State& state) const
{
    state.last = state.line;
    if (state.tape[state.pos])
    {
        state.line = _trueLine;
    }
    else
    {
        state.line = _falseLine;
    }
}

std::string IfCommand::toString() const
{
    std::stringstream sstr;
    sstr << _line << ' ' << static_cast<char> (_op) << ' ' << _falseLine << ',' << _trueLine;
    return sstr.str();
}

/* 
 * File:   command.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 15:24
 */

#ifndef COMMAND_H
#define	COMMAND_H

#include "State.h"

// Базовый абстрактный класс для комманд

class Command {
public:
    // Типы комманд

    enum commands {
        STOP = '!',
        SET = 'V',
        CLEAR = 'X',
        LEFT = '<',
        RIGHT = '>',
        IF = '?'
    };

    Command(size_t line, commands op);
    virtual ~Command();
    // Выполняет комманду
    virtual void execute(State& state) const = 0;
    // Строковое представление комманды
    virtual std::string toString() const = 0;
    // Номер строки
    size_t line() const;
    // Комманда
    commands command() const;
protected:
    size_t _line;
    commands _op;
};

#endif	/* COMMAND_H */

/* 
 * File:   command.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 15:24
 */

#include <iostream>
#include "Command.h"

Command::Command(size_t line, commands op)
: _line(line)
, _op(op)
{
}

Command::~Command()
{
}

size_t Command::line() const
{
    return _line;
}

Command::commands Command::command() const
{
    return _op;
}

/* 
 * File:   ClearCommand.h
 * Author:
 *
 * Created on 11 Июнь 2013 г., 23:13
 */

#ifndef CLEARCOMMAND_H
#define	CLEARCOMMAND_H

#include "SimpleCommand.h"

// Класс-комманда для останова машины

class ClearCommand : public SimpleCommand {
public:
    ClearCommand(size_t line, size_t to);
    virtual ~ClearCommand();
    virtual void execute(State& state) const;
private:

};

#endif	/* CLEARCOMMAND_H */

/* 
 * File:   ClearCommand.cpp
 * Author:
 * 
 * Created on 11 Июнь 2013 г., 23:13
 */

#include "ClearCommand.h"
#include "RuntimeMachineException.h"

ClearCommand::ClearCommand(size_t cur, size_t to)
: SimpleCommand(cur, CLEAR, to)
{
}

ClearCommand::~ClearCommand()
{
}

void ClearCommand::execute(State& state) const
{
    if (!state.tape[state.pos])
    {
        throw RuntimeMachineException("Нельзя стереть пустое поле", state);
    }
    state.tape[state.pos] = false;
    SimpleCommand::execute(state);
}

Шаг: 0
        V
00111110111000   |   1 X 2

Шаг: 1
        V
00111110011000   |   2 > 3

Шаг: 2
         V
00111110011000   |   3 ? 4,5

Шаг: 3
         V
00111110011000   |   5 < 6

Шаг: 4
        V
00111110011000   |   6 ? 5,7

Шаг: 5
        V
00111110011000   |   5 < 6

Шаг: 6
       V
00111110011000   |   6 ? 5,7

Шаг: 7
       V
00111110011000   |   5 < 6

Шаг: 8
      V
00111110011000   |   6 ? 5,7

Шаг: 9
      V
00111110011000   |   7 X 8

Шаг: 10
      V
00111100011000   |   8 > 9

Шаг: 11
       V
00111100011000   |   9 ? 8,1

Шаг: 12
       V
00111100011000   |   8 > 9

Шаг: 13
        V
00111100011000   |   9 ? 8,1

Шаг: 14
        V
00111100011000   |   8 > 9

Шаг: 15
         V
00111100011000   |   9 ? 8,1

Шаг: 16
         V
00111100011000   |   1 X 2

Шаг: 17
         V
00111100001000   |   2 > 3

Шаг: 18
          V
00111100001000   |   3 ? 4,5

Шаг: 19
          V
00111100001000   |   5 < 6

Шаг: 20
         V
00111100001000   |   6 ? 5,7

Шаг: 21
         V
00111100001000   |   5 < 6

Шаг: 22
        V
00111100001000   |   6 ? 5,7

Шаг: 23
        V
00111100001000   |   5 < 6

Шаг: 24
       V
00111100001000   |   6 ? 5,7

Шаг: 25
       V
00111100001000   |   5 < 6

Шаг: 26
      V
00111100001000   |   6 ? 5,7

Шаг: 27
      V
00111100001000   |   5 < 6

Шаг: 28
     V
00111100001000   |   6 ? 5,7

Шаг: 29
     V
00111100001000   |   7 X 8

Шаг: 30
     V
00111000001000   |   8 > 9

Шаг: 31
      V
00111000001000   |   9 ? 8,1

Шаг: 32
      V
00111000001000   |   8 > 9

Шаг: 33
       V
00111000001000   |   9 ? 8,1

Шаг: 34
       V
00111000001000   |   8 > 9

Шаг: 35
        V
00111000001000   |   9 ? 8,1

Шаг: 36
        V
00111000001000   |   8 > 9

Шаг: 37
         V
00111000001000   |   9 ? 8,1

Шаг: 38
         V
00111000001000   |   8 > 9

Шаг: 39
          V
00111000001000   |   9 ? 8,1

Шаг: 40
          V
00111000001000   |   1 X 2

Шаг: 41
          V
00111000000000   |   2 > 3

Шаг: 42
           V
00111000000000   |   3 ? 4,5

Шаг: 43
           V
00111000000000   |   4 !