Lab Assignment #7

Implementing a Priority Queue in Smaltalk - Part 2

Description

In this lab you will finish implementing the priority queue that you began implementing in the previous lab. You write two new methods do: and collect:. Neither do: nor collect: modify the queue. You will be given an implementation of a priority queue with an unsorted linked list if you want to use it, or you can use your own from the previous lab.

The do: method should apply a block to every element in a list. Each element is passed to the block as an argument. The return values are ignored.

This is useful when you want to iterate over all the elements in the queue and do the same thing for each. For example, if I wanted to print out every single value in a PriorityQueue I could use do: [ :each | each printOn: Transcript].

The collect: method should apply a block to every element in a list and collect the results into an OrderedCollection. An OrderedCollection is used instead of another PriorityQueue because the block passed to this function can return a value of any type. For example if some of the returned values are #apple symbols and others are #orange symbols than we could not take the minimum of #apple and #orange and a PriorityQueue made up of such values would not work correctly.

This is useful when you want to find out something about each element in the queue. For example, you could collect the pointers of each element in the queue or you could return the scaled or rounded-off values of each element in a queue.

If you would like to use the given PriorityQueueUL instead of your own, you can get the code here. This includes the whole PriorityQueue category.

Testing your code

FILE OUT your changes before testing them, just in case your program doesn't work and instead it crashes SmallTalk. Try the code below on the PriorityQueueOC or PriorityQueueSC first to get an idea of how yours should behave.

For testing, you will load a queue with some random numbers by using the block below.

[ :aPQueue :number |
  |rand|
  rand := Random new.
  1 to: number do:
     [ :n | aPQueue insert: (rand next)].
  ^aPQueue
]

You can test do: as follows (assumming aPQueue points to a priority queue that you have previously loaded by using the block above):

    " load the queue with the block above or manually with insert "
  aPQueue do: [ :each | each printOn: Transcript.
                        Transcript cr.].
  Transcript show: 'Finished' ; cr

To test collect: you can use the block

 [ :n | ^n * 10 ]

which takes one argument and returns its value multiplied by ten. When passed to the collect: method it should multiply each element in the queue by 10 and collect the results in a new collection. The elements in the queue themselves should not be affected. You can check if it worked by printing out the returned OrderedCollection. Use "print it" instead of "do it" or send it a "printOn:" message.

Turning in your code

Turn in the code for your priority queue class.

(1:30-3)
cat file.txt | mail -s "lab 7 - YOUR NAME" joita@cc.gatech.edu
OR (3-4:30)
cat file.txt | mail -s "lab 7 - YOUR NAME" jyan@cc.gatech.edu
OR (4:30-6)
cat file.txt Game.st | mail -s "lab 7 - YOUR NAME" smk@cc.gatech.edu

That's all for this lab. Please quit from VisualWorks before you logout.