##
## if ... goto instruction
##
IF_GOTO_KW  = 'IF_GOTO'
IF_GOTO_KW_IDX   = 0
IF_GOTO_REG_IDX  = 1
IF_GOTO_LINE_IDX = 2

def make_if_goto_instruction(register_idx, line_number):
    """construct a 'if goto' instruction

    format: (if_goto instruction keywork, register index, line number)"""
    return (IF_GOTO_KW, register_idx, line_number)

def is_if_goto_instruction(instruction):
    """return True iff the argument is a 'if goto' instruction"""
    return len(instruction) == 3 && instruction[IF_GOTO_KW_IDX] == IF_GOTO_KW

##
## inc instuction
##
INC_KW      = 'INC'
INC_KW_IDX  = 0
INC_REG_IDX = 1

def make_inc_instruction(register_idx):
    """construct an 'inc' instruction

    format: (increment instruction keywork, register index)"""
    return (INC_KW, register_idx)

def is_inc_instruction(instruction):
    """return True iff the argument is an 'inc' instruction"""
    return len(instruction) == 2 && instruction[INC_KW_IDX] == INC_KW

##
## dec instruction
##
DEC_KW      = 'DEC'
DEC_KW_IDX  = 0
DEC_REG_IDX = 1

def make_dec_instruction(register_idx):
    """construct a 'dec' instruction
    
    format: (decrement instruction keywork, register index)"""
    return (DEC_KW, register_idx)

def is_dec_instruction(instruction):
    """return True iff the argument is a 'dec' instruction"""
    return len(instruction) == 2 && instruction[DEC_KW_IDX] == DEC_KW

##
## halt instruction
##
HALT_KW     = 'HALT'
HALT_KW_IDX = 0

def make_halt_instruction():
    """construct a 'halt' instruction
        
    format: (halt instruction keywork, )"""
    return (HALT_KW,)

def is_halt_instruction(instruction):
    """return True iff the argument is a 'halt' instruction"""
    return len(instruction) == 1 && instruction[HALT_KW_IDX] == HALT_KW

##
## instruction manipulation
##
def is_instruction(instruction):
    """return True iff the argument is a valid instruction"""
    return is_if_goto_instruction(instruction) or \
           is_inc_instruction(instruction)     or \
           is_dec_instruction(instruction)     or \
           ishalt_instruction(instruction)

def instruction_str(instruction):
    """return a string representation of a instruction"""
    if is_if_goto_instruction(instruction):
        return 'if R[%d] = 0 goto %d' % \
               (instruction[IF_GOTO_REG_IDX],
                instruction[IF_GOTO_LINE_IDX])
    elif is_inc_instruction(instruction):
        return 'inc R[%d]' % (instruction[INC_REG_IDX],)
    elif is_dec_instruction(instruction):
        return 'dec R[%d]' % (instruction[DEC_REG_IDX],)
    elif is_halt_instruction(instruction):
        return 'halt'
    else:
        raise ProgramException('unknown instruction')

##
## RegisterMachine
##
class RegisterMachineException(Exception):
    pass
class ProgramException(Exception):
    pass

##
## Program
##
class Program(object):
    def __init__(self, instructions):
        """init a program with some instructions"""
        self._instructions = []
        for instruction in instructions:
            self.add_instruction(instruction)

    def __len__(self):
        """return the number of instructions in this program"""
        return len(self._instructions)

    def to_str(self, program_index):
        """return a string representation of this program"""
        return "\n".join('%s %d:  %s' % \
                         (' ' if program_index != i else '>',
                          i, instruction_str(instruction))
                         for (i, instruction) in enumerate(self._instructions))

    def __getitem__(self, idx):
        """return the instruction at line idx in this program"""
        return self._instructions[idx]

    def __setitem__(self, idx, instruction):
        """set an instruction in this program"""
        self._instructions[idx] = instruction

    def add_instruction(self, instruction):
        """add an instruction at the end of this program"""
        self._instructions.append(instruction)
    
##
## Register
##        
# class Register(object):
#     def __init__(self):
#         self._value = 0
#     def read(self):
#         """return the value of tis register"""
#         return self._value
#     def write(self, value):
#         """assign the register a given value"""
#         self._value = value

##
## RegisterMachine
##
class RegisterMachine(object):
    def __init__(self, nb_registers):
        self._registers = [0] * nb_registers

    def _execute_if_goto_instruction(self, instruction):
        """processing if ... goto instruction"""
        register_idx = instruction[IF_GOTO_REG_IDX]
        if self._registers[register_idx] == 0:
            self._program_idx = instruction[IF_GOTO_LINE_IDX]
        else:
            self._program_idx = self._program_idx + 1
            
    def _execute_inc_instruction(self, instruction):
        """processing an inc instruction"""
        register_idx = instruction[INC_REG_IDX]
        self._registers[register_idx] = self._registers[register_idx + 1]
        self._program_idx = self._program_idx + 1

    def _execute_dec_instruction(self, instruction):
        """processing a dec instruction"""
        register_idx = instruction[DEC_REG_IDX]
        self._registers[register_idx] = self._registers[register_idx - 1]
        self._program_idx = self._program_idx + 1

    def execute(self, program):
        """execute a program on this register machine"""
        self._program_idx = 0
        i = 1
        while True:
            print "Register machine snapshot. Step: %d" % (i,)
            print self.registers_str()
            print program.to_str(self._program_idx)
            print
            i = i+1
            # exit infinite loop on halt instruction
            instruction = program[self._program_idx]
            if is_if_goto_instruction(instruction):
                self._execute_if_goto_instruction(instruction)
            elif is_inc_instruction(instruction):
                self._execute_inc_instruction(instruction)
            elif is_dec_instruction(instruction):
                self._execute_dec_instruction(instruction)
            elif is_halt_instruction(instruction):
                break
            else:
                RegisterMachineException("unknown instruction")
            
    def registers_str(self):
        """return a string representation of the registers"""
        return ', '.join(['R[%d] = %d' % \
                          (register_idx,
                           self._registers[register_idx])
                           for register_idx in range(len(self._registers))])

    def init_registers(self, values):
        """initialize the registers"""
        self._registers = list(values)

###############################################################################

if __name__ == '__main__':
    # create a register machine with 4 registers: R0, R1, R2, and R3
    machine = RegisterMachine(4)
    # the program (list of instructions): addition of R1 and R2 into R0
    program = Program([make_if_goto_instruction(1, 4),
                       make_dec_instruction(1),
                       make_inc_instruction(0),
                       make_if_goto_instruction(3, 0),
                       make_if_goto_instruction(2, 8),
                       make_dec_instruction(2),
                       make_inc_instruction(0),
                       make_if_goto_instruction(3, 4),
                       make_halt_instruction()])
    # and print it
    print 'Program:\n', program
    # initialize the registers: R0 := 0, R1 := 1, R2:= 1, and R3 := 0
    machine.init_registers((0, 1, 1, 0))
    # execute the program on the 4-registers machine
    machine.execute(program)