# IAL-501 (Prof. Dr. Silvio do Lago Pereira)

from util import *

#-----------------------------------------------------------
# Exemplo 1
#-----------------------------------------------------------

def lsearch(x,v):
    n = len(v)
    for i in range(0,n):
        if x == v[i]:
            return True
    return False

#-----------------------------------------------------------
# Exercicio 3
#-----------------------------------------------------------

def clsearch(x,v):
    n = len(v)
    for i in range(0,n):
        if x == v[i]: return i+1
    return n

#-----------------------------------------------------------
# Exercicio 4
#-----------------------------------------------------------

def linear():
    X = range(100,1001,100)
    Y = []
    for n in X:
        v = seq(n,0,n)
        Y.append(sum(clsearch(x,v) for x in v)/n)
    title('Caso médio da busca linear')   
    xlabel('tamanho da entrada')
    ylabel('itens examinados')
    plot(X,Y,'r-o')
    grid(True)
    show()

#-----------------------------------------------------------
# Exemplo 2
#-----------------------------------------------------------

def solsearch(x,v):
    n = len(v)
    for i in range(0,n):
        if x == v[i]:
            if i > 0: troca(v,i,i-1)     
            return True
    return False

#-----------------------------------------------------------
# Exercicio 12
#-----------------------------------------------------------

def csolsearch(x,v):
    n = len(v)
    for i in range(0,n):
        if x == v[i]:
            if i > 0: troca(v,i,i-1)     
            return i+1
    return n

def organizing():
    X,Y,Z = range(1,11),[],[]
    v = seq(100,0,100)
    s = seq(10**5,M([range(0,10),range(10,100),range(100,1000)],
                    [0.85, 0.10, 0.05]))
    for i in X:
        shuffle(v)
        Y.append(sum(clsearch(x,v) for x in s)/len(s))
        Z.append(sum(csolsearch(x,v) for x in s)/len(s))
    title('Caso favorável para busca linear auto-organizadora')
    xlabel('permutação da entrada')
    ylabel('número médio de itens examinados')
    plot(X,Y,'r-o',label='lsearch')
    plot(X,Z,'b-s',label='solsearch')
    legend(loc='center left')
    grid(True)
    show() 

#-----------------------------------------------------------
# Exemplo 3
#-----------------------------------------------------------

def bsearch(x,v):
    n = len(v)
    p = 0
    u = n-1
    while p <= u:
        m = (p+u)//2
        if x == v[m]: return True
        if x < v[m]: u = m-1
        else: p = m+1 
    return False

#-----------------------------------------------------------
# Exercicio 14
#-----------------------------------------------------------

def cbsearch(x,v):
    c = 0
    n = len(v)
    p = 0
    u = n-1
    while p <= u:
        m = (p+u)//2
        c += 1
        if x == v[m]: return c
        if x < v[m]: u = m-1
        else: p = m+1 
    return c

#-----------------------------------------------------------
# Exercicio 15
#-----------------------------------------------------------

def binary():
    X = [2**k-1 for k in range(1,11)]
    Y = []
    for n in X:
        v = range(n)
        Y.append(sum(cbsearch(x,v) for x in v)/n)
    title('Caso médio da busca binária')   
    xlabel('tamanho da entrada')
    ylabel('itens examinados')
    plot(X,Y,'b-s')
    grid(True)
    show()

#-----------------------------------------------------------
# Exemplo 4
#-----------------------------------------------------------

def interp(x,xp,p,xu,u):
    return p + (u-p)*(x-xp)/(xu-xp)

#-----------------------------------------------------------
# Exemplo 5
#-----------------------------------------------------------

def isearch(x,v):
    n = len(v)
    p = 0
    u = n-1
    while p <= u:
        q = p + (u-p)*(x-v[p])//max(v[u]-v[p],1)
        if q<p or q>u: return False
        if x == v[q]: return True
        if x < v[q]: u = q-1
        else: p = q+1 
    return False

#-----------------------------------------------------------
# Exercicio 18
#-----------------------------------------------------------

def cisearch(x,v):
    c = 0
    n = len(v)
    p = 0
    u = n-1
    while p <= u:
        q = p + (u-p)*(x-v[p])//max(v[u]-v[p],1)
        if q<p or q>u: return c
        c += 1 
        if x == v[q]: return c
        if x < v[q]: u = q-1
        else: p = q+1
    return c

#-----------------------------------------------------------
# Exercicio 22
#-----------------------------------------------------------

def interpolation():
    X = range(2,21)
    Y,Z = [],[]
    for n in [2**k-1 for k in X]:
        v = sorted(seq(n,U(0,3*n)))
        Y.append(sum(cbsearch(x,v) for x in v)/n)
        Z.append(sum(cisearch(x,v) for x in v)/n)
    title('Caso médio da busca por interpolação') 
    xlabel('tamanho da entrada ($n = 2^k-1$)')
    ylabel('itens examinados')
    plot(X,Y,'r-o',label='binary')
    plot(X,Z,'b-s',label='interpolation')
    legend(loc='upper left')
    grid(True)
    show()