{- |
Description: Binary tree layout; in-order
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P64" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P64 (layoutInorder) where

import           Problems.BinaryTrees

-- | Lay out a binary tree using in-order positions.
layoutInorder :: Tree a -> Tree (a, (Int,Int))
layoutInorder :: forall a. Tree a -> Tree (a, (Int, Int))
layoutInorder Tree a
t = (Tree (a, (Int, Int)), Int) -> Tree (a, (Int, Int))
forall a b. (a, b) -> a
fst ((Tree (a, (Int, Int)), Int) -> Tree (a, (Int, Int)))
-> (Tree (a, (Int, Int)), Int) -> Tree (a, (Int, Int))
forall a b. (a -> b) -> a -> b
$ Tree a -> Int -> Int -> (Tree (a, (Int, Int)), Int)
forall a. Tree a -> Int -> Int -> (Tree (a, (Int, Int)), Int)
layout Tree a
t Int
1 Int
1

layout :: Tree a -> Int -> Int -> (Tree (a, (Int, Int)), Int)
layout :: forall a. Tree a -> Int -> Int -> (Tree (a, (Int, Int)), Int)
layout Tree a
Empty Int
order Int
_ = (Tree (a, (Int, Int))
forall a. Tree a
Empty, Int
order)
layout (Branch a
x Tree a
l Tree a
r) Int
order Int
depth = ((a, (Int, Int))
-> Tree (a, (Int, Int))
-> Tree (a, (Int, Int))
-> Tree (a, (Int, Int))
forall a. a -> Tree a -> Tree a -> Tree a
Branch (a
x, (Int
order', Int
depth)) Tree (a, (Int, Int))
l' Tree (a, (Int, Int))
r', Int
order'')
  where (Tree (a, (Int, Int))
l', Int
order') = Tree a -> Int -> Int -> (Tree (a, (Int, Int)), Int)
forall a. Tree a -> Int -> Int -> (Tree (a, (Int, Int)), Int)
layout Tree a
l Int
order (Int
depthInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
        (Tree (a, (Int, Int))
r', Int
order'') = Tree a -> Int -> Int -> (Tree (a, (Int, Int)), Int)
forall a. Tree a -> Int -> Int -> (Tree (a, (Int, Int)), Int)
layout Tree a
r (Int
order'Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
depthInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)