#!/usr/bin/env python
#
# Macchina di Turing
# Matteo Bertini 13/03/2001
# License: Public Domain

import sys

class LogicUnit:
    "Unita' logica della macchina di Turing"
    def __init__(self, matrice):
        self.InfoMatriceFunzionale = matrice[0]
        self.MatriceFunzionale = matrice[1]
    def valuta(self, (esterno, interno)):
        """
        Cerca sulla tabella i tre valori di uscita corrispondenti ai due di ingresso
        Rende NULL se il il valore non viene trovato
        """
        return self.MatriceFunzionale.get((str(esterno), str(interno)))

class MacchinaDiTuring(LogicUnit):
    "Implementazione in python della Macchina di Turing"
    def __init__(self, matrice, NastroOriginale, PosizioneIniziale, ValoreIniziale):
        #Per inizializzare la classe generatrice devo riferirmi direttamente
        #al metodo __init__ 
        LogicUnit.__init__(self, matrice)
        self.NastroOriginale, self.nastro = NastroOriginale, NastroOriginale
        self.PosizioneIniziale, self.posizione = PosizioneIniziale, PosizioneIniziale
        self.ValoreIniziale, self.valore = ValoreIniziale, ValoreIniziale
        self.passo = 0
    def Passo(self):
        "Va avanti di un ciclo"
        self.passo = self.passo + 1
        if(self.valore != '!'):
        #Se non ho finito...
            #Legge il valore presente sul nastro alla posizione corrente,
            #se l'indice e' esterno all'array rende ' '
            try:
                esterno = self.nastro[self.posizione]
            except:
                esterno = ' '
            interno = self.valore
            risposta = self.valuta((esterno, interno))
            #Scrive il valore di ritorno sul nastro alla posizione corrente,
            #se l'indice e' esterno all'array aggiunge ' '
            if self.posizione < 0:
                #inserisce in testa e riporta il carrello a 0 (cioe' su quello che ho
                #appena inserito
                self.nastro.insert(0, risposta[0])
                self.posizione = 0
            else:
                try:
                    #cerco di modificare il valore
                    self.nastro[self.posizione] = risposta[0]
                except:
                    #se non ci riesco allora aggiungo in coda
                    self.nastro.append(risposta[0])
            #Aggiorna la posizione sul nastro
            self.posizione = self.posizione + int(risposta[1])
            self.valore = risposta[2]
            return 1 #c'e' ancora da fare
        else:
            return 0 #ho finito
    def StampaStato(self):
        nastro = '|'
        for n in range(len(self.nastro)):
            nastro = nastro + '' + str(self.nastro[n]) + '|'
        if self.posizione >= 0:
            posizione = '    '
            for p in range(self.posizione):
                posizione = posizione + '  '
        else:
            posizione = '  '
        posizione = posizione + self.valore
        print "%3d) %s" % (self.passo, nastro)    
        print "  %s (%s)" % (posizione, self.posizione)
    def StampaInfo(self):
        print "*** Macchina di Turing ***"
        print "Matrice Funzionale:"
        chiavi = self.MatriceFunzionale.keys()
        chiavi.sort()
        print self.InfoMatriceFunzionale
        for i in chiavi:
            print i, "->", self.MatriceFunzionale.get(i)
        print "Nastro:"
        self.StampaStato()

SommaDiDueNumeri =["Calcola la somma di due numeri espressi sotto forma di sbarre.",
                   {('I','q0'):(' ',1,'q2'), ('I','q1'):('I',-1,'q1') ,('I','q2'):('I',1,'q2'),
                    (' ','q0'):(' ',1,'q0'), (' ','q1'):(' ', 1,'q0') ,(' ','q2'):('I',0,'q1'),
                    ('*','q0'):(' ',0,'!'),  ('*','q1'):('*',-1,'q1') ,('*','q2'):('*',1,'q2')}]

SommaUno = ["Aggiunge 1 ad un numero espresso in forma decimale.",
            {('0','q0'):('1', 0, '!'),
            ('1','q0'):('2', 0, '!'),
            ('2','q0'):('3', 0, '!'),
            ('3','q0'):('4', 0, '!'),
            ('4','q0'):('5', 0, '!'),
            ('5','q0'):('6', 0, '!'),
            ('6','q0'):('7', 0, '!'),
            ('7','q0'):('8', 0, '!'),
            ('8','q0'):('9', 0, '!'),
            ('9','q0'):('0',-1,'q0'),
            (' ','q0'):('1', 0, '!')}]

ContaSbarre = ["Conta in forma decimale un numero espresso sotto forma di sbarre.",
               {('0','q0'):('1', 0,'q2'),('0','q1'):('0', 0, '!'),('0','q2'):('0', 1, 'q2'),
               ('1','q0'):('2', 0,'q2'),('1','q1'):('1', 0, '!'),('1','q2'):('1', 1, 'q2'),
               ('2','q0'):('3', 0,'q2'),('2','q1'):('2', 0, '!'),('2','q2'):('2', 1, 'q2'),
               ('3','q0'):('4', 0,'q2'),('3','q1'):('3', 0, '!'),('3','q2'):('3', 1, 'q2'),
               ('4','q0'):('5', 0,'q2'),('4','q1'):('4', 0, '!'),('4','q2'):('4', 1, 'q2'),
               ('5','q0'):('6', 0,'q2'),('5','q1'):('5', 0, '!'),('5','q2'):('5', 1, 'q2'),
               ('6','q0'):('7', 0,'q2'),('6','q1'):('6', 0, '!'),('6','q2'):('6', 1, 'q2'),
               ('7','q0'):('8', 0,'q2'),('7','q1'):('7', 0, '!'),('7','q2'):('7', 1, 'q2'),
               ('8','q0'):('9', 0,'q2'),('8','q1'):('8', 0, '!'),('8','q2'):('8', 1, 'q2'),
               ('9','q0'):('0',-1,'q0'),('9','q1'):('9', 0, '!'),('9','q2'):('9', 1, 'q2'),
               (' ','q0'):('1', 0,'q2'),(' ','q1'):(' ', 0, '!'),(' ','q2'):(' ',-1, 'q1'),
               ('I','q0'):('I',-1,'q0'),('I','q1'):(' ',-1,'q0'),('I','q2'):('I', 1, 'q2')}]

Nastro1 = ['I','I','I','*','I','I','I','I','I']     # SommaDiDueNumeri, Nastro1, 0, 'q0'
Nastro2 = ['1','2','5']                             # SommaUno, Nastro2, 2, 'q0'
Nastro3 = ['9','9','9','9']                         # SommaUno, Nastro3, 3, 'q0'
Nastro4 = ['I','I','I','I','I','I','I','I','I','I'] # ContaSbarre, Nastro4, 9, 'q1'

try:
    argomento = int(sys.argv[1])
except:
    argomento = 3

if   argomento == 1:
    pippo = MacchinaDiTuring(SommaDiDueNumeri, Nastro1, 0, 'q0')
elif argomento == 2:
    pippo = MacchinaDiTuring(SommaUno, Nastro2, 2, 'q0')
elif argomento == 3:
    pippo = MacchinaDiTuring(SommaUno, Nastro3, 3, 'q0')
elif argomento == 4:
    pippo = MacchinaDiTuring(ContaSbarre, Nastro4, 9, 'q1')
else:
    print "Esempio non disponibile!"

pippo.StampaInfo()
while pippo.Passo():
    pippo.StampaStato()

class LogicUnit:
    "Unita' logica della macchina di Turing"
    def __init__(self, matrice):
        self.InfoMatriceFunzionale = matrice[0]
        self.MatriceFunzionale = matrice[1]
    def valuta(self, (esterno, interno)):
        """
        Cerca sulla tabella i tre valori di uscita corrispondenti ai due di ingresso
        Rende NULL se il il valore non viene trovato
        """
        return self.MatriceFunzionale.get((str(esterno), str(interno)))

class MacchinaDiTuring(LogicUnit):
    "Implementazione in python della Macchina di Turing"
    def __init__(self, matrice, NastroOriginale, PosizioneIniziale, ValoreIniziale):
        #Per inizializzare la classe generatrice devo riferirmi direttamente
        #al metodo __init__
        LogicUnit.__init__(self, matrice)
        self.NastroOriginale, self.nastro = NastroOriginale, NastroOriginale
        self.PosizioneIniziale, self.posizione = PosizioneIniziale, PosizioneIniziale
        self.ValoreIniziale, self.valore = ValoreIniziale, ValoreIniziale
        self.passo = 0

    def Passo(self):
        "Va avanti di un ciclo"
        self.passo = self.passo + 1
        if(self.valore != '!'):
        #Se non ho finito...
            #Legge il valore presente sul nastro alla posizione corrente,
            #se l'indice e' esterno all'array rende ' '
            try:
                esterno = self.nastro[self.posizione]
            except:
                esterno = ' '
            interno = self.valore
            risposta = self.valuta((esterno, interno))
            #Scrive il valore di ritorno sul nastro alla posizione corrente,
            #se l'indice e' esterno all'array aggiunge ' '
            if self.posizione < 0:
                #inserisce in testa e riporta il carrello a 0 (cioe' su quello che ho
                #appena inserito
                self.nastro.insert(0, risposta[0])
                self.posizione = 0
            else:
                try:
                    #cerco di modificare il valore
                    self.nastro[self.posizione] = risposta[0]
                except:
                    #se non ci riesco allora aggiungo in coda
                    self.nastro.append(risposta[0])
            #Aggiorna la posizione sul nastro
            self.posizione = self.posizione + int(risposta[1])
            self.valore = risposta[2]
            return 1 #c'e' ancora da fare
        else:
            return 0 #ho finito