Build a print scheduler using a priority queue represented with a maximum binary

Question

Build a print scheduler using a priority queue represented with a maximum binary heap as the data structure. Each print request has the following associated fields: ID, user’s login name, request time, priority, file size in bytes, and file handle.

Write a program that supports the following operations:

int add(string login, string time, int priority, int size, int handle): add a new request to a queue; return a sequential ID# if successful, or FULL if the total file size of all pending requests exceeds the maximum spool size of 50MB. The input argument handle is not used in this exercise, so set it to NULL. The ID cycles in the range of 1 - 1024.

int print_next(): return EMPTY if the queue is empty, or return the ID of the pending highest-priority request and delete it from the queue.

int find_next(): return EMPTY if the queue is empty, or return the ID of the pending highest-priority request.

int cancel(string login): delete all the requests made by the login user; return the number of deleted requests if successful, or return NONE if not found.

int cancel(int ID): delete the request with the ID; return 0 if successful, or return NONE if not found.

String status(): return a string containing information about all pending requests' ID, login, creation time, priority, file size, and file handle; return “EMPTY” if there's no pending request. The order of the print requests returned does not matter.

Error codes: -1 for FULL, -2 for EMPTY, -3 for NONE. (If you add more error codes, clearly state them in your program code.)

Explanation / Answer

package priorityQueue;

import java.util.Scanner;
import java.util.logging.FileHandler;

/** class Task **/
class Task
{
int id=0;
String login;
String time;
int priority;
int size;
int handle;

/** Constructor **/
public Task(String login, String time, int priority, int size, int handle)
{
   id = id+1;
this.login = login;
this.time = time;
this.priority = priority;
this.size = size;
this.handle = handle;
}
/** toString() **/
public String toString()
{
return "Login : "+ login +" Time : "+ time+" Priority : "+priority+" size : "+size;
}
  
public int getId(){
   return this.id;
}
}

/** Class PriorityQueue **/
class PriorityQueue
{
private Task[] heap;
private int heapSize, capacity;

/** Constructor **/
public PriorityQueue(int capacity)
{
this.capacity = capacity + 1;
heap = new Task[this.capacity];
heapSize = 0;
}
/** function to clear **/
public void clear()
{
heap = new Task[capacity];
heapSize = 0;
}
/** function to check if empty **/
public boolean isEmpty()
{
return heapSize == 0;
}
/** function to check if full **/
public boolean isFull()
{
return heapSize == capacity - 1;
}
/** function to get Size **/
public int size()
{
return heapSize;
}
/** function to insert task **/
public void insert(String login, String time, int priority, int size, int handle)
{
Task newJob = new Task(login, time, priority, size, 0);
  
heap[++heapSize] = newJob;
int pos = heapSize;
while (pos != 1 && newJob.priority > heap[pos/2].priority)
{
heap[pos] = heap[pos/2];
pos /=2;
}
heap[pos] = newJob;
}
/** function to remove task **/
public Task remove()
{
int parent, child;
Task item, temp;
if (isEmpty() )
{
System.out.println("Heap is empty");
return null;
}

item = heap[1];
temp = heap[heapSize--];

parent = 1;
child = 2;
while (child <= heapSize)
{
if (child < heapSize && heap[child].priority < heap[child + 1].priority)
child++;
if (temp.priority >= heap[child].priority)
break;

heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;

return item;
}
public int findnext(){
   Task temp = remove();
   //System.out.println(temp.toString());
   insert(temp.login,temp.time,temp.priority,temp.size,temp.handle);
   return temp.id;
}
  
public int cancelJob(int jobId){
   Task temp = remove();
   //System.out.println(temp.toString());
   if(temp.id == jobId){
       return temp.id;
   }
   insert(temp.login,temp.time,temp.priority,temp.size,temp.handle);
   return 0;
}
}

/** Class PriorityQueueTest **/
public class PriorityQueueTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Priority Queue Test ");   

System.out.println("Enter size of priority queue ");
PriorityQueue pq = new PriorityQueue(scan.nextInt() );

char ch;
/* Perform Priority Queue operations */
do
{
System.out.println(" Priority Queue Operations ");
System.out.println("1. insert");
System.out.println("2. remove");
System.out.println("3. find Next");
System.out.println("4. Cancel job");
System.out.println("5. check status");

int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter Name:");
String name = scan.next();
System.out.println("Enter request time:");
String time = scan.next();
System.out.println("Enter priority: ");
int priority = scan.nextInt();
System.out.println("enter file size: ");
int size = scan.nextInt();
pq.insert(name,time,priority,size,0);   
break;
case 2 :
System.out.println(" Job removed "+ pq.remove());
break;
case 3 :
System.out.println(" Next Job : "+ pq.findnext());
break;
case 4 :
   System.out.println("Enter Job Id:");
   int result = pq.cancelJob(scan.nextInt());
   if(result == 0){
       System.out.println("Job not found");
   }
System.out.println(" "+result+"Job Cancelled ");
break;   
case 5 :
System.out.println(" Full Status : "+ pq.isFull() );
break;
default :
System.out.println("Wrong Entry ");
break;   
}

System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}

Priority Queue Test

Enter size of priority queue
3

Priority Queue Operations

1. insert
2. remove
3. find Next
4. Cancel job
5. check status
1
Enter Name:
a
Enter request time:
2
Enter priority:
2
enter file size:
34

Do you want to continue (Type y or n)

y

Priority Queue Operations

1. insert
2. remove
3. find Next
4. Cancel job
5. check status
1
Enter Name:
b
Enter request time:
3
Enter priority:
5
enter file size:
45

Do you want to continue (Type y or n)

y

Priority Queue Operations

1. insert
2. remove
3. find Next
4. Cancel job
5. check status
3

Next Job : 1

Do you want to continue (Type y or n)

y

Priority Queue Operations

1. insert
2. remove
3. find Next
4. Cancel job
5. check status
5

Full Status : false

Do you want to continue (Type y or n)

2

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.