class VM #If you rename this class, you must change the VM::strip_chars in the load method

UNBALANCED_BRACKETS = 'Unbalanced Brackets'
DONE_LOADING        = 'Done'
INVALID_CHARACTER   = 'Invalid Character'
GETCHAR             = Proc.new {$stdin.getc.ord rescue puts(INVALID_CHARACTER)}
PUTCHAR             = Proc.new do |num|
                          if 0 <= num && num <= 255
                              $stdout.putc(num.chr)
                          else
                              $stdout.print("\\#{num}")
                          end
                      end
EXECUTION_DONE      = 'Execution Done'


attr_accessor :ptr, :pc, :mem, :tape #For IRB testing
def initialize
    @ptr, @pc = 0, 0
    @mem, @tape = Array.new, Array.new
end     

def execute
    @ptr, @pc, @mem, len = 0, 0, Array.new, @tape.length
    while @pc < len && @ptr >= 0
        cell = @mem[@ptr]
        cmd  = @tape[@pc]
        case cmd[0]
        when :add 
            cell ? @mem[@ptr] += cmd[1] : @mem[@ptr] = cmd[1]
        when :add_ptr
            @ptr += cmd[1]
        when :put
            cmd[1].times {PUTCHAR.call(@mem[@ptr])}
        when :get
            cmd[1].times {temp = GETCHAR.call ; temp ? @mem[@ptr] = temp : nil}
        when :jtc 
            @pc = cmd[1] if cell == 0
        when :jto 
            @pc = cmd[1] unless cell == 0
        end
        @pc += 1
    end
    EXECUTION_DONE
end
    

def self.strip_chars(str)
    str.gsub(/[^\[\]+-.,<>]+/, '')
end

def load(str)
    @tape.clear
    str = VM::strip_chars(str)
    index = 0
    str.each_char do |char|
        case char
        when '+'
            @tape[index] = [:add, 1]
        when '-'
            @tape[index] = [:add, -1]
        when '>'
            @tape[index] = [:add_ptr, 1]
        when '<'
            @tape[index] = [:add_ptr, -1]
        when '.'
            @tape[index] = [:put, 1]
        when ','
            @tape[index] = [:get, 1]
        when '['
            @tape[index] = [:jtc, 1]
        when ']'
            @tape[index] = [:jto, 1]
        end
        index += 1
    end
    optimize
    add_jmps
end

def pass_once
    @tape.each_index do |i|
        if @tape[i] && @tape[i + 1]
            if @tape[i][0] == @tape[i + 1][0] && !(@tape[i][0] == :jtc || @tape[i][0] == :jto)
                @tape[i][1] += @tape[i + 1][1]
                @tape.delete_at(i + 1)
            end
        end
    end
    @tape
end

def optimize
    while (prev ||= @tape.dup) != pass_once
        prev = @tape.dup
    end
    @tape.each_index {|i| @tape.delete_at(i) if @tape[i][1] == 0}
end

def add_jmps
    ids = Array.new
    id = '0'
    @tape.each_index do |i|
        case @tape[i][0]
        when :jtc
            id.succ!
            ids << id.dup
            @tape[i][1] = id.dup
        when :jto
            matching = @tape.find_index([:jtc, ids.last])
            return(UNBALANCED_BRACKETS) unless matching
            ids.pop
            @tape[i][1] = matching
            @tape[matching][1] = i
        end
    end
    return(UNBALANCED_BRACKETS) unless ids.empty?
    DONE_LOADING
end      
private :pass_once, :optimize, :add_jmps
end