import estructura
from lista import *

#P1

estructura.crear("coeficiente", "valor potencia")
P = lista(coeficiente(5,3), lista(coeficiente(3,1), None))
P2 = lista(coeficiente(5,3), lista(coeficiente(0,2), lista(coeficiente(3,1), lista(coeficiente(0,0), None))))

# evaluar: lista(coeficiente) int -> int
# evalua un polinomio en un valor dado
# Ej: evaluar(P, 2) == 46
def evaluar(P, x):
	if P == None:
		return 0
	coef = cabeza(P)
	v = coef.valor
	p = coef.potencia
	resultado = v*x**p
	return resultado + evaluar(cola(P), x)

assert evaluar(P, 2) == 46

# evaluarLista: lista(coeficiente) lista(int) -> lista(int)
# evalua un polinomio segun una lista de valores
# Ej: evaluarLista(P, lista(2, lista(3, None))) == lista(46, lista(144, None))
def evaluarLista(P, L):
	if L == None:
		return None
	valor = cabeza(L)
	resultado = evaluar(P, valor)
	return lista(resultado, evaluarLista(P, cola(L)))

assert evaluarLista(P, lista(2, lista(3, None))) == lista(46, lista(144, None))

# eliminarCeros: lista(coeficiente) -> lista(coeficiente)
# eliminar los ceros de un polinomio
# Ej: eliminarCeros(P2) == lista(coeficiente(5,3),lista(coeficiente(3,1),None))
def eliminarCeros(P):
	if P == None:
		return None
	coef = cabeza(P)
	v = coef.valor
	if v == 0:
		return eliminarCeros(cola(P))
	else:
		return lista(coef, eliminarCeros(cola(P)))

assert eliminarCeros(P2) == lista(coeficiente(5,3), lista(coeficiente(3,1), None))

#P2

estructura.crear("arbol", "valor izq der")
A = arbol(27, arbol(12, None, None), arbol(35, None, arbol(42, None, None)))
B = arbol(12, arbol(6, None, None), arbol(35, None, None))

# enArbol: int arbol(int) -> bool
# verifica si un valor esta en un arbol
# Ej: enArbol(35, A) == True
def enArbol(x, A):
	if A == None:
		return False
	v = A.valor
	if x == v:
		return True
	else:
		return enArbol(x, A.izq) or enArbol(x, A.der)

assert enArbol(27, A)
assert not enArbol(14, A)

# quitarValor: arbol(int) -> arbol(int)
# quita la raiz de un arbol
# Ej: quitarRaiz(B) == arbol(6, None ,arbol(35,None,None))
def quitarRaiz(A):
	if A == None:
		return None
	elif A.izq == None and A.der == None:
		return None
	elif A.izq == None:
		return arbol((A.der).valor, A.izq, quitarRaiz(A.der))
	else:
		return arbol((A.izq).valor, quitarRaiz(A.izq), A.der)

assert quitarRaiz(A) == arbol(12, None, arbol(35, None, arbol(42, None, None)))
assert quitarRaiz(B) == arbol(6, None, arbol(35, None, None))

# inter: arbol(int) arbol(int) -> arbol(int)
# intersecta dos arboles
# Ej: inter(A, B) == arbol(12,None,arbol(35,None,None)))
def inter(A, B):
	if A == None:
		return None
	v = A.valor
	if enArbol(v, B):
		return arbol(v, inter(A.izq, B), inter(A.der, B))
	if A.izq == None and A.der == None:
		return None
	elif A.izq == None:
		return inter(A.der, B)
	elif A.der == None:
		return inter(A.izq, B)
	II = inter(A.izq, B)
	ID = inter(A.der, B)
	if II == None and ID == None:
		return None
	elif II == None:
		return ID
	elif ID == None:
		return II
	else:
		return arbol(II.valor, quitarRaiz(II), ID)

assert (inter(A, B) == arbol(12, None, arbol(35, None, None))) or (inter(A, B) == arbol(35, arbol(12, None, None), None))

# binario: int -> int
# transforma un numero a binario
# Ej: FUNCION NO HACE NADA, ES SOLO PARA QUE LA SIGUIENTE CORRA
def binario(x):
	return 1

# aBinario: arbol -> arbol
# transforma los valores de un arbol a binario
def aBinario(B):
	if B == None:
		return None
	else:
		return arbol(binario(B.valor), aBinario(B.izq), aBinario(B.der))

#P3

L = lista(18790521,lista(18100918,lista(18180212,lista(20180503, None))))

# fechasDelMes: lista(int) int -> lista(int)
# entrega las fechas de una lista que pertenecen a cierto mes
# Ej: fechasDelMes(L, 5) == lista(18790521,lista(20180503,None))
def fechasDelMes(L, mes):
	if L == None:
		return None
	v = cabeza(L)
	m = (v/100)%100
	if m == mes:
		return lista(v, fechasDelMes(cola(L),mes))
	else:
		return fechasDelMes(cola(L),mes)

assert fechasDelMes(L, 5) == lista(18790521,lista(20180503, None))

A = arbol(18790521, arbol(18100918, None, arbol(18180212, None, None)), arbol(20180503, None, None))

# menor: arbol(int) -> int
# entrega el menor valor de un arbol
# Ej: menor(A) == 18100918
def menor(A):
	if A == None:
		return None
	elif A.izq == None:
		return A.valor
	else:
		return menor(A.izq)

assert menor(A) == 18100918