;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-reader.ss" "lang")((modname L22_P2-hw8-hints) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f)))


Starting with the following layout for the allocation of disk space:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Part A: Fill in the following bitmap to represent what the minimal normal form
HBS would be; being a normal form, there is only one correct answer.
(Note: it would probably be easier to just fill in the 1/#t's,
treating all empty boxes as 0/#f)

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                               |                               | Level-3 (8-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|               |               |               |               | Level-2 (4-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       |       |       |       |       |       |       |       | Level-1 (2-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | Level-0 (1-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Part B: Now, what would be the returned value (the starting block for the
chunk you allocate) if the user requests a 2-chunk?
Answer (block#): _____

Fill in the updated HBS:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                               |                               | Level-3 (8-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|               |               |               |               | Level-2 (4-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       |       |       |       |       |       |       |       | Level-1 (2-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | Level-0 (1-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Part C: What would be the returned value if the user then requests
another 2-chunk?
Answer (block#): _____

Fill in the updated HBS:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                               |                               | Level-3 (8-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|               |               |               |               | Level-2 (4-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+n---+---+
|       |       |       |       |       |       |       |       | Level-1 (2-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | Level-0 (1-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+


======================================================================

Exercise 4:
Part A:
Start with the following HBS:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|               0               |               0               | Level-3 (8-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       1       |       0       |       0       |       1       | Level-2 (4-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   0   |   0   |   1   |   0   |   0   |   1   |   0   |   0   | Level-1 (2-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | Level-0 (1-chunks)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

The user calls free-chunk to free up a chunk of size 2 at block# 6.
First, simply free the chunk by marking the correct single bit at the correct
level. Outline the steps involved.

Part B:
As discussed in lecture today, the above setting of a freed bit will create
a new HBS that is correctly minimal, but not fully normalized. So that's
what you would do next.
Let's assume the function that normalizes the HBS is called "normalize-hbs",
and that it takes two parameters: the HBS that needs normalizing, and the
level to fix down to, specified as a chunk size. Outline the steps involved.
Remember: you should use standard structureal recursion.

We have provided the first few steps for you:
1. Call normalize-hbs with the args "the entire HBS" (so, HBS-at-Level-3)
   and chunksize=2, since that's where the chunk was freed, and so a #t
   was added.
2. Checks chunksize arg against level's chunksize (2 vs. 8), recurses
    by calling normalize-hbs with HBS-at-level-2

3.    Checks chunksize arg against level's chunksize (2 vs. 4), recurses

4.      Checks chunksize arg against level's chunksize (2 vs. 2); this
        is base case; interpretation: this is level at which #t was added,
        but since recursion acts like the hbs arg is in fact the entire
        HBS, top level can have pairs of #t in normal form, so just returns
5.    After return from (normalize-hbs Level-1 ...), back to
      (normalize-hbs Level-2 ...) it does ...

6.


7.


8.


9.


10.


Part B: Time permitting, start converting above pseudocode into real
ISL code.