TdA - TP1 v2.9

###                          ###
###  ESTADISTICO DE ORDEN K  ###
###                          ###


# En ambas formas, cand es el indice en conj del numero candidato
# Asumiendo minimo k cuando hay repetidos
def fuerza_bruta1(conj, cand, k):
    real_k = 1
    for i in conj:
        if (i < conj[cand]):
            real_k += 1
            if (real_k > k):
                return False
    if (real_k < k):
        return False
    return True

# Sin esa restriccion
def fuerza_bruta2(conj, cand, k):
    min_real_k = 1
    diff_max_k = 0

    for idx, i in enumerate(conj):
        if (i < conj[cand]):
            min_real_k += 1
            if (min_real_k > k):
                return False
        elif (i == conj[cand] and idx != cand):
            diff_max_k += 1
    if (min_real_k + diff_max_k < k):
        return False
    return True


def ordenar_y_seleccionar(conj, k):
    conj.sort()
    return conj[k-1]


# k > 0
def k_selecciones(array, k):
    for i in range(0, k):
        min = i
        for j in range(i+1,len(array)):
            if array[j] < array[min]:
                min = j
        if i != min:
            array[i] , array[min] = array[min] , array[i]
    return array[k-1]


# Para heapificar
def moveDown(conj, actual, last):
    hijo = 2 * actual + 1
    while (hijo <= last):
        if (hijo < last and conj[hijo] > conj[hijo + 1]):
            hijo += 1
        if (conj[actual] > conj[hijo]):
            conj[actual], conj[hijo] = conj[hijo], conj[actual]
            actual = hijo
            hijo = 2 * actual + 1
        else:
            return


def k_heapsort(array, k):
    last = len(array)
    for i in xrange(0, k):
        last -= 1
        #heapifico
        for j in xrange(last // 2, -1, -1):
            moveDown(array, j, last)
        if i != (k-1):
            array[0], array[last] = array[last], array[0]
    return array[0]


# k >= 1
def heapselect(conj, k):
    last = len(conj) - 1
    # heapifico
    for i in xrange(last // 2, 0-1, -1):
        moveDown(conj, i, last)
    limit = last - k + 1
    for i in xrange(last, limit, -1):
        if (conj[0] < conj[i]):
            conj[0], conj[i] = conj[i], conj[0]
            moveDown(conj, 0, i - 1)
    return conj[0]


def quickselect():
    return




### TESTS ###

## fuerza_bruta
my_list = [4, 1, 5, 9, 12, 3, 0, 2, 7, 6]
true_k  = [5, 2, 6, 9, 10, 4, 1, 3, 8, 7]
for idx, k in enumerate(true_k):
	assert fuerza_bruta1(my_list, idx, k)

my_list = [1, 1, 5, 12, 12, 5, 7, 2, 7, 6]
true_k  = [1, 2, 4,  9, 10, 5, 7, 3, 8, 6]
for idx, k in enumerate(true_k):
    assert fuerza_bruta2(my_list, idx, k)

## ordenar_y_seleccionar
my_list = [1, 1, 5, 12, 12, 5, 7, 2, 7, 6]
sorted_l = my_list
sorted_l.sort()
result = []
for k in xrange(1, 11):
    result.append(ordenar_y_seleccionar(my_list, k))
assert result == sorted_l

## k_selecciones
my_list  = [4, 1, 5, 9, 12, 3, 0, 2, 7, 6]
sorted_l = [0, 1, 2, 3, 4, 5, 6, 7, 9, 12]
for idx in xrange(0, 8):
    assert k_selecciones(my_list, idx+1) == idx

## k_heapsort
my_list  = [4, 1, 5, 9, 12, 3, 0, 2, 7, 6]
sorted_l = [0, 1, 2, 3, 4, 5, 6, 7, 9, 12]
for idx, i in enumerate(sorted_l):
    assert k_heapsort(my_list, idx+1) == i

## heapselect
my_list  = [4, 1, 5, 9, 12, 3, 0, 2, 7, 6]
sorted_l = [0, 1, 2, 3, 4, 5, 6, 7, 9, 12]
for idx, i in enumerate(sorted_l):
    assert heapselect(my_list, idx+1) == i


# auxiliar
def print_list(array):
    print "[",
    for i in xrange(0, len(array)):
        print array[i], ",",
    print "]"