import nltk
from ipythonblocks import BlockGrid, colors
# import time
# from IPython.display import clear_output

def print_chart(chart, num_of_tabs=1):
    """
    Nicht notwendige, selbstgebastelte Funktion zum Drucken von Charts.
    Wandelt Sets (aus optischen Gründen) in Listen um und kann diese
    eingerückt (mit Tabulator) darstellen.
    """
    tabstring = '\t' * num_of_tabs
    for row in chart:
        print tabstring+"\t".join([str(list(element)) for element in row])

words = ["I", "shot", "an", "elephant", "in", "my", "pajamas"]
n = len(words)

grammar = nltk.parse_cfg("""
 S -> NP VP
 PP -> P NP
 NP -> Det N | 'I' | NP PP
 VP -> V NP | VP PP
 Det -> 'an' | 'my'
 N -> 'elephant' | 'pajamas'
 V -> 'shot'
 P -> 'in'
 """)

# leere Chart bauen
chart = []
for i in range(n+1):
    # Erzeuge eine leere Zeile
    row = []
    # Haenge n+1 leere Mengen (set()) an
    for j in range(n+1):
        row.append(set())
    # Haenge die neue Zeile an die Chart an
    chart.append(row)

grid = BlockGrid(n+1, n+1)
known_terminals = set()

# Terminalproduktionen
# Iteriere ueber alle Positionen des Eingabesatzes
for i in range(n):
    # Iteriere ueber alle Regeln der Grammatik, die das Wort words[i] als rechte Seite haben
    # z.B. words[4] = 'elephant' und N -> 'elephant'
    print "productions for terminal '{}':".format(words[i])
    for prod in grammar.productions(rhs=words[i]):
        print prod
        # Fuege in die Zelle fuer die Spanne von i bis i+1 die linke Regel (z.B. N) ein
        print "\t{0} added to chart[{1}][{2}]\n".format(prod.lhs(), i, i+1)
        grid[i, i+1] = colors['White']
        grid.flash(display_time=1.0)
        chart[i][i+1].add(prod.lhs())
        known_terminals.add((i, i+1))
        
grid.show()

grid = BlockGrid(n+1, n+1)
seconds_per_step = 1.0
known_lhs = set()

# Iteriere ueber alle Spannen ab Laenge 2
for width in range(2, n+1):
    # Iteriere ueber alle moeglichen Anfaenge einer Spanne
    for i in range(0, n-width+1): # i + width <= n
        # Iteriere ueber alle moeglichen Teilungspunkte dieser Spanne
        for j in range(1, width): # 1 <= j <= width-1
            # Jetzt wollen wir Nichtterminale aus 2 gegebenen Chartzellen kombinieren
            nts1 = chart[i][i+j]
            grid[i, i+j] = colors['Yellow'] # Nichtterminal 1: gelb
            
            # j ist der Teilungspunkt: eine Spanne geht von i bis i+j, die andere von
            # i+j bis i+width
            nts2 = chart[i+j][i+width]
            grid[i+j, i+width] = colors['Orange'] # Nichtterminal 2: orange
            
            print ("\ntry to combine nonterminals from [{0}][{1}] ({2})"
                  " and [{3}][{4}] ({5})".format(i, i+j, list(nts1), i+j, i+width, list(nts2)))            
            
            # Iteriere nun ueber alle Nichtterminale der ersten Zelle
            for nt1 in nts1:
                # Bestimme die Kandidatenregeln, die ein Nichtterminal aus nts1 als
                # erstes Element auf ihrer rechten Regelseite haben
                # Beispiel: nts1 enthaelt NP => suche alle Regeln der Form X => NP Y,
                # z.B. S -> NP VP
                productions = grammar.productions(rhs=nt1)
                if productions:
                    print "\tproductions, where NT '{0}' is 1st element of RHS: {1}".format(nt1, productions)
                else:
                    print "\tNO productions where nonterminal '{}' is the 1st element of RHS!".format(nt1)
                # Gehe nun diese Kandidatenregeln durch
                for production in productions:
                    # Pruefe, ob das 2. Element der rechten Regelseite (production.rhs()[1]),
                    # (also im Beispiel oben VP) im anderen Kaestchen enthalten ist
                    if production.rhs()[1] in nts2:
                        # ok, fuege dann die linke Regelseite (also S) in das Zielkaestchen
                        # chart[i][i+width] ein. Dieses enthaelt alle Nichtterminale, die die
                        # Eingabe zwischen den Positionen i und i+width ableitet.
                        print ("\t\t2nd element of production RHS '{0}' is also in '{1}'"
                              "\n\t\tLHS will be added to [{2}][{3}]".format(production, list(nts2), i, i+width))
                        chart[i][i+width].add(production.lhs())
                        grid[i, i+width] = colors['Green']
                        known_lhs.add((i, i+width)) # wir merken uns schon gefundene LHS
                    else:
                        print "\t\t2nd element of production RHS '{0}' NOT in '{1}'!".format(production, list(nts2))

            grid.flash(display_time=seconds_per_step) # Nichtterminale aufleuchten für X Sekunden
            # Farben zuruecksetzen
            for (row, column) in ((i, i+j), (i+j, i+width)):
                if (row, column) in known_terminals:
                    grid[row, column] = colors['White'] # wenn schon ein Nichtterminal in diesem Kästchen gespeichert ist
                elif (row, column) in known_lhs:
                    grid[row, column] = colors['Green'] # wenn schon eine RHS in diesem Kästchen gespeichert ist
                else:
                    grid[row, column] = colors['Black']
                    
grid.show()

print_chart(chart)