Sorting a Queue ADT

[Goldfinch]

Hi, I'm having some trouble writing a method to sort a LinkedQueue ADT. I find it difficult to keep track of the order things when sorting is concerned (ha ha ha).
I'm trying to pull the values out of a Queue which store objects of type PrinterItem. Those objects in turn each store two variables jobNumber (each of which is a unique integer value) and numPages (as well as a third variable that isn't relevant).
I am trying to sort the objects from least to greatest numPages value and if any two objects have the same numPages value then sort then from least to greatest jobNumber.

Here is the relevant code (which doesn't work). Note: the pass() method in this code merely takes in the object and returns it ensuring it has been properly cast.

sort method:

        LinkedQueue<PrinterItem> tempQueue = new LinkedQueue();
        while (!(obj.isEmpty())) {
            PrinterItem firstSeen = pass(obj.dequeue());
            if (obj.size() != 0) {
                if ((pass(obj.first())).compareTo(firstSeen) == 1) {/*
                     * Swap items
                     */
                    if (obj.size() != 0) {
                        PrinterItem secondSeen = pass(obj.dequeue());
                        tempQueue.enqueue(firstSeen);
                        tempQueue.enqueue(secondSeen);
                    }
                } else if ((pass(obj.first())).compareTo(firstSeen) == -1) {/*
                     * replace dequed item
                     */
                    if (obj.size() != 0) {
                        tempQueue.enqueue(firstSeen);
                    }
                } else if ((pass(obj.first())).compareTo(firstSeen) == 0) {/*
                     * do nothing
                     */

                }
            }

        }
        return tempQueue;
    }

and the compareTo method in the PrintItem class is:

    @Override
    public int compareTo(PrinterItem o) {
        int returnIt=0;
        if (this.numPages < o.numPages) {
            returnIt=-1;
        } else if (this.numPages > o.numPages) {
            returnIt=1;
        } else if (this.numPages == o.numPages) {
            if (this.jobNumber < o.jobNumber) {
                returnIt=-1;
            } else if (this.jobNumber > o.jobNumber) {
                returnIt=1;
            } else {
                returnIt=0;
            }
        }
        return returnIt;
    }

[Taywin]

OK, are you required to do it with 2 queues in the implementation? Are you allowed to use recursive methods instead? Does your queue class has a peek() method -- a method to look at the value of the last item in the queue and not dequeue the queue.

Anyway, I would like to comment on your compareTo() method definition. You do not need to have an extra variable (returnIt) in the method but rather return a constant right away. Also, once you change it to return a constant right away, the second else if (this.numPages==o.numPages) is not necessary. The reason is that if the first 2 statements (if & else if) are executed and passed through, you know for sure that the numPages of 2 objects are the same.

[Goldfinch]

OK, are you required to do it with 2 queues in the implementation?

The only requirement for the sort method is that it takes a queue as data and then returns that queue in sorted order

Are you allowed to use recursive methods instead?

Yes, as long as the method succeeds at sorting I think recursive is fine.

Does your queue class has a peek() method -- a method to look at the value of the last item in the queue and not dequeue the queue.

Not exactly, it has a first method which may be essentially equivalent. Here is the code for that:

   @Override
    public T first () throws EmptyCollectionException {  
        if (isEmpty()) throw new EmptyCollectionException("Queue underflow");
        return front.getElement();
     }

The front object in the return statement is of type LinearNode and the code for the LinearNode class is:

public class LinearNode<T>
{
   private LinearNode<T> next;
   private T element;

   //-----------------------------------------------------------------
   //  Creates an empty node.
   //-----------------------------------------------------------------
   public LinearNode()
   {
      next = null;
      element = null;
   }

   //-----------------------------------------------------------------
   //  Creates a node storing the specified element.
   //-----------------------------------------------------------------
   public LinearNode (T elem)
   {
      next = null;
      element = elem;
   }

   //-----------------------------------------------------------------
   //  Returns the node that follows this one.
   //-----------------------------------------------------------------
   public LinearNode<T> getNext()
   {
      return next;
   }

   //-----------------------------------------------------------------
   //  Sets the node that follows this one.
   //-----------------------------------------------------------------
   public void setNext (LinearNode<T> node)
   {
      next = node;
   }

   //-----------------------------------------------------------------
   //  Returns the element stored in this node.
   //-----------------------------------------------------------------
   public T getElement()
   {
      return element;
   }

   //-----------------------------------------------------------------
   //  Sets the element stored in this node.
   //-----------------------------------------------------------------
   public void setElement (T elem)
   {
      element = elem;
   }
}

[Taywin]

Oops, sorry I mean peek() is to get at the first element in the queue without dequeuing it. If your first() seems to be OK, then you could use a recursive method to dequeue all of the queue element, and then reconrstruct the queue again. The trick for reconstruct the queue is to see if the new insert should be after than the current first element. If it is, keep popping the element until it found where it should be, and then insert it. A sort of pseudo code is below.

 insertElem(object)
   if the queue is empty or
   the comparison of object and the first element in the queue is fine
     enqueue(object)
   else
     deQ <- dequeue the queue
     insertElem(object)   // recursive call to find the right place to insert
     enqueue(deQ)        // insert the element back to the queue
   end if
 end insert

 sortQueue()
   if the queue is not empty
     elem <- dequeue the queue
     sortQueue()         // recursive call to break down each element
     insertElem(elem)    // do insert (the queue will be sorted while inserting)
   end if
 end sortQueue

The idea is to break down each element in a queue first. Then start from the last element it seen to insert. If it is OK, enqueue it; otherwise, dequeue the one in front until it find the right place.

/*
For example, a queue looks like below and you want to sort in ascending order
5,3,1,8,2,9

call sortQueue()
queue is not empty, take 5 out, queue is now 3,1,8,2,9
call sortQueue()
queue is not empty, take 3 out, queue is now 1,8,2,9
call sortQueue()
...
queue is not empty, take 9 out, queue is now empty

call insertElem(9)
queue is empty, enqueue(9), queue is now 9
return back to the caller
call insertElem(2)
queue is not empty and the first element 9>2, so enqueue(2), queue is 2,9
return back to the caller
call insertElem(8)
queue is not empty but the first element 2<8
dequeue and save the element 2  (queue is 9)
call insertElem(8)
queue is not empty and the first element 9>8, so enqueue(8), queue is 8,9
return back to the caller
enqueue(2) back to the queue, queue is 2,8,9
return back to the caller
...
..., queue is 1,2,3,8,9
call insertElem(5)
queue is not empty but the first element 1<5
dequeue and save the element 1  (queue is 2,3,8,9)
call insertElem(5)
queue is not empty but the first element 2<5
dequeue and save the element 2  (queue is 3,8,9)
call insertElem(5)
queue is not empty but the first element 3<5
dequeue and save the element 3  (queue is 8,9)
call insertElem(5)
queue is not empty and the first element 8>5, so enqueue(5), queue is 5,8,9
return back to the caller
enqueue(3) back to the queue, queue is 3,5,8,9
return back to the caller
enqueue(2) back to the queue, queue is 2,3,5,8,9
return back to the caller
enqueue(1) back to the queue, queue is 1,2,3,5,8,9
return back to the caller   // done
*/

[Goldfinch]

By the way, I wanted to say thank you for your help. My tight schedule kept me distracted, but I felt I had to say that.