9 Replies - 11975 Views - Last Post: 08 March 2010 - 04:22 PM Rate Topic: -----

#1 Guest_Andre*


Reputation:

Priority Queues and linked lists

Posted 07 March 2010 - 12:33 PM

Can somebody pls help me...i have been given 2 classes, namely CellSim and ListQueue...CellSim simulates the behaviour of a cell phone base station. It allows the user to specify the maximum number of connections (or "lines") that the base station can support at any time, the average time between customers making calls and the average length (or duration) of a call. It also asks the user for the number of calls to be simulated. It then simulates this number of calls, reporting at the end of the run on the number of calls that were dropped because there were insufficient connections available, and the related "grade of service" (i.e. the fraction of calls dropped). ListQueue is just a priority queue class that has been given....


basically what i need to do is firstly:
to modify the existing ListQueue class to implement a priority queue. This will involve changing the QueueNode class to store a priority value (an integer) with each item of data. You will need to change the add method to handle the priority values. You will also need to provide a method to retrieve the priority value of the item at the head of the queue. Note that the class you develop will no longer conform to the Queue interface, but should rather have the following methods:

public void add (T item, int pri);
// Add new item to a queue with given priority

public T remove ();
// Remove item from head of queue

public T head ();
// Return a copy of item at head of queue

public int getPriority ();
// Return priority of item at head of queue

public boolean isEmpty ();
// Return TRUE if no items in queue

In this context, lower priority values are associated with larger integer values, so, for example, an item with priority value of 1 has a higher priority than an item with a value of 5, and should come before it in the queue.

The ListQueue class is as follows...if any1 can help ill greatly appreciate it, pls also explain what the code is doing.

public class ListQueue<T> implements Queue<T>
  { private class QueueNode
      { public T data;
        public QueueNode next;
      } // inner class QueueNode

    /** Reference to the head (front) of the queue.
      */
    private QueueNode hd;
    /** Reference to the tail (back) of the queue.
      */
    private QueueNode tl;

    /** Create an empty queue.
      * <BR><I>Postcondition:</I> The queue is empty.
      */
    public ListQueue ()
      { hd = tl = null; }

    /** Add an item to the tail of a queue.
      * <BR><I>Postcondition:</I> The queue is not empty.
      * @param item The item to be added to the queue.
      */
    public void add (T item)
      { QueueNode newNode = new QueueNode();
        newNode.data = item;
        newNode.next = null;
        if (tl != null)
          tl.next = newNode;
        tl = newNode;
        if (hd == null) // First item in queue
          hd = tl;
      } // add

    /** Remove an item from the head of a queue.
      * <BR><I>Precondition:</I> The queue is not empty.
      * <BR><I>Postcondition:</I> The item at the head of the queue is removed and returned.
      * @return The item from the head of the queue.
      * @throws Assertionerror If the queue is empty.
      */
    public T remove ()
      { assert hd != null;
        T tmpData = hd.data;
        hd = hd.next;
        if (hd == null) // Was last element
          tl = null;
        return tmpData;
      } // remove

    /** Return a copy of the item at the head of a queue.
      * <BR><I>Precondition:</I> The queue is not empty.
      * @return The value of the item at the head of the queue.
      * @throws Assertionerror If the queue is empty.
      */
    public T head ()
      { assert hd != null;
        return hd.data;
      } // head

    /** Tell if a queue contains any items.
      * @return <CODE>true</CODE> if there are no items in the queue, otherwise <CODE>false</CODE>.
      */
    public boolean isEmpty ()
      { return hd == null;
      } // isEmpty

  } // class ListQueue


Is This A Good Question/Topic? 0

Replies To: Priority Queues and linked lists

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,262
  • Joined: 27-December 08

Re: Priority Queues and linked lists

Posted 07 March 2010 - 12:50 PM

I'll give you a hint- It simply comes down to inserting the new element at the correct position (if you've worked with Insertion sort, this will be very familiar). As for the explanations, the code you were given seems to be very well commented. Is there a specific part you don't understand?

If you need any more help, feel free to post, but remember to show your good faith efforts at solving your problems.
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Andre*


Reputation:

Re: Priority Queues and linked lists

Posted 07 March 2010 - 01:13 PM

View Postmacosxnerd101, on 07 March 2010 - 11:50 AM, said:

I'll give you a hint- It simply comes down to inserting the new element at the correct position (if you've worked with Insertion sort, this will be very familiar). As for the explanations, the code you were given seems to be very well commented. Is there a specific part you don't understand?

If you need any more help, feel free to post, but remember to show your good faith efforts at solving your problems.


ok so at the moment the add method looks like this:

public void add (T item, int pri)
      { QueueNode newNode = new QueueNode();
        newNode.data = item;
        pri = newNode;
        newNode.next = null;
        if (tl != null)
          tl.next = newNode;
        tl = newNode;
        if (hd == null) // First item in queue
          hd = tl;
} // add



is this right?? im just really new with linked lists and iv never used a priority queue so i dont really know what else to change

This post has been edited by Dogstopper: 07 March 2010 - 01:14 PM
Reason for edit:: don't forget the tags thanks!

Was This Post Helpful? 0

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,262
  • Joined: 27-December 08

Re: Priority Queues and linked lists

Posted 07 March 2010 - 01:18 PM

If you're uncomfortable with Linked Lists, you should check out my Linked List Tutorial.

As for your add() method, it is correct for a regular Queue. However, for a Priority Queue, you want to insert the elements based on Priority. So your Node class (as your instructions said) should have a priority attribute. Since we're not just adding elements to the end of the Queue anymore, but possibly to the middle, you cannot simply append to the tail node. Instead, you'll have to start at the head and work forward. This is similar to the add(index, elem) method I talk about in my tutorial.

Also, you may want to read up on Insertion Sort as this is the exact method it takes to sort elements. Hint- think about comparing priorities.

This post has been edited by macosxnerd101: 07 March 2010 - 01:19 PM

Was This Post Helpful? 0
  • +
  • -

#5 Guest_Andre*


Reputation:

Re: Priority Queues and linked lists

Posted 07 March 2010 - 03:13 PM

View Postmacosxnerd101, on 07 March 2010 - 12:18 PM, said:

If you're uncomfortable with Linked Lists, you should check out my Linked List Tutorial.

As for your add() method, it is correct for a regular Queue. However, for a Priority Queue, you want to insert the elements based on Priority. So your Node class (as your instructions said) should have a priority attribute. Since we're not just adding elements to the end of the Queue anymore, but possibly to the middle, you cannot simply append to the tail node. Instead, you'll have to start at the head and work forward. This is similar to the add(index, elem) method I talk about in my tutorial.

Also, you may want to read up on Insertion Sort as this is the exact method it takes to sort elements. Hint- think about comparing priorities.


Thank you sooooo much for that tutorial!! really helped...so iv changed the add method to the following:
public void add (T item, int pri)
{
temp = hd;
for(int i = 0; i < pri; i++)
temp = temp.next;
QueueNode newNode = new QueueNode();
newNode.data = item;
newNode.next = temp.next;
temp.next = newNode;
counter++;
}

However im now getting errors in the cellSim class:
import java.util.PriorityQueue;
import java.util.Scanner;

public class CellSim
  { private enum EventType { CALL_START, CALL_END };  // Enumeration for event types

    private class CallEvent // Event types to be queued
      { public int callNumber; // Index value
        public EventType event; // CALL_START or CALL_END
      } // inner class CallEvent

    private int poisson (double av)
    //=============================
    // Calculate poisson distribution value for given average
      { return (int)(-Math.log((Math.random() * 1000.0 + 1.0)/1000.0) * av + 0.5);
      } // poisson

    private double lossPrediction (int numLines, double demand)
    //=========================================================
    // Theoretical prediction of grade of service given the number of connections
    // available and the demand (i.e. average call length/avg call interval)
      { if (numLines == 0)
          return 1.0;
        else
          { double w = lossPrediction(numLines-1, demand);
            return (demand * w) / (numLines + demand * w);
          }
      } // lossPrediction


    public void doSimulation ()
    //=========================
      { PriorityQueue<CallEvent> q = new PriorityQueue<CallEvent>(); // Event queue
        CallEvent nextEvent; // The next event (call started or ended)
        int time = 0, // Current simulated time
            numLines = 0, // Number of connections or "lines" available
            numMade = 0;  // Total number of calls made
        double avgCallLength = 0.0,  // Average length of call in seconds
               avgCallArrival = 0.0; // Average time between calls

        // First get the parameters for this simulation
        Scanner in = new Scanner(System.in);
        System.out.print("Enter the number of connections/lines available: ");
        numLines = in.nextInt();

        System.out.print("Enter the number of calls to be made: ");
        numMade = in.nextInt();

        System.out.print("Enter the average call length: ");
        avgCallLength = in.nextDouble();

        System.out.print("Enter the average interval between calls: ");
        avgCallArrival = in.nextDouble();

        // Queue the start of all the calls
        for (int call = 0; call < numMade; call++) // Run for given number of calls
          { time += poisson(avgCallArrival);
            nextEvent = new CallEvent();
            nextEvent.callNumber = call;
            nextEvent.event = EventType.CALL_START;
            // Now add the event to the queue, using the time as the priority
            q.add(nextEvent, time);
          }

        // Now run the actual simulation
        int numUsed = 0, // Number of connections in use
            numDropped = 0; // Number of calls dropped

        while (! q.isEmpty()) // Handle events
          { time = q.getPriority();
            nextEvent = q.remove();
            System.out.print("Time: " + time + "  call: " + nextEvent.callNumber + "  ");

            // Handle nextEvent
            if (nextEvent.event == EventType.CALL_START)
              { if (numUsed < numLines) // A connection/line is available
                  { numUsed++;
                    System.out.println("call made. " + numUsed + " connections/lines used.");
                    // Schedule the end of this call
                    nextEvent.event = EventType.CALL_END;
                    q.add(nextEvent, time + poisson(avgCallLength));
                  }
                else // No connection/line is available
                  { numDropped++;
                    System.out.println("call dropped.");
                  }
              }
            else // Call ended
              { numUsed--;
                System.out.println("call ended. " + numUsed + " connections/lines used.");
              }
          } // while

        // Now report on the statistics
        System.out.println("\nStatistical Report\n~~~~~~~~~~~~~~~~~~");
        System.out.println(numMade + " calls were made using " + numLines + " connections/lines.");
        System.out.println(numDropped + " calls could not be handled.");
        System.out.println("The service grade is: " + (double)numDropped/(double)numMade);
        System.out.println("The theoretical predicted service grade is: "
                           + lossPrediction(numLines, avgCallLength/avgCallArrival));
      } // doSimulation

    public static void main (String args[])
    //=====================================
      { CellSim sim = new CellSim();
        sim.doSimulation();
      } // main

  } // class CellSim



its giving me errors by the q.add(nextEvent, time);
time = q.getPriority();
q.add(nextEvent, time + poisson(avgCallLength));


thank you for all the help
Was This Post Helpful? 0

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,262
  • Joined: 27-December 08

Re: Priority Queues and linked lists

Posted 07 March 2010 - 03:23 PM

Wait, are you supposed to be designing your own Priority Queue or using the java.util.PriorityQueue?
Was This Post Helpful? 0
  • +
  • -

#7 Guest_Andre*


Reputation:

Re: Priority Queues and linked lists

Posted 08 March 2010 - 04:31 AM

View Postmacosxnerd101, on 07 March 2010 - 02:23 PM, said:

Wait, are you supposed to be designing your own Priority Queue or using the java.util.PriorityQueue?


well we supposed to implement a priority queue so i think we are meant to use the import...Does the java.util.PriorityQueue import make it more difficult to solve this question??
Was This Post Helpful? 0

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,262
  • Joined: 27-December 08

Re: Priority Queues and linked lists

Posted 08 March 2010 - 09:02 AM

Well, if you are supposed to design your own, then you shouldn't be importing the java.util.PriorityQueue. However, if your job is to make a program work using some PriorityQueue, the one in the java.util package will make your life easier.
Was This Post Helpful? 0
  • +
  • -

#9 Araujo2nd  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 11-October 07

Re: Priority Queues and linked lists

Posted 08 March 2010 - 01:29 PM

hey man its me again....ok so i am mean to import the java.util.priorityQueue and implement it into the listQueue... so the listQueue class should now start like: public class ListQueue<T> implements PriorityQueue<T>

however as soon as i changed it to implement PriorityQueue it gives me an error saying "interface expected here" pls help
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,262
  • Joined: 27-December 08

Re: Priority Queues and linked lists

Posted 08 March 2010 - 04:22 PM

PriorityQueue is a class, not an interface. So you can extend PriorityQueue, but not implement it like an interface.

Take a look at the API for more information on PriorityQueue: http://java.sun.com/...orityQueue.html
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1