-- David Bai, David Hammarth, Winston Xu, Nick Crews (sort of)

--import Debug.Trace (trace)

data Color = R | B
data Tree elt = Empty | Node Color ( Tree elt ) elt ( Tree elt )

type Set a = Tree a

empty :: Set elt
empty = Empty

member :: Ord elt => elt -> Set elt -> Bool
member x Empty = False
member x ( Node _ left x2 right ) =
  if x == x2 then True
  else if x < x2 then member x left
  else member x right

memberp x Empty = False
memberp x ( Node _ left x2 right ) | x < x2  = memberp x left
                                   | x == x2 = True
                                   | x > x2  = memberp x right


map_tree :: ( a -> b ) -> ( Tree a ) -> ( Tree b )
map_tree f Empty = Empty
map_tree f ( Node c left x right ) = Node c ( map_tree f left ) ( f x ) ( map_tree f right )

insert :: Ord elt => elt -> Set elt -> Set elt
insert x s = makeBlack ( ins s )
  where ins Empty = Node R Empty x Empty
        ins ( Node c left x2 right ) =
          if x < x2 then
            balance c ( ins left ) x2 right
          else if x > x2 then
            balance c left x2 ( ins right )
          else
            Node c left x2 right

        makeBlack ( Node _ l x r ) = Node B l x r

balance :: Color -> ( Tree elt ) -> elt -> ( Tree elt ) -> Tree elt
balance B ( Node R ( Node  R a x b ) y c ) z d = Node R ( Node B a x b ) y ( Node B c z d )
balance B ( Node R a x ( Node  R b y c ) ) z d = Node R ( Node B a x b ) y ( Node B c z d )
balance B a x ( Node R ( Node  R b y c ) z d ) = Node R ( Node B a x b ) y ( Node B c z d )
balance B a x ( Node R b y ( Node  R c z d ) ) = Node R ( Node B a x b ) y ( Node B c z d )
balance c a x b = Node c a x b

------------------
show_color :: Color -> [Char]
show_color R = "R"
show_color B = "B"

instance Show Color where
  show = show_color

show_tree :: Show a => (Tree a) -> [Char]
show_tree Empty = "null"
show_tree (Node c left x right) = sl ++ " - " ++ sx ++ " - " ++ sr
  where
    sl = show_tree left
    sr = show_tree right
    sx = show c ++ ": " ++ show x

instance ( Show a ) => ( Show (Tree a) ) where
  show = show_tree

tree_fold :: (b -> a -> b) -> b -> Tree a -> b
tree_fold f x Empty = x
tree_fold f x (Node c left x2 right) = tree_fold f ( f (tree_fold f x left) x2 ) right

set_remove2 :: Show elt => Ord elt => elt -> Set elt -> Set elt --didn't quite work - was trying naive solution for basic BST removal (no balancing)
--set_remove2 :: Ord elt => elt -> Set elt -> Set elt
set_remove2 x Empty = Empty
set_remove2 x (Node c Empty x2 Empty) =
  if x == x2 then Empty
  else Node c Empty x2 Empty
set_remove2 x ( Node c left x2 (Node rc rleft rx rright) ) =
  if x == x2 then Node c left rx ( set_remove2 x (Node rc rleft x2 rright) )
  else if member x left then
    Node c (set_remove2 x left) x2 right
  else if member x right then
    Node c left x2 (set_remove2 x right)
  else (Node c left x2 right)
  where right = (Node rc rleft rx rright)
set_remove2 x ( Node c (Node lc lleft lx lright) x2 right ) =
  if x == x2 then Node c ( set_remove2 x (Node lc lleft x2 lright) ) lx right
  else if member x left then
    Node c (set_remove2 x left) x2 right
  -- else if member x right then  {- right should be empty in this case -}
  --   set_remove2 x right
  else (Node c left x2 right)
  where left = (Node lc lleft lx lright)

-- Talked to Nick who mentioned inserting non-parameter elements into a new tree, works but only for trivial trees :(
set_remove :: Ord elt => elt -> Set elt -> Set elt
set_remove x Empty = Empty
set_remove x (Node c left x2 right) = if member x (Node c left x2 right) then new_tree_maker (Node c left x2 right) else (Node c left x2 right)
  where
    new_tree_maker (Node c2 Empty x3 Empty)  = if x2 /= x3 then insert x2 new_tree                else new_tree
    new_tree_maker (Node c2 left2 x3 Empty)  = if x2 /= x3 then insert x2 (new_tree_maker left2 ) else (new_tree_maker left2)
    new_tree_maker (Node c2 Empty x3 right2) = if x2 /= x3 then insert x2 (new_tree_maker right2) else (new_tree_maker right2)
    --new_tree_maker (Node c2 left2 x3 right2) = if x2 != x3 then insert x2 (new_tree_maker left2 )
    new_tree = Empty

my_tree = Node R (Node B Empty 5 Empty) 10 (Node B Empty 2 Empty)
tree1 = Node R Empty 10 (Node B Empty 2 (Node R Empty 3 Empty))




-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------


-- David Bai, David Hammarth, Winston Xu, Nick Crews (sort of)

--import Debug.Trace (trace)

data Color = R | B
data Tree elt = Empty | Node Color ( Tree elt ) elt ( Tree elt )

type Set a = Tree a

empty :: Set elt
empty = Empty

member :: Ord elt => elt -> Set elt -> Bool
member x Empty = False
member x ( Node _ left x2 right ) =
  if x == x2 then True
  else if x < x2 then member x left
  else member x right

memberp x Empty = False
memberp x ( Node _ left x2 right ) | x < x2  = memberp x left
                                   | x == x2 = True
                                   | x > x2  = memberp x right


map_tree :: ( a -> b ) -> ( Tree a ) -> ( Tree b )
map_tree f Empty = Empty
map_tree f ( Node c left x right ) = Node c ( map_tree f left ) ( f x ) ( map_tree f right )

insert :: Ord elt => elt -> Set elt -> Set elt
insert x s = makeBlack ( ins s )
  where ins Empty = Node R Empty x Empty
        ins ( Node c left x2 right ) =
          if x < x2 then
            balance c ( ins left ) x2 right
          else if x > x2 then
            balance c left x2 ( ins right )
          else
            Node c left x2 right

        makeBlack ( Node _ l x r ) = Node B l x r

balance :: Color -> ( Tree elt ) -> elt -> ( Tree elt ) -> Tree elt
balance B ( Node R ( Node  R a x b ) y c ) z d = Node R ( Node B a x b ) y ( Node B c z d )
balance B ( Node R a x ( Node  R b y c ) ) z d = Node R ( Node B a x b ) y ( Node B c z d )
balance B a x ( Node R ( Node  R b y c ) z d ) = Node R ( Node B a x b ) y ( Node B c z d )
balance B a x ( Node R b y ( Node  R c z d ) ) = Node R ( Node B a x b ) y ( Node B c z d )
balance c a x b = Node c a x b

------------------
show_color :: Color -> [Char]
show_color R = "R"
show_color B = "B"

instance Show Color where
  show = show_color

show_tree :: Show a => (Tree a) -> [Char]
show_tree Empty = "null"
show_tree (Node c left x right) = sl ++ " - " ++ sx ++ " - " ++ sr
  where
    sl = show_tree left
    sr = show_tree right
    sx = show c ++ ": " ++ show x

instance ( Show a ) => ( Show (Tree a) ) where
  show = show_tree

tree_fold :: (b -> a -> b) -> b -> Tree a -> b
tree_fold f x Empty = x
tree_fold f x (Node c left x2 right) = tree_fold f ( f (tree_fold f x left) x2 ) right

set_remove2 :: Show elt => Ord elt => elt -> Set elt -> Set elt --didn't quite work - was trying naive solution for basic BST removal (no balancing)
--set_remove2 :: Ord elt => elt -> Set elt -> Set elt
set_remove2 x Empty = Empty
set_remove2 x (Node c Empty x2 Empty) =
  if x == x2 then Empty
  else Node c Empty x2 Empty
set_remove2 x ( Node c left x2 (Node rc rleft rx rright) ) =
  if x == x2 then Node c left rx ( set_remove2 x (Node rc rleft x2 rright) )
  else if member x left then
    Node c (set_remove2 x left) x2 right
  else if member x right then
    Node c left x2 (set_remove2 x right)
  else (Node c left x2 right)
  where right = (Node rc rleft rx rright)
set_remove2 x ( Node c (Node lc lleft lx lright) x2 right ) =
  if x == x2 then Node c ( set_remove2 x (Node lc lleft x2 lright) ) lx right
  else if member x left then
    Node c (set_remove2 x left) x2 right
  -- else if member x right then  {- right should be empty in this case -}
  --   set_remove2 x right
  else (Node c left x2 right)
  where left = (Node lc lleft lx lright)

-- Talked to Nick who mentioned inserting non-parameter elements into a new tree, works but only for trivial trees :(
set_remove :: Ord elt => elt -> Set elt -> Set elt
set_remove x Empty = Empty
set_remove x (Node c left x2 right) = if member x (Node c left x2 right) then new_tree_maker (Node c left x2 right) else (Node c left x2 right)
  where
    new_tree_maker (Node c2 Empty x3 Empty)  = if x2 /= x3 then insert x2 new_tree                else new_tree
    new_tree_maker (Node c2 left2 x3 Empty)  = if x2 /= x3 then insert x2 (new_tree_maker left2 ) else (new_tree_maker left2)
    new_tree_maker (Node c2 Empty x3 right2) = if x2 /= x3 then insert x2 (new_tree_maker right2) else (new_tree_maker right2)
    --new_tree_maker (Node c2 left2 x3 right2) = if x2 != x3 then insert x2 (new_tree_maker left2 )
    new_tree = Empty

my_tree = Node R (Node B Empty 5 Empty) 10 (Node B Empty 2 Empty)
tree1 = Node R Empty 10 (Node B Empty 2 (Node R Empty 3 Empty))