{- |
Description: Supporting definitions for multiway tree problems
Copyright: Copyright (C) 2023 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Supporting definitions for multiway tree problems.
-}
module Problems.MultiwayTrees (
  MultiwayTree (MultiwayTree),
  multitree1, multitree2, multitree3, multitree4, multitree5,
  multitreeSize,
  ) where

import           Control.DeepSeq
import           GHC.Generics    (Generic)

-- | A multiway tree is composed of a root element
-- and a (possibly empty) set of successors which are multiway trees themselves.
-- A multiway tree is never empty.  The set of successor trees is sometimes called a forest.
data MultiwayTree a = MultiwayTree a [MultiwayTree a]
  deriving (MultiwayTree a -> MultiwayTree a -> Bool
forall a. Eq a => MultiwayTree a -> MultiwayTree a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: MultiwayTree a -> MultiwayTree a -> Bool
$c/= :: forall a. Eq a => MultiwayTree a -> MultiwayTree a -> Bool
== :: MultiwayTree a -> MultiwayTree a -> Bool
$c== :: forall a. Eq a => MultiwayTree a -> MultiwayTree a -> Bool
Eq, Int -> MultiwayTree a -> ShowS
forall a. Show a => Int -> MultiwayTree a -> ShowS
forall a. Show a => [MultiwayTree a] -> ShowS
forall a. Show a => MultiwayTree a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [MultiwayTree a] -> ShowS
$cshowList :: forall a. Show a => [MultiwayTree a] -> ShowS
show :: MultiwayTree a -> String
$cshow :: forall a. Show a => MultiwayTree a -> String
showsPrec :: Int -> MultiwayTree a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> MultiwayTree a -> ShowS
Show, forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (MultiwayTree a) x -> MultiwayTree a
forall a x. MultiwayTree a -> Rep (MultiwayTree a) x
$cto :: forall a x. Rep (MultiwayTree a) x -> MultiwayTree a
$cfrom :: forall a x. MultiwayTree a -> Rep (MultiwayTree a) x
Generic, forall a. NFData a => MultiwayTree a -> ()
forall a. (a -> ()) -> NFData a
rnf :: MultiwayTree a -> ()
$crnf :: forall a. NFData a => MultiwayTree a -> ()
NFData)

-- | Example of the following multiway tree.
--
-- ![single node 'a'](images/MultiwayTrees/tree1.svg)
--
-- >>> multitree1 == MultiwayTree 'a' []
-- True
multitree1 :: MultiwayTree Char
multitree1 :: MultiwayTree Char
multitree1 = forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'a' []

-- | Example of the following multiway tree.
--
-- !['a' has successor 'b'](images/MultiwayTrees/tree2.svg)
--
-- >>> multitree2 == MultiwayTree 'a' [MultiwayTree 'b' []]
-- True
multitree2 :: MultiwayTree Char
multitree2 :: MultiwayTree Char
multitree2 = forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'a' [forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'b' []]

-- | Example of the following multiway tree.
--
-- !['a' has successor 'b', 'b' has successor 'c'](images/MultiwayTrees/tree3.svg)
--
-- >>> multitree3 == MultiwayTree 'a' [MultiwayTree 'b' [MultiwayTree 'c' []]]
-- True
multitree3 :: MultiwayTree Char
multitree3 :: MultiwayTree Char
multitree3 = forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'a' [forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'b' [forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'c' []]]

-- | Example of the following multiway tree.
--
-- !['b' has successors 'd', 'e'](images/MultiwayTrees/tree4.svg)
--
-- >>> multitree4 == MultiwayTree 'b' [MultiwayTree 'd' [], MultiwayTree 'e' []]
-- True
multitree4 :: MultiwayTree Char
multitree4 :: MultiwayTree Char
multitree4 = forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'b' [forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'd' [], forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'e' []]

-- | Example of the following multiway tree.
--
-- !['a' has successors 'f', 'c', 'b', and 'f' has successor 'g', and 'b' has successors 'd', 'e'](images/MultiwayTrees/tree5.svg)
--
-- >>> :{
-- multitree5 == MultiwayTree 'a'
--   [ MultiwayTree 'f' [MultiwayTree 'g' []]
--   , MultiwayTree 'c' []
--   , MultiwayTree 'b' [MultiwayTree 'd' [], MultiwayTree 'e' []]
--   ]
-- :}
-- True
multitree5 :: MultiwayTree Char
multitree5 :: MultiwayTree Char
multitree5 = forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'a'
  [ forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'f' [forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'g' []]
  , forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'c' []
  , forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'b' [forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'd' [], forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
'e' []]
  ]

-- | Returns the number of nodes in a multiway tree.
--
-- === Examples
--
-- >>> multitreeSize multitree1
-- 1
--
-- >>> multitreeSize multitree5
-- 7
--
-- === __Notes__
--
-- This was originally problem 70C.  This is not included as a problem,
-- to avoid a numbering conflict with the somewhat unrelated problem 70 in the original list,
-- which is more interesting.
multitreeSize :: MultiwayTree a -> Int
multitreeSize :: forall a. MultiwayTree a -> Int
multitreeSize (MultiwayTree a
_ [MultiwayTree a]
ts) = Int
1 forall a. Num a => a -> a -> a
+ forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum (forall a b. (a -> b) -> [a] -> [b]
map forall a. MultiwayTree a -> Int
multitreeSize [MultiwayTree a]
ts)