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 job priority.

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 textbook'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, user priority, and pages to the screen. OutsidePrintjobs should also show their cost.

Printjob.java OutsidePrintjob.java Printer.java

---

input.txt

Joe 3 50 I Sue 1 40 I Ben 2 25 O Kevin 2 10 I Pam 3 15 O Sam 1 30 I Megan 3 20 I John 2 5 O Jessie 1 10 O David 3 25 I Danielle 1 20 O George 2 11 O Maria 3 3 I

---

// BinaryHeap class // // CONSTRUCTION: with optional capacity (that defaults to 100) // or an array containing initial items // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // Comparable deleteMin( )--> Return and remove smallest item // Comparable findMin( ) --> Return smallest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // ******************ERRORS******************************** // Throws UnderflowException as appropriate /** * Implements a binary heap. * Note that all "matching" is based on the compareTo method. * @author Mark Allen Weiss */ public class BinaryHeap> { /** * Construct the binary heap. */ public BinaryHeap( ) { this( DEFAULT_CAPACITY ); } /** * Construct the binary heap. * @param capacity the capacity of the binary heap. */ public BinaryHeap( int capacity ) { currentSize = 0; array = (AnyType[]) new Comparable[ capacity + 1 ]; } /** * Construct the binary heap given an array of items. */ public BinaryHeap( AnyType [ ] items ) { currentSize = items.length; array = (AnyType[]) new Comparable[ ( currentSize + 2 ) * 11 / 10 ]; int i = 1; for( AnyType item : items ) array[ i++ ] = item; buildHeap( ); } /** * Insert into the priority queue, maintaining heap order. * Duplicates are allowed. * @param x the item to insert. */ public void insert( AnyType x ) { if( currentSize == array.length - 1 ) enlargeArray( array.length * 2 + 1 ); // Percolate up int hole = ++currentSize; for( array[ 0 ] = x; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 ) array[ hole ] = array[ hole / 2 ]; array[ hole ] = x; } private void enlargeArray( int newSize ) { AnyType [] old = array; array = (AnyType []) new Comparable[ newSize ]; for( int i = 0; i < old.length; i++ ) array[ i ] = old[ i ]; } /** * Find the smallest item in the priority queue. * @return the smallest item, or throw an UnderflowException if empty. */ public AnyType findMin( ) { if( isEmpty( ) ) throw new UnderflowException( ); return array[ 1 ]; } /** * Remove the smallest item from the priority queue. * @return the smallest item, or throw an UnderflowException if empty. */ public AnyType deleteMin( ) { if( isEmpty( ) ) throw new UnderflowException( ); AnyType minItem = findMin( ); array[ 1 ] = array[ currentSize-- ]; percolateDown( 1 ); return minItem; } /** * Establish heap order property from an arbitrary * arrangement of items. Runs in linear time. */ private void buildHeap( ) { for( int i = currentSize / 2; i > 0; i-- ) percolateDown( i ); } /** * Test if the priority queue is logically empty. * @return true if empty, false otherwise. */ public boolean isEmpty( ) { return currentSize == 0; } /** * Make the priority queue logically empty. */ public void makeEmpty( ) { currentSize = 0; } private static final int DEFAULT_CAPACITY = 10; private int currentSize; // Number of elements in heap private AnyType [ ] array; // The heap array /** * Internal method to percolate down in the heap. * @param hole the index at which the percolate begins. */ private void percolateDown( int hole ) { int child; AnyType tmp = array[ hole ]; for( ; hole * 2 <= currentSize; hole = child ) { child = hole * 2; if( child != currentSize && array[ child + 1 ].compareTo( array[ child ] ) < 0 ) child++; if( array[ child ].compareTo( tmp ) < 0 ) array[ hole ] = array[ child ]; else break; } array[ hole ] = tmp; } // Test program public static void main( String [ ] args ) { int numItems = 10000; BinaryHeap h = new BinaryHeap<>( ); int i = 37; for( i = 37; i != 0; i = ( i + 37 ) % numItems ) h.insert( i ); for( i = 1; i < numItems; i++ ) if( h.deleteMin( ) != i ) System.out.println( "Oops! " + i ); } }