#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Nov 29 10:28:50 2019

@author: andrea
"""

from rtrace import trace

# verifico se una stringa è palindroma (è uguale a se stessa se letta al contrario)
@trace
def palindromaP( stringa ):
    if len(stringa) < 2:
        return True
    else:
        if stringa[0] != stringa[-1]:
            return False
        else:
            return palindromaP(stringa[1:-1])

# versione efficiente che NON genera sottostringhe
# ma sposta due indici nella stringa che indicano i due caratteri
# da confrontare
@trace
def palindroma_efficiente(stringa, primo, ultimo):
    if (ultimo-primo)<1:
        return True
    if stringa[primo] != stringa[ultimo]:
        return False
    return palindroma_efficiente(stringa, primo+1, ultimo-1)

# funzione di appoggio che valorizza i due indici in modo corretto
# a seconda della stringa passata come argomento
@trace
def palindroma_appoggio(stringa):
    return palindroma_efficiente(stringa, 0, len(stringa)-1)


# merge di due liste ordinate
    # caso base: se una è vuota torno l'altra
    # caso ricorsivo:
        # torno il minimo tra i primi due elementi
        # seguito dal merge del resto delle due liste
@trace
def merge(L1, L2):
    if not L1:      # se L1 è vuota
        return L2
    if not L2:
        return L1
    if L1[0] < L2[0]:
        # LA SOLUZIONE È IL MINIMO TROVATO SEGUITO DAL RESTO ORDINATO
        return [L1[0]] + merge(L1[1:], L2)
    else:
        return [L2[0]] + merge(L1, L2[1:])


# merge_sort di una lista DISORDINATA
    # caso base: una lista di 0 o 1 elemento è già ordinata
    # caso ricorsivo:
        # spezzo la lista in due sottoliste DISORDINATE
        # ordino ciascuna lista usando merge_sort (mi fido!)
        # fondo le due liste ORDINATE usando il passo merge

@trace
def merge_sort(L):
    if len(L) < 2:
        return L
    mezzo =len(L)//2
    L1, L2 = L[:mezzo], L[mezzo:]
    L1_ordinata = merge_sort(L1)
    L2_ordinata = merge_sort(L2)
    return merge(L1_ordinata, L2_ordinata)


# generazione delle permutazioni di una lista


import os

# elenco i file contenuti in una directory
def lista_files(path):
    files = os.listdir(path)
    for filename in files:
        print(f"{path}/{filename}")

# elenco ricorsivamente i file contenuti in una directory
# E IN TUTTE LE SOTTODIRECTORY CONTENUTE
def lista_files_R(path):
    files = os.listdir(path)
    for filename in files:
        fullpath = f"{path}/{filename}"
        if os.path.isdir(fullpath):
            # se è una sottodirectory ne stampo il contenuto ricorsivamente
            lista_files_R(fullpath)
        else:
            print(fullpath)

# cerchiamo tutti i file .txt

# costruiamo un dizionario che contiene tutti i nomi dei file
# { "nomedir" : <dizionario>,
#   "nomefile": <dimensione>, ...  }
            
def elenca_files_e_dir(path):
    dizionario = {}
    for name in os.listdir(path):
        fullname = path + "/" + name
        if os.path.isdir(fullname):
            dizionario[name] = elenca_files_e_dir(fullname)
        else:
            dizionario[name] = os.stat(fullname).st_size
    return dizionario

def dimensioni_dir(path):
    dim = 0
    for name in os.listdir(path):
        fullname = path + "/" + name
        if os.path.isdir(fullname):
            dim += dimensioni_dir(fullname)
        else:
            dim += os.stat(fullname).st_size
    return dim


class NodoBinario:
    def __init__(self, V, SX=None, DX=None):
        self.valore = V
        self.sx = SX
        self.dx = DX
        
    
    def __str__(self, livello=0):
        risultato = '\t'*livello + f"{self.valore}"
        if self.sx:
            risultato += '\n' + '\t'*livello + self.sx.__str__(livello+1)
        if self.dx:
            risultato += '\n' + '\t'*livello + self.dx.__str__(livello+1)
        return risultato
    
    def altezza(self):
        hs = 0
        hd = 0
        if self.sx:
            hs = self.sx.altezza()
        if self.dx:
            hd = self.dx.altezza()
        return max(hs, hd)+1