apart-0.1.3: Data/Apart/Structures/Tree/Binary/Redblack.hs

module Data.Apart.Structures.Tree.Binary.Redblack (Redblack, Color (..), paint) where

import "free" Control.Comonad.Cofree (Cofree (..))

import Data.Apart.Structures.Tree.Binary (Binary, Branches (..))

data Color = Red | Black deriving Show

type Redblack a = Binary (a, Color)

paint :: Binary a -> Redblack a
paint tree = step Black tree where

	step :: Color -> Binary a -> Redblack a
	step color (x :< End) = (x, Black) :< End
	step color (x :< rest) = (x, color) :< (step (invert color) <$> rest)

	invert :: Color -> Color
	invert Black = Red
	invert Red = Black