Comp202: Principles of Object-Oriented Programming II
Recall the Restrict Access Container (RAC) from last semester:
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:
Quick link to download the code from last semester's lectures on RAC's: http://www.owlnet.rice.edu/~comp201/07-spring/lectures/lec31/rac/rac.zip
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.
Note that it is now possible for your RAC to be full, so be sure to implement it accordingly.
Download the source code for Heapifier.java and add it to your RAC project.
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:32 CDT
©2007 Stephen Wong and Dung Nguyen