Programming Assignment #3 100 points Due Date/Time Your program will be due on: • edoras server Monday, April 12th at 11:59 p.m. • No late assignments accepted. Early submissions receive extra credit....

This program is in java


Programming Assignment #3 100 points Due Date/Time Your program will be due on: • edoras server Monday, April 12th at 11:59 p.m. • No late assignments accepted. Early submissions receive extra credit. The Assignment For this assignment, you will write an implementation of a Priority Queue. Using the PriorityQueue.java interface, you will write a binary heap implementation. Your heap implementation must implement the interface exactly and efficiently. The implementation must have two constructors as in the first assignment—use the DEFAULT_MAX_CAPACITY in the interface for one constructor and take a size parameter for the second. Your project will consist of the following files. You must use exactly these filenames. • PriorityQueue.java The ADT interface. • BinaryHeapPriorityQueue.java The binary heap implementation. Additional Details: • Each method must be as efficient as possible. That is, a O(n) is unacceptable if the method could be written with O(log n) complexity. Both insert and remove must be O(log n). • Your binary heap must be stable—able to determine the oldest entry among those with identical priority. • Your iterator must be fail-fast. • You may not make any modifications to the PriorityQueue interface provided. I will grade your project with my copy of this file. • All relevant requirements from earlier assignments apply here. The PriorityQueue interface /* Your name Your cssc account number */ /* The PriorityQueue ADT may store objects in any order. However, removal of objects from the PQ must follow specific criteria. The object of highest priority that has been in the PQ longest must be the object returned by the remove() method. FIFO return order must be preserved for objects of identical priority. Ranking of objects by priority is determined by the Comparable interface. All objects inserted into the PQ must implement this interface. */ package data_structures; import java.util.Iterator; public interface PriorityQueue> extends Iterable { public static final int DEFAULT_MAX_CAPACITY = 1000; // Inserts a new object into the priority queue. Returns true if // the insertion is successful. If the PQ is full, the insertion // is aborted, and the method returns false. public boolean insert(E object); // Removes the object of highest priority that has been in the // PQ the longest, and returns it. Returns null if the PQ is empty. public E remove(); // Deletes all instances of the parameter obj from the PQ if found, and // returns true. Returns false if no match to the parameter obj is found. public boolean delete(E obj); // Returns the object of highest priority that has been in the // PQ the longest, but does NOT remove it. // Returns null if the PQ is empty. public E peek(); // Returns true if the priority queue contains the specified element // false otherwise. public boolean contains(E obj); // Returns the number of objects currently in the PQ. public int size(); // Returns the PQ to an empty state. public void clear(); // Returns true if the PQ is empty, otherwise false public boolean isEmpty(); // Returns true if the PQ is full, otherwise false. List based // implementations should always return false. public boolean isFull(); // Returns an iterator of the objects in the PQ, in no particular // order. public Iterator iterator(); } Turning in your project: To submit your project, you must copy your Java source code files into your handin/p3 subdirectory. You will submit a printout of this file in class on the due date.[IMPORTANT NOTE: Do not recreate the data_structures subdirectory in the handin subdirectory--just copy your file into the handin/p3 directory itself.] Be sure to check the Program Submission Guidelines below. Late programs are not accepted. Programs turned in early will be eligible for additional points. Here is an example of the directory structure for this program [cssc0000@edoras ~]$ ls handin p1 p2 p3 [cssc0000@edoras ~]$ ls handin/p3 BinaryHeapPriorityQueue.java Early Programs Early programs will be accepted with a bonus each day for up to two days before the due date. The submission date will be determined by the timestamp of your file on edoras. For example, this program is due Monday, April 12th at 11:59 p.m. If your program timestamp is any time Sunday, April 11th, your will receive a 8 point bonus, and if your program timestamp is any time Saturday, April 10th (or earlier) you will receive a 15 point bonus. Cheating Policy There is a zero tolerance policy on cheating in this course. You are expected to complete all programming assignments on your own. Collaboration with other students in the course is not permitted. You may discuss ideas or solutions in general terms with other students, but you must not exchange code. During the grading process I will examine your code carefully. Anyone caught cheating on a programming assignment (or on an exam) will receive an "F" in the course, and a referral to Judicial Procedures. Program Submission Guidelines Note that your program will NOT compile in your handin subdirectory. If it does, then you have done something wrong and you will receive a zero for the assignment. This directory is only a place to turn in your files, not a suitable location for project development. Do not create any package folders within the handin/ directory tree. To be collected for grading, your program file must have the correct name and be in the correct location. If the grading script fails to find your program file, you will not get any credit for the assignment. Programs must compile with no errors. Programs that fail to compile will receive very little or no credit. Programs will be compiled on edoras using the Sun JDK 1.8 (or JDK 8) compiler. The timestamp on your file will be used to determine the date and time when your project was submitted. The act of copying your program files into your handin/ subdirectory constitutes submission of your program for grading. You must not place incomplete programs in your handin/ subdirectory. At any time after the due date, programs may be collected from this handin/p3/ subdirectory. Once collection has occurred, you may not resubmit. IMPORTANT: Resubmission of projects is not allowed once your program has been collected for grading; no further changes or resubmissions will be permitted. On rare exceptions (as determined by me) where resubmission is allowed due to packaging or other trivial errors on your part, the minimum grade penalty will be 15%. Also, you must not open or edit your program file after the due date, as this will change the timestamp on your file, making it late. You may print your files or view them without modifying the timestamp. Use the UNIX command 'view FILENAME' to run the read-only version of the text editor vi. Checking that everything works on edoras Use a sandbox directory, like this: ~/sandbox/p3/ SomeBinHeapTester.java ~/sandbox/p3/data_structures PriorityQueue.java BinaryHeapPriorityQueue.java Compile from ~/sandbox/p3 directory: [cssc0000@edoras p3]$ javac SomeBinHeapTester.java [cssc0000@edoras p3]$ java SomeBinHeapTester When ready, copy your three files into the handin/p3 folder. To copy using UNIX commands: From ~/sandbox/p3 directory, first create the destination folder if you haven’t already: mkdir ~/handin/p3 Now copy the data structure file from ~/sandbox/p3 directory to ~/handin/p3: cp data_structures/BinaryHeapPriorityQueue.java ~/handin/p3/ Verify the correct file is in ~/handin/p3: ls ~/handin/p3/ prog3 details Priority queue interface /* The PriorityQueue ADT may store objects in any order. However, removal of objects from the PQ must follow specific criteria. The object of highest priority that has been in the PQ longest must be the object returned by the remove() method. FIFO return order must be preserved for objects of identical priority. Ranking of objects by priority is determined by the Comparable interface. All objects inserted into the PQ must implement this interface. */ package data_structures; import java.util.Iterator; public interface PriorityQueue> extends Iterable { public static final int DEFAULT_MAX_CAPACITY = 1000; // Inserts a new object into the priority queue. Returns true if // the insertion is successful. If the PQ is full, the insertion // is aborted, and the method returns false. public boolean insert(E object); // Removes the object of highest priority that has been in the // PQ the longest, and returns it. Returns null if the PQ is empty. public E remove(); // Deletes all instances of the parameter obj from the PQ if found, and // returns true. Returns false if no match to the parameter obj is found. public boolean delete(E obj); // Returns the object of highest priority that has been in the // PQ the longest, but does NOT remove it. // Returns null if the PQ is empty. public E peek(); // Returns true if the priority queue contains the specified element // false otherwise. public boolean contains(E obj); // Returns the number of objects currently in the PQ. public int size(); // Returns the PQ to an empty state. public void clear(); // Returns true if the PQ is empty, otherwise false public boolean isEmpty(); // Returns true if the PQ is full, otherwise false. List based // implementations should always return false. public boolean isFull(); // Returns an iterator of the objects in the PQ, in no particular // order. public Iterator iterator(); }