{- |
Description: Dotstring representation of binary trees
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P69" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P69 (dotstringToTree, treeToDotstring) where

import           Control.Monad
import           Problems.BinaryTrees

-- | Convert a dotstring representation into its corresponding binary tree.
dotstringToTree :: String -> Maybe (Tree Char)
dotstringToTree :: String -> Maybe (Tree Char)
dotstringToTree String
s = do
  (Tree Char
t, String
s') <- String -> Maybe (Tree Char, String)
parseDotstring String
s
  Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> Maybe ()) -> Bool -> Maybe ()
forall a b. (a -> b) -> a -> b
$ String -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null String
s'
  Tree Char -> Maybe (Tree Char)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return Tree Char
t

parseDotstring :: String -> Maybe (Tree Char, String)
parseDotstring :: String -> Maybe (Tree Char, String)
parseDotstring (Char
'.':String
xs) = (Tree Char, String) -> Maybe (Tree Char, String)
forall a. a -> Maybe a
Just (Tree Char
forall a. Tree a
Empty, String
xs)
parseDotstring (Char
c:String
xs) = do
  (Tree Char
l, String
xs') <- String -> Maybe (Tree Char, String)
parseDotstring String
xs
  (Tree Char
r, String
xs'') <- String -> Maybe (Tree Char, String)
parseDotstring String
xs'
  (Tree Char, String) -> Maybe (Tree Char, String)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
c Tree Char
l Tree Char
r, String
xs'')
parseDotstring String
_ = Maybe (Tree Char, String)
forall a. Maybe a
Nothing

-- | Convert a binary tree to its dotstring representation.
treeToDotstring :: Tree Char -> String
treeToDotstring :: Tree Char -> String
treeToDotstring Tree Char
Empty          = String
"."
treeToDotstring (Branch Char
x Tree Char
l Tree Char
r) = [Char
x] String -> String -> String
forall a. [a] -> [a] -> [a]
++ Tree Char -> String
treeToDotstring Tree Char
l String -> String -> String
forall a. [a] -> [a] -> [a]
++ Tree Char -> String
treeToDotstring Tree Char
r