from funcionesAbstractas import *
L=lista(2,lista(3,lista(1,None)))

#ordenar: lista -> lista
#lista con valores de L ordenados (y distintos)
#ej: ordenar(L)->lista(1,lista(2,lista(3,None)))

def ordenar(L):
    assert esLista(L)
    if vacia(L): return listaVacia
    menor=reductor(L,min,cabeza(L))
    mayores=filtro(L,lambda x: x>menor)
    return lista(menor,ordenar(mayores))

assert ordenar(L)==lista(1,lista(2,lista(3,None)))

#concatenar: lista lista -> lista
#lista con x1, x2, … , y1, y2, …
#ej: concatenar(lista(1,lista(2,None)), lista(3,None)) ->
#               lista(1,lista(2,lista(3,None)))

def concatenar(x,y):
    assert esLista(x)
    assert esLista(y)
    if vacia(x): return y
    return lista(cabeza(x),concatenar(cola(x),y))

assert concatenar(lista(1,lista(2,None)), lista(3,None))==\
                  lista(1,lista(2,lista(3,None)))

assert concatenar(lista(1,None),listaVacia)==lista(1,None)

assert concatenar(listaVacia,lista(1,None))==lista(1,None)


L=lista(2,lista(3,lista(1,lista(3,None))))
#ordenar: lista -> lista
#lista con valores de L ordenados
#ej: ordenar(L)->lista(1,lista(2,lista(3,lista(3,None))))

def ordenar(L):
    assert esLista(L)
    if vacia(L): return listaVacia
    menor=reductor(cola(L),min,cabeza(L))
    menores=filtro(L,lambda x: x==menor)
    mayores=filtro(L,lambda x: x>menor)
    return concatenar(menores,ordenar(mayores))


#mcd: int int -> int
#maximo comun dividosr entre x e y (enteros positivos)
#ej: mcd(18,24)->6, mcd(9,4)->1
def mcd(x,y):
    assert type(x)==int and x>0
    assert type(y)==int and y>0
    return x if x==y else mcd(x,y-x) if x<y else mcd(x-y)
    
from fraccion import *
L=lista(fraccion(2,3),lista(fraccion(1,2),None))
#ordenarFracciones: lista(fraccion) -> lista(fraccion)
#lista con fracciones de L ordenadas
#ej: ordenarFracciones(L) -> 
#    lista(fraccion(1,2),lista(fraccion(2,3),None))

def ordenarFracciones(L):
    assert esLista(L)
    if vacia(L): return listaVacia
    def min(x,y): return x if comparar(x,y)<0 else y
    menor=reductor(cola(L),min,cabeza(L))
    menores=filtro(L,lambda x: comparar(x,menor)==0)
    mayores=filtro(L,lambda x: comparar(x,menor)>0)
    return concatenar(menores,ordenarFracciones(mayores))

assert ordenarFracciones(L)==\
       lista(fraccion(1,2),lista(fraccion(2,3),None))