|
Comp202: Principles of Object-Oriented Programming II
|
Recall the Restrict Access Container (RAC) from last semester:
http://www.owlnet.rice.edu/~comp201/05-spring/lectures/lec31/
What we did there was to implement RAC using LRStruct. In particular, for priority queues, we used a sorted LRStruct with a InsertInOrder visitor as insertion strategy:
http://www.owlnet.rice.edu/~comp201/05-spring/lectures/lec31/priority/
The purpose of this lab is to implement a priority RAC using arrays with the heap structure. We will do this in two steps that mirror the LRStruct implementation of RAC:
Write stub code for ArrayPQueueFactory and write a JUnit test for it! You don't think you can get away without writing test classes, do you?
Mimic the implementation of ALRSRACFactory done in the Comp201 RAC lecture by defining a protected static class called AArrayContainer that implements IRAContainer by using a protected fixed size array (pick a number of the form 2n - 1). ArrayContainer is abstract with two abstract methods: get() and put(...). For now, the elements(...) method is concrete and just returns the IList containing the elements in the array data store.
In this class, anonymously extend AArrayContainer by implementing get() and put(...) using the siftup() and siftdown() method of a Heapifier as shown in the lecture. The makeRAC() method will simply return an instance of this anonymous class.
Last Revised Thursday, 03-Jun-2010 09:52:24 CDT
©2006 Stephen Wong and Dung Nguyen