{- |
Description: Binary tree layout; constant distance at each level
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

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

import           Problems.BinaryTrees

-- | Lay out a binary tree with constance distance at each level.
layoutLevelConstant :: Tree a -> Tree (a, (Int,Int))
layoutLevelConstant :: forall a. Tree a -> Tree (a, (Int, Int))
layoutLevelConstant Tree a
t = Int -> Tree (a, (Int, Int)) -> Tree (a, (Int, Int))
forall a. Int -> Tree (a, (Int, Int)) -> Tree (a, (Int, Int))
shift Int
amount Tree (a, (Int, Int))
layoutTree
  where layoutTree :: Tree (a, (Int, Int))
layoutTree = Tree a -> Int -> Int -> Int -> Tree (a, (Int, Int))
forall a. Tree a -> Int -> Int -> Int -> Tree (a, (Int, Int))
layout Tree a
t Int
0 Int
1 Int
distance
        distance :: Int
distance = Int
2Int -> Int -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^(Tree a -> Int
forall a. Tree a -> Int
treeHeight Tree a
t Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
2)
        amount :: Int
amount = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Tree (a, (Int, Int)) -> Int
forall a. Tree (a, (Int, Int)) -> Int
minPos Tree (a, (Int, Int))
layoutTree

layout :: Tree a -> Int -> Int -> Int -> Tree (a, (Int, Int))
layout :: forall a. Tree a -> Int -> Int -> Int -> Tree (a, (Int, Int))
layout Tree a
Empty Int
_ Int
_ Int
_ = Tree (a, (Int, Int))
forall a. Tree a
Empty
layout (Branch a
x Tree a
l Tree a
r) Int
pos Int
depth Int
distance = (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
pos, Int
depth)) Tree (a, (Int, Int))
l' Tree (a, (Int, Int))
r'
  where l' :: Tree (a, (Int, Int))
l' = Tree a -> Int -> Int -> Int -> Tree (a, (Int, Int))
forall a. Tree a -> Int -> Int -> Int -> Tree (a, (Int, Int))
layout Tree a
l (Int
pos Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
distance) Int
depth' Int
distance'
        r' :: Tree (a, (Int, Int))
r' = Tree a -> Int -> Int -> Int -> Tree (a, (Int, Int))
forall a. Tree a -> Int -> Int -> Int -> Tree (a, (Int, Int))
layout Tree a
r (Int
pos Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
distance) Int
depth' Int
distance'
        depth' :: Int
depth' = Int
depth Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
        distance' :: Int
distance' = Int
distance Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2

shift :: Int -> Tree (a, (Int, Int)) -> Tree (a, (Int, Int))
shift :: forall a. Int -> Tree (a, (Int, Int)) -> Tree (a, (Int, Int))
shift Int
_ Tree (a, (Int, Int))
Empty = Tree (a, (Int, Int))
forall a. Tree a
Empty
shift Int
amount (Branch (a
v, (Int
x,Int
y)) Tree (a, (Int, Int))
l Tree (a, (Int, Int))
r) = (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
v, (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
amount,Int
y)) Tree (a, (Int, Int))
l' Tree (a, (Int, Int))
r'
  where l' :: Tree (a, (Int, Int))
l' = Int -> Tree (a, (Int, Int)) -> Tree (a, (Int, Int))
forall a. Int -> Tree (a, (Int, Int)) -> Tree (a, (Int, Int))
shift Int
amount Tree (a, (Int, Int))
l
        r' :: Tree (a, (Int, Int))
r' = Int -> Tree (a, (Int, Int)) -> Tree (a, (Int, Int))
forall a. Int -> Tree (a, (Int, Int)) -> Tree (a, (Int, Int))
shift Int
amount Tree (a, (Int, Int))
r

minPos :: Tree (a, (Int, Int)) -> Int
minPos :: forall a. Tree (a, (Int, Int)) -> Int
minPos Tree (a, (Int, Int))
Empty                    = Int
0
minPos (Branch (a
_, (Int
x, Int
_)) Tree (a, (Int, Int))
l Tree (a, (Int, Int))
_) = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
x (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Tree (a, (Int, Int)) -> Int
forall a. Tree (a, (Int, Int)) -> Int
minPos Tree (a, (Int, Int))
l
-- No need to check right subtree.
-- Halving horizontal distance at each level means no node in the right subtree
-- can ever be positioned to the left of the parent node.