{- |
Description: Tree construction from a node string
Copyright: Copyright (C) 2023 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P70" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P70 (stringToMultitree, multitreeToString) where

import           Problems.MultiwayTrees

-- | We suppose that the nodes of a multiway tree contain single characters.
-- The characters in the node string are in depth-first order of the tree.
-- The special character @^@ is inserted whenever the move is
-- a backtrack to the previous level during tree traversal.
-- Note that the tree traversal will also backtrack from the root node of the tree.
--
-- Write a function to construct the 'MultiwayTree' when the string is given.
stringToMultitree :: String -> Maybe (MultiwayTree Char)
stringToMultitree :: String -> Maybe (MultiwayTree Char)
stringToMultitree String
s = (MultiwayTree Char, String) -> MultiwayTree Char
forall a b. (a, b) -> a
fst ((MultiwayTree Char, String) -> MultiwayTree Char)
-> Maybe (MultiwayTree Char, String) -> Maybe (MultiwayTree Char)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> String -> Maybe (MultiwayTree Char, String)
toNode String
s

toNode :: String -> Maybe (MultiwayTree Char, String)
toNode :: String -> Maybe (MultiwayTree Char, String)
toNode (Char
x:String
xs) = do
  ([MultiwayTree Char]
ts, String
remaining) <- ([MultiwayTree Char], String)
-> Maybe ([MultiwayTree Char], String)
toTreeList ([], String
xs)
  (MultiwayTree Char, String) -> Maybe (MultiwayTree Char, String)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Char -> [MultiwayTree Char] -> MultiwayTree Char
forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
x [MultiwayTree Char]
ts, String
remaining)
toNode [] = Maybe (MultiwayTree Char, String)
forall a. Maybe a
Nothing

toTreeList :: ([MultiwayTree Char], String) -> Maybe ([MultiwayTree Char], String)
toTreeList :: ([MultiwayTree Char], String)
-> Maybe ([MultiwayTree Char], String)
toTreeList ([MultiwayTree Char]
ts, Char
'^':String
xs) = ([MultiwayTree Char], String)
-> Maybe ([MultiwayTree Char], String)
forall a. a -> Maybe a
Just ([MultiwayTree Char] -> [MultiwayTree Char]
forall a. [a] -> [a]
reverse [MultiwayTree Char]
ts, String
xs)
toTreeList ([MultiwayTree Char]
ts, String
s) = do
  (MultiwayTree Char
node, String
remaining) <- String -> Maybe (MultiwayTree Char, String)
toNode String
s
  ([MultiwayTree Char], String)
-> Maybe ([MultiwayTree Char], String)
toTreeList (MultiwayTree Char
node MultiwayTree Char -> [MultiwayTree Char] -> [MultiwayTree Char]
forall a. a -> [a] -> [a]
: [MultiwayTree Char]
ts, String
remaining)

-- | Construct the node string from a 'MultiwayTree'.
multitreeToString :: MultiwayTree Char -> String
multitreeToString :: MultiwayTree Char -> String
multitreeToString (MultiwayTree Char
x [MultiwayTree Char]
ts) = Char
x Char -> String -> String
forall a. a -> [a] -> [a]
: (MultiwayTree Char -> String) -> [MultiwayTree Char] -> String
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap MultiwayTree Char -> String
multitreeToString [MultiwayTree Char]
ts String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
"^"