Question: Hello I need help writing a class. You might need other source files too and I have posted them below please. This is the question
Hello I need help writing a class. You "might" need other source files too and I have posted them below please. This is the question
package lib280.tree;
public class IterableArrayedHeap280> extends ArrayedHeap280 {
/**
* Create an iterable heap with a given capacity.
* @param cap The maximum number of elements that can be in the heap.
*/
public IterableArrayedHeap280(int cap) {
super(cap);
}
// TODO
// Add iterator() and deleteAtPosition() methods here.
}
#PriorityQueue Class
package lib280.dispenser;
import lib280.tree.IterableArrayedHeap280;
public class PriorityQueue280> {
// This is the heap that we are restricting.
// Items in the priority queue get stored in the heap.
protected IterableArrayedHeap280 items;
/**
* Create a new priorty queue with a given capacity.
* @param cap The maximum number of items that can be in the queue.
*/
public PriorityQueue280(int cap) {
items = new IterableArrayedHeap280(cap);
}
public String toString() {
return items.toString();
}
// TODO
// Add Priority Queue ADT methods (from the specification) here.
/* UNCOMMENT THE REGRESSION TEST WHEN YOU ARE READY
public static void main(String args[]) {
class PriorityItem implements Comparable
I item;
Double priority;
public PriorityItem(I item, Double priority) {
super();
this.item = item;
this.priority = priority;
}
public int compareTo(PriorityItem o) {
return this.priority.compareTo(o.priority);
}
public String toString() {
return this.item + ":" + this.priority;
}
}
PriorityQueue280
// Test isEmpty()
if( !Q.isEmpty())
System.out.println("Error: Queue is empty, but isEmpty() says it isn't.");
// Test insert() and maxItem()
Q.insert(new PriorityItem
if( Q.maxItem().item.compareTo("Sing") != 0) {
System.out.println("??Error: Front of queue should be 'Sing' but it's not. It is: " + Q.maxItem().item);
}
// Test isEmpty() when queue not empty
if( Q.isEmpty())
System.out.println("Error: Queue is not empty, but isEmpty() says it is.");
// test count()
if( Q.count() != 1 ) {
System.out.println("Error: Count should be 1 but it's not.");
}
// test minItem() with one element
if( Q.minItem().item.compareTo("Sing")!=0) {
System.out.println("Error: min priority item should be 'Sing' but it's not.");
}
// insert more items
Q.insert(new PriorityItem
if( Q.maxItem().item.compareTo("Sing")!=0) System.out.println("Front of queue should be 'Sing' but it's not.");
Q.insert(new PriorityItem
if( Q.maxItem().item.compareTo("Sing")!=0) System.out.println("Front of queue should be 'Sing' but it's not.");
Q.insert(new PriorityItem
if( Q.maxItem().item.compareTo("Jump")!=0) System.out.println("Front of queue should be 'Jump' but it's not.");
if(Q.minItem().item.compareTo("Dance") != 0) System.out.println("minItem() should be 'Dance' but it's not.");
if( Q.count() != 4 ) {
System.out.println("Error: Count should be 4 but it's not.");
}
// Test isFull() when not full
if( Q.isFull())
System.out.println("Error: Queue is not full, but isFull() says it is.");
Q.insert(new PriorityItem
if( Q.maxItem().item.compareTo("Eat")!=0) System.out.println("Front of queue should be 'Eat' but it's not.");
if( !Q.isFull())
System.out.println("Error: Queue is full, but isFull() says it isn't.");
// Test insertion on full queue
try {
Q.insert(new PriorityItem
System.out.println("Expected ContainerFull280Exception inserting to full queue but got none.");
}
catch(ContainerFull280Exception e) {
// Expected exception
}
catch(Exception e) {
System.out.println("Expected ContainerFull280Exception inserting to full queue but got a different exception.");
e.printStackTrace();
}
// test deleteMin
Q.deleteMin();
if(Q.minItem().item.compareTo("Sing") != 0) System.out.println("Min item should be 'Sing', but it isn't.");
Q.insert(new PriorityItem
if(Q.minItem().item.compareTo("Dig") != 0) System.out.println("minItem() should be 'Dig' but it's not.");
// Test deleteMax
Q.deleteMax();
if( Q.maxItem().item.compareTo("Jump")!=0) System.out.println("Front of queue should be 'Jump' but it's not.");
Q.deleteMax();
if( Q.maxItem().item.compareTo("Fly")!=0) System.out.println("Front of queue should be 'Fly' but it's not.");
if(Q.minItem().item.compareTo("Dig") != 0) System.out.println("minItem() should be 'Dig' but it's not.");
Q.deleteMin();
if( Q.maxItem().item.compareTo("Fly")!=0) System.out.println("Front of queue should be 'Fly' but it's not.");
Q.insert(new PriorityItem
Q.insert(new PriorityItem
if( Q.maxItem().item.compareTo("Fly")!=0) System.out.println("Front of queue should be 'Fly' but it's not.");
// test deleteAllMax()
Q.deleteAllMax();
if( Q.maxItem().item.compareTo("Scream")!=0) System.out.println("Front of queue should be 'Scream' but it's not.");
if( Q.minItem().item.compareTo("Scream") != 0) System.out.println("minItem() should be 'Scream' but it's not.");
Q.deleteAllMax();
// Queue should now be empty again.
if( !Q.isEmpty())
System.out.println("Error: Queue is empty, but isEmpty() says it isn't.");
System.out.println("Regression test complete.");
}
*/
}
#ArrayedHeap280
package lib280.tree;
import lib280.base.Dispenser280;
import lib280.exception.ContainerEmpty280Exception;
import lib280.exception.ContainerFull280Exception;
import lib280.exception.NoCurrentItem280Exception;
public class ArrayedHeap280> extends ArrayedBinaryTree280 implements Dispenser280 {
/**
* Create a new heap.
* @param cap The maximum capacity of the heap.
*/
@SuppressWarnings("unchecked")
public ArrayedHeap280(int cap) {
super(cap);
items = (I[]) new Comparable[capacity+1]; // Override the constructor's implementation of items
}
/**
* Insert a new item into the heap.
*
* @param item The item to be inserted.
* @throws ContainerFull280Exception if the heap is full.
*/
public void insert(I item) throws ContainerFull280Exception {
// Insert normally
if( this.isFull() ) throw new ContainerFull280Exception("Cannot add item to a lib280.tree that is full.");
else {
count ++;
items[count] = item;
}
this.currentNode = 1;
if( count == 1 ) return;
// Then propagate the new item up the lib280.tree.
int n = count;
// As long as the items[n] is bigger than its parent...
while(n > 1 && items[n].compareTo(items[findParent(n)]) > 0) {
// find the offset of the parent
int p = findParent(n);
// Swap items[n] with its parent
I temp = items[p];
items[p] = items[n];
items[n] = temp;
// Move to the parent and check again.
n = p;
}
}
/**
* Removes the item at the top of the heap.
*
* @throws ContainerEmpty280Exception if the heap is empty.
*
*/
public void deleteItem() throws ContainerEmpty280Exception, NoCurrentItem280Exception {
if(this.isEmpty())
throw new ContainerEmpty280Exception("Cannot delete an item from an empty heap.");
// Delete the root by moving in the last item.
// If there is more than one item, and we aren't deleting the last item,
// copy the last item in the array to the current position.
if( this.count > 1 ) {
this.currentNode = 1;
this.items[currentNode] = this.items[count];
}
this.count--;
// If we deleted the last remaining item, make the the current item invalid, and we're done.
if( this.count == 0) {
this.currentNode = 0;
return;
}
// Propagate the new root down the lib280.tree.
int n = 1;
// While offset n has a left child...
while( findLeftChild(n)
// Select the left child.
int child = findLeftChild(n);
// If the right child exists and is larger, select it instead.
if( child + 1
child++;
// If the parent is smaller than the root...
if( items[n].compareTo(items[child])
// Swap them.
I temp = items[n];
items[n] = items[child];
items[child] = temp;
n = child;
}
else return;
}
}
/**
* Helper for the regression test. Verifies the heap property for all nodes.
*/
private boolean hasHeapProperty() {
for(int i=1; i
if( findRightChild(i)
// ... and i is smaller than either of them, , then the heap property is violated.
if( items[i].compareTo(items[findRightChild(i)])
if( items[i].compareTo(items[findLeftChild(i)])
}
else if( findLeftChild(i)
// ... and i is smaller than it, then the heap property is violated.
if( items[i].compareTo(items[findLeftChild(i)])
}
else break; // Neither child exists. So we're done.
}
return true;
}
/**
* Regression test
*/
public static void main(String[] args) {
ArrayedHeap280
// Empty heap should have the heap property.
if(!H.hasHeapProperty()) System.out.println("Does not have heap property.");
// Insert items 1 through 10, checking after each insertion that
// the heap property is retained, and that the top of the heap is correctly i.
for(int i = 1; i
H.insert(i);
if(H.item() != i) System.out.println("Expected current item to be " + i + ", got " + H.item());
if(!H.hasHeapProperty()) System.out.println("Does not have heap property.");
}
// Remove the elements 10 through 1 from the heap, chekcing
// after each deletion that the heap property is retained and that
// the correct item is at the top of the heap.
for(int i = 10; i >= 1; i--) {
// Remove the element i.
H.deleteItem();
// If we've removed item 1, the heap should be empty.
if(i==1) {
if( !H.isEmpty() ) System.out.println("Expected the heap to be empty, but it wasn't.");
}
else {
// Otherwise, the item left at the top of the heap should be equal to i-1.
if(H.item() != i-1) System.out.println("Expected current item to be " + i + ", got " + H.item());
if(!H.hasHeapProperty()) System.out.println("Does not have heap property.");
}
}
System.out.println("Regression Test Complete.");
}
}
#ArrayedBinaryTree280
package lib280.tree;
import lib280.base.Container280;
import lib280.exception.NoCurrentItem280Exception;
/**
* @author eramian
*
*/
public abstract class ArrayedBinaryTree280 implements Container280 {
protected int currentNode; // Index of the node corresponding to the current cursor position.
protected int capacity; // Maximum number of elements in the lib280.tree.
protected int count; // Current number of elements in the lib280.tree.
protected I items[];
/**
* Constructor.
*
* @param cap Maximum number of elements that can be in the lib280.tree.
*/
@SuppressWarnings("unchecked")
public ArrayedBinaryTree280(int cap) {
capacity = cap;
currentNode = 0;
count = 0;
items = (I[]) new Object[capacity+1];
}
/**
* Gets the index of the left child of the node at index 'node'.
*/
protected int findLeftChild(int node) {
return node * 2;
}
/**
* Gets the index of the right child of the node at index 'node'.
*/
protected int findRightChild(int node) {
return node * 2 + 1;
}
/**
* Gets the index of the parent of the node at index 'node'.
*/
protected int findParent(int node) {
return node / 2;
}
/**
* Get the item at the cursor.
*
* @precond The lib280.tree must not be empty. The cursor position must be valid.
* @throws NoCurrentItem280Exception if the cursor is not positioned at an item.
* @return The item at the cursor.
*/
public I item() throws NoCurrentItem280Exception {
if(!itemExists() ) throw new NoCurrentItem280Exception();
else return items[currentNode];
}
/**
* Determines if an item exists.
*
* @return true if there is an item at the cursor, false otherwise.
*/
public boolean itemExists(){
return count > 0 && (currentNode > 0 && currentNode
}
/**
* Get the maximum capacity of the lib280.tree.
*
* @return The maximum number of items the lib280.tree can store.
*/
public int capacity() {
return capacity;
}
/**
* Get the number of items in the lib280.tree.
*
* @return The number of items in the lib280.tree.
*
*/
public int count() {
return count;
}
/** Empty the lib280.tree
*
* Remove all elements from the lib280.tree.
*/
public void clear() {
count = 0;
currentNode = 0;
}
/**
* Returns a shallow clone of the lib280.tree. The new lib280.tree contains
* copies of item references, not new items.
*
* @return A reference to the new copy.
*/
@SuppressWarnings("unchecked")
public ArrayedBinaryTree280 clone() {
ArrayedBinaryTree280 temp;
try {
temp = (ArrayedBinaryTree280) super.clone();
}
catch (CloneNotSupportedException e) {
temp = null;
}
return temp;
}
/**
* Determine if the lib280.tree is empty.
*
* @return true if the lib280.tree is empty. false otherwise.
*/
public boolean isEmpty() {
return count == 0 && currentNode == 0;
}
/**
* Determine if the lib280.tree is full.
*
* @return true if the lib280.tree is full. false otherwise.
*/
public boolean isFull() {
return count == capacity;
}
public String toString() {
String out = "";
for(int i=1; i
out += items[i] + ", ";
}
out += " " + "Cursor is on item with array index " + this.currentNode + " (item "+this.items[this.currentNode]+")";
return out;
}
}
#Container280
package lib280.base;
/** A container class with functions to test for empty or full, and
procedure clear to remove all items. */
public interface Container280 extends Cloneable
{
/** Is the data structure empty?. */
public boolean isEmpty();
/** Is the data structure full?. */
public boolean isFull();
/** Remove all items from the data structure. */
public void clear();
}
#ContainerFull280Exception
package lib280.exception;
/** This exception is used to signal that an insertion
is being attempted into an already full container. */
public class ContainerFull280Exception extends Container280Exception
{
/** Create an exception with the specified message.
Analysis: Time = O(1) */
public ContainerFull280Exception(String message)
{
super(message);
}
/** Create an exception with the default message.
Analysis: Time = O(1) */
public ContainerFull280Exception()
{
super("ContainerFull280Exception thrown!");
}
}
#Dispenser280
package lib280.base;
import lib280.exception.ContainerFull280Exception;
import lib280.exception.DuplicateItems280Exception;
import lib280.exception.NoCurrentItem280Exception;
/** A Container class which keeps track of the current item as
insertions are made. Only the current item can be deleted.
The current item depends on the type of dispenser. */
public interface Dispenser280 extends Container280, Cursor280
{
/** Insert x into the data structure.
* @precond !isFull() and !has(x)
* @param x item to be inserted into the data structure
* @throws ContainerFull280Exception if the dispenser is already full.
* @throws DuplicateItems280Exception if the dispenser already contains x.
*/
public void insert(I x) throws ContainerFull280Exception, DuplicateItems280Exception;
/** Delete current item from the data structure.
* @precond itemExists()
* @throws NoCurrentItem280Exception if the cursor is not currently positioned at a valid item.
*/
public void deleteItem() throws NoCurrentItem280Exception;
}
#Cousor280
package lib280.base;
import lib280.exception.NoCurrentItem280Exception;
/** A cursor to keep track of the current item in a data structure.
It includes an itemExists routine to determine if the
cursor is presently referring to an item in the structure. */
public interface Cursor280 extends CursorPosition280, Cloneable
{
/** The current item.
* @precond The cursor is at a valid item.
* @return Returns the item at the cursor if there is one.
* @throws NoCurrentItem280Exception when the cursor is not at a valid item.
*/
public I item() throws NoCurrentItem280Exception;
/** Is there a current item?. */
public boolean itemExists();
}
Write a class PriorityQueue280 which is a restriction (as defined in Section 2.1) of IterableArrayedHeap280 which implements the priority queue ADT specification given in the Appendix of this document. This means that PriorityQueue 280 should have an IterableArrayedHeap280 as an instance vari- able, and it is in the heap that the queue items are stored. In this way we can hide the functionality of IterableArrayedHeap280 that we don't want exposed as well as add the functionality that it lacks. Page 3 Some of the priority queue methods, like isFull and deleteMax, require identical behavior to existing methods in the IterableArrayedHeap280 and can be written as a single call to a method in the IterableArrayedHeap280 instance variable. Other methods, like minItem and deleteAllMax, require functionality that doesn't exist in IterableArrayedHeap280 which will be up to you to implement-this wl still be done by calling methods of the internal heap, but a single call won't be enough, for example, you may need to iterate over the heap using an iterator. I have provided you with a mostly incomplete PriorityQueue280.java file in the dispenser package lib280-asn4 which contains a regression test for your convenience (you do not have to write your own). Write a class PriorityQueue280 which is a restriction (as defined in Section 2.1) of IterableArrayedHeap280 which implements the priority queue ADT specification given in the Appendix of this document. This means that PriorityQueue 280 should have an IterableArrayedHeap280 as an instance vari- able, and it is in the heap that the queue items are stored. In this way we can hide the functionality of IterableArrayedHeap280 that we don't want exposed as well as add the functionality that it lacks. Page 3 Some of the priority queue methods, like isFull and deleteMax, require identical behavior to existing methods in the IterableArrayedHeap280 and can be written as a single call to a method in the IterableArrayedHeap280 instance variable. Other methods, like minItem and deleteAllMax, require functionality that doesn't exist in IterableArrayedHeap280 which will be up to you to implement-this wl still be done by calling methods of the internal heap, but a single call won't be enough, for example, you may need to iterate over the heap using an iterator. I have provided you with a mostly incomplete PriorityQueue280.java file in the dispenser package lib280-asn4 which contains a regression test for your convenience (you do not have to write your own)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help