```{- |
Description: Binary tree layout; in-order
Maintainer: dev@chungyc.org

Part of Ninety-Nine Haskell "Problems".  Some solutions are in "Solutions.P64".
-}
module Problems.P64 (layoutInorder, tree64) where

import           Problems.BinaryTrees
import qualified Solutions.P64        as Solution

{- |
Let's say we want to draw a binary tree.  In preparation, a layout algorithm is
required to determine the position of each node in a rectangular grid.
Several layout methods are conceivable.  One of them is shown in the illustration below:

![Layout example](images/BinaryTrees/Layout-P64.svg)

In this layout strategy, the position of a node \(v\) is obtained by the following two rules:

* \(x(v)\) is equal to the position of the node \(v\) in the in-order sequence.
* \(y(v)\) is equal to the depth of the node \(v\) in the tree.

Write a function to annotate each node of the tree with a position,
where \((1,1)\) is the top left corner of the rectangle bounding the drawn tree.

=== Examples

>>> layoutInorder tree64
Branch ('n',(8,1)) (Branch ('k',(6,2)) (Branch ('c',(2,3)) ...

=== __Notes__

In fact, the image was rendered to SVG using the return value of 'layoutInorder'
with 'Problems.BinaryTrees.SVG.writeSVG'.  The images for "Problems.P65" and "Problems.P66"
were also rendered similarly.
-}
layoutInorder :: Tree a -> Tree (a, (Int,Int))
layoutInorder :: forall a. Tree a -> Tree (a, (Int, Int))
layoutInorder = forall a. Tree a -> Tree (a, (Int, Int))
Solution.layoutInorder

-- | Tree used as the example for "Problems.P64".
tree64 :: Tree Char
tree64 :: Tree Char
tree64 = forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'n'
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'k'
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'c'
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'a' forall a. Tree a
Empty forall a. Tree a
Empty)
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'h'
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'g'
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'e' forall a. Tree a
Empty forall a. Tree a
Empty)
forall a. Tree a
Empty)
forall a. Tree a
Empty))
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'm' forall a. Tree a
Empty forall a. Tree a
Empty))
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'u'
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'p'
forall a. Tree a
Empty
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
's'
(forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
'q' forall a. Tree a
Empty forall a. Tree a
Empty)
forall a. Tree a
Empty))
forall a. Tree a
Empty)
```