Lab: Applications of Data Structures

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 may assume that the input is valid and that methods are called in a reasonable order.

You should work in teams of 2-3 on this lab (but submit separately). Some of these problems will require you to debate the best data structure to use. Sometimes, two or more data structures can be used, but you'll need to think about which one is better. You may need to use multiple data structures for some problems.

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, such as PriorityQueue):

Interface	Hash Table	Resizable Array	Balanced Tree	Linked List	Hash Table + Linked List	Min-Heap
`Set`	`HashSet`		`TreeSet`		`LinkedHashSet`
`List`		`ArrayList`		`LinkedList`
`Queue`		`ArrayDeque`		`LinkedList`		`PriorityQueue`
`Deque`		`ArrayDeque`		`LinkedList`
`Map`	`HashMap`		`TreeMap`		`LinkedHashMap`

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

Don't forget, time complexity is not the only thing that matters! An algorithm that is O(1) but always takes 100 seconds to run may not always be as good as an O(n) algorithm that takes 0.5 seconds per item! If you are failing performance tests, you may want to try a different data type.

Starter Code

Start by downloading this file, which contains all the classes you will need:

Applications.java

Each of the applications below is implemented as a separate inner class in the file. You will need to implement the methods in each of these classes.

Unit tests for each application are provided in the sections below.

If you prefer, you can instead download the following zip file, which contains a fully configured VS Code folder containing all files for the lab:

cs240_application_lab.zip

1. Duplicate Tracker

Tests for this application are in the file:

DuplicateTrackerTest.java

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.

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.

In addition, the getDuplicates method should return a modifiable copy of the duplicates. This means that if you modify the returned list, it should not affect the internal state of the DuplicateTracker object.

2. Job Sequencer

Tests for this application are in the file:

JobSequencerTest.java

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"

3. Event Sequencer

Tests for this application are in the file:

EventSequencerTest.java

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 add 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"

Hint: It may be helpful to implement an inner class that represents an event! This class should implement the Comparable interface to compare against other events. For example:

private class Event implements Comparable<Event> {
    private int time;
    private String name;

    ...

    @Override
    public int compareTo(Event other) {
        return this.time - other.time;
    }
}

4. Triage

Tests for this application are in the file:

TriageTrackerTest.java

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.

Note: Larger numbers are considered higher priority!

The nextPatient method should always remove and return the patient with the highest priority. In the event of tied priorities, patients should be processed in the order they were added. You may assume that each patient has a unique ID.

The removePatient method makes it possible to remove a specific patient from the collection even if they have not been served. It must do so efficiently, in a way that does not require iterating through the entire collection.

    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"

5. Neighbors

Tests for this application are in the file:

NeighborCounterTest.java

Complete the methods in NeighborCounter so that all operations are as efficient as possible. The purpose of this class is to maintain a collection of two-dimensional points and to determine how many points are within a particular distance from a query point. Duplicate points at the same location are not permitted.

    NeighborCounter nc = new NeighborCounter();

    // Add four points arranged in a square pattern:
    nc.addPoint(0.0, 0.0);
    nc.addPoint(0.0, 1.0);
    nc.addPoint(1.0, 0.0);
    nc.addPoint(1.0, 1.0);

    // All four points are within 1.0 of (.5, .5)...
    System.out.println(nc.numNeighbors(.5, .5, 1.0));  // Prints 4

    // No points are within .1 of (.5, .5)...
    System.out.println(nc.numNeighbors(.5, .5, 0.1));  // Prints 0

    // Only one point, (0, 0), is within .5 of (.1, .1)...
    System.out.println(nc.numNeighbors(.1, .1, .5));   // Prints 1

Submission

Submit each file containing your solution to Gradescope.