#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 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

'''
Problema: trovare i k massimi di una lista L di valori numerici
'''

'''
# rappresentazione dei dati? (in questo caso lo sappiamo)
# controlliamo se ci sono condizioni di validità dei dati
#   K potrebbe essere negativo? NO
#   K potrebbe essere > len(L)  
        diamo errore?
        tornare un numero di elementi minori di K
# effetti collaterali?
    modificare distruttivamente L
    non modificarla
# il risultato deve avere qualche caratteristica?

Scegliamo:
        - se K è sbagliato diamo un errore
        - modificare distruttivamente L
        - il risultato può essere in qualsiasi ordine

# per estrarre i k massimi da L
    # controllo che k sia valido
    # definisco la variabile risultato e la inizializzo = []
    # ripeto per k volte
        # estraggo un elemento massimo da L eliminandolo
        # aggiungo questo elemento al risultato
    # torno il risultato

'''

# per estrarre i k massimi da L
@profile
def k_massimi(k, L):
    # controllo che k sia valido
    assert 0 <= k <= len(L), "K non è valido"
    # definisco la variabile risultato e la inizializzo = []
    risultato = []
    # ripeto per k volte
    for _ in range(k):
        # estraggo un elemento massimo da L eliminandolo
        M = estrai_massimo_da_lista(L)
        # aggiungo questo elemento al risultato
        risultato.append(M)
    # torno il risultato
    return risultato

'''
# per estrarre ed eliminare un massimo da una lista
    # cerco il massimo
    # lo elimino dalla lista
    # torno il massimo
'''

# per estrarre ed eliminare un massimo da una lista
@profile
def estrai_massimo_da_lista(L):
    # cerco il massimo
    M = max(L)              # tempo proporzionale a len(L)
    # lo elimino dalla lista
    L.remove(M)             # tempo proporzionale a len(L)
    # torno il massimo
    return M

'''
# per calcolare i k_massimi SENZA modificare L
    # copio la lista
    # uso k_massimi sulla copia
'''
# per calcolare i k_massimi SENZA modificare L
@profile
def k_massimi_ND(k, L):
    # copio la lista
    L2 = L.copy()
    # uso k_massimi (distruttivo) sulla copia
    return k_massimi(k, L2)

# tempo di questa implementazione è proporzionale a len(L)*k

'''
seconda idea

# per estrarre i primi k massimi da L (non distruttivo)
    # controllo se k è valido
    # ordino tutti i valori in ordine decrescente
    # estraggo i primi k
'''

# per estrarre i primi k massimi da L (non distruttivo)
@profile
def k_massimi_ordinati(k, L):
    # controllo se k è valido
    assert 0 <= k <= len(L), "K non valido"
    # ordino tutti i valori in ordine decrescente
    ordinata = sorted(L, reverse=True)   # N*log(N)
    # estraggo i primi k
    return ordinata[:k]                  # k

###############################################################

'''
Vogliamo usare poca memoria

    tenere in memoria SOLO k valori 

per ottenere i k massimi di tantissimi valori estratti a caso
    definisco ed inizializzo una lista vuota per i k valori
    scandisco tutti i valori in input e per ciascuno 
        aggiorno la lista dei k migliori già visti
    ritornare la lista dei k valori finale

per aggiornare la lista dei k valori con un nuovo valore X
    se la lista di valori ha meno di k elementi
        aggiungo il nuovo valore
    se X è minore o uguale del minimo dei k valori
        lo posso ignorare
    altrimenti è maggiore del minimo
        tolgo il valore più piccolo
        aggiungo il nuovo valore
        
gestire bene k=0
'''

import random

# per ottenere i k massimi di tantissimi valori estratti a caso
@profile
def k_massimi_da_seq_casuale(k, N, seed):
    # settare il generatore al valore iniziale
    random.seed(seed)
    #definisco ed inizializzo una lista vuota per i k valori
    risultato = []
    #scandisco tutti i valori in input e per ciascuno
    for _ in range(N):
        valore = random.randint(-1000000, +1000000)
        # aggiorno la lista dei k migliori già visti
        aggiorna_k_massimi(risultato, valore, k)
    # ritornare la lista dei k valori finale
    return risultato
    
# per aggiornare la lista dei k valori con un nuovo valore X
@profile
def aggiorna_k_massimi(L, X, K):
    """
    Parameters
    ----------
    L : lista di numeri da aggiornare
    
    X : valore numerico da inserire in L se necessario
    
    K : numero di elementi di L 
    
    Returns
    -------
    None.
    """
    # se la lista di valori ha meno di k elementi
    if len(L) < K:
        # aggiungo il nuovo valore
        L.append(X)                     # costante
        return
    # se X è minore o uguale del minimo dei k valori
    m = min(L)                          # len(L)
    if X <= m:                        
        # lo posso ignorare
        pass
    # altrimenti è maggiore del minimo
    else:
        # tolgo il valore più piccolo
        L.remove(m)                      # len(L)
        # aggiungo il nuovo valore
        L.append(X)                     # costante

'''
se tengo la lista di k valori ordinata
- trovare il minimo è costante (ultimo elemento)
- eliminare il minimo è costante
- per mantenere la lista ordinata
    - aggiungere l'elemento
    - riordinare la lista
'''

def aggiorna_lista_k_massimi_ordinati(Lordinata, X, K):
    # se len(Lordinata) < K aggiungo il valore
    if len(Lordinata) < K:
        # aggiungo il valore
        Lordinata.append(X)                 # costante
        # mantengo ordinata la lista
        Lordinata.sort(reverse=True)        # N*log(N)
    # se X è maggiore del minimo 
    elif X > Lordinata[-1]:                 # costante
        # lo aggiungo e tolgo il minimo
        Lordinata[-1] = X                   # costante
        # mantengo ordinata la lista
        Lordinata.sort(reverse=True)        # N*log(N)
    # altrimento X <= minimo e posso ignorarlo


# per ottenere i k massimi di tantissimi valori estratti a caso
@profile
def k_massimi_da_seq_casuale_ordinata(k, N, seed):
    # settare il generatore al valore iniziale
    random.seed(seed)
    #definisco ed inizializzo una lista vuota per i k valori
    risultato = []
    #scandisco tutti i valori in input e per ciascuno
    for _ in range(N):
        valore = random.randint(-1000000, +1000000)
        # aggiorno la lista dei k migliori già visti
        aggiorna_lista_k_massimi_ordinati(risultato, valore, k)
    # ritornare la lista dei k valori finale
    return risultato
    

'''
L'aggiornamento della lista ordinata può essere fatto in tempo
N + log(N) se 
usiamo una ricerca binaria per trovare la posizione log(N)
e poi un insert (N)
'''


if __name__ == '__main__':
    # questo codice non viene eseguito all'import
    import random
    # creo una lista di 1000 valori casuali (anche ripetuti)
    L = random.choices(range(-1000000,1000000),k=1000)
    k_massimi_ND(100,L)
    k_massimi_ordinati(100,L)
    
    L1 = k_massimi_da_seq_casuale(1000, 100000, 0)
    L2 = k_massimi_da_seq_casuale_ordinata(1000, 100000, 0)
    L1.sort(reverse=True)
    print(L1 == L2)