# Laboratory: Stacks, Queues, and Priority Queues

Summary: In this laboratory, you will explore the use and abuse of restricted access collections.

## Preparation

a. Copy the code from the end of this lab into your definitions pane. Warning! There's a lot of code. You will need to use the procedure navigator in DrFu to find particular procedures.

b. Create and show a new 200x200 image called `canvas`.

## Exercises

### Exercise 1: Exploring Linear Structures

The mass of code that you just loaded includes a procedure called `collection.test0`. Look at the code for that procedure and explain what it does.

a. If you have not modified the code you copied and pasted, stacks are currently set as the default collection (that is, what we use when we call `collection.____`). What output do you expect to get when you run `collection.test0`?

````>` `(collection.test0)`
```

c. Comment out the lines that tell DrFu to use the stack procedures as the collection procedures and then uncomment the lines that tell DrFu to use the queue procedures.

d. What output do you expect to get when you run `collection.test0`?

f. Comment out the lines that tell DrFu to use the queue procedures as the collection procedures and then uncomment the lines that tell DrFu to use the priority queue procedures.

g. What output do you expect to get when you run `collection.test0`?

### Exercise 2: Exploring Linear Structures, Revisited

The code also includes a procedure named `collection.test1` that tests not just what happens when you add a bunch of values and then remove them, but also what happens when you alternately add and remove values. Read that procedure and make sure that you understand what it does.

a. What output do you expect `collection.test1` to have if we use stacks to implement collections?

````>` `(collection.test1)`
```

c. What output do you expect `collection.test1` to have if we use queues to implement collections?

e. What output do you expect `collection.test1` to have if we use priority queues to implement collections?

### Exercise 3: Simple Fractal Rectangles

Review the code to the new version of the `simple-fractal-rectangle!` procedure.

a. Uncomment the lines that tell DrFu to use queues as the mechanism for implementing collections.

b. How do you expect `simple-fractal-rectangle!` to draw a level-2 fractal rectangle? (That is, in what order will it draw rectangles?)

````>` `(simple-fractal-rectangle! canvas color.red 0 0 199 199 2)`
```

d. Suppose we tell DrFu to use priority queues as the mechanism for implementing collections. In what order will it draw the rectangles in a level-2 fractal rectangle?

f. Uncomment the line in `simple-fractal-rectangle!` that prints out the current collection of remaining tasks. Rerun the command to print out a level-2 fractal rectangle. Explain the results you get.

g. Re-comment that line.

### Exercise 4: Randomizing Drawing Order

For this exercise, keep priority queues as your implementation of collections.

Update `simple-fractal-rectangle!` so that it chooses a random priority for each sub-rectangle rather than a priority of 0.

a. What effect do you have this to happen when we draw a level-3 fractal rectangle?

````>` `(simple-fractal-rectangle! canvas color.blue 0 0 199 199 3)`
```

### Exercise 5: Simulating Deep Recursion with Stacks

As you may have observed, neither queues nor priority queues give the same behavior as the original recursive procedure. Why? Because Scheme completely finishes one call (e.g., to draw a single rectangle by drawing all of its sub-rectangles). As the reading suggested, this behavior is much more stack-like than queue-like.

For this exercise, make stacks the default implementation of collections.

a. How do you expect `simple-fractal-rectangle!` to draw a level-2 fractal rectangle? (That is, in what order will it draw rectangles?)

````>` `(simple-fractal-rectangle! canvas color.red 0 0 199 199 2)`
```

c. As you may have observed, the behavior is similar to that of the original fractal rectangle procedure (that is, we completely finish one rectangle before going on to the next), with one important difference: Instead of starting in the upper-left corner, it starts in the lower-right. Let's figure out why. First, uncomment the line that prints the collection. Next, draw a level 1 rectangle. What do you notice about the structure of the stack?

d. Using what you've just learned (ask a teacher or TA if you didn't figure it out), rewrite `simple-fractal-rectangle!` so that it draws the rectangles in the “correct” order.

e. What effect do you expect this rewriting to have on the behavior of `simple-fractal-rectangle!` if we use queues or priority queues?

## For Those With Extra Time

### Extra 1: Stack-like Behavior with Priority Queues

For the case of `simple-fractal-rectangle!`, we can almost get the behavior of stacks by using the level of a rectangle as its priority.

a. Check this assertion experimentally by updating the code to `simple-fractal-rectangle!`

b. Make any other changes necessary to get the “proper” behavior.

## Some Useful Procedures

```; +--------+----------------------------------------------------------
; | Stacks |
; +--------+

(define stack.new
(lambda ()
null))

(define stack.get
(lambda (stuff)
(if (null? stuff)
(throw "Cannot get values from empty stacks.")
(car stuff))))

(define stack.drop
(lambda (stuff)
(if (null? stuff)
(throw "Cannot remove values from empty stacks.")
(cdr stuff))))

(lambda (stuff val prio)
(cons val stuff)))

(define stack.empty?
(lambda (stuff)
(null? stuff)))

; +--------+----------------------------------------------------------
; | Queues |
; +--------+

; Queues are implemented as a vector of two lists, front and back.  We remove
; elements from front and add elements to back.  Here's the trick: When we
; run out of elements in front, we move the elements in back to front,
; reversing their order.

(define queue.new
(lambda ()
(vector null null)))

(define queue.get
(lambda (stuff)
(cond
((queue.empty? stuff)
(throw "Cannot get values from an empty collection."))
((null? (vector-ref stuff 0))
(car (reverse (vector-ref stuff 1))))
(else
(car (vector-ref stuff 0))))))

(define queue.drop
(lambda (stuff)
(cond
((queue.empty? stuff)
(throw "Cannot drop values from an empty collection."))
((null? (vector-ref stuff 0))
(vector (cdr (reverse (vector-ref stuff 1))) null))
(else
(vector (cdr (vector-ref stuff 0)) (vector-ref stuff 1))))))

(lambda (stuff val prio)
(vector (vector-ref stuff 0) (cons val (vector-ref stuff 1)))))

(define queue.empty?
(lambda (stuff)
(and (null? (vector-ref stuff 0))
(null? (vector-ref stuff 1)))))

; +-----------------+-------------------------------------------------
; | Priority Queues |
; +-----------------+

; A priority queue is a list of (value . priority) pairs, kept in order by
; priority.  We use techniques similar to those for insertion sort to keep
; the queue in order.

(define priority-queue.new
(lambda ()
null))

(define priority-queue.get
(lambda (stuff)
(if (null? stuff)
(throw "Cannot get a value from an empty collection.")
(car (car stuff)))))

(define priority-queue.drop
(lambda (stuff)
(if (null? stuff)
(throw "Cannot drop a value from an empty collection.")
(cdr stuff))))

(lambda (stuff val prio)
(cond
((null? stuff)
(list (cons val prio)))
((< prio (cdr (car stuff)))
(cons (cons val prio) stuff))
(else
(cons (car stuff) (priority-queue.add (cdr stuff) val prio))))))

(define priority-queue.empty?
(lambda (stuff)
(null? stuff)))

; +----------------------------+--------------------------------------
; | Choosing Linear Structures |
; +----------------------------+

(define collection.new stack.new)
(define collection.get stack.get)
(define collection.drop stack.drop)
(define collection.empty? stack.empty?)

;(define collection.new queue.new)
;(define collection.get queue.get)
;(define collection.drop queue.drop)
;(define collection.empty? queue.empty?)

;(define collection.new priority-queue.new)
;(define collection.get priority-queue.get)
;(define collection.drop priority-queue.drop)
;(define collection.empty? priority-queue.empty?)

; +---------+---------------------------------------------------------
; | Testing |
; +---------+

(define collection.test0
(letrec ((get-print-drop
(lambda (stuff)
(display "Removing: ")
(display (collection.get stuff))
(newline)
(collection.drop stuff)))
(dump
(lambda (stuff)
(if (not (collection.empty? stuff))
(dump (get-print-drop stuff))))))
(lambda ()
(let* ((c0 (collection.new))
(dump c4)))))

(define collection.test1
(letrec ((get-print-drop
(lambda (stuff)
(display "Removing: ")
(display (collection.get stuff))
(newline)
(collection.drop stuff)))
(dump
(lambda (stuff)
(if (not (collection.empty? stuff))
(dump (get-print-drop stuff))))))
(lambda ()
(let* ((c0 (collection.new))
(c5 (get-print-drop c4))
(c6 (get-print-drop c5))
(c10 (get-print-drop c9))
(dump c11)))))

; +-------------------+-----------------------------------------------
; | Fun With Fractals |
; +-------------------+

(define simple-fractal-rectangle!
(lambda (image color left top right bottom level)
(letrec
; Process the task at the front of the collection,
; returning the modified collection.
((process-rect
; Note: Each task is a vector of the form
;   #(color left top right bottom level)
(let ((color (vector-ref rect 0))
(left (vector-ref rect 1))
(top (vector-ref rect 2))
(right (vector-ref rect 3))
(bottom (vector-ref rect 4))
(level (vector-ref rect 5)))
; Draw the rectangle (we may draw over it)
(envt.set-fgcolor! color)
(image.select-rectangle! image selection.replace
left top
(- right left)
(- bottom top))
(image.fill! image)
(image.select-nothing! image)
(envt.update-displays!)
(cond
; Base case: We're done, so return the remaining tasks
((= level 0)
(else
(let ((midcol (round (* 0.5 (+ left right))))
(midrow (round (* 0.5 (+ bottom top))))
(nextlevel (- level 1)))
(display (list 'midcol midcol 'midrow midrow)) (newline)
(let* ((rect1 (vector (rgb.lighter color)
left top midcol midrow (- level 1)))
(rect2 (vector (rgb.darker color)
midcol top right midrow (- level 1)))
(rect3 (vector (rgb.darker color)
left midrow midcol bottom (- level 1)))
(rect4 (vector color
midcol midrow right bottom (- level 1)))
c4)))))))
(kernel
; Uncomment the following line to keep track of the tasks
; left to do.
'Success
This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit `http://creativecommons.org/licenses/by-nc/2.5/` or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.