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

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 MediaScript to find particular procedures. b. Create and show a new 200x200 image called canvas.

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? b. Check your answer experimentally. > (collection.test0) c. Comment out the lines that tell the Scheme interpreter to use the stack procedures as the collection procedures and then uncomment the lines that tell the Scheme interpreter to use the queue procedures. d. What output do you expect to get when you run collection.test0? e. Check your answer experimentally. f. Comment out the lines that tell the Scheme interpreter to use the queue procedures as the collection procedures and then uncomment the lines that tell the Scheme interpreter to use the priority queue procedures. g. What output do you expect to get when you run collection.test0? h. Check your answer experimentally.

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? b. Check your answer experimentally. > (collection.test1) c. What output do you expect collection.test1 to have if we use queues to implement collections? d. Check your answer experimentally. e. What output do you expect collection.test1 to have if we use priority queues to implement collections? f. Check your answer experimentally.

Review the code to the new version of the simple-fractal-rectangle! procedure. a. Uncomment the lines that tell the Scheme interpreter 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?) c. Check your answer experimentally. > (simple-fractal-rectangle! canvas color.red 0 0 199 199 2) d. Suppose we tell the Scheme interpreter to use priority queues as the mechanism for implementing collections. In what order will it draw the rectangles in a level-2 fractal rectangle? e. Check your answer experimentally. 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.

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? b. Check your answer experimentally. > (simple-fractal-rectangle! canvas color.blue 0 0 199 199 3)

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?) b. Check your answer experimentally. > (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 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.

; +--------+---------------------------------------------------------- ; | Stacks | ; +--------+ ; +--------+---------------------------------------------------------- ; | Queues | ; +--------+ ; +-----------------+------------------------------------------------- ; | Priority Queues | ; +-----------------+ ; +----------------------------+-------------------------------------- ; | Choosing Linear Structures | ; +----------------------------+ (define collection.new stack.new) (define collection.get stack.get) (define collection.drop stack.drop) (define collection.add stack.add) (define collection.empty? stack.empty?) ;(define collection.new queue.new) ;(define collection.get queue.get) ;(define collection.drop queue.drop) ;(define collection.add queue.add) ;(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.add priority-queue.add) ;(define collection.empty? priority-queue.empty?) ; +---------+--------------------------------------------------------- ; | Testing | ; +---------+ ; +-------------------+----------------------------------------------- ; | Fun With Fractals | ; +-------------------+