#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Oct  9 11:50:46 2018

@author: andrea
"""

import random

def k_massimi(L, K):
    assert 0 <= K <= len(L), "K non è compreso tra 0 e len(L)"
    massimi = []
    for i in range(K):
        massimi.append(estrai_massimo(L))
    return massimi

def estrai_massimo(L):
    assert L, "la lista è vuota"
    M = max(L)
    L.remove(M)
    return M


def k_massimi2(L, K):
    L2 = sorted(L, reverse=True)
    return L2[:K]

def k_massimi3(N, K):
    massimi = []
    for _ in range(N):
        X = random.randint(-10000000, 10000000)
        aggiorna_massimi(massimi, X, K)
    return massimi

def aggiorna_massimi(lista, valore, K):
    if len(lista) < K:
        lista.append(valore)
        return
    minimo = min(lista)
    if minimo >= valore:
        return
    lista.remove(minimo)
    lista.append(valore)
    
def aggiorna_massimi2(lista, valore, K):
    if len(lista) < K:
        lista.append(valore)
        lista.sort()
        return
    minimo = lista[0]
    if minimo >= valore:
        return
    lista.pop(0)
    lista.append(valore)
    lista.sort()

def k_massimi4(N, K):
    massimi = []
    for _ in range(N):
        X = random.randint(-10000000, 10000000)
        aggiorna_massimi2(massimi, X, K)
    return massimi


''' Per esercizio
    Implementate aggiorna_massimi in modo da:
    - mantenere la lista massimi ordinata
    - inserire il valore nella lista con una ricerca binaria
  '''

# per inserire un valore X in una lista ordinata L mantenendola ordinata
    # all'inizio la zona in cui il valore va inserito va da 0 a N-1
    # ovvero inizializzo inizio=0 e fine=len(lista)-1
    # ripeto se inizio < fine
        # calcolo l'indice medio
        # se l'elemento che sta in quella posizione è < X
            # il valore va alla destra del punto medio
            # ovvero inizio = medio+1
        # altrimenti
            # il valore va alla sinistra di medio
            # ovvero fine = medio-1
    # quando fine==inizio oppure fine<inizio
        # inserisco il valore nella posizione inizio

if __name__ == '__main__':
    L = k_massimi4(1000000, 300)