/**
 *
 * Class to implement priority queue with pointers
 *
 * written by : R. G. Garside
 *
 * first written : 10/July/96
 * last rewritten : 11/July/96
 *
 */

import java.io.* ;
import java.lancs.* ;

class QueueNode
    {
    int priority ;
    String data ;
    QueueNode next ;

    /**
     * Constructor
     */

    public QueueNode(int p, String d)
        {
        priority = p ;
        data = d ;
        next = null ;
        } // end of constructoe method

    } // end of class QueueNode

public class PriorityQueue
    {
    private QueueNode firstPointer = null ;

    /**
     * Constructor
     */

    public PriorityQueue()
        {
        firstPointer = null ;
        // System.out.println("pointer implementation") ;
        } // end of constructor method

    /**
     * initialize - initializes a PriorityQueue to empty
     */

    public void initialize()
        {
        firstPointer = null ;
        } // end of method initialize

    /**
     * insert - insert in the priority queue a QueueElement "d"
     */

    public void insert(QueueElement d)
        {
        boolean qStart = true ;
        QueueNode pointer = firstPointer,
	     pointer1 = null ;

        while ((pointer != null) &&
	       (pointer.priority <= d.getPriority()))
 	    {
	    pointer1 = pointer ;
	    qStart = false ;
	    pointer = pointer.next ;
	    }

        QueueNode newPointer = new QueueNode(d.getPriority(), d.getData()) ;
        newPointer.next = pointer ;
        if (qStart)
	    firstPointer = newPointer ;
        else
	    pointer1.next = newPointer ;
        }

    /**
     * first - return the QueueElement which is the first item in the
     *     priority queue, without removing it; the exception
     *     "queue_empty" is thrown if the queue is empty
     */

    public QueueElement first() throws QueueEmptyException
        {
        if (isEmpty())
            throw new QueueEmptyException() ;

        return new QueueElement(firstPointer.priority, firstPointer.data) ;
        } // end of method first

    /**
     * remove - remove the first item from the priority queue "q", 
     *     returning the priority "p" and data "d"; the exception
     *     "queue_empty" is raised if there are no items in the queue
     */

    public QueueElement remove() throws QueueEmptyException
        {
        if (isEmpty())
             throw new QueueEmptyException() ;

        QueueElement temp = new QueueElement(firstPointer.priority,
   				        firstPointer.data) ;
        firstPointer = firstPointer.next ;
        return temp ;
        } // end of method remove

    /**
     * length - returns the number of items in the priority queue "q"
     */

    public int length()
        {
        int count = 0 ;
        for (QueueNode pointer = firstPointer ;
	     pointer != null ;
	     pointer = pointer.next)
	count++ ;
        return count ;
        } // end of method length

    /**
     * isFull - returns TRUE if the PriorityQueue "q" is full, otherwise
     *     returns FALSE.
     */

    public boolean isFull()
        {
        return false ;
        } // end of method isFull

    /**
     * isEmpty - returns TRUE if the PriorityQueue "q" is empty,
     *     otherwise returns FALSE.
     *
     */

    public boolean isEmpty()
        {
        return firstPointer == null ;
        } // end of method isEmpty


    /**
     * main
     */

    public static void main(String[] args) throws IOException
        {
        int priority ;
        String data ;
        String response ;
        boolean continueLoop = true ;
        PriorityQueue q = new PriorityQueue() ;
        QueueElement temp = new QueueElement() ;

        while (continueLoop)
            {
            displayMenu() ;

            try {
                response = BasicIo.readString().toLowerCase() ;
                if (response.length() == 0)
	            response = "x" ;

                switch (response.charAt(0))
                    {
                    case '1' :
                        q.initialize() ;
                        System.out.println("queue initialized") ;
                        break ;

                    case '2' :
                        BasicIo.prompt("priority? ") ;
                        priority = BasicIo.readInteger() ;
                        BasicIo.prompt("string to insert? ") ;
                        data = BasicIo.readString() ;
                        temp.setPriority(priority) ;
                        temp.setData(data) ;
                        q.insert(temp) ;
                        System.out.print("'" + data) ;
                     System.out.print("' inserted in queue with priority ") ;
	                System.out.println(priority) ;
                        break ;

                    case '3' :
                        temp = q.first() ;
                        System.out.print("'" + temp.getData()) ;
                     System.out.print("' at head of queue with priority ") ;
	                System.out.println(temp.getPriority()) ;
                        break ;

                    case '4' :
                        temp = q.remove() ;
                        System.out.print("'" + temp.getData()) ;
                     System.out.print("' removed from queue with priority ") ;
	                System.out.println(temp.getPriority()) ;
                        break ;

                    case '5' :
                        System.out.print("there are " + q.length()) ;
		        System.out.println(" items in the queue") ;
                        break ;

                    case '6' :
                        System.out.print("the queue is ") ;
                        if (!q.isFull())
                            System.out.print("not ") ;
                        System.out.println("full") ;
                        break ;

                    case '7' :
                        System.out.print("the queue is ") ;
                        if (!q.isEmpty())
                            System.out.print("not ") ;
                        System.out.println("empty") ;
                        break ;

                    case '8' :
                        while (true)
                            {
                            BasicIo.prompt("priority (0 to terminate)? ") ;
                            priority = BasicIo.readInteger() ;
                            if (priority == 0)
                                break ;
            
                            BasicIo.prompt("string to insert? ") ;
                            data = BasicIo.readString() ;

                            temp.setPriority(priority) ;
                            temp.setData(data) ;
                            q.insert(temp) ;
                            }
                        break ;

                    case '9' :
                        while (!q.isEmpty())
                            {
                            temp = q.remove() ;
                            System.out.print("'" + temp.getData()) ;
                            System.out.print("' with priority ") ;
                            System.out.println(temp.getPriority()) ;
                            }
                        System.out.println("**end of queue**") ;
                        break ;

                    case 'a' :
	                q.print() ;
	                break ;

                    case 'q' :
                        continueLoop = false ;
                        break ;

                    default :
                        System.out.println("invalid response") ;
	                break ;
                    }

                if (continueLoop)
	            {
      	            BasicIo.prompt("press RETURN to continue") ;
                    response = BasicIo.readString() ;
                    }
                }
            catch (QueueEmptyException e)
		{
                System.out.println("exception thrown: queue is empty") ;
                BasicIo.prompt("press RETURN to continue") ;
                response = BasicIo.readString() ;
                }
            }

        System.out.println("program terminating") ;
        } // end of method main

    /**
     * displayMenu
     */

    private static void displayMenu()
        {
        System.out.println() ;
        System.out.println("Options to Exercise the Priority Queue") ;
        System.out.println() ;
        System.out.println("1 : initialise") ;
        System.out.println("2 : insert") ;
        System.out.println("3 : first") ;
        System.out.println("4 : remove") ;
        System.out.println("5 : length") ;
        System.out.println("6 : is full") ;
        System.out.println("7 : is empty") ;
        System.out.println() ;
        System.out.println("8 : multiple item insert") ;
        System.out.println("9 : scan and empty queue") ;
        System.out.println("a : print queue contents") ;
        System.out.println() ;
        System.out.println("q : quit") ;
        } // end of method displayMenu

    /**
     * print
     */

    private void print()
        {
        System.out.println("the queue is (highest priority first)") ;
        int i = 0 ;
        for (QueueNode pointer = firstPointer ;
	     pointer != null ;
	     pointer = pointer.next)
            {
            System.out.print(i) ;
            System.out.print(": priority = " + pointer.priority) ;
            System.out.print(": data = '" + pointer.data) ;
            System.out.println("'") ;
            i++ ;
            }
        } // end of method print
    } // end of class PriorityQueue