Assignment #5 Solution

Description

Objectives:

 

• To create a binary tree using an array.

 

• To create a priority queue.

 

• To apply data abstraction: hiding a complex data type inside a simpler ADT.

 

• To continue exposure to the principles of inheritance, encapsulation and modularity.

 

• To continue to practice unit testing.

 

Introduction

 

A group of patients are sitting in the Emergency Room waiting room at the local hospital, when the attending physician arrives for her shift. The triage nurse has already assessed patients by their main complaint and provides an electronic device whereby the physician can touch the screen and the next patient chart is provided. The order of the list is determined by the patient’s priority. You have been selected to write part of the software that stores the patient information and prioritizes the list for the ER physician. Your boss wants the code to be in the form of a priority queue that uses an array-­‐based heap to store the ER_Patient objects (this class has already been completed).

 

Preparation

 

1. Refer to Chapter 12 of the textbook for background on the array-­‐based heap and the PriorityQueue ADT. We will be avoiding the use of generic datatypes in this assignment and referencing the provided ER_Patient class. Note that the Heap is the hidden data type we will use as the main instance variable of the PriorityQueue

 

2. Download all the necessary java files for this assignment into a folder created for this assignment.

 

3. All the files will compile; run javac *.java. During the process of completing the assignment, check to make sure everything still compiles before continuing.

 

4. Familiarize yourself with the ER_Patient class. It is the item that will be stored in the Heap, so you will need to know how to instantiate it and compare the priorities of two patients. You do not need to understand the implementation, but you are welcome to, for learning purposes. You can

 

easily work with the class by reading the documentation; simply run javadoc ER_Patient.java NoSuchCategoryException.java and then open the index.html file that was created.

 

Implementation details

 

 

You are to write and test the implementation of the Heap and PriorityQueue classes.

 

The following ordered steps are provided to guide you:

1. Complete the Heap class:

 

1. A shell has been provided. Fill in the comments above each of the public methods and write the code that makes these methods work.

 

1. You are strongly encouraged to add as many additional instance variables and methods as you need. However, you must not change the provided method headers or the instance variable. There are two reasons for this requirement:

 

1. You are a programmer on a team; others are expecting their code to plug into your code.

 

1. You are a student in CSC115, doing an exercise that enhances your skills as a programmer. To obtain adequate feedback, the marker(s) are counting on easy access to your implementation.

 

1. Note that the array size is not determined or limited. Somewhere in the source code, there must be a provision for increasing the size of the array to accommodate large numbers of patients. It is not sufficient to assume an upper limit on the number of patients in an ER.; it is also not good programming practice. Create a private method that doubles the size of the array to accommodate more patients into a full array.

 

1. You must test all of your public Heap methods in the main method. The more rigorously you test, the more robust your code. Do not move to the next step until you are confident that your Heap works as expected.

 

1. Note that the ER_Patient main class has a unit tester. It uses a sleep() call to spread a single second between admit times. You may use this technique or choose to create your own times and insert them into one of the constructors. For the sake of the marker’s sanity, DO NOT use Thread.sleep in any method other than main.

 

2. Complete the PriorityQueue class using a Heap data structure as the main instance variable.

 

1. Comment each of the methods appropriately

 

1. Fill in each of the methods. HINT: Let the hidden Heap do all the work for the PriorityQueue.

 

1. Note that the default constructor is complete as is.

1. Test the PriorityQueue:

 

1. If the Heap has been thoroughly tested, it is sufficient to insert a few patients and then dequeue and print until the queue is empty. A sorted print out indicates success.

Some tips and considerations

 

• As in the previous assignment, there are hidden gems to learn from the professional style of the programming; please take advantage of these, by reading the code thoroughly, until you understand it.

 

• It is a good idea to create private methods that help you test your code. For instance, a method that prints out the contents of the array in the Heap class is a handy tool to mark the progress of the implementation. Because it is private, only the programmer can use it.

 

The Heap vs the PriorityQueue

 

A PriorityQueue can use a linked data structure, an un-­‐ordered array, an ordered array, or a tree as its private data structure. We use the Heap in this exercise, because the Heap data structure is so beautifully similar to a PriorityQueue and takes O(log n) for both insert and remove operations. However, the Heap is a complete binary tree data structure and is not necessarily bound by the PriorityQueue ADT. For instance, it is allowed to have an iterator and it is allowed to have a size method. There are other tree-­‐related methods such as isInternal that are not part of the PriorityQueue ADT. There is also nothing stopping a Heap from deleting an item in the middle of its structure, although there are better data structures for that kind of operation.

 

The PriorityQueue ADT is much more limiting. For that reason, you want to make sure that the user does not ever have access to the Heap itself. It is desirable to have the PriorityQueue hide any extra functionality of the Heap.

 

Submission

 

Submit your Heap.java and PriorityQueue.java using conneX. Please be sure you submit your assignment, not just save a draft.

 

A reminder that it is OK to talk about your assignment with your classmates, and you are encouraged to design solutions together, but each student must implement their own solution.

 

Grading

 

If you submit something that does not compile, you will receive a grade of 0 for the assignment. It is your responsibility to make sure you submit the correct files.

 

 

Requirement	Marks
You submit something that compiles	expected
Method commenting style	1
All specifications implemented and	7
correct
Thorough unit testing	2