I’m a little confused as to how to go about this assignment…
The goal is to implement a sequentially-linked structure in the form of a Priority Queue. To get experience with
parametric polymorphism. Or so it says…
Anyways, I’ve got 5 classes but I’ll try and keep this short and simple.
I’ve been messing around with the program but I just can’t seem to get it to work. There is 2 interfaces: Prioritized and PriorityQueue. Now, the Prioritized interface extends itself and the comparable interface, and I don’t understand why. Hence my first issue.
The other 2 classes that are within the same priority package are LinkedPriorityQueue (pretty much where all the hard coding goes), and PQNode (which serves to instantiate nodes within the queue. I think.)
Now I’m fairly proficient with creating single, double, and circular linked lists. My MAIN issue here is that I am adding and removing movies based on their priority (aka their rating, prioritising the lowest rating using a first in first out data structure). The reason this is an issue for me is because I’m used to manipulating nodes with simple types like Ints or Strings but not objects. Anyways, this may seem a bit confusing and I’m honestly not looking for anyone to spoon feed me, but I would like some pointers to help me understand what I’m supposed to do and what I’m doing wrong…
Here are the classes:
[/code][code]
[font=Verdana][size=2]package priority;[/size][/font]
/*This interface represents a supertype of an element that can be stored in a PriorityQueue.
*Note that it also extends the Comparable interface, meaning you’ll have to implement the
*compareTo function.
*/
public interface Prioritized<E extends Prioritized> extends Comparable {
public String getKey();
public double getPriority();
public double changePriority(double newPriority);
}
[font=Verdana][size=2px][/code][code][/font][/size]
package priority;
/*This is the interface for a PriorityQueue.
*A priority queue is a First-In, First-Out (FIFO) structure, but with a twist.
*Elements each have a ‘priority’. The FIFO behaviour only applies to elements with identical
*priorities. But the element with either the highest or lowest (in this case, highest) priority is always removed first!
*
*Note: A NoSuchElementException is thrown if the P.Q. is empty when the user tries to removeFirst or peekFirst.
*A NoSuchElementException is also thrown if the user tries to update the priority of an element that isn’t there.
*
*Make sure to include the line:
*import java.util.NoSuchElementException;
*at the start of LinkedPriorityQueue.java
*
*@see also:
- Prioritized
- PQNode
- LinkedPriorityQueue
*/
public interface PriorityQueue<E extends Prioritized> {
public void add(E item);
public E removeFirst(); //If PQ is empty, throw new NoSuchElementException
public E peekFirst(); //If PQ is empty, throw new NoSuchElementException
public void updatePriority(String key, double newPriority); //If key isn’t found, throw new NoSuchElementException
public boolean empty();
//Note: you’ll need to include “import java.util.NoSuchElementException;” in your LinkedPriorityQueue.java
}
[/code][code]
/*This class represents an actual implementation of a Priority Queue.
*In this case, it’s a dynamically-allocated one.
*Note that there are two overall approaches for implementing a priority queue.
*Refer to the assignment sheet for explanations of both.
*/
public class LinkedPriorityQueue<E extends Prioritized> implements PriorityQueue {
//INSTANCE VARIABLE(S) GOES HERE
//Remember that you can use a header/sentinel if you like
private PQNode head;
private PQNode current;
private PQNode previous;
private PQNode tail;
private E priority;
private Prioritized p;
public LinkedPriorityQueue() {
//If you’d like to, include code here.
}
//The add function adds an item to the PQ.
public void add(E item) {
//FILL THIS IN
PQNode newNode = new PQNode (item, null, null);
if (head == null) {
head = newNode;
}
else {
current = head;
while (current != null) {
previous = current;
current = current.getNext();
}
previous.setNext(newNode);
}
}
/*The removeFirst function removes the element with the highest priority
*from the queue and returns it.
*If more than one element in the PQ has the same priority, it returns
*the highest-priority element that was added first.
*Note: When an element has its priority changed, that counts as adding it fresh to the queue.
*If this function is called when the PQ is empty, a NoSuchElementException is thrown.
*/
public E removeFirst() {
//FILL THIS IN
if (head!=null) {
current = head;
}
while (current.getNext() != null) {
System.out.println(p.getPriority());
previous = current;
current = current.getNext();
}
previous.setNext(null);
return priority;
}
/*The peekFirst function is like the removeFirst function, except the PQ structure doesn’t change.
*i.e. the highest-priority element is returned, but isn’t removed from the PQ.
*If this function is called when the PQ is empty, a NoSuchElementException is thrown.
*/
public E peekFirst() {
//FILL THIS IN
if (head!=null) {
current = head;
}
while (current.getNext() != null) {
System.out.println(p.getPriority());
previous = current;
current = current.getNext();
}
previous.setNext(null);
return priority;
}
/*The updatePriority method locates an element (identified by its key), and assigns a new
*priority to it.
*If no element in the queue matches the provided key, a NoSuchElementException is thrown.
*/
public void updatePriority(String key, double newPriority) {
//FILL THIS IN
}
//This function returns true when the PQ is empty; false otherwise
public boolean empty() {
//FILL THIS IN
if(head == null) {
return true;
}
return false;
}
}
[/code][code]
package priority;
//This class represents a simple wrapper, used by a linked structure (in this case, a LinkedPriorityQueue).
class PQNode {
//FILL IN INSTANCE VARIABLES AND CONSTRUCTOR HERE
private E value;
private PQNode next;
private PQNode previous;
private PQNode key;
public PQNode () {
}
public PQNode (E newValue, PQNode newNext, PQNode newPrev) {
value = newValue;
next = newNext;
previous = newPrev;
}
public E getValue () {
return value;
}
public PQNode getNext () {
return next;
}
public PQNode getPrev () {
return previous;
}
public void setValue (E newValue) {
value = newValue;
}
public void setNext (PQNode newNext) {
next = newNext;
}
public void setPrev (PQNode newPrev) {
previous = newPrev;
}
}
.
[/code][code]
package testing;
import priority.*;
/*This class represents some item that one might wish to store in a structure, and compare against
*other instances of itself.
*Note that this class is nearly complete.
*
*The only thing you have to do is to fill in the compareTo function so that:
**If this movie has the same rating, it returns 0
**If this movie has a lower rating, it returns a positive value
**If this movie has a higher rating, it returns a negative value
*
*If that sounds backwards, remember that compareTo gives an indication of ordering.
*We’re assuming that one would prefer to watch a good movie before a bad one.
*/
public class Movie implements Prioritized {
private String title;
private double rating;
private String year;
PriorityQueue pq=new LinkedPriorityQueue();
public Movie(String title, String year, double rating) {
this.title=title;
this.year=year;
this.rating=rating;
}
public int compareTo(Movie other) {
/FILL IN THIS FUNCTION HERE./
if (this.equals(other)){
return 0;
}
else if (getRating() < other.getRating()) {
return 1;
}
else {
return -1;
}
}
public double changeRating(double newRating) {
return (-1*(rating-(rating=newRating)));
}
public String getTitle() {
return title;
}
public String getYear() {
return year;
}
public double getRating() {
return rating;
}
public String getKey() {
return title+" ("+year+")";
}
public double getPriority() {
return getRating();
}
public double changePriority(double newP) {
return changeRating(newP);
}
}
This is just the testing harness
[/code][code]
package testing;
import priority.*;
import java.util.NoSuchElementException;
/*This class represents a simple test harness, to verify the behaviour of a priority queue.
*Make sure that you test the following:
**Exceptions are thrown when removing and when peeking on an empty queue.
**Updating priority actually, uh, works.
**Trying to update priority based on a key not in the PQ throws an exception.
**For titles of equal rating, the PQ needs to be FIFO (i.e. a queue).
*/
public class TestHarness {
public static void main(String[] args) {
PriorityQueue pq=new LinkedPriorityQueue();
Movie[] movies={
new Movie(“The Matrix”,“1999”,7.5),
new Movie(“Spider-Man”,“1999”,8.5),
new Movie(“American Pie”,“1999”,6.5),
new Movie(“Army of Darkness”,“1992”,9.5),
new Movie(“The Last House on the Left”,“1972”,1.5),
new Movie(“The Last House on the Left”,“2009”,1.5),
new Movie(“Iron Man”,“2008”,8.5)
}; //Add more movies to this list (they don’t need to be real)
//Feel free to also instantiate and add more Movies that aren’t on the list
//TESTING GOES HERE (Feel free to use helper methods if you like)
pq.add(movies[0]);
System.out.println(pq);
}
}
[/code]
Anyways, I tried to complete it to the best of my knowledge but I am completely lost. I didn’t think that priority queues would be so much more challenging than Linked Lists…
Any help would be appreciated (also my prof took the liberty of commenting everything. The hints were helping, but I still couldn’t grasp it)
)?