I am tasked with writing my own PriorityQueue class in Java. It is based on LinkedLists. To quote the directions:
The type of the data stored in the nodes should be a generic type that is comparable. That is write for the class declaration: public class PriorityQueue (E extends Comparable)) -> note: the curly braces are meant to mean <>, whatever I write between <> is disappearing...
I will be using the PriorityQueue to write two other classes, one of type patient, the other of waitingRoom. This is where the compareTo method will come into play, as I sort the two classes into their individual PriorityQueues.
I have been defining the ListNode class inside of the PriorityQueue class itself, so I have a class within a class. Now comes the question:
Where am I going to implement/Override the inherited compareTo method from Comparable?
It can't get implemented in the PriorityQueue class because compareTo can only take one argument. Yet, this is where it seems like it should go, as this is the actual class extending Comparable.
If I implement it inside the ListNode class, well, I have no idea how I would. Do I turn ListNode into an interface? An AbstractClass?
Below is the quite novice code I have written, thanks for the help
package hostpitalQueue;
import java.util.AbstractList;
public class PriorityQueue<E extends Comparable<E>> {
private ListNode front;
public PriorityQueue() {
front = null;
}
public PriorityQueue(ListNode n1) {
front = n1;
}
//method for addingNode to beginning,
//perhaps overload method for next nodes?
public void addNode(ListNode n1) {
if(front == null) {
front = n1;
}else {
//need to find last node and add n1 to it
ListNode lastNode = findLastNode(n1);
lastNode.addNode(n1);
}
}
//need to compare, remember, this is a priorityqueue
public ListNode findLastNode(ListNode n) {
//compare the data of both
//compare to front
ListNode n1 = front;
int i = n1.compareTo(n);
//only do something here if n is higher priority
if(i > 0) {
E frontData = n1.data;
E nodesData = n.data;
ListNode holder = n1;
front = n;
n.next = holder;
holder.previous = n;
}else if(n1.next == null) {
n1.next = n;
n.previous = n1;
}
else {
while(front.next != null) {
n1 = front.next;
//is n1 a higher priority?
Integer ii = n1.compareTo(n);
if(ii > 0) {
//this means that we should return the previous node, to insert
//before this one
return n1.previous;
}
}
}
return n1;
}
public class ListNode {
//contains a left and a right, as well as a data field
public E data;
public ListNode previous,next;
//construct
public ListNode() {
data = null;
previous = null;
next = null;
}
//previous to next
public ListNode(E data) {
this.data = data;
previous = null;
next = null;
}
public ListNode(E data,ListNode n1) {
this.data = data;
previous = n1;
next = null;
}
public ListNode(E data,ListNode n1,ListNode n2) {
this.data = data;
previous = n1;
next = n2;
}
public void addNode(ListNode n1) {
//gotta check if my next is null
ListNode holder = null;
if(this.next != null) {
holder = this.next;
}
this.next = n1;
n1.previous = this;
n1.next = holder;
}
public int compareTo(ListNode n1) {
return 0;
}
public void printMe() {
System.out.println(this.data);
}
}
}
Each class that you will use as element type of PriorityQueue must implement the Comparable interface and the compareTo method.
Note that as your ListNode class implements a compareTo method, you could have made it implement Comparable<ListNode>:
public class ListNode implements Comparable<ListNode> {
...
@Override
public int compareTo(ListNode n1) {
return data.compareTo(n1.data);
}
Note that as you ListNode classe doesn't depend on an instance of PriorityQueue, you could have made it static; in which case, you would have had to declare a generic argument:
public static class ListNode<T extends Comparable<T>>
implements Comparable<ListNode<T>> {
//contains a left and a right, as well as a data field
public T data;
public ListNode<T> previous,next;
//construct
public ListNode() {
data = null;
previous = null;
next = null;
}
//previous to next
public ListNode(T data) {
this.data = data;
previous = null;
next = null;
}
public ListNode(T data,ListNode<T> n1) {
this.data = data;
previous = n1;
next = null;
}
public ListNode(T data,ListNode<T> n1,ListNode<T> n2) {
this.data = data;
previous = n1;
next = n2;
}
public void addNode(ListNode<T> n1) {
//gotta check if my next is null
ListNode<T> holder = null;
if(this.next != null) {
holder = this.next;
}
this.next = n1;
n1.previous = this;
n1.next = holder;
}
@Override
public int compareTo(ListNode<T> n1) {
return data.compareTo(n1.data);
}
public void printMe() {
System.out.println(this.data);
}
}
class ListNode has fields, so you can't change it to an interface (why the hell would you do that anyway?)
You should perhaps ask yourself if you really need a doubly linked list and if a singly linked list would not suffice.
It is unclear in your question if you need to implement a linked list or if you could make use of the class LinkedList in which case you would not need the ListNode class: PriorityQueue would just encapsulate a LinkedList<E>.