Java priority queue that extends comparable?

Question

I am working on a class assignment and I don't quite understand how to use comparator in the way the assignment is asking.

The assignment reads:

"Complete the Priority Queue class

1. Your Priority Queue must use an anonymous function to decide priority
2. It must take the Function interface as a parameter to the constructor
3. You should still have the default constructor – and if no function is provide use the compareTo function of the class"

This is the class that I am working on...

public class PriorityQueue <Item extends Comparable<Item>> {

    public PriorityQueue()
    {

    }
    public PriorityQueue(Comparator<Item> compare )
    {

    }  

    private int size = 0;
    private Node<Item> head = null;
    private Comparator<Item> compare ;

    private static class Node<Item>
    {
       private Item data;
       private Node<Item> next;


    public Node(Item data, Node<Item> next)
       {
          this.data = data;
          this.next = next;
       }       
       public Node(Item data)
       {
          this.data = data;
          this.next = null;
       }       
       public Node()
       {
          this.data = null;
          this.next = null;
       }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Item dequeue() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public void enqueue(Item item) {
        Node<Item> curr = head;
        Node<Item> prev = curr;

        if (isEmpty())
        {
            head = new Node<Item>(item,null);
        }
        else
        {
            while (curr != null)
            {
                prev = curr;
                curr = curr.next;
            }

            prev.next = new Node<Item>(item, curr);
        }
        size++;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void printQueue() {
        Node<Item> curr = head;

        while (curr != null)
        {
            System.out.println(curr.data);
            curr = curr.next;
        }

    }
}

This is the process class that the queue will contain...

public class Process implements Comparable<Process> {

    private ProcessPriorty priority;
        private String name;

    public Process(ProcessPriorty priority, String name) {
        super();
        this.priority = priority;
        this.name = name;
    }

    public void setPriority(ProcessPriorty priority) {
        this.priority = priority;
    }

    @Override
    public String toString() {
        return name + "... Priority = " + priority + ".";
    }

    public String getName() {
        return name;
    }

    public ProcessPriorty getPriority() {
        return priority;
    }

    @Override
    public int compareTo(Process other) {

        if(other == null)
        {
            return  1;
        }
        return this.priority.compareTo(other.priority) ;
    }
}

I understand the concept of a queue and have even coded the enqueue method to work as a simple queue that inserts the items as they come in. The problem I am coming across is comparing the nodes within that method to sort the list by priority at insertion. Which I believe relates back to those three directions of the assignment. So, what am I suppose to do with the constructors, the Comparator variable, and how do I make it default to compareTo?

Answer 1

Well since you have a reference to the head of the queue, its pretty simple from there. You have 2 cases -

1. compare != null

2. compare == null

   • In the first case, you are interested in Comparator::compareTo. From the definition of a priority queue, all you have to do is traverse the queue beginning from head, and as soon as the item in enqueue(Item item) is greater than the current element in the traversal, you insert item before element. You'll use compare.compareTo(item, element) to determine their order.

   • In the second case you'll simply use item.compareTo(element) to make the above stated comparison, the traversal and insertion will be the same.