Estructuras II TP 1

import Prelude

data NdTree p = Node (NdTree p) p (NdTree p) Int | Empty
                deriving (Eq, Ord, Show)

class Punto p where
    dimension :: p -> Int
    coord :: Int -> p -> Double
    dist :: p -> p -> Double
    -- Se crea una lista con las diferencias al cuadrado de todas las coordenadas.
    -- Luego, se suman todos los elementos.
    dist a b = foldl (+) 0 [((coord i a) - (coord i b)) ^ 2 | i <- [0 .. ((dimension a ) - 1)]]


newtype Punto2d = P2d (Double, Double) deriving (Eq, Show)
newtype Punto3d = P3d (Double, Double, Double) deriving (Eq, Show)
type Rect = (Punto2d, Punto2d)


instance Punto Punto2d where
  dimension p = 2
  coord 0 (P2d (x, y)) = x
  coord 1 (P2d (x, y)) = y

instance Punto Punto3d where
  dimension p = 3
  coord 0 (P3d (x, y, z)) = x
  coord 1 (P3d (x, y, z)) = y
  coord 2 (P3d (x, y, z)) = z


sortNuestro :: Punto p => Int -> [p] -> [p]
sortNuestro _ [] = []
sortNuestro c (x:xs) = sortNuestro c menores ++ [x] ++ sortNuestro c mayores
    where cx = (coord c x)
          menores = [a | a <- xs, (coord c a) <= cx]
          mayores = [b | b <- xs, (coord c b) >  cx]


armarArbol :: Punto p => [p] -> Int -> NdTree p
-- Cuando una lista quede vacía, se construye una hoja.
armarArbol [] _ = Empty
-- En caso contrario, se procede a dividir el arreglo para construir un árbol no vacío.
armarArbol (x:xs) h = let mitad = div (length (x:xs)) 2
                          eje = mod h (dimension x) -- El eje a partir del cual se ordena al arreglo.
                          xsOrdenado = sortNuestro eje (x:xs)
                          mediana = xsOrdenado !! mitad -- Tomamos el valor de la mediana, y se revisa que
                                                        -- todos los valores con una coordenada igual
                                                        -- queden en el mismo subárbol.
                          primeraMitad = takeWhile (\x -> (coord eje x) <= (coord eje mediana)) xsOrdenado
                          pivot = last primeraMitad -- El nodo que se usará de raíz será el último punto que
                                                    -- contenga la misma coordenada que la mediana
                          segundaMitad = drop (length primeraMitad) xsOrdenado -- La segunda mitad es el resto del arreglo.
                       -- Se construye el nodo, dejando la primera mitad como árbol izquierdo,
                       -- la segunda mitad como árbol derecho y el pivot como dato.
                       in Node
                          (armarArbol (init primeraMitad) (h + 1))
                          pivot
                          (armarArbol segundaMitad (h + 1))
                          eje


fromList :: Punto p => [p] -> NdTree p
-- Se llama a la función auxiliar de construcción, indicando que la altura del primer nodo es 0.
fromList xs = armarArbol xs 0


insertarAux :: Punto p => p -> NdTree p -> Int -> NdTree p
-- Si se llega a una hoja, construimos el nodo con el valor correspondiente allí.
insertarAux punto Empty h            = Node Empty punto Empty (mod h (dimension punto))
-- Si no, se compara la coordenada correspondiente del valor a agregar con el nodo raíz,
-- y se lo inserta de acuerdo a si es menor o mayor.
insertarAux punto (Node i r d eje) h | (coord eje punto) <= (coord eje r) = Node (insertarAux punto i (h + 1) ) r d eje
                                     | otherwise                          = Node i r (insertarAux punto d (h + 1) ) eje


insertar :: Punto p => p -> NdTree p -> NdTree p
-- Se llama a la función auxiliar de inserción, indicando que la altura del primer nodo es 0.
insertar punto arbol = insertarAux punto arbol 0


minDeATres :: Punto p => p -> p -> p -> Int -> p
-- Devuelve el punto con menor coordenada de acuerdo a un eje.
minDeATres x y z eje | coordX <= coordY && coordX <= coordZ = x
                     | coordY <= coordX && coordY <= coordZ = y
                     | otherwise                            = z
                     where coordX = coord eje x
                           coordY = coord eje y
                           coordZ = coord eje z


buscarMinAux :: Punto p => NdTree p -> Int -> p -> p
-- Si se llega a una hoja, se devuelve como valor mínimo el posible valor actual.
buscarMinAux Empty ejeComp posibleMin = posibleMin
-- Si no, se buscan recursivamente los mínimos de ambos subárboles y se devuelve el menor entre ellos y el nodo raíz.
-- Se tiene la salvedad de que si el eje de comparación coincide con el eje del nodo,
-- no se busca en los dos subárboles, sino sólo en el izquierdo.
buscarMinAux (Node i dato d eje) ejeComp posibleMin |  eje == ejeComp = if (coord ejeComp dato) <= (coord ejeComp minI) then dato else minI
                                                    |  otherwise      = minDeATres (buscarMinAux i ejeComp posibleMin) dato (buscarMinAux d ejeComp posibleMin) ejeComp
                                                    where minI = (buscarMinAux i ejeComp posibleMin)


buscarMin :: Punto p => NdTree p -> Int -> p
-- Se llama a la función auxiliar, indicando que el posible mínimo es la raíz del árbol.
buscarMin raiz@(Node i dato d eje) ejeComp = buscarMinAux raiz ejeComp dato


maxDeATres :: Punto p => p -> p -> p -> Int -> p
-- Devuelve el punto con mayor coordenada de acuerdo a un eje.
maxDeATres x y z eje | coordX >= coordY && coordX >= coordZ = x
                     | coordY >= coordX && coordY >= coordZ = y
                     | otherwise                            = z
                     where coordX = coord eje x
                           coordY = coord eje y
                           coordZ = coord eje z


buscarMaxAux :: Punto p => NdTree p -> Int -> p -> p
-- Si se llega a una hoja, se devuelve como valor máximo el posible valor actual.
buscarMaxAux Empty ejeComp posibleMax = posibleMax
-- Si no, se buscan recursivamente los máximos de ambos subárboles y se devuelve el mayor entre ellos y el nodo raíz.
-- Se tiene la salvedad de que si el eje de comparación coincide con el eje del nodo,
-- no se busca en los dos subárboles, sino sólo en el derecho.
buscarMaxAux (Node i dato d eje) ejeComp posibleMax |  eje == ejeComp = if (coord ejeComp dato) >= (coord ejeComp maxD) then dato else maxD
                                                    |  otherwise = maxDeATres (buscarMaxAux i ejeComp posibleMax) dato (buscarMaxAux d ejeComp posibleMax) ejeComp
                                                    where maxD = (buscarMaxAux d ejeComp posibleMax)

buscarMax :: Punto p => NdTree p -> Int -> p
-- Se llama a la función auxiliar, indicando que el posible máximo es la raíz del árbol.
buscarMax raiz@(Node i dato d eje) ejeComp = buscarMaxAux raiz ejeComp dato


eliminar :: (Eq p, Punto p) => p -> NdTree p -> NdTree p
-- Si se llega una hoja, no se modifica.
eliminar punto Empty = Empty
-- Si se llega a un nodo con hojas como hijos, se lo elimina si el dato coincide con el buscado.
eliminar punto nodo@(Node Empty dato Empty _ ) = if punto == dato then Empty else nodo
-- Si el nodo posee algún hijo no vacío, se compara su dato con el buscado.
-- En caso de ser iguales, se busca el mínimo con respecto al eje del nodo en el subárbol derecho como reemplazo.
-- Si éste fuera vacío, se busca el máximo en el izquierdo.
-- Si el dato no es igual al buscado, se revisa el subárbol correspondiente al orden entre las coordenadas del dato y el buscado.
eliminar punto (Node i dato d eje) | punto == dato                     = if d /= Empty
                                                                             then (Node i candidatoD (eliminar candidatoD d) eje)
                                                                             else (Node (eliminar candidatoI i) candidatoI d eje)
                                   | coord eje punto <= coord eje dato = (Node (eliminar punto i) dato d eje)
                                   | otherwise                         = (Node i dato (eliminar punto d) eje)
                                   where candidatoD = buscarMin d eje
                                         candidatoI = buscarMax i eje


limites :: Rect -> Int -> (Double, Double)
-- Dado un rectángulo y un eje, devuelve una tupla con los valores mínimo y máximo
-- en ese eje que determinan los vértices de la diagonal.
limites (P2d(x1,y1), P2d (x2,y2) ) 0 = if x1 <= x2 then (x1, x2) else (x2, x1)
limites (P2d(x1,y1), P2d (x2,y2) ) 1 = if y1 <= y2 then (y1, y2) else (y2, y1)


ortogonalSearch :: NdTree Punto2d -> Rect -> [Punto2d]
-- Si se llega a una hoja, se devuelve una lista vacía.
ortogonalSearch Empty _ = []
-- Si no, se revisa el dato para ver si se lo debe agregar a la lista.
ortogonalSearch (Node i dato d eje) rect
                                         -- Si su coordenada está por debajo del límite inferior,
                                         -- sólo se busca en su subárbol derecho.
                                         | coordDato < lInf                          = ortogonalSearch d rect
                                         -- Si su coordenada está por encima del límite superior,
                                         -- sólo se busca en su subárbol izquierdo.
                                         | coordDato > lSup                          = ortogonalSearch i rect
                                         -- Si su coordenada está entre los valores de los límites,
                                         -- se lo agrega a la lista si está entre los valores en el otro eje.
                                         | coordDato2 >= lInf2 && coordDato2 <= lSup2 =  [dato] ++ busqHijos
                                         -- Si no, sólo se devuelve la búsqueda en sus hijos.
                                         | otherwise                                     = busqHijos
                                         where
                                               -- Límites inferior y superior del rectángulo en
                                               -- el eje del nodo.
                                               (lInf, lSup) = limites rect eje
                                               -- Límites inferior y superior del rectángulo en
                                               -- el otro eje.
                                               (lInf2, lSup2) = limites rect (mod (eje + 1) 2)
                                               -- Coordenada del dato en el eje del nodo.
                                               coordDato = coord eje dato
                                               -- Coordenada del dato en el otro eje.
                                               coordDato2 = coord (mod (eje + 1) 2) dato
                                               -- Resultado de la búsqueda en ambos subárboles.
                                               busqHijos = (ortogonalSearch i rect) ++ (ortogonalSearch d rect)


-- ALGUNOS EJEMPLOS CON LOS QUE PROBAMOS LAS FUNCIONES

-- Lista de los nodos usados como ejemplo en los enunciados del Trabajo.
listaEj = [P2d (2,3), P2d (5,4), P2d (9,6), P2d (4,7), P2d (8,1), P2d (7,2)]
-- Arbol construido a partir de la lista de ejemplo.
arbolEj = fromList listaEj
-- Prueba de insertar un valor mayor a todos los existentes.
arbolIns1 = insertar (P2d (100,100)) arbolEj
-- Prueba de insertar luego un valor intermedio.
arbolIns2 = insertar (P2d (4,8)) arbolIns1

-- Prueba de eliminar un dato inexistente.
arbolDel1 = eliminar (P2d (66, 66)) arbolEj
-- Prueba de eliminar una hoja.
arbolDel2 = eliminar (P2d (2.0, 3.0)) arbolEj
-- Prueba de eliminar un nodo con subárbol derecho vacío.
arbolDel3 = eliminar (P2d (9, 6)) arbolEj
-- Prueba de eliminar la raíz.
arbolDel4 = eliminar (P2d (7, 2)) arbolEj

-- Rectángulo de prueba para la función de búsqueda.
rectEj = ( (P2d (5,5)), (P2d (10,10)) )
-- Prueba de búsqueda en el árbol del ejemplo.
searchEj = ortogonalSearch arbolEj rectEj

-- Resultados de los ejemplos anteriores.
{-
NOTA: Intercalamos renglones entre valores de la estructura de la raíz para que queden con el formato:
Node
 Subárbol Izquierdo
 Valor del Nodo
 Subárbol Derecho
 Eje

arbolEj =
Node
(Node (Node Empty (P2d (2.0,3.0)) Empty 0) (P2d (5.0,4.0)) (Node Empty (P2d (4.0,7.0)) Empty 0) 1)
(P2d (7.0,2.0))
(Node (Node Empty (P2d (8.0,1.0)) Empty 0) (P2d (9.0,6.0)) Empty 1)
0

arbolIns1 =
Node
(Node (Node Empty (P2d (2.0,3.0)) Empty 0) (P2d (5.0,4.0)) (Node Empty (P2d (4.0,7.0)) Empty 0) 1)
(P2d (7.0,2.0))
(Node (Node Empty (P2d (8.0,1.0)) Empty 0) (P2d (9.0,6.0)) (Node Empty (P2d (100.0,100.0)) Empty 0) 1)
0


arbolIns2 =
Node
(Node (Node Empty (P2d (2.0,3.0)) Empty 0) (P2d (5.0,4.0)) (Node (Node Empty (P2d (4.0,8.0)) Empty 1) (P2d (4.0,7.0)) Empty 0) 1)
(P2d (7.0,2.0))
(Node (Node Empty (P2d (8.0,1.0)) Empty 0) (P2d (9.0,6.0)) (Node Empty (P2d (100.0,100.0)) Empty 0) 1)
0


arbolDel1 == arbolEj =
True


arbolDel2 =
Node
(Node Empty (P2d (5.0,4.0)) (Node Empty (P2d (4.0,7.0)) Empty 0) 1)
(P2d (7.0,2.0))
(Node (Node Empty (P2d (8.0,1.0)) Empty 0) (P2d (9.0,6.0)) Empty 1)
0


arbolDel3 =
Node
(Node (Node Empty (P2d (2.0,3.0)) Empty 0) (P2d (5.0,4.0)) (Node Empty (P2d (4.0,7.0)) Empty 0) 1)
(P2d (7.0,2.0))
(Node Empty (P2d (8.0,1.0)) Empty 1)
0


arbolDel4 =
Node
(Node (Node Empty (P2d (2.0,3.0)) Empty 0) (P2d (5.0,4.0)) (Node Empty (P2d (4.0,7.0)) Empty 0) 1)
(P2d (8.0,1.0))
(Node Empty (P2d (9.0,6.0)) Empty 1)
0


searchEj =
[P2d (9.0,6.0)]
-}