A quadtree for a black and white image is constructed by successively dividing the image into four equal quadrants. If all the pixels in a quadrant are the same color (all black or all white) the division process for that quadrant stops. Quadrants that contain both black and white pixels are subdivided into four equal quadrants and this process continues until each subquadrant consists of either all black or all white pixels. It is entirely possible that some subquadrants consist of a single pixel.

For example, using 0 for white and 1 for black, the region on the left below is represented by the matrix of zeros and ones in the middle. The matrix is divided into subquadrants as shown on the right where gray squares represent subquadrants that consist entirely of black pixels.

A quadtree is constructed from the block structure of an image. The root of the tree represents the entire array of pixels. Each non-leaf node of a quadtree has four children, corresponding to the four subquadrants of the region represented by the node. Leaf nodes represent regions that consist of pixels of the same color and thus are not subdivided. For example, the image shown above, with the block structure on the right, is represented by the quadtree below.

A tree can be represented by a sequence of numbers representing the
root-to-leaf paths of black nodes. Each path is a base five number
constructed by labeling branches with 1, 2, 3, or 4 with NW = 1, NE =
2, SW = 3, SE = 4, and with the least significant digit of the base
five number corresponding to the branch from the root. For example,
the node labeled 4 has path NE, SW which is 32_{5} (base 5) or
17_{10} (base 10); the node labeled 12 has path SW, SE or
43_{5} = 23_{10}; and the node labeled 15 has path SE,
SW, NW or 134_{5} = 44_{10}. The entire tree is
represented by the sequence of numbers (in base 10)

`9 14 17 22 23 44 63 69 88 94 113`

`14 24 32 42 43 134 223 234 323 334 423`

`[41] [42] [23] [24] [34] [431] [322] [432] [323] [433] [324]`

All images consist of black and white pixles. All images are square and the size is a power of two, e.g., 4x4, 8x8, 16x16. Write a function that converts images into root-to-leaf paths and a function that converts root-to-leaf paths into images.

If *n* is positive, the zero/one representation follows; if
*n* is negative, the sequence of black node paths follows.
A one-node tree that represents an all-black image is
represented by the number 0. A one-node tree that represents an all-white
image is represented by an empty sequence.

The end of data is signaled by a value of 0 for *n*.

Then, if
the image is represented by zeros and ones, output the
root-to-leaf paths of all black nodes in the quadtree that represents
the image.
The values should be base 10 representations of the base 5
path numbers, and the values should *sorted* numerically when printed.
Print the all the numbers on a single line.

If the image is represented by the root-to-leaf paths of black nodes,
the output consists of an US-ASCII representation of
the image with the character '.' used for white/zero and the character
'*' used for black/one.
There should be *n* characters per line for an
*n*×*n* image.

8 00000000 00000000 00001111 00001111 00011111 00111111 00111100 00111000 -8 9 14 17 22 23 44 63 69 88 94 113 -1 2 00 00 -4 0 -1 0

Image 1: size = 8, black nodes = 11, black pixels = 26 9 14 17 22 23 44 63 69 88 94 113 Image 2: size = 8, black nodes = 11, black pixels = 26 ........ ........ ....**** ....**** ...***** ..****** ..****.. ..***... Image 3: size = 2, black nodes = 0, black pixels = 0 The empty list Image 4: size = 4, black nodes = 1, black pixels = 16 **** **** **** ****

This problem is adapted from the 1998 ICPC World Finals, Problem G.

- Haskell
- Hudak's lecture slides
- A Tour of the Haskell Syntax by Arjan van IJzendoorn
- A Tour of the Haskell Prelude, the most usefull Haskell predefined functions
- A solution of the problem "Rare Order"
written in Haskell,
`rare.hs`, illustrating line-oriented IO in Haskell - Haskell Homework Help
- Good Haskell Style

Be sure to eliminate all warnings detected by `-Wall`
before submitting your project.

The following is a sample main program.

module Main where import qualified System.IO as IO -- main program to reverse each line of input main = interact (unlines . map f . lines) f line = reverse line {- built-in functions: -- unlines :: [String] -> String ; combines separate lines into one string -- lines :: String -> [String] ; breaks input into separate lines -- reverse :: [a] -> [a] ; reverse list back to front -}

Turn in the source code for your project in a file named `main.hs`.
Your project will be compiled like this:

ghc -Wall --make main.hsThe compiler is:

ghc -Wall --version The Glorious Glasgow Haskell Compilation System, version 6.4.1

Write the program as clearly as possible, including reasonable comments. You may work alone or with one other student in the class, as long as you did not work with this partner in any of the previous projects. It is important to get the output formatted correctly, as the output must conform character by character to the specification. Incorrectly formatted output will fail the test cases. If there is any question about the output, please ask.

Turn in the Haskell source code for the program using the submission server.
The project is `proj4`.
In the comments somewhere at the beginning of your source file
include a header like the following:

{- - Author: name1, e-mail address - Author: name2, e-mail address - Course: CSE 4520, Fall 2017 - Project: Spatial Structures -}