'''
Diciamo che un dizionario d rappresenta un albero (e lo indichiamo come dizionario-albero)
se ciascuna chiave di d e' un identificativo di un nodo dell'albero  e l'attributo della chiave e' la lista 
(eventualmente vuota) degli identificativi dei  figli del nodo. Gli identificativi dei nodi 
all'interno delle liste sono in ordine lessicografico crescente.



Ecco un esempio di dizionario d che rappresenta un dizionario-albero

d={
'a':['b'],
'b':['c','d'],
'c':['i'],
'd':['e','l'],
'e':['f','g','h'],
'f':[],
'g':[],
'h':[],
'i':[],
'l':[]
}

L'albero rappresentato da d e'

                             'a'
                              |
                _____________'b'____________             
               |                            |            
              'c'                  ________'d'_______   
               |                  |                  |  
              'i'         _______'e'_______         'l'
                         |        |        |               
                        'f'      'g'      'h'


Implementare le seguenti funzioni:

1) 
la funzione genera_sottoalbero(fnome,x,fout) che, presi:

- il nome di un file json contenente un dizionario-albero  d (fonome)
- un identificativo x
- il nome di un file json (fout)

produce   il  dizionario-albero che rappresenta   il sottoalbero  radicato 
nell'identificativo x che si ottiene dal dizionario-albero d. 
Il dizionario-albero ottenuto va registrato nel file fout.
Se l'identificativo x non e' tra i nodi di d allora  il dizionario-albero prodotto 
deve essere vuoto.

Ad esempio se fnome contiene il dizionario-albero d allora dopo l'esecuzione di 
genera_sottoalbero(fname,'d',fout)
il file fout conterra' il dizionario
{'f': [], 'g': [], 'h': [], 'e': ['f', 'g', 'h'], 'l': [], 'd': ['e', 'l']}



2)
la funzione cancella_sottoalbero(fnome,x,fout) che, presi:

- il nome di un file json contenente un dizionario-albero  d (fonome)
- un identificativo x
- il nome di un file json (fout)

ricava  da d il sottoalbero radicato in x e lo salva nel file fout.
Se x non e' presente tra le chiavi di  d allora  il dizionario-albero d non viene modificato.

Ad esempio se fnome contiene il dizionario-albero d allora dopo l'esecuzione di 
cancella_sottoalbero(fname,'d',fout)
il file fout conterra' il dizionario
{'a': ['b'], 'b': ['c'], 'c': ['i'], 'i':[]}


3)
la funzione dizionario_livelli(fnome, fout) che, presi:
- il nome di un file json contenente un dizionario-albero  d (fonome)
- il nome di un file json (fout)

costruisce il  dizionario che ha come  chiavi i livelli del dizionario-albero d. L'attributo di una 
chiave di valore x e' la lista degli identificativi  dei nodi che si trovano a livello x  nell'albero rappresentato da d. 
La lista e' ordinata lessicograficamente ed in modo crescente. 
Il dizionario cosi' costruito va registrato nel file fout.

Ad esempio se fnome contiene il dizionario-albero d allora dopo l'esecuzione di  
dizionario_livelli(fname,fout)
il file fout conterra' il dizionario
{0: ['a'], 1: ['b'], 2: ['c', 'd'], 3: ['e','i','l'], 4: ['f', 'g', 'h']}

4)
la funzione dizionario_gradi_antenati(fnome,y,fout) che, presi:
- il nome di un file json contenente un dizionario-albero  d (fonome)
- un intero y
- il nome di un file json (fout)

costuisce  il dizionario che ha come chiavi gli identificativi dei nodi dell'albero 
rappresentato dal dizionario-albero d, Attributo di una chiave di valore x e' il numero 
di antenati di grado y che ha il nodo con identificativo x nell'albero.
Registra il dizionario costruito nel file fout.

Ad esempio se fnome contiene il dizionario-albero d allora dopo l'esecuzione di  
dizionario_gradi_antenati(fnome,2,fout)
il file fout conterra' il dizionario 
{'a': 0, 'b': 0, 'c': 1, 'd': 1, 'e': 2, 'f': 2, 'g': 2, 'h': 2, 'i': 1, 'l': 2}

AVVERTENZE: non usare caratteri non ASCII, come le lettere accentate; non
importare moduli che non sono nella libreria standard.
'''




import json

def leggialbero(fnome):
    with open (fnome) as f:
        albero = json.load(f)
    return albero

def scrivialbero(albero, fnome):
    with open (fnome, 'w') as f:
        json.dump(albero, f)

def gen_sottoalb(albero, sottoalb, x):
# aggiungo x al sottoalbero
    sottoalb[x]=albero[x][:]
# aggiungo i figli di x al sottoalbero
    for figlio in albero[x]:
        gen_sottoalb(albero, sottoalb, figlio)
    
def genera_sottoalbero(fnome,x,fout):
    '''inserire qui il vostro codice'''
    albero=leggialbero(fnome)
    sottoalb={}
    if x in albero:
        gen_sottoalb(albero, sottoalb, x)
    scrivialbero(sottoalb, fout)

def canc_sa(albero, nodo):
    #elimina i figli di nodo
    for figlio in albero[nodo]:
        canc_sa(albero, figlio)
    #elimina nodo
    del albero[nodo]

def cancella_sottoalbero(fnome,x,fout):
    '''inserire qui il vostro codice'''
    albero=leggialbero(fnome)
    canc_sa(albero, x)
    for figli in albero.values():
        if x in figli:
            figli.remove(x)
            break
    scrivialbero(albero, fout)

def trova_radice(albero):
    nodi=set(albero.keys())
    figli=set()
    for listaf in albero.values():
        figli.update(listaf)
    (radice,)=nodi-figli
    return radice

def gen_dizlev(albero, dizliv, nodo, livello):
    if livello in dizliv:
        dizliv[livello].append(nodo)
    else:
        dizliv[livello]=[nodo]
    for figlio in albero[nodo]:
        gen_dizlev(albero, dizliv, figlio, livello+1)

def dizionario_livelli(fnome,fout):
    '''inserire qui il vostro codice'''
    albero=leggialbero(fnome)
    dizliv={}
    radice = trova_radice(albero)
    gen_dizlev(albero, dizliv, radice, 0)
    for nodi in dizliv.values():
        nodi.sort()
    scrivialbero(dizliv, fout)

def gen_dizga(albero, dizga, nodo, n, y):
    dizga[nodo]=n
    if len(albero[nodo]) == y:
        n+=1
    for figlio in albero[nodo]:
        gen_dizga(albero, dizga, figlio, n, y)

def dizionario_gradi_antenati(fnome,y,fout):
    '''inserire qui il vostro codice'''
    albero=leggialbero(fnome)
    radice = trova_radice(albero)
    dizga={}
    gen_dizga(albero, dizga, radice, 0, y)
    scrivialbero(dizga, fout)