Project #3 Due Dates: Saturday, October 31 at 11:59 pm…

Question:

Project #3

Due Dates: Saturday, October 31 at 11:59pm

Submit: eLearning

Late Policy: -10 points per hour late

Instructions: This is an individual assignment. Answers should be your own work.

Introduction:

In this project you will apply the heap data structure to a problem.

Description:

The problem is to simulate the operation of a printer that prints the
jobs according to priority.

The priority of a job is determined by two factors:

  user_priority:  an integer from 1 to 3   (1 is highest)
  numpages:       pages to be printed

Job priority = user_priority * numpages

For example, consider two users:

      Joe:  user_priority = 3, numpages=50
      Sue:  user_priority = 1, numpages=10

      Joe's priority = 3x50 = 150
      Sue's priority = 1x10 = 10

      Since Sue has a high user-priority and is only printing 10 pages, she will 
      have priority over Joe.

A job to print should be represented by a class named Printjob. This class
should contain the user’s name, the user’s priority, and number of pages. It
should implement Comparable with compareTo based on these factors.

Derive a subclass of Printjob called OutsidePrintjob. These are just like
Printjobs, but they compute a cost based on 10 cents per page.

Another class called Printer should read an input file and create objects
for each entry. These objects should be added to a priority queue
using the author’s BinaryHeap class (unmodified).

The input file contains each job to print on a separate line, with tabs between
the fields. The fields are name, user priority, pages, and a flag indicating
inside or outside job (I or O).

Once the file is read and the print jobs have been added to the binary heap,
the Printer object should deleteMin each job and print its user’s name, priority,
and pages to the screen. OutsidePrintjobs should also show their cost.

Submit to eLearning:
Printjob.java
OutsidePrintjob.java
Printer.java

Author Binary Heap:
http://users.cis.fiu.edu/~weiss/dsaajava/code/DataStructures/BinaryHeap.java

Answer:

Code:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Printer

{

     public static void main(String[] args)

     {

          try (BufferedReader lbr = new BufferedReader(newFileReader("Jobs.txt")))

          {

              String line;

              BinaryHeap <PrintJob> pq=newBinaryHeap<PrintJob>();

              while ((line = lbr.readLine()) != null)

              {

                   System.out.println(line);

                   String [] var= line.split("\t");

                   pq.add(newPrintJob(Integer.parseInt(var[0]),var[1],Integer.parseInt(var[2])));

              }

              System.out.println("Jobs added");

              while(!pq.isEmpty())

              {

                   System.out.println("Jobs removed");

                   pq.remove().lprint();

              }

          }

          catch (IOException e)

          {

              e.printStackTrace();

          }

     }

}

class PrintJob implements Comparable

{

     private int Priority;

     private String JobName;

     private int No_Of_Pages;

     public PrintJob(int Prio, String Name, int Number )

     {

          setPriority(Prio);

          setName(Name);

          setNo_Of_Pages(Number);

     }

     public void setPriority(int Prio)

     {

          Priority = Prio;

     }

     public void setName(String Name)

     {

          JobName = Name;

     }

     public void setNo_Of_Pages ( int Number)

     {

          No_Of_Pages = Number;

     }

     public String getName()

     {

          return JobName;

     }

     public int getPriority()

     {

          return Priority*No_Of_Pages;

     }

     public int lgetNumberOfPages()

     {

          return No_Of_Pages;

     }

     public void lprint()

     {

          System.out.println("Priority: "+Priority +"\tJob Name:"+JobName+"\tNo Of Pages: "+No_Of_Pages+"\tJobPriority ="+No_Of_Pages*Priority);

     }

     public int compareTo(Object x)

     {

          PrintJob pj=(PrintJob)x;

          if(getPriority()==pj.getPriority())

          return 0;

          else if(getPriority()>pj.getPriority())

          return 1;

          else

          return -1;

     }

}

class BinaryHeap <T extends Comparable> extends PriorityQueue

{

     private static final int lDEFAULT_CAPACITY = 10;

     protected T[] array;

     protected int lsize;

     public BinaryHeap ()

     {

          array = (T[])new Comparable[lDEFAULT_CAPACITY];

          lsize = 0;

     }

     //Adding value to min heap

     public void add(T value)

     {

          // if needed growing array

          if (lsize >= array.length - 1)

          {

              array = this.resize();

          }      

          // placing element at bottom of heap

          lsize++;

          int lindex = lsize;

          array[lindex] = value;

          bubbleUp();

     }

     // Returns true if heap empty otherwise returns false.

     public boolean isEmpty()

     {

          return lsize == 0;

     }

     //Minimum element in heap is removed

     public T peek()

     {

          if (this.isEmpty())

          {

              throw new IllegalStateException();

          }

          return array[1];

     }

     // minimum element in heap is removed and returned.

     public T remove()

     {

          T result = peek();

          array[1] = array[lsize];

          array[lsize] = null;

          lsize--;

          bubbleDown();

          return result;

     }

     //string representation of heap is returned with values in heap structure order.

     public String toString()

     {

          return Arrays.toString(array);

     }

     //Placing element at root to its correct position by maintaining heap property

     protected void bubbleDown()

     {

          int lindex = 1;

         

          // bubbling down

          while (lhasLeftChild(lindex))

          {

              int lsmallerChild = lleftIndex(lindex);

              // bubbling with smaller child

              if (lhasRightChild(lindex)

              &&                                                                          array[lleftIndex(lindex)].compareTo(array[lrightIndex(linde                      x)]) > 0)

              {

                   lsmallerChild = lrightIndex(lindex);

              }

              if (array[lindex].compareTo(array[lsmallerChild])> 0)

              {

                   swap(lindex, lsmallerChild);

              }

              else

              {

                   break;

              }

              // loop counter updation

              lindex = lsmallerChild;

          }      

     }

     // newly inserted element is placed into correct position

     protected void bubbleUp()

     {

          int lindex = this.lsize;

          while (lhasParent(lindex)

          && (parent(lindex).compareTo(array[lindex]) > 0))

          {

             

              // swaping parent & child in case they are out of order

              swap(lindex, parentIndex(lindex));

              lindex = parentIndex(lindex);

          }      

     }

     protected boolean lhasParent(int i)

     {

          return i > 1;

     }

     protected int lleftIndex(int i)

     {

          return i * 2;

     }

     protected int lrightIndex(int i)

     {

          return i * 2 + 1;

     }

     protected boolean lhasLeftChild(int i)

     {

          return lleftIndex(i) <= lsize;

     }

     protected boolean lhasRightChild(int i)

     {

          return lrightIndex(i) <= lsize;

     }

     protected T parent(int i)

     {

          return array[parentIndex(i)];

     }

     protected int parentIndex(int i)

     {

          return i / 2;

     }

     protected T[] resize()

     {

          return Arrays.copyOf(array, array.length * 2);

     }

     protected void swap(int lindex1, int lindex2)

     {

          T tmp = array[lindex1];

          array[lindex1] = array[lindex2];

          array[lindex2] = tmp;      

     }

}

Leave a Comment

Your email address will not be published. Required fields are marked *