Priority Queue (parametric polymorphism halp pls) [SOLVED]


#1

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)


#2

You said you didn’t want to be spoonfed, but didn’t explain what exactly you were having an issue with. From what I understand you are having trouble figuring out how to compare two movies because they arent a type like int or String? The answer to that is here:

*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

This is what you should be using to sort the list


#3

[quote=“Davidi2, post:2, topic:555679”]You said you didn’t want to be spoonfed, but didn’t explain what exactly you were having an issue with. From what I understand you are having trouble figuring out how to compare two movies because they arent a type like int or String? The answer to that is here:

[quote] *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[/quote]

This is what you should be using to sort the list[/quote]

okay to be a little more specific, I think the issue I’m having is with generics. I don’t understand how to place a Movie object into a Node, and then to make a reference to the next movie within the list of nodes. I think after I’ve figured out how to do that I should be able to sort the list based on priority using the compareTo function.

Edit: I can’t seem to grasp how generics are being handled in this particular package. Maybe a little spoon feeding goes a long way (just an example or two :frowning: )?


#4

[quote=“zzjimmy, post:3, topic:555679”][quote author=Davidi2 link=topic=674892.msg4509957#msg4509957 date=1466778247]
You said you didn’t want to be spoonfed, but didn’t explain what exactly you were having an issue with. From what I understand you are having trouble figuring out how to compare two movies because they arent a type like int or String? The answer to that is here:

[quote] *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[/quote]

This is what you should be using to sort the list
[/quote]

okay to be a little more specific, I think the issue I’m having is with generics. I don’t understand how to place a Movie object into a Node, and then to make a reference to the next movie within the list of nodes. I think after I’ve figured out how to do that I should be able to sort the list based on priority using the compareTo function.

Edit: I can’t seem to grasp how generics are being handled in this particular package. Maybe a little spoon feeding goes a long way (just an example or two :frowning: )?[/quote]

The difference between storing an Integer and storing a Movie object is no different, that’s why we have generics: so we can store objects of varying types while still maintaining type-safety. This means you can perform operations of varying types consistently. However, why can’t we just store an Integer? Notice that your parameterized type has a constraint: E extends Prioritized. Why does this work with a Movie?

Let E be a Movie.
=> Movie class implements Prioritized interface (from the definition in your Movie class).
=> Therefore, E extends Prioritized.

Let E be an Integer.
=> Integer class does not implement the Prioritized interface.
=> Therefore, E does NOT extend Prioritized.

So when you’re working with a type such as E, in the context of your assignment here, think of it as just being a placeholder for a Movie.

Given all that, you do the same operations you would with any other type in a linked list. For example, to add: create a node for your Movie, iterate through each node in the linked list until you find a priority < the current one (use compareTo to compare your Movie objects), then change the pointers in the previous and next nodes to point to the one you’re adding. etc etc.


#5
The difference between storing an Integer and storing a Movie object is no different, that's why we have generics: so we can store objects of varying types while still maintaining type-safety. This means you can perform operations of varying types consistently. However, why can't we just store an Integer? Notice that your parameterized type has a constraint: E extends Prioritized. Why does this work with a Movie?

Let E be a Movie.
=> Movie class implements Prioritized interface (from the definition in your Movie class).
=> Therefore, E extends Prioritized.

Let E be an Integer.
=> Integer class does not implement the Prioritized interface.
=> Therefore, E does NOT extend Prioritized.

So when you’re working with a type such as E, in the context of your assignment here, think of it as just being a placeholder for a Movie.

Given all that, you do the same operations you would with any other type in a linked list. For example, to add: create a node for your Movie, iterate through each node in the linked list until you find a priority < the current one (use compareTo to compare your Movie objects), then change the pointers in the previous and next nodes to point to the one you’re adding. etc etc.

Okay I think I’m starting to put the pieces together, but does that mean I would need to implement the compareTo function in my PQNode class? Because if I’m looking for the movie with the highest priority within my LinkedPriorityQueue and the Nodes serve as placeholders for the Movies, I would need to compare the Nodes in order to find the priority of the movie. Correct me if I’m wrong, and sorry I’m gonna apply all of this once I get home from work.

Edit: If that’s the case then I think that my prof wanted me to handle it in a different way but I honestly don’t think it even matters as long as it works


#6

You should not need to implement compareTo in the node class, just use node.value to compare.


#7

Everything makes sense now, I was over-complicating things/didn’t understand the whole concept of generics. It doesn’t matter what object the node takes in as its value, it could be anything and I just need to get that value in order to access all of its functions. Thank you guys :slight_smile: