Applications Lab

The goal of this lab is to apply some of the techniques and structures we’ve studied this semester. You should read the problem descriptions, determine appropriate collection types, and implement efficient solutions. You should work in groups on this lab.

DO NOT RE-INVENT THE WHEEL! None of these problems require custom data structures; they can all be implemented efficiently using existing data structures from the Java Collections Framework. These include the following (among others):

(Table reproduced from https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/doc-files/coll-overview.html)

Another option that does not appear in the table is the PriorityQueue class.

Setup

Since we need to be able to compare timings between teams, testing must be performed on the lab computers. Complete the following steps to set up a VS Code workspace that will contain the starter code and test files.

Log in as student, open a terminal, then enter the following commands:

wget --no-parent https://w3.cs.jmu.edu/spragunr/CS240/labs/application/CS240_App_Lab.zip
unzip CS240_App_Lab.zip
code ./CS240_App_Lab --extensions-dir /home/student/CS240_App_Lab/extensions/

Note that if you are logged in under your own eid, you’ll need to modify the third command to refer to your own home directory. It would probably be something like /cs/home/stu/YOUREID/CS240_App_Lab/extensions/.

Q1 – Duplicate Tracker

Complete the methods of the DuplicateTracker class so that all operations are as efficient as possible. The purpose of this class is to process a sequence of user IDs such that duplicate IDs are identified and may be efficiently retrieved as a sorted List. You should assume that both the “add” and the “get” methods may be called arbitrarily many times and in any order: efficiency matters for both.

Be careful! Returning a reference to a mutable instance variable is generally not a good idea. The provided tests will check to make sure that modifying the returned list doesn’t change the state of the DuplicateTracker object.

Here is a code snippet that illustrates the desired functionality:

    tracker.addID(5);
    tracker.addID(2);
    tracker.addID(1);
    tracker.addID(2);
    tracker.addID(5);
    tracker.addID(5);
    
    System.out.println(tracker.getDuplicates()); // Prints "[2, 5]"
    
    tracker.addID(1);
    
    System.out.println(tracker.getDuplicates()); // Prints "[1, 2, 5]"

You can test your implementation by executing the JUnit tests. These will run some tests for correctness as well as timing tests. Your goal is to pass all correctness tests with an overall execution time that is as small as possible.

Q2 – Job Sequencer

Complete the methods of the JobSequencer class so that all operations are as efficient as possible. The purpose of this class is to process jobs of different types in the order that they are added to the system. Because there are a limited number of job handlers and they are specialized for a particular job type, you must make sure that the “nextJob” methods only return jobs of the requested type. You must also ensure that jobs of a particular type are processed in the order in which they arrived. You should assume that both the “addJob” and the “nextJob” methods may be called arbitrarily many times and in any order: efficiency matters for both.

Here is a code snippet that illustrates the desired functionality:

    JobSequencer sequencer = new JobSequencer();
    
    sequencer.addJob("A", 101);
    sequencer.addJob("B", 105);
    sequencer.addJob("A", 93);
    sequencer.addJob("B", 202);
    
    System.out.println(sequencer.nextJob("A")); // Prints "101"
    System.out.println(sequencer.nextJob("B")); // Prints "105"
    System.out.println(sequencer.nextJob("B")); // Prints "202"
    System.out.println(sequencer.nextJob("A")); // Prints "93"

Q3 – Event Sequencer

Complete the methods of the EventSequencer class so that all operations are as efficient as possible. The purpose of this class is to store events that are tagged with an integer time stamp and then to return those events in strict chronological order: once an event with a particular time stamp has been retrieved, it should not be possible to retrieve an event with an equal or earlier time stamp, even if this means that some events are discarded. You should assume that both the “add” and the “get” methods may be called arbitrarily many times and in any order: efficiency matters for both.

    EventSequencer sequencer = new EventSequencer();
    
    sequencer.addEvent(0, "A"); // Event "A" at time 0.
    sequencer.addEvent(4, "C");
    sequencer.addEvent(1, "B");
   
    System.out.println(sequencer.nextEvent()); // Prints "A"
    System.out.println(sequencer.nextEvent()); // Prints "B"
    
    sequencer.addEvent(1, "e"); 
    sequencer.addEvent(3, "f");
    sequencer.addEvent(5, "g");
    
    System.out.println(sequencer.nextEvent()); // Prints "f"
    System.out.println(sequencer.nextEvent()); // Prints "C"
    System.out.println(sequencer.nextEvent()); // Prints "g"

Q4 – Triage

Complete the methods in TriageTracker so that all operations are as efficient as possible. The purpose of this class is to prioritize patients as they seek health care. Each patient is entered into the system along with an integer priority value that quantifies the urgency of their medical condition. The nextPatient method should always remove and return the patient with the highest priority. In event of tied priorities, patients should be processed in the order they were added. The removePatient method makes it possible to remove a patient from the collection even if he or she has not been served.

    TriageTracker triage = new TriageTracker();
    
    triage.addPatient("01-A", 10); // Patient "01-A" has priority 10.
    triage.addPatient("02-A", 10);
    triage.addPatient("03-A", 1);
    triage.addPatient("04-A", 1);
    triage.addPatient("05-A", 10);
    triage.addPatient("06-A", 5000);
    
    triage.removePatient("02-A"); // Patient "02-A" got tired of waiting.
    
    System.out.println(triage.nextPatient()); // "06-A" (Highest priority)
    System.out.println(triage.nextPatient()); // "01-A" (First 10 priority)
    System.out.println(triage.nextPatient()); // "05-A" ("02-A" was removed!)
    System.out.println(triage.nextPatient()); // "03-A"
    System.out.println(triage.nextPatient()); // "04-A"