public class PriorityQueue extends LList
{
//Enqueue without priority
public void enqueue (Object o)
{
enqueue(o,0);
}
//enqueue with priority
public void enqueue (Object o, int priority)
{
//when key is true stop inserting
boolean key = false;
//if the list is not empty
if(!this.isEmpty())
{
this.setFirst();
//while current value is not null check
while (this.currValue() != null && key != true)
{
//priority is greater than the previous priority
if(priority >= this.currPriority())
{
if (priority >0)
{
if (priority == this.currPriority())
{
//if the priority is the same
while(this.currPriority() == priority)
{
this.next();
}
this.insert(o, priority);
key = true;
}
//if not the same
else
{
this.insert(o, priority);
key = true;
}
}
//if priority is 0
else
{
this.insert(o, priority);
key = true;
}
}
if (priority != this.currPriority())
this.next();
}
}
else
{
this.insert(o,priority);
}
}
// clear
public void clear ()
{
head.setNext(null);
curr = tail = head;
num = 0;
}
//dequeue
public Object dequeue ()
{
this.setFirst();
return this.remove();
}
//checks if empty
public boolean isEmpty()
{
if (head.next() == null)
return true;
else
return false;
}
//print
public void print()
{
if (isEmpty())
System.out.println("()");
else
{
System.out.print("( ");
for (setFirst(); isInList(); next())
System.out.print(currValue() + " ");
System.out.println(")");
}
}
//find size
public int size()
{
int a =0;
a = length();
return a;
}
}
class LList
{ // Linked list class
protected Link head; // Pointer to list header
protected Link tail; // Pointer to last Object in list
protected Link curr; // Pointer to current Object
protected int num;
LList(int sz) {
setup();
} // Constructor -- Ignore sz
LList() {
setup();
} // Constructor
private void setup()
{ // Do initialization
tail = head = curr = new Link(null);
num = 0;
} // Create header node
public void clear()
{ // Remove all Objects from list
head.setNext(null); // Drop access to rest of links
curr = tail = head; // Reinitialize
num = 0;
}
// Insert Object at current position
public void insert(Object it, int n) {
/* in 1.4, we can say:
assert (curr != null) : "No current element.";
Leave this in old form for now:
*/
Assert.notNull(curr, "No current element");
curr.setNext(new Link(it,n, curr.next()));
if (tail == curr) // Appended new Object
tail = curr.next();
}
// Insert Object at end of list
public void append(Object it,int n) {
tail.setNext(new Link(it,n, null));
tail = tail.next();
}
public Object remove() { // Remove and return current Object
if (!isInList())
return null;
Object it = curr.next().element(); // Remember value
if (tail == curr.next())
tail = curr; // Removed last: set tail
curr.setNext(curr.next().next()); // Remove from list
return it; // Return value removed
}
public void setFirst() // Set curr to first position
{ curr = head; }
public void next() { // Move curr to next position
if (curr != null) curr = curr.next();
}
public void prev() { // Move curr to previous position
if ((curr == null) || (curr == head)) { // No previous Object
curr = null;
return;
} // so just return
Link temp = head; // Start at front of list
while ((temp != null) && (temp.next() != curr))
temp = temp.next();
curr = temp; // Found previous link
}
public int length() { // Return current length of list
int cnt = 0;
for (Link temp = head.next(); temp != null; temp = temp.next())
cnt++; // Count the number of Objects
return cnt;
}
public void setPos(int pos) { // Set curr to specified position
curr = head;
for(int i=0; (curr!=null) && (i<pos); i++)
curr = curr.next();
}
public void setValue(Object it) { // Set current Object's value
/* in 1.4, we can say:
assert (isInList()) : "No current element.";
Leave this in old form for now:
*/
Assert.notFalse(isInList());
curr.next().setElement(it);
}
public Object currValue() { // Return value of current Object
if (!isInList())
return null;
return curr.next().element();
}
public int currPriority() { //Return the current priority of the object
if(!isInList())
return 0;
return curr.next().priority();
}
public boolean isEmpty() { // Return true if list is empty
return head.next() == null;
}
public boolean isInList() { // True if curr is within list
return (curr != null) && (curr.next() != null);
}
public void print() { // Print out the list's elements
if (isEmpty())
System.out.println("()");
else {
System.out.print("( ");
for (setFirst(); isInList(); next())
System.out.print(currValue() + " ");
System.out.println(")");
}
}
} // class LList
class Link { // A singly linked list node
private Object element; // Object for this node
private Link next; // Pointer to next node in list
private int num;
Link(Object it,int n, Link nextval) { // Constructor 1
element = it;
next = nextval;
num = n;
} // Given Object
Link(Link nextval) {
next = nextval;
} // Constructor 2
Link next() {
return next;
}
Link setNext(Link nextval) {
next = nextval;
return next;
}
Object element() {
return element;
}
int priority() {
return num;
}
Object setElement(Object it) {
element = it;
return element;
}
int setPriority(int i) {
num = i;
return i;
}
} // class Link
class Assert
{
static public void notFalse(boolean b)
throws IllegalArgumentException {
if(b == false)
throw new IllegalArgumentException(
"boolean expression false");
}
static public void notNull(Object obj)
throws IllegalArgumentException {
if(obj == null)
throw new IllegalArgumentException("null argument");
}
static public void notFalse(boolean b, String s)
throws IllegalArgumentException {
if(b == false)
throw new IllegalArgumentException(s);
}
static public void notNull(Object obj, String s)
throws IllegalArgumentException {
if(obj == null)
throw new IllegalArgumentException(s);
}
}