# definizione vuota del decoratore @profile per non avere errori
# quando NON si usa il line-profiler
import builtins
if 'profile' not in dir(builtins):
    def profile(X) : return X

'''

RECAP
- while e "do while"
- dictionary (con chiavi immutabili) e set (con elementi immutabili)
- list set e dictionary comprehension
- sorted e sort con argomento key e funzione/lambda

OGGI: come si analizza un problema
ESEMPIO: k-massimi di una lista
- trovare i k valori più grandi di una lista

Vincoli applicativi
- IN
    - K : valore intero >=0
    - L : lista di valori confrontabili
        - ordinati
        - disordinati
- OUT
    - lista di K elementi che sono i k massimi di L
- EFFETTI COLLATERALI
    - L può essere modificata distruttivamente? 
- POSSIBILI ERRORI
    K < 0 oppure K<=len(L)
        - lanciare un errore se K<0
        - tornare meno elementi se K>len(L)
    L non omogenea
- RETURN
    - la lista deve essere ordinata?
    - i massimi devono essere unici?
- ALGORITMO A GRANDI LINEE

'''
'''
#k-massimi distruttivo
    # controllo che K sia sensato e casomai lancio un errore
    # all'inizio il risultato è []
    # per k volte
        # trovo il massimo e lo elimino dalla lista
        # lo metto nel risultato
    # torno il risultato


# per estrarre un massimo e eliminarlo dalla lista
    # trovo il massimo
    # lo tolgo da L
    # torno il valore trovato

'''

#k-massimi distruttivo
def k_massimi_distruttivo(K, L):
    # controllo che K sia sensato
    assert 0 <= K <= len(L) , "K non è un valore tra 0 e len(L)"
    # all'inizio il risultato è []
    risultato = []
    # per k volte
    for _ in range(K):          # k volte
        # trovo il massimo e lo elimino dalla lista
        massimo = estrai_massimo(L)  # prop a len(L)
        # lo metto nel risultato
        risultato.append(massimo)   # 
    # torno il risultato
    return risultato

#    estrai_massimo e lo elinìmino dalla lista
def estrai_massimo(L):
    # trovo il massimo
    massimo = max(L)            # proporzionale a len(L)
    # lo tolgo da L
    L.remove(massimo)           # proporzionale a len(L)
    # trno il valore trovato
    return massimo

'''
# per una versione non distruttiva
    # copio la lista 
    # uso k.... sulla copia

'''

# per una versione non distruttiva
def k_massimi_ND(K, L):
    # copio la lista 
    lista1 = L.copy()
    # uso k.... sulla copia
    return k_massimi_distruttivo(K, lista1)

'''
Se la lista iniziale fosse stata ordinata le cose sarebbero state molto più semplici
    IDEA: ordiniamo la lista 
        e prendiamo i primi K valori
'''

# per ottenere i k massimi
def k_massimi_ordinati(K,L):
    # controllo su K
    # ordiniamo L
    ordinati = sorted(L, reverse=True)   # N log(N)
    # estraggo i k primi valori
    # li ritorno
    return ordinati[:K]


if __name__ == '__main__':
    ''' mettiamo qui le istruzioni da NON eseguire all'import'''
    pass

# per la prossima puntata
#K-massimi con poca memoria
#    disordinata

#    ordinata