#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Oct 18 10:00:00 2019

@author: andrea
"""

from random import randint, seed

# Definire una funzione che riceve come parametri una lista di interi L e una costante positiva K e torna come risultato i K valori più grandi di L

# 1) ricerca distruttiva dei primi k massimi

# per estrarre i primi k massimi da una lista di interi
    # se k > len(L) lancio una eccezione
    # inizializzo il risultato con una lista vuota
    # per k volte cerco il massimo
        # rimuovo il massimo dalla lista
        # lo aggiungo al risultato
    # torno il risultato

# per estrarre i primi k massimi da una lista di interi
def k_massimi_distruttiva(L, k):
    """
    L : lista di interi
    K : intero
    torna i primo K massimi della lista
    Effetti collaterali: 
        L viene modificata
        se k>len(L) viene lanciata una eccezione
    Non esaminato:
        - k deve essere un intero >= 0
        - la lista deve contenere interi
    """
    # se k > len(L) lancio una eccezione
    assert k <= len(L), f"la lista è più corta di k={k}"
    # inizializzo il risultato con una lista vuota
    risultato = []
    # per k volte cerco il massimo
    for i in range(k):             # per k volte
        massimo = cerca_massimo(L) # tempo N
        # rimuovo il massimo dalla lista
        L.remove(massimo)          # tempo N
        # lo aggiungo al risultato
        risultato.append(massimo)  # tempo 1
    # torno il risultato
    return risultato

# per cercare il massimo di una lista
def cerca_massimo(L):
    "cerco il massimo"
    return max(L)


# per cercare i k massimi
def k_massimi(L, k):
    # controllo gli input
    # No effetti collaterali
    assert type(k) == int, "K dev'essere un intero"
    assert 0 <= k <= len(L), "K dev'essere compreso tra 0 e {len(L)}"
    # ordino la lista L senza modificare L
    ordinata = sorted(L, reverse=True)   # N * log(N)   
    # estraggo i k massimi
    return ordinata[:k]    

# AGGIUNGO IL VINCOLO CHE LA LISTA L NON È TUTTA IN MEMORIA
    
# per cercare i k massimi in una sequenza casuale di N elementi
    # all'inizio il risultato=[]
    # per ogni valore estratto a caso
        # se len(risultato) < k: aggiungo il valore
        # se è minore del minimo tra i massimi raccolti lo ignoro
        # altrimenti butto il minimo e aggiungo questo valore
    # torno i k massimi

# per cercare i k massimi in una sequenza casuale di N elementi
def k_massimi_casuali(S, N, k):
    " cerco i k massimi di una sequenza di lunghezza N a partire dal seme S"
    # all'inizio il risultato=[]
    risultato = []
    seed(S)             # inizializzo il generatore casuale
    # per N volte
    for _ in range(N):
        # estraggo a caso un valore
        valore = randint(-1000000000, 1000000000)
        # se len(risultato) < k: aggiungo il valore
        if len(risultato) < k:
            risultato.append(valore)
        # se è minore del minimo tra i massimi raccolti lo ignoro
        elif min(risultato) > valore:
            continue
        # altrimenti butto il minimo e aggiungo questo valore
        else:
            risultato.remove(min(risultato))
            risultato.append(valore)
    # torno i k massimi
    return risultato

# IDEA: mantenere i k valori ordinati
    # la ricerca del minimo diventa immediata (è l'ultimo elemento)
    # l'inserimento di un nuovo valore deve mantenere l'ordinamento
    # NON conviene eseguire un sort per ogni inserimento
    # conviene trovare la posizione in cui inserire l'elemento con una ricerca binaria














#       tempo: k*N

# 2) ordinamento ed estrazione dei primi K valori




















#       tempo: N*log(N) + K

# ESEMPIO2: k-massimi con limiti di memoria

# 3) mantengo una lista degli ultimi k massimi visti






















#       tempo: N + K*N

# 4) mantengo la lista dei K elementi ordinata



























#       tempo: N + N*log(K)