Estructuras II Práctica 5

-- EJERCICIO 1
-- CALCULAR TRABAJO Y PROFUNDIDAD

data BTree a = Empty | Node Int (BTree a) a (BTree a) deriving Show

-- Suponemos que lo hace de manera consciente.

sizeBT :: BTree a -> Int
sizeBT Empty = 0
sizeBT (Node size _ _ _) = size

nth :: BTree a -> Int -> a
nth (Node size l d r) indice | indice < sizeL  = nth l indice
                             | indice == sizeL = d
                             | otherwise       = nth r (indice - sizeL - 1)
                             where sizeL = sizeBT l

cons :: a -> BTree a -> BTree a
cons dato Empty = Node 1 Empty dato Empty
cons dato (Node size l d r) = Node (size + 1) (cons dato l) d r

tabulateAux :: (Int -> a) -> Int -> Int -> BTree a
tabulateAux f 0 _ = Empty
tabulateAux f numero offset | (mod numero 2) == 0 = let mitadI = div numero 2
                                                        mitadD = (div numero 2) - 1
                                                        tabI = tabulateAux f mitadI offset
                                                        dato = f (mitadI + offset)
                                                        tabD = tabulateAux f mitadD (offset + mitadI + 1)
                                                    in (Node numero tabI dato tabD)
                            | otherwise           = let mitad = div numero 2
                                                        tabI = tabulateAux f mitad offset
                                                        dato = f (mitad + offset)
                                                        tabD = tabulateAux f mitad (offset + mitad + 1)
                                                    in (Node numero tabI dato tabD)

tabulate :: (Int -> a) -> Int -> BTree a
tabulate f numero = tabulateAux f numero 0

mapBT :: (a -> b) -> BTree a -> BTree b
mapBT f Empty = Empty
mapBT f (Node size l d r) = Node size mapL (f d) mapR
                            where mapL = mapBT f l
                                  mapR = mapBT f r

takeBT :: Int -> BTree a -> BTree a
takeBT n Empty = Empty
takeBT 0 _ = Empty
takeBT n (Node size l d r) | n <= sizeL  = takeBT n l
                           | n == (sizeL + 1) = Node n l d Empty
                           | otherwise  = Node (min size n) l d (takeBT (n - sizeL - 1) r)
                           where sizeL = sizeBT l

dropBT :: Int -> BTree a -> BTree a
dropBT n Empty = Empty
dropBT n (Node size l d r) | n <= sizeL  = Node (size - n) (dropBT n l) d r
                           | n == (sizeL + 1) = r
                           | otherwise  = dropBT (n - sizeL - 1) r
                           where sizeL = sizeBT l

-- EJERCICIO 2
-- FALTA DEMOSTRAR

data Tree a = E | Leaf a | Join (Tree a) (Tree a)

mapreduce :: (a -> b) -> (b -> b -> b) -> b -> Tree a -> b
mapreduce f g e = mr where mr E          = e
                           mr (Leaf x)   = f x
                           mr (Join l r) = g (mr l) (mr r)


fMap :: Int -> (Int, Int, Int, Int)
fMap x = (x, max x 0, max x 0, max x 0)

fRed :: (Num a, Ord a) => (a, a, a, a) -> (a, a, a, a) -> (a, a, a, a)
fRed (mSumL,mPrefL,mSufL,sumL) (mSumR,mPrefR,mSufR,sumR) = let mSumT = max (max mSumL mSumR) (mSufL + mPrefR)
                                                               mPrefT = max mPrefL (sumL + mPrefR)
                                                               mSufT = max mSufR (mSufL + sumR)
                                                               sumT = sumL + sumR
                                                            in (mSumT, mPrefT, mSufT, sumT)


mcssAux :: Tree Int -> (Int,Int,Int,Int)
mcssAux tree = mapreduce fMap fRed casoBase tree
                         where casoBase = (minBound, 0, 0, 0)

mcss :: Tree Int -> Int
mcss t = let (a,b,c,d) = mcssAux t
         in a


--EJERCICIO 3
data Tree a = E | Leaf a | Join (Tree a) (Tree a) deriving Show

reduceT :: (a -> a -> a) -> a -> Tree a -> a
reduceT f e E = e
reduceT f e (Leaf x) = x
reduceT f e (Join l r) = f (reduceT f e l) (reduceT f e r)

mapreduce :: (a -> b) -> (b -> b -> b) -> b -> Tree a -> b
mapreduce f g e = mr where mr E          = e
                           mr (Leaf x)   = f x
                           mr (Join l r) = g (mr l) (mr r)


smartJoin :: Tree Int -> Tree Int -> Tree Int
smartJoin t1 E = t1
smartJoin t1 t2 = Join t1 t2


sufijosAux :: Tree Int -> Tree Int -> (Tree (Int, Tree Int), Tree Int)
sufijosAux E tAcum = (Leaf (0, tAcum) , tAcum) -- Tipo correcto.
sufijosAux (Leaf x) tAcum = (Leaf (x, tAcum), tRes) where tRes = (smartJoin (Leaf x) tAcum)  -- Tipo correcto.
sufijosAux (Join l r) tAcum = (Join hijoIzq hijoDer, acumIzq) --lI y lD deben ser Tree (Int, Tree Int)
                               where (hijoDer, acumDer) = sufijosAux r tAcum
                                     (hijoIzq, acumIzq) = sufijosAux l acumDer


conSufijos :: Tree Int -> Tree (Int, Tree Int)
conSufijos tree = t1 where (t1, _) = sufijosAux tree E

maxT :: Tree Int -> Int
maxT tree = reduceT max 0 tree

maxVenta :: (Int, Tree Int) -> Int
maxVenta (compra, arbolVentas) = (maxT arbolVentas) - compra

maxAll :: Tree (Int, Tree Int) -> Int
maxAll tree = mapreduce maxVenta max 0 tree


mejorGanancia :: Tree Int -> Int
mejorGanancia tree = maxAll (conSufijos tree)


ej = Join (Join (Leaf 10) (Leaf 150)) (Leaf 20) :: Tree Int
ej2 = Join (Join (Join (Leaf 5) (Leaf 3) ) (Join (Leaf 4) (Leaf 1))) (Leaf 5) :: Tree Int


-- EJERCICIO 4
data T a = E | N (T a) a (T a)

altura :: T a -> Int
altura E = 0
altura (N l x r ) = 1 + max (altura l , altura r )

seekAndDestroy :: T a -> (T a, a)
seekAndDestroy (N E d E) = (E, d)
seekAndDestroy (N E d r) = (r, d)
seekAndDestroy (N l d r) = ((N arbolNuevo d r), raiz) where (arbolNuevo, raiz) = seekAndDestroy l

combinar :: T a -> T a -> T a
combinar t1 E = t1
combinar E t2 = t2
combinar (N l d E) t2 = N l d t2
combinar (N E d r) t2 = N t2 d r
combinar t1@(N l d r) t2 = N nuevot1 nuevaRaiz t2 where (nuevot1, nuevaRaiz) = seekAndDestroy t1

combinarCeci :: T a -> T a -> T a
combinarCeci E t = t
combinarCeci (Node l d r) t = Node t d (combinar l r)


filterT :: (a -> Bool) -> T a -> T a
filterT pred E = E
filterT pred (N l d r) = if (pred d) then N (filterT l) d (filterT r)
                                     else combinar (filterT l) (filterT r)

-- Estoy convencido que se debe poder hacer más fácil, pero anda
filterT2 :: (a -> Bool) -> T a -> (T a, T a)
filterT2 pred E = (E, E)
filterT2 pred (N l d r) = let (lMenores, lMayores) = filterT2 pred l
                              (rMenores, rMayores) = filterT2 pred r
                         in if (pred d) then (N lMenores d rMenores, combinar lMayores rMayores)
                                        else (combinar lMenores rMenores, N lMayores d rMayores)

quickSortT :: T Int -> T Int
quickSortT E = E
quickSortT tree@(N l d r) = let (N ll d' rr, right) = filterT2 (\x -> x <= d) tree
                            in N (quickSortT (combinar ll rr)) d (quickSortT right)


-- EJERCICIO 5
{-
Para agregar control de casos ilegales, agregar esto al principio de la guarda:
| n < 0 = (E, raiz)
| n >= size = (raiz, E)
-}
splitAtBT :: BTree a -> Int -> (BTree a, BTree a)
splitAtBT Empty n = (Empty, Empty)
splitAtBT raiz@(Node size l d r) n | n <= sizeL = let (mitadI, mitadD) = splitAtBT l n
                                                  in (mitadI, Node (size - n) mitadD d r)
                                   | n == (sizeL + 1) = (Node n l d Empty, r)
                                   | otherwise = let (mitadI, mitadD) = splitAtBT r (n - sizeL - 1)
                                                 in (Node n l d mitadI, mitadD)
                                   where sizeL = sizeBT l

ej1 = Node 7 (Node 3 (Node 1 Empty 1 Empty) 2 (Node 1 Empty 3 Empty)) 4 (Node 3 (Node 1 Empty 5 Empty) 6 (Node 1 Empty 7 Empty)) :: BTree Int