3. Urgency Queue v2026.fa

Notice

This document contains the description for the Urgency Queue project intended for students in the Fall 2026 CSCI 1302 classes at the University of Georgia.

3.1. Project Deadlines

This Urgency Queue project is broken up into three parts, and each part has its own deadline. The deadlines for each part are summarized in the deadline table, and instructions are provided in the Project Checklist section later in this document.

Urgency Queue Deadlines

Part	Due Date
1	Monday, November 2nd @ 11:55 PM
2	Sunday, November 8th @ 11:55 PM
3	Thursday, November 12th @ 11:55 PM

To earn full points, you are required to submit all three parts. If you want extra credit, then complete and submit the first and / or second parts before their deadlines, as explained in the drop-down below.

Submission-Based (SB) Extra Credit

Students who perform their final submission for Part 1 and / or Part 2 of the project via the specific submit1302 command mentioned for that part before its deadline stated in the deadline table will automatically receive +5 points of Submission-Based (SB) extra credit for that part. This assumes the submission also earns other credit since extra credit is extra and never intended to be the only credit earned.

If a student submits each part of the project correctly and on time, then the highest grade they can earn overall is 110 instead of 100.

Late Penalties

Late penalties do not start applying until after the final date/time listed in the deadline table.

3.2. Project Preface

This third CSCI 1302 project for Fall 2026 is designed to help you apply and extend your prerequisite Java programming knowledge with new concepts from CSCI 1302 in a Unix development environment (i.e., Odin).

Motivation

This project will require you to apply several advanced concepts covered in CSCI 1302, including generic types and type bounds, functional interfaces, lambda expressions, exceptions, named packages, and Java development in a Unix environment. It will also require you to design and implement an object-oriented hierarchy utilizing interfaces, abstract classes, inheritance, and polymorphism to maximize code reuse. If you have actively engaged with the CSCI 1302 course content offered so far this semester, then you should be able to comfortably, but not necessarily quickly, complete those aspects of the project by applying what you have practiced and learned from your content engagement.

Finally, this project may require you to do things that you have never been given explicit directions or instructions for — this is just a part of software development. In such cases, you may need to do some research to help you plan your solution. That being said, we have carefully prepared this project description document so that it answers the majority of your questions. If not, then please do not hesitate to ask a question on the course Piazza or during office hours.

Academic Honesty

All students at the University of Georgia explicitly agree to abide by the UGA student honor code when they sign the application for their admission to the University. Additionally, all students enrolled in a CSCI 1302 course section in Fall 2026 are subject to the Academic Honesty policy included in the Fall 2026 CSCI 1302 course syllabus. Furthermore, anyone with access to this project description document is expected to respect the copyright and licensing terms provided or linked to at the bottom of this document and the starter code.

With academic honesty in mind, we ask all Fall 2026 CSCI 1302 students not to fork the project repository on GitHub. Doing so may make your copy of the project publicly visible, and that can violate several of the policies described earlier. Instead of forking the repository, please follow the instructions provided later in this document to acquire a copy of the starter code.

Course-Specific Learning Outcomes

If you work on and complete this project, then you will gain exposure and practice with the following learning outcomes:

#	Exposure	Description
LO1.c	⭐⭐	Create and modify text files and source code using a powerful terminal-based text editor such as Emacs or Vi.
LO1.d	⭐⭐	Use shell commands to compile new and existing software solutions that are organized into multi-level packages.
LO2.a	⭐⭐	Identify redundancy in a set of classes and interfaces, then refactor using inheritance and polymorphism.
LO2.b	⭐⭐	Define, throw, and propagate exceptions appropriately in a software solution.
LO2.d	⭐⭐	Implement, design, and use generic classes, interfaces, and methods with type bounds.
LO2.e	⭐⭐	Utilize functional interfaces and lambda expressions to pass behavior as arguments.
LO3.a	⭐⭐	Create and update source code that adheres to established style guidelines.
LO3.b	⭐⭐	Create class, interface, method, and inline documentation that satisfies a set of requirements.
LO4.c	⭐⭐	Design, create and use inheritance relationships in a software solution.
LO7.c	⭐⭐	Use common abstract data types and structures, including queues and linked lists, in solving typical problems.

Project Updates

If your instructor updates the project requirements or starter code before the project is due, then this section will be updated to include a summary of those updates and, if needed, instructions that describe how to update your working copy of the project with the latest versions of any changed files.

3.3. Project Description

In this project, you are tasked with writing and testing the code for two classes that each implement, in their own unique way, the Abstract Data Type (ADT) described by the generic UrgencyQueue<ItemType> interface that is declared in cs1302-urgency-queue.jar and documented in its API documentation.

Required Reading

Make sure that you have completed the readings listed below prior to starting this project:

• Interfaces Tutorial

• ADTs and Lists Tutorial

• Generics Tutorial

• Exceptions Tutorial

• API Documentation for the Starter Code

Introduction to Urgency Queue Objects

Package Conventions for Provided Code

Several of the UML diagrams in this project description include packages with a <<jar>> or <<java>> stereotype. You do not and must not recreate the classes and interfaces in these packages since they are already provided for you.

The UrgencyQueue<ItemType> Interface

The UrgencyQueue<ItemType> interface defines an ADT for urgency-based queue operations. From an external perspective, each urgency queue object maintains a line of zero or more items (i.e., non-null references to objects of type ItemType). Unlike a standard queue, which orders its line of items according to FIFO (first-in-first-out) semantics, an urgency queue associates a level of urgency with each item and orders its items according to their relative level of urgency.

You will NOT be writing the code for this interface yourself; instead, a compiled version is provided for you in cs1302-urgency-queue.jar. Read the starter API documentation and the UML diagram shown below in Fig. 3.1.

Fig. 3.1 UML diagram of the UrgencyQueue<ItemType> interface. [svg] [png]

The enqueueAll method declares its own type parameter, SubType, in addition to the ItemType parameter declared by the interface. Its declaration, <SubType extends ItemType>, uses ItemType as the upper bound for SubType. Refer to the method details for enqueueAll and Examples 2–3 in the provided API documentation.

The Implementing Classes

Both implementations use the same storage representation: a singly linked chain of the provided Node<ItemType> objects. Their ordering policies differ:

• LinkedUrgencyQueue uses the natural ordering defined by Comparable<ItemType> and its compareTo method.

• CustomLinkedUrgencyQueue uses the Comparator<ItemType> supplied to its constructor. This lets a caller choose an urgency ordering independently of an item's natural ordering.

The abstract BaseLinkedUrgencyQueue class declares the shared size and head instance variables and implements operations that both concrete classes need. Each concrete queue object contains these inherited fields once. Constructing a subclass object does not create a separate base queue object.

Fig. 3.2 Both concrete classes extend the same abstract base and use the same provided node type. [svg] [png]

The class specifications distinguish declared members, inherited members, and each class's responsibilities.

The Provided Node Class

The Node<ItemType> class is provided in cs1302.gen. Its item and next fields have package-private access. Your queue classes are in cs1302.p3, so use the public getter methods and setter methods (getItem, setItem, getNext, and setNext) to read or replace those field values.

Fig. 3.3 The provided generic node class. The UML ~ visibility symbol denotes package-private access. [svg] [png]

A node stores an item reference value and a next-node reference value. If its next field has the value null, it does not refer to another node. Distinguish replacing one of those reference values from modifying the object to which that value refers.

The node example illustrates these relationships without implementing a queue insertion algorithm.

See the Node class API documentation for code examples that illustrate how to create and use a linked list of Node objects and visualize its links using Node.asString.

Functional Interfaces

A functional interface has a single abstract method contract that a lambda expression can implement. Default and static methods do not count toward that contract, nor do abstract declarations matching public methods of Object. The following links open the official Java 25 API documentation.

These interfaces let you supply behavior to queue operations and provided helper methods:

• Comparator<T> — int compare(T a, T b) compares two items and returns with a negative integer, zero, or a positive integer to indicate their relative order. Custom urgency queues use this comparison to determine which item is more urgent.

• Consumer<T> — void accept(T item) performs an action using an item and returns without a value when it completes normally. The dequeue(action) and dequeueMany(num, action) methods use a consumer to process removed items.

• Predicate<T> — boolean test(T item) checks an item and returns with true or false. The queue's filter method uses this result to select items for the new queue.

• IntFunction<R> — R apply(int value) accepts an int and returns with a result of type R. The toArray method accepts an IntFunction<ItemType[]> that supplies a reference to an array of the requested length.

• Function<T, R> — R apply(T item) maps an input to a result. The provided Node.asString(node, toString) helper accepts a Function<ItemType, String> to produce each item's text.

The following interfaces also satisfy the functional-interface definition. In this project, you encounter them mainly through classes that implement them, rather than through callback lambdas:

• Comparable<T> — int compareTo(T other) compares the receiving object with another object to define natural ordering. Natural-order urgency queues require items whose class implements the appropriate Comparable interface, such as Person implementing Comparable<Person>.

• Iterable<T> — Iterator<T> iterator() returns with a reference to an iterator over the elements. The enqueueAll method accepts an Iterable so it can visit the supplied items, including items supplied through a List.

Using and Testing Urgency Queue Objects

Understanding ADT Expectations

The interface API documentation specifies the behavior of each method, including exceptional completion and requirements about changes to the calling queue. Read its introduction and method specifications before planning an implementation.

Comparison Results and Stable Ties

For this assignment, the sign of a.compareTo(b) or comparator.compare(a, b) determines urgency:

Result	Required urgency relationship
Negative	a is less urgent than b.
Zero	a and b have equal urgency.
Positive	a is more urgent than b.

Use the sign rather than assuming that a comparison produces only -1, 0, or 1. The most urgent items appear first. For equal urgency, preserve FIFO order: an item enqueued earlier remains before an item enqueued later. Equal urgency does not require equal objects or identical reference values.

For example, enqueue "aa", "b", "cc", and "dddd" in that order into a custom queue whose comparator compares string lengths. The queue's string representation must be [dddd, aa, cc, b]. The two length-two strings retain their arrival order. With the reversed length comparator, the representation must be [b, aa, cc, dddd]: reversing the urgency relationship preserves FIFO order within the tie.

The comparator teaching example lets you inspect comparison signs separately from queue implementation.

Observe Both the Result and the Calling Queue

Start with the length-ordered queue [dddd, aa, cc, b] above and perform the following operations in sequence. Each method call that completes normally with a queue result returns with a reference to a new queue of the same concrete type as the calling queue. A custom result queue uses the same comparator.

Define the following predicate using java.util.function.Predicate:

Predicate<String> isLength2 = (String item) -> {
    return item.length() == 2;
}; // lambda

Filtering selects items; bulk dequeue removes items.

Operation	Result queue	Calling queue afterward
filter(isLength2)	[aa, cc]	[dddd, aa, cc, b]
dequeueMany(2)	[dddd, aa]	[cc, b]

filter must leave the calling queue unchanged. dequeueMany(int) removes the requested number of most urgent items from that queue. Test the result, its ordering policy, and the calling queue's state; checking only the result misses part of each contract. For the consumer overloads, check the removed items' order and the actions performed on them. User-supplied behavior must be non-interfering, as described in the API documentation.

Boundary and Exception Contracts

An empty queue's peek() and dequeue() method calls must complete abruptly with IllegalStateException. Both dequeueMany overloads require IllegalArgumentException for a negative count and IllegalStateException when the count exceeds size(). A count of zero is valid when the other arguments satisfy their contracts.

Read each null-argument rule separately. For example, enqueue(null) requires NullPointerException, whereas enqueueAll(items) requires IllegalArgumentException if any item in a non-null iterable is null; that call must leave the queue unchanged. A null iterable, predicate, action, or array generator requires NullPointerException. These examples supplement the API documentation, which specifies every method.

Oracle Classes for Testing

To assist you in testing your code, the starter JAR file provides two fully implemented oracle classes in the cs1302.oracle package:

• OracleLinkedUrgencyQueue

• OracleCustomLinkedUrgencyQueue

These oracle classes satisfy all functional requirements of the assignment. You can construct oracle objects in your test programs to establish the expected behavior and compare results against your own implementations.

Provided JAR Classes: State, References, and Type Constraints

These programs use the provided Node<ItemType> class, oracle queue classes, and data models from cs1302-urgency-queue.jar. The supplied Person and Movie classes let you explore ordering and type constraints without defining replacement model classes. The programs demonstrate public API use; they do not implement queue operations or belong in your project submission.

Each execution pause occurs immediately before the highlighted driver line executes. Only the driver or short test program is displayed; the provided JAR supplies the library classes for compilation and execution. Follow the driver statements alongside the corresponding object state. The explanations below also describe the key states without requiring the interactive controls.

Construction and Initial State

Purpose: connect the class hierarchy to an object's initial state and distinguish copying a comparator reference value from constructing another comparator object.

Before line 21, natural refers to an empty natural-order oracle. Before line 25, custom refers to an empty custom-order oracle; its comparator field and byAge refer to the same comparator object. Before line 26, both custom queues use that same comparator. Each queue has its own inherited size and head fields, with values 0 and null. The final pause is before line 27, after the output statement has executed.

ConstructorDriver is an instructor-written demonstration class. It is not included in the project starter code, and you do not need to create it.

|< < Prev

Step 1 of 4: ConstructorDriver.java:21

Next > >|

1234

Listing 3.6 Construct empty oracle queues for the two ordering policies.

package cs1302.urgency.demo;

import cs1302.gen.UrgencyQueue;
import cs1302.oracle.OracleCustomLinkedUrgencyQueue;
import cs1302.oracle.OracleLinkedUrgencyQueue;
import cs1302.oracle.model.Person;
import java.util.Comparator;

/**
 * Constructs the supplied oracle queues without implementing queue operations.
 */
public class ConstructorDriver {

    /**
     * Demonstrates empty state and a shared comparator reference value.
     *
     * @param args the command-line arguments, which are unused
     */
    public static void main(String[] args) {
        UrgencyQueue<Person> natural = new OracleLinkedUrgencyQueue<Person>();
        Comparator<Person> byAge = (Person personA, Person personB) -> {
            return personA.age() - personB.age();
        };
        UrgencyQueue<Person> custom = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        UrgencyQueue<Person> samePolicy = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        System.out.println("Constructed one natural oracle and two custom oracles.");
    } // main

} // ConstructorDriver

    public static void main(String[] args) {
        UrgencyQueue<Person> natural = new OracleLinkedUrgencyQueue<Person>();
        Comparator<Person> byAge = (Person personA, Person personB) -> {
            return personA.age() - personB.age();
        };
        UrgencyQueue<Person> custom = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        UrgencyQueue<Person> samePolicy = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        System.out.println("Constructed one natural oracle and two custom oracles.");
    } // main

Initial queue fields and shared comparator reference values. Note: The debugger breakpoint is on line 21 in ConstructorDriver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        UrgencyQueue<Person> natural = new OracleLinkedUrgencyQueue<Person>();
        Comparator<Person> byAge = (Person personA, Person personB) -> {
            return personA.age() - personB.age();
        };
        UrgencyQueue<Person> custom = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        UrgencyQueue<Person> samePolicy = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        System.out.println("Constructed one natural oracle and two custom oracles.");
    } // main

Initial queue fields and shared comparator reference values. Note: The debugger breakpoint is on line 25 in ConstructorDriver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        UrgencyQueue<Person> natural = new OracleLinkedUrgencyQueue<Person>();
        Comparator<Person> byAge = (Person personA, Person personB) -> {
            return personA.age() - personB.age();
        };
        UrgencyQueue<Person> custom = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        UrgencyQueue<Person> samePolicy = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        System.out.println("Constructed one natural oracle and two custom oracles.");
    } // main

Initial queue fields and shared comparator reference values. Note: The debugger breakpoint is on line 26 in ConstructorDriver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        UrgencyQueue<Person> natural = new OracleLinkedUrgencyQueue<Person>();
        Comparator<Person> byAge = (Person personA, Person personB) -> {
            return personA.age() - personB.age();
        };
        UrgencyQueue<Person> custom = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        UrgencyQueue<Person> samePolicy = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
        System.out.println("Constructed one natural oracle and two custom oracles.");
    } // main

Initial queue fields and shared comparator reference values. Note: The debugger breakpoint is on line 27 in ConstructorDriver.java. [code listing] [download] [open]

Constructed one natural oracle and two custom oracles.

>_ Console Output

The lambda body compares the two age values directly. The diagram shows that body from the driver. The shared object identifier confirms that byAge and both comparator fields refer to the same lambda object within this trace.

The diagrams show actual oracle objects, including their inherited fields. A parent class constructor invocation operates on the same object being constructed; it does not construct a separate base queue object. Java supplies default values for instance fields before constructor execution. Local variables follow different definite assignment rules and are not automatically initialized to those defaults.

Node Reference Values and Aliases

Purpose: follow a short, manually constructed node chain and observe the difference between changing a node's item field and reassigning a local reference variable.

Before line 25, alias and middle refer to the same node; itemAlias stores the item reference value read from that node. Before line 27, the setter method has changed the node's item field, while itemAlias still refers to the earlier item object. Before line 30, reassigning alias makes that local variable refer to the tail node; it has not changed the head node's next-node field. Before line 33, all printed comparisons are available. The tail node's next value remains null.

NodeDriver is an instructor-written demonstration class. It is not included in the project starter code, and you do not need to create it.

|< < Prev

Step 1 of 4: NodeDriver.java:25

Next > >|

1234

Listing 3.7 Read and replace reference values through public node methods.

package cs1302.urgency.demo;

import cs1302.gen.Node;
import cs1302.oracle.model.Person;

/**
 * Demonstrates a manually constructed chain and node aliases, not a queue algorithm.
 */
public class NodeDriver {

    /**
     * Uses the supplied node's public getter and setter methods from another package.
     *
     * @param args the command-line arguments, which are unused
     */
    public static void main(String[] args) {
        Person first = new Person(70, "C");
        Person second = new Person(30, "A");
        Person third = new Person(30, "B");
        Node<Person> tail = new Node<Person>(third);
        Node<Person> middle = new Node<Person>(second, tail);
        Node<Person> head = new Node<Person>(first, middle);
        Node<Person> alias = head.getNext();
        Person itemAlias = alias.getItem();
        System.out.println("Same node: " + (alias == middle));
        alias.setItem(first);
        System.out.println("Middle item: " + middle.getItem());
        System.out.println("Earlier item reference: " + itemAlias);
        alias = alias.getNext();
        System.out.println("Local alias is tail: " + (alias == tail));
        System.out.println("Head still links to middle: " + (head.getNext() == middle));
        System.out.println("Tail has next node: " + tail.hasNext());
    } // main

} // NodeDriver

    public static void main(String[] args) {
        Person first = new Person(70, "C");
        Person second = new Person(30, "A");
        Person third = new Person(30, "B");
        Node<Person> tail = new Node<Person>(third);
        Node<Person> middle = new Node<Person>(second, tail);
        Node<Person> head = new Node<Person>(first, middle);
        Node<Person> alias = head.getNext();
        Person itemAlias = alias.getItem();
        System.out.println("Same node: " + (alias == middle));
        alias.setItem(first);
        System.out.println("Middle item: " + middle.getItem());
        System.out.println("Earlier item reference: " + itemAlias);
        alias = alias.getNext();
        System.out.println("Local alias is tail: " + (alias == tail));
        System.out.println("Head still links to middle: " + (head.getNext() == middle));
        System.out.println("Tail has next node: " + tail.hasNext());
    } // main

Node aliases, item aliases, and an unchanged chain link. Note: The debugger breakpoint is on line 25 in NodeDriver.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Person first = new Person(70, "C");
        Person second = new Person(30, "A");
        Person third = new Person(30, "B");
        Node<Person> tail = new Node<Person>(third);
        Node<Person> middle = new Node<Person>(second, tail);
        Node<Person> head = new Node<Person>(first, middle);
        Node<Person> alias = head.getNext();
        Person itemAlias = alias.getItem();
        System.out.println("Same node: " + (alias == middle));
        alias.setItem(first);
        System.out.println("Middle item: " + middle.getItem());
        System.out.println("Earlier item reference: " + itemAlias);
        alias = alias.getNext();
        System.out.println("Local alias is tail: " + (alias == tail));
        System.out.println("Head still links to middle: " + (head.getNext() == middle));
        System.out.println("Tail has next node: " + tail.hasNext());
    } // main

Node aliases, item aliases, and an unchanged chain link. Note: The debugger breakpoint is on line 27 in NodeDriver.java. [code listing] [download] [open]

Same node: true

>_ Console Output

    public static void main(String[] args) {
        Person first = new Person(70, "C");
        Person second = new Person(30, "A");
        Person third = new Person(30, "B");
        Node<Person> tail = new Node<Person>(third);
        Node<Person> middle = new Node<Person>(second, tail);
        Node<Person> head = new Node<Person>(first, middle);
        Node<Person> alias = head.getNext();
        Person itemAlias = alias.getItem();
        System.out.println("Same node: " + (alias == middle));
        alias.setItem(first);
        System.out.println("Middle item: " + middle.getItem());
        System.out.println("Earlier item reference: " + itemAlias);
        alias = alias.getNext();
        System.out.println("Local alias is tail: " + (alias == tail));
        System.out.println("Head still links to middle: " + (head.getNext() == middle));
        System.out.println("Tail has next node: " + tail.hasNext());
    } // main

Node aliases, item aliases, and an unchanged chain link. Note: The debugger breakpoint is on line 30 in NodeDriver.java. [code listing] [download] [open]

Same node: true
Middle item: Person[age=70, name=C]
Earlier item reference: Person[age=30, name=A]

>_ Console Output

    public static void main(String[] args) {
        Person first = new Person(70, "C");
        Person second = new Person(30, "A");
        Person third = new Person(30, "B");
        Node<Person> tail = new Node<Person>(third);
        Node<Person> middle = new Node<Person>(second, tail);
        Node<Person> head = new Node<Person>(first, middle);
        Node<Person> alias = head.getNext();
        Person itemAlias = alias.getItem();
        System.out.println("Same node: " + (alias == middle));
        alias.setItem(first);
        System.out.println("Middle item: " + middle.getItem());
        System.out.println("Earlier item reference: " + itemAlias);
        alias = alias.getNext();
        System.out.println("Local alias is tail: " + (alias == tail));
        System.out.println("Head still links to middle: " + (head.getNext() == middle));
        System.out.println("Tail has next node: " + tail.hasNext());
    } // main

Node aliases, item aliases, and an unchanged chain link. Note: The debugger breakpoint is on line 33 in NodeDriver.java. [code listing] [download] [open]

Same node: true
Middle item: Person[age=70, name=C]
Earlier item reference: Person[age=30, name=A]
Local alias is tail: true
Head still links to middle: true
Tail has next node: false

>_ Console Output

This example deliberately replaces a node's stored item reference value to isolate aliasing behavior. It is not an example of maintaining queue urgency order. Your queue operations must additionally preserve all ordering and size requirements.

Comparison Signs and Generic Type Constraints

Purpose: inspect comparison results without implementing or sorting a queue. The supplied Person class implements Comparable<Person> and compares age, then name. The lambda in this driver instead compares age only, so two people with the same age and different names can have equal urgency under that custom policy.

Before line 28, the output confirms that the two same-age people are distinct objects and that their different names affect natural ordering. Before line 31, the age-only comparator has produced zero for their tie, a positive result for the higher age, and a negative result for the lower age. Before line 34, reversing the comparator has reversed the nonzero signs while preserving zero for the tie. A queue using either policy must still preserve arrival order among equal-urgency items.

ComparatorDriver is an instructor-written demonstration class. It is not included in the project starter code, and you do not need to create it.

|< < Prev

Step 1 of 3: ComparatorDriver.java:30

Next > >|

123

Listing 3.8 Compare supplied Person objects by age and reversed age.

package cs1302.urgency.demo;

import cs1302.oracle.model.Person;
import java.util.Comparator;

/**
 * Demonstrates comparison signs for distinct items, including an equal-urgency pair.
 * This example performs comparisons only; it does not implement or sort a queue.
 */
public class ComparatorDriver {

    /**
     * Compares supplied person objects using natural, age-only, and reversed age ordering.
     *
     * @param args the command-line arguments, which are unused
     */
    public static void main(String[] args) {
        Person a = new Person(30, "A");
        Person b = new Person(30, "B");
        Person c = new Person(70, "C");
        Person d = new Person(10, "D");
        Comparator<Person> byAge = (Person personA, Person personB) -> {
            return personA.age() - personB.age();
        };
        Comparator<Person> reversed = (Person personA, Person personB) -> {
            return personB.age() - personA.age();
        };
        System.out.println("A and B are distinct objects: " + (a != b));
        System.out.println("natural(A, B): " + a.compareTo(b));
        System.out.println("byAge(A, B): " + byAge.compare(a, b));
        System.out.println("byAge(C, A): " + byAge.compare(c, a));
        System.out.println("byAge(D, A): " + byAge.compare(d, a));
        System.out.println("reversed(C, A): " + reversed.compare(c, a));
        System.out.println("reversed(D, A): " + reversed.compare(d, a));
        System.out.println("reversed(A, B): " + reversed.compare(a, b));
    } // main

} // ComparatorDriver

    public static void main(String[] args) {
        Person a = new Person(30, "A");
        Person b = new Person(30, "B");
        Person c = new Person(70, "C");
        Person d = new Person(10, "D");
        Comparator<Person> byAge = (Person personA, Person personB) -> {
            return personA.age() - personB.age();
        };
        Comparator<Person> reversed = (Person personA, Person personB) -> {
            return personB.age() - personA.age();
        };
        System.out.println("A and B are distinct objects: " + (a != b));
        System.out.println("natural(A, B): " + a.compareTo(b));
        System.out.println("byAge(A, B): " + byAge.compare(a, b));
        System.out.println("byAge(C, A): " + byAge.compare(c, a));
        System.out.println("byAge(D, A): " + byAge.compare(d, a));
        System.out.println("reversed(C, A): " + reversed.compare(c, a));
        System.out.println("reversed(D, A): " + reversed.compare(d, a));
        System.out.println("reversed(A, B): " + reversed.compare(a, b));
    } // main

Comparator objects, Person objects, and printed comparison signs. Note: The debugger breakpoint is on line 30 in ComparatorDriver.java. [code listing] [download] [open]

A and B are distinct objects: true
natural(A, B): -1

>_ Console Output

    public static void main(String[] args) {
        Person a = new Person(30, "A");
        Person b = new Person(30, "B");
        Person c = new Person(70, "C");
        Person d = new Person(10, "D");
        Comparator<Person> byAge = (Person personA, Person personB) -> {
            return personA.age() - personB.age();
        };
        Comparator<Person> reversed = (Person personA, Person personB) -> {
            return personB.age() - personA.age();
        };
        System.out.println("A and B are distinct objects: " + (a != b));
        System.out.println("natural(A, B): " + a.compareTo(b));
        System.out.println("byAge(A, B): " + byAge.compare(a, b));
        System.out.println("byAge(C, A): " + byAge.compare(c, a));
        System.out.println("byAge(D, A): " + byAge.compare(d, a));
        System.out.println("reversed(C, A): " + reversed.compare(c, a));
        System.out.println("reversed(D, A): " + reversed.compare(d, a));
        System.out.println("reversed(A, B): " + reversed.compare(a, b));
    } // main

Comparator objects, Person objects, and printed comparison signs. Note: The debugger breakpoint is on line 33 in ComparatorDriver.java. [code listing] [download] [open]

A and B are distinct objects: true
natural(A, B): -1
byAge(A, B): 0
byAge(C, A): 40
byAge(D, A): -20

>_ Console Output

    public static void main(String[] args) {
        Person a = new Person(30, "A");
        Person b = new Person(30, "B");
        Person c = new Person(70, "C");
        Person d = new Person(10, "D");
        Comparator<Person> byAge = (Person personA, Person personB) -> {
            return personA.age() - personB.age();
        };
        Comparator<Person> reversed = (Person personA, Person personB) -> {
            return personB.age() - personA.age();
        };
        System.out.println("A and B are distinct objects: " + (a != b));
        System.out.println("natural(A, B): " + a.compareTo(b));
        System.out.println("byAge(A, B): " + byAge.compare(a, b));
        System.out.println("byAge(C, A): " + byAge.compare(c, a));
        System.out.println("byAge(D, A): " + byAge.compare(d, a));
        System.out.println("reversed(C, A): " + reversed.compare(c, a));
        System.out.println("reversed(D, A): " + reversed.compare(d, a));
        System.out.println("reversed(A, B): " + reversed.compare(a, b));
    } // main

Comparator objects, Person objects, and printed comparison signs. Note: The debugger breakpoint is on line 36 in ComparatorDriver.java. [code listing] [download] [open]

A and B are distinct objects: true
natural(A, B): -1
byAge(A, B): 0
byAge(C, A): 40
byAge(D, A): -20
reversed(C, A): -40
reversed(D, A): 20
reversed(A, B): 0

>_ Console Output

The age-only comparison results are 0, 40, and -20. Only their signs determine urgency. The chosen ages keep the subtraction within the int range.

The next example deliberately fails to compile. The natural-order oracle requires Comparable<T>, and the supplied Movie class does not satisfy that bound. This is a type constraint checked by the compiler, not a runtime queue exception. A custom queue can order movie objects using a supplied comparator, such as Movie.Order.byRating() for an OracleCustomLinkedUrgencyQueue<Movie>.

InvalidComparable is an instructor-written test class. It is not included in the project starter code, and you do not need to create it.

Listing 3.9 Expected compilation failure for an unsatisfied Comparable bound.

package cs1302.urgency.demo;

import cs1302.gen.UrgencyQueue;
import cs1302.oracle.OracleLinkedUrgencyQueue;
import cs1302.oracle.model.Movie;

/**
 * An intentionally invalid example: the supplied Movie record has no natural ordering.
 * This source is compiled only as an expected-error example.
 */
public class InvalidComparable {

    /**
     * Attempts to use Movie where the supplied oracle requires {@code Comparable<Movie>}.
     *
     * @param args the command-line arguments, which are unused
     */
    public static void main(String[] args) {
        UrgencyQueue<Movie> invalid = new OracleLinkedUrgencyQueue<Movie>();
    } // main

} // InvalidComparable

Compiler error (expected)

cs1302/urgency/demo/InvalidComparable.java:19: error: type argument Movie is not within bounds of type-variable ItemType
        UrgencyQueue<Movie> invalid = new OracleLinkedUrgencyQueue<Movie>();
                                                                   ^
  where ItemType is a type-variable:
    ItemType extends Comparable<ItemType> declared in class OracleLinkedUrgencyQueue
1 error

In the error message, not within bounds means that Movie does not satisfy the constraint on the oracle's type parameter ItemType. The bound ItemType extends Comparable<ItemType> requires Movie to implement Comparable<Movie>, which the supplied class does not implement. The compiler reports both uses of Movie: one in the variable's declared type and one in the class instance creation expression. This is a compilation error, so the program does not execute. Review the bounded-type examples in the generics practice page.

Generic types are also invariant. Although Person is a child of Object, a queue parameterized by Person is not a child of the corresponding queue parameterized by Object. The next assignment therefore deliberately fails to compile. The method type parameter SubType extends ItemType in the real API's enqueueAll is a separate, explicitly declared relationship; it does not make parameterized queue types covariant.

InvalidInvariance is an instructor-written test class. It is not included in the project starter code, and you do not need to create it.

Listing 3.10 Expected compilation failure for an incompatible generic assignment.

package cs1302.urgency.demo;

import cs1302.gen.UrgencyQueue;
import cs1302.oracle.OracleLinkedUrgencyQueue;
import cs1302.oracle.model.Person;

/**
 * An intentionally invalid teaching example of generic invariance.
 * This source is compiled only as an expected-error example.
 */
public class InvalidInvariance {

    /**
     * Attempts an assignment between incompatible generic queue types.
     *
     * @param args the command-line arguments, which are unused
     */
    public static void main(String[] args) {
        UrgencyQueue<Person> people = new OracleLinkedUrgencyQueue<Person>();
        UrgencyQueue<Object> invalid = people;
    } // main

} // InvalidInvariance

Compiler error (expected)

cs1302/urgency/demo/InvalidInvariance.java:20: error: incompatible types: UrgencyQueue<Person> cannot be converted to UrgencyQueue<Object>
        UrgencyQueue<Object> invalid = people;
                                       ^
1 error

Here, incompatible types and cannot be converted mean that the assignment cannot copy the reference value stored in people into invalid. Their declared types are UrgencyQueue<Person> and UrgencyQueue<Object>, respectively. Although Person is a child of Object, that relationship does not make the first queue type a child of the second; generic types are invariant. There is no permitted assignment conversion between these two queue types. Review Reference Types and Assignment Values for the reference-assignment rules.

Getting Started

You will not be starting from scratch. Starter code is provided in a Git repository that you will clone onto Odin. To download the starter code, follow these instructions:

1. Log in to Odin.

2. If you have not done so, create a directory inside your home directory to store your CSCI 1302 projects.

3. Change into your CSCI 1302 projects directory.

4. Execute the following command to clone the starter code into a directory called cs1302-urgency-queue:

   git clone --depth 1 https://github.com/cs1302uga/cs1302-urgency-queue.git
   

5. Change into the newly created cs1302-urgency-queue directory and inspect the starter files:

   cd cs1302-urgency-queue
   

   ls -la
   

   The starter repository contains the following files. Keep the JAR at the project root; the scripts use that location.

   cs1302-urgency-queue/
   ├── .gitignore
   ├── README.md
   ├── compile.sh
   ├── test.sh
   ├── cs1302-urgency-queue.jar
   ├── UrgencyQueue.svg
   └── src/
       └── cs1302/
           ├── p3/
           │   ├── BaseLinkedUrgencyQueue.java
           │   ├── LinkedUrgencyQueue.java
           │   └── CustomLinkedUrgencyQueue.java
           └── test/
               └── QueueTester.java
   

   The three cs1302.p3 files are incomplete implementation skeletons. QueueTester.java is a reusable testing scaffold. The JAR contains the cs1302.gen package and cs1302.oracle package packages; do not recreate those types. README.md links to this authoritative project description. The supplied diagram is a reference image, not Java source.

6. Create a SUBMISSION.md file directly in your cs1302-urgency-queuedirectory containing your name, UGA ID (811#), and your hosted API documentation website URL (see SUBMISSION.md Non-Functional Requirement).

7. Stage and commit your SUBMISSION.md file:

   git add SUBMISSION.md
   

   git commit -m "added my info to SUBMISSION.md"
   

Compile, Test, and Retest

Use JDK 25 on Odin and run the provided scripts from inside the cs1302-urgency-queue project root:

./compile.sh

./test.sh oracle

./test.sh custom-oracle

./test.sh linked

./test.sh custom

The provided compile.sh script:

• Explicitly compiles the three supplied queue classes and QueueTester.java into bin for Java 25 with debug information and strict raw-type and unchecked-warning checks.

• Runs check1302 on each file.

• Generates API documentation in doc with links to the supplied API.

• Recreates bin and doc; keep your source files under src.

Add compile and style-check commands to the script for any additional classes you create. Fix compilation failures before running tests.

The provided test.sh script first runs the compile.sh script, then runs the supplied QueueTester dispatcher. It requires exactly one implementation name; there is no default when invoking the script.

The oracle and custom-oracle choices use the two provided oracle classes. The linked and custom choices use your implementations. Run the same scenarios against each applicable choice. Keep earlier passing tests when you add a new one so later changes are checked for regressions.

When writing tests in QueueTester:

• Write instance test methods named by model and operation, such as testPersonQueuePeek(), testPersonQueueEnqueue(), or testMovieQueueEnqueue().

• Use testPersonQueueSize() and testMovieQueueSize() as minimal examples. Each checks that a new queue has size zero.

• Add a call in testAll() for each new test; declaring a method alone does not run it.

• Keep scenario variables typed as UrgencyQueue<Person> or UrgencyQueue<Movie> so the same checks can exercise the oracle and your implementation.

Use the supplied construction helpers:

• newPersonQueue() constructs the selected implementation with Person natural ordering, which compares age first, then name. For custom modes, it supplies Comparator.naturalOrder() so tests use the same ordering in all four modes.

• newPersonQueue(comparator) constructs a custom person queue with your supplied comparator. Use it to test alternative orderings and distinct equal-urgency items.

• newMovieQueue(comparator) constructs a custom movie queue. For example, supply Movie.Order.byRating() or your own comparator. Movie does not implement Comparable<Movie>.

The comparator-taking helpers require custom-oracle or custom; they throw IllegalStateException in natural-order modes. Organize calls in testAll() as follows:

• Place person tests that use newPersonQueue() before the custom-mode branch so they run in every mode.

• Place calls to movie tests and custom-comparator person tests inside the custom-mode branch. Natural-order modes print a message explaining that custom-only tests are skipped.

In Part 1, your constructors and method stubs deliberately throw UnsupportedOperationException. The oracle runs should pass the supplied size tests applicable to that mode, while runs against your stubs are expected to fail. Such a failure does not establish functional correctness. As you implement each part, replace expected stub failures with passing tests and investigate every other failure. Retest the natural implementation while completing the custom implementation.

3.4. Project Checklist

The steps in the following checklist guide your development through the three milestones.

Part 1. Prepare and Plan (due Monday, November 2^nd @ 11:55 PM)

Preparing for Part 1

Follow the steps provided below to prepare the BaseLinkedUrgencyQueue, LinkedUrgencyQueue, and CustomLinkedUrgencyQueue classes so that everything compiles without errors or warnings on Odin, and set up a tester program to verify behavior against the provided oracle classes.

Due Before:

Monday, November 2^nd @ 11:55 PM.

1. Download the starter code on Odin by following the instructions in Getting Started.

2. In each skeleton file under src/cs1302/p3/, add "stub" methods (placeholders that throw UnsupportedOperationException) for all required method overrides:

   • In BaseLinkedUrgencyQueue.java: Declare package-private instance variables int size and Node<ItemType> head. Add stub implementations for:

     • public int size()

     • public ItemType peek()

     • public String toString()

     • public ItemType dequeue()

     • public void dequeue(Consumer<ItemType> action)

     • public void dequeueMany(int num, Consumer<ItemType> action)

     • public void clear()

     • public <SubType extends ItemType> boolean enqueueAll(Iterable<SubType> items)

     • public ItemType[] toArray(IntFunction<ItemType[]> generator)

   • In LinkedUrgencyQueue.java: Add stub implementations for:

     • public boolean enqueue(ItemType item)

     • public UrgencyQueue<ItemType> dequeueMany(int num)

     • public UrgencyQueue<ItemType> filter(Predicate<ItemType> cond)

   • In CustomLinkedUrgencyQueue.java: Declare a private instance variable Comparator<ItemType> comparator. Add stub implementations for:

     • public boolean enqueue(ItemType item)

     • public UrgencyQueue<ItemType> dequeueMany(int num)

     • public UrgencyQueue<ItemType> filter(Predicate<ItemType> cond)

   Example "stub" method

   /**
    * Returns with the number of elements in this urgency queue.
    * {@inheritDoc}
    */
   @Override
   public int size() {
       // TODO: return with the current size of the queue
       throw new UnsupportedOperationException("not yet implemented");
   } // size
   

3. Read the supplied src/cs1302/test/QueueTester.java scaffold. Identify its newPersonQueue and newMovieQueue construction helpers, testAll dispatcher, and two model-specific size tests. Plan additional tests that can run against the common UrgencyQueue interface.

4. Follow Compile, Test, and Retest to compile all implementation and tester sources, generate doc, check style, and run the applicable size tests against both oracle choices. Confirm that the student choices fail because their constructors or methods are still stubs; preserve that distinction in your notes.

5. Replace the // TODO in each stub method with detailed planning comments describing the step-by-step logic required to implement that method.

6. Stage and commit your changes:

   git add src/
   

   git commit -m "Part 1: stubs, planning comments, and tester skeleton"
   

7. Regenerate doc by running the provided compile.sh script, host the API documentation as required below, and check SUBMISSION.md and code style.

8. Complete How to Submit for part1 before Monday, November 2^nd @ 11:55 PM. That procedure includes changing to the parent directory before running the submission command.

Part 2. Implement Base and Linked Urgency Queue (due Sunday, November 8^th @ 11:55 PM)

Preparing for Part 2

To prepare for this part of the project, you must first complete and submit Part 1. Your submission for Part 2 is expected to meet all functional requirements for BaseLinkedUrgencyQueue and LinkedUrgencyQueue as well as all non-functional requirements.

Due After:

Submitting Part 1.

Due Before:

Sunday, November 8^th @ 11:55 PM.

1. Implement the methods in BaseLinkedUrgencyQueue and LinkedUrgencyQueue in the recommended order below:

   Recommended implementation order for Part 2

   #	Class	Method
   1	BaseLinkedUrgencyQueue	Constructor, int size(), ItemType peek()
   2	LinkedUrgencyQueue	Constructor, boolean enqueue(ItemType item)
   3	BaseLinkedUrgencyQueue	String toString()
   4	BaseLinkedUrgencyQueue	ItemType dequeue()
   5	BaseLinkedUrgencyQueue	void dequeue(Consumer<ItemType> action)
   6	BaseLinkedUrgencyQueue	void dequeueMany(int num, Consumer<ItemType> action)
   7	BaseLinkedUrgencyQueue	void clear()
   8	BaseLinkedUrgencyQueue	<SubType extends ItemType> boolean enqueueAll(Iterable<SubType> items)
   9	BaseLinkedUrgencyQueue	ItemType[] toArray(IntFunction<ItemType[]> generator)
   10	LinkedUrgencyQueue	UrgencyQueue<ItemType> dequeueMany(int num)
   11	LinkedUrgencyQueue	UrgencyQueue<ItemType> filter(Predicate<ItemType> cond)

2. For each method:

   • Write automated tests in QueueTester comparing your method's return values and exceptions against the oracle class.

   • Implement the method body.

   • Test until all assertions pass.

   • Stage and commit your changes with descriptive Git commit messages.

3. From the project root, run:

   ./compile.sh
   

   ./test.sh oracle
   

   ./test.sh linked
   

   Keep all earlier tests enabled. Custom student tests may still fail on their Part 3 stubs.

4. Check your generated and hosted API documentation and SUBMISSION.md, then complete How to Submit for part2 before Sunday, November 8^th @ 11:55 PM.

Part 3. Implement Custom Linked Urgency Queue and Final Polish (due Thursday, November 12^th @ 11:55 PM)

Preparing for Part 3

To prepare for this part of the project, you must first complete and submit Part 2. Your submission for Part 3 represents your final project submission and must satisfy all functional and non-functional requirements across all classes.

Due After:

Submitting Part 2.

Due Before:

Thursday, November 12^th @ 11:55 PM.

1. Implement CustomLinkedUrgencyQueue:

   • Implement constructor CustomLinkedUrgencyQueue(Comparator<ItemType> cmp) ensuring a NullPointerException is thrown if cmp is null.

   • Implement boolean enqueue(ItemType item) using the comparator.

   • Implement UrgencyQueue<ItemType> dequeueMany(int num) returning with a reference to a new CustomLinkedUrgencyQueue configured with the same comparator.

   • Implement UrgencyQueue<ItemType> filter(Predicate<ItemType> cond) returning with a reference to a new CustomLinkedUrgencyQueue with the same comparator.

2. Refactor and Eliminate Redundancy:

   Notice similarities between the implementations in LinkedUrgencyQueue and CustomLinkedUrgencyQueue. Can common logic be moved up to BaseLinkedUrgencyQueue? Refactoring to maximize code reuse without breaking encapsulation is strongly encouraged.

3. Run comprehensive tests in QueueTester covering:

   • Boundary cases (empty queue, single element, large queues).

   • Correct exception throwing (checking null arguments, invalid counts).

   • The method type bound in enqueueAll and the array generator supplied to toArray.

   • Behavioral equivalence to both oracle classes.

4. Follow Compile, Test, and Retest and require all applicable tests to pass for both oracle choices and both student choices. Check the dependency restrictions using the examples under No Implementation Dependencies.

5. Update SUBMISSION.md, regenerate doc by running the provided compile.sh script, verify the hosted documentation, and commit your completed work.

6. Complete How to Submit for part3 before Thursday, November 12^th @ 11:55 PM. This is your final submission of all three classes and their retained tests.

3.5. Functional Requirements

A functional requirement defines a specific behavior between program inputs and outputs. If your submission satisfies a functional requirement listed in this section, then the requirement's point total is added to your submission grade.

Overview: Class Structure and Initial State

Start with the hierarchy, then inspect each class's focused specification below. UML distinguishes declarations from relevant inherited members; it does not add extra copies of inherited fields to the object. An inherited method can use the same object's fields even when the method declaration is in its parent class.

Fig. 3.4 The required hierarchy and common linked storage representation. [svg] [png]

Constructors are not inherited. A <<new>> entry denotes a constructor declared by that class. The concrete constructors must establish an empty queue with size equal to 0 and head equal to null; the custom constructor must also preserve its non-null comparator reference value.

The constructor example shows the empty state of the provided oracle queues. Their runtime class names belong to the oracle implementation; use the required student class hierarchy shown here when writing your own implementation.

cs1302.p3.BaseLinkedUrgencyQueue

Implement the abstract generic class BaseLinkedUrgencyQueue in src/cs1302/p3/BaseLinkedUrgencyQueue.java. It directly implements UrgencyQueue<ItemType> and declares package-private int size and Node<ItemType> head fields. These fields are shared by inheritance with both concrete implementations; do not redeclare them in either subclass.

Fig. 3.5 Members declared by the abstract base, including its constructor, and the remaining inherited abstract obligations. Constructors are not inherited. [svg] [png]

Implement the methods listed as declared in this class according to the UrgencyQueue interface contract. The remaining abstract operations are implemented in the concrete subclasses. Shared operations must work for either ordering policy and must not depend on a concrete child class. Use the existing interface operations when one shared operation needs behavior supplied by a concrete queue.

The base constructor establishes the empty state. Throughout normal operation, size must agree with the number of reachable item nodes. For an empty queue, head has the value null. For a nonempty queue, head refers to the first node, which stores the most urgent item's reference value. Following the next-node reference values reaches the remaining items in urgency order and eventually a node whose next value is null.

cs1302.p3.LinkedUrgencyQueue

Implement LinkedUrgencyQueue in src/cs1302/p3/LinkedUrgencyQueue.java with type parameter ItemType extends Comparable<ItemType> and parent class BaseLinkedUrgencyQueue<ItemType>. Its public no-argument constructor initializes an empty queue through the base constructor.

Fig. 3.6 The natural-order queue's declarations and relevant members inherited from the shared base. [svg] [png]

Implement enqueue, dequeueMany(int), and filter in this class. Compare items using their natural ordering and preserve FIFO order for equal urgency. The queue result produced by either of the latter two methods must be a new LinkedUrgencyQueue object with the same item type. Preserve the distinction between filtering without modifying the calling queue and dequeuing items from that queue.

The provided Person class implements Comparable<Person>. You can therefore write tests for UrgencyQueue<Person> using an OracleLinkedUrgencyQueue<Person> object immediately, then run those same tests using a LinkedUrgencyQueue<Person> object once you have implemented the class. Refer to the OracleLinkedUrgencyQueue API documentation for the provided implementation, whose type parameter is declared as ItemType extends Comparable<ItemType>.

Important

The provided Person class is used in examples throughout the project's API documentation. These are runnable examples, not merely theoretical illustrations. You can run them right now by placing the example statements in the main method of a driver or tester class, adding the required imports, and compiling and running the class with cs1302-urgency-queue.jar on the classpath. You do not need to finish your queue implementation before trying examples that use the provided oracle.

cs1302.p3.CustomLinkedUrgencyQueue

Implement CustomLinkedUrgencyQueue in src/cs1302/p3/CustomLinkedUrgencyQueue.java with type parameter ItemType and parent class BaseLinkedUrgencyQueue<ItemType>. Declare a private Comparator<ItemType> field named comparator. Its public constructor accepts that comparator, rejects null with NullPointerException, and initializes an empty queue.

Fig. 3.7 The custom-order queue's declarations, its own comparator field, and relevant members inherited from the shared base. [svg] [png]

Implement enqueue, dequeueMany(int), and filter using the supplied comparator's ordering. Preserve FIFO order for equal urgency. Both queue-producing methods must create a new CustomLinkedUrgencyQueue object that uses the same comparator. Copying that reference value does not copy the comparator object. The custom queue does not impose a Comparable upper bound on its class type parameter.

You can use the provided Movie class and Person class to write tests for UrgencyQueue<Movie> or UrgencyQueue<Person>, using an OracleCustomLinkedUrgencyQueue<Movie> object or an OracleCustomLinkedUrgencyQueue<Person> object, respectively. Refer to the OracleCustomLinkedUrgencyQueue API documentation for this provided implementation. Its type parameter is ItemType, with no explicit Comparable upper bound.

Supply a comparator to each queue constructor. You can create your own comparators by writing concrete classes that implement Comparator<Movie> or Comparator<Person>, or by using lambda expressions. You can also use the comparators provided by the methods in Movie.Order and Person.Order, respectively. Once you have implemented CustomLinkedUrgencyQueue, run the same tests using your implementation with the same comparators.

Important

The provided Movie and Person classes are used in examples throughout the project's API documentation. These are runnable examples, not merely theoretical illustrations. You can run them right now by placing the example statements in the main method of a driver or tester class, adding the required imports, and compiling and running the class with cs1302-urgency-queue.jar on the classpath. You do not need to finish your queue implementation before trying examples that use the provided oracle.

Hidden Test Cases (100 points)

The bulk of your grade will be derived from functional test cases executed against your compiled classes by our automated test suite on Odin. These tests will verify:

• Correct insertion ordering in enqueue according to natural (Comparable) and custom (Comparator) orderings.

• Correct FIFO tie-breaking for items of equal urgency.

• Proper tracking of queue size() and empty state.

• Correct values returned and removed by peek(), dequeue(), and dequeueMany().

• Correct behavior of functional methods (filter, dequeue(Consumer), dequeueMany(int, Consumer)).

• The method type parameter SubType extends ItemType in enqueueAll and correct array generation and item ordering in toArray.

• Strict adherence to exception-throwing specifications (e.g., NullPointerException, IllegalStateException, IllegalArgumentException).

3.6. Non-Functional Requirements

A non-functional requirement specifies criteria that can be used to judge your submission independently from its function or behavior. If functional requirements describe what your submission should do, then the non-functional requirements describe how your submission is supposed to be. If your submission does not satisfy a non-functional requirement listed in this section, then the requirement's point total is deducted from your submission grade.

Missing Parts (45 points)

You are expected to submit all three parts of this project as described elsewhere in this document. 15 points will be subtracted from your earned point total for each missing part, up to a maximum deduction of 45 points.

Environment and Structure (100 points)

This project targets Java 25 and must compile and run correctly on Odin using JDK 25. Your directory structure and package structure should match the structure of the starter code.

• The source root must be a direct subdirectory of cs1302-urgency-queue named src. Place package directories beneath this source root.

  • The only .java files that you should include are BaseLinkedUrgencyQueue.java, LinkedUrgencyQueue.java, CustomLinkedUrgencyQueue.java, and QueueTester.java (as well as the .java files for any child classes of QueueTester that you create, if applicable).

  • The BaseLinkedUrgencyQueue.java, LinkedUrgencyQueue.java, CustomLinkedUrgencyQueue.java, and QueueTester.java files (as well as the .java files for any child classes of QueueTester that you create, if applicable) are expected to compile without any errors or warnings on Odin using:

    javac --release 25 -d bin -cp cs1302-urgency-queue.jar \
        -Xlint:rawtypes -Xlint:unchecked -Werror \
        src/cs1302/p3/*.java src/cs1302/test/*.java
    

• The compiled class root must be a subdirectory of cs1302-urgency-queue named bin. The compilation command creates package directories beneath it.

  • If you include compiled code with your submission, then it will be ignored. Graders are instructed to recompile your submission on Odin before testing your submission.

• The location of your generated API documentation website files should be a sub-directory of cs1302-urgency-queue called doc.

  • See the API Documentation Website non-functional requirement for more information about what should be in the doc directory.

If a problem is encountered for your submission that is explicitly described above, then 100 points will be subtracted from your earned point total; however, if the problem is compilation-related or structure-related and NOT explicitly described above, then it will be handled on an individual basis.

Code Style (20 points)

Every .java file that you include as part of your submission for this project must be in valid style as defined in the CS1302 Code Style Guide. All of the individual code style guidelines listed in the style guide document are considered for this requirement.

If check1302 on Odin reports any style violations for your submission, then 5 points will be subtracted from your earned point total for each violation, up to a maximum deduction of 20 points.

API Documentation Website (5 points)

Generate the API documentation website for all of the code in the cs1302.test and cs1302.p3 packages into a directory named doc directly inside your cs1302-urgency-queue directory, then host the documentation on Odin using cs1302-urgency-queue-doc as the name for your symbolic link. Instructions describing how to do both of those things are provided in the Javadoc and API Documentation chapter.

Assuming you are directly inside your cs1302-urgency-queue directory, the command below can be used to generate the website files and place them in the doc directory:

javadoc --release 25 -d doc \
    -cp cs1302-urgency-queue.jar \
    -sourcepath src \
    -subpackages cs1302

To host the API documentation website so that it is accessible via your Webwork URL, create a symbolic link to your project's doc directory at ~/public_html/cs1302-urgency-queue-doc using the ln command by adapting the instructions in Hosting the API Documentation Website. You only need to create the symbolic link once, assuming you create it correctly.

If your doc directory is missing OR does not contain the appropriate files, then 5 points will be subtracted from your earned point total. This will be checked for each part, so make sure to double check your doc directory and the generated website to make sure they are up to date prior to submitting each part of the project.

SUBMISSION.md (5 points)

Create or update the file named SUBMISSION.md inside the cs1302-urgency-queue directory to include the following information:

1. Your name and UGA ID number; and

2. The full link to the API documentation website that you generated and hosted to satisfy the related non-functional requirement stated earlier.

Create this file yourself; it is not supplied in the starter code. For example:

Sally Smith (811-000-999)
https://webwork.cs.uga.edu/~user/cs1302-urgency-queue-doc

Be sure to modify the contents of SUBMISSION.md with your information. Although the file extension is .md, the SUBMISSION.md file is just a plain text file that you can edit with a text editor like Emacs.

If your SUBMISSION.md file is missing OR does not contain the appropriate information, then 5 points will be subtracted from your earned point total. This will be checked for each part, so make sure to double check your SUBMISSION.md file prior to submitting each part of the project.

Git Commit Log (15 points)

The files in your project submission must be under version control and fully committed using Git, and your Git commit log should indicate progress since the project was assigned or since the last part was due, whichever is more recent.

Each part of the project requires you to make several commits, so this shouldn't be a problem so long as you are following the instructions in the Project Checklist.

If no such progress is indicated via your commit log, then 5 points will be subtracted from your earned point total for each applicable part, up to a maximum deduction of 15 points.

Node Sequence Storage (100 points)

You must use a singly linked chain of Node<ItemType> objects for the internal storage of items in your queue implementations. Unlike an array-based implementation, this type of storage is not limited to a fixed capacity (because there is no underlying array); instead, it is limited only by the available memory for the Java program using the urgency queue object.

If you use Java's java.util.LinkedList class, java.util.ArrayList, java.util.PriorityQueue, or something similar (e.g., any class that implements java.util.Collection), then that will result in an immediate violation of this non-functional requirement, regardless of any use of Node objects elsewhere in the class. This requirement also prohibits any use of third-party implementations of list- or queue-like data structures.

No Implementation Dependencies (100 points)

You are not permitted to use one implementation of the UrgencyQueue<ItemType> interface in another implementation. For example, you cannot use the CustomLinkedUrgencyQueue class inside of your LinkedUrgencyQueue class or vice versa. Additionally, BaseLinkedUrgencyQueue cannot depend on either of its child implementations; however, it can (and should) depend on the UrgencyQueue<ItemType> interface itself. If you have any questions about this, then please ask your instructor.

From the project root, compile first:

./compile.sh

Then inspect class dependencies:

jdeps -v -cp cs1302-urgency-queue.jar bin

In the output, A -> B means that class A depends on type B. These abbreviated examples illustrate permitted dependencies:

cs1302.p3.LinkedUrgencyQueue       -> cs1302.p3.BaseLinkedUrgencyQueue
cs1302.p3.BaseLinkedUrgencyQueue   -> cs1302.gen.UrgencyQueue
cs1302.p3.BaseLinkedUrgencyQueue   -> cs1302.gen.Node
cs1302.p3.CustomLinkedUrgencyQueue -> java.util.Comparator
cs1302.test.QueueTester           -> cs1302.p3.LinkedUrgencyQueue

These dependencies violate the implementation or library restrictions:

cs1302.p3.LinkedUrgencyQueue       -> cs1302.p3.CustomLinkedUrgencyQueue
cs1302.p3.CustomLinkedUrgencyQueue -> cs1302.p3.LinkedUrgencyQueue
cs1302.p3.BaseLinkedUrgencyQueue   -> cs1302.p3.LinkedUrgencyQueue
cs1302.p3.BaseLinkedUrgencyQueue   -> cs1302.oracle.OracleLinkedUrgencyQueue
cs1302.p3.LinkedUrgencyQueue       -> java.util.Arrays
cs1302.p3.LinkedUrgencyQueue       -> java.util.PriorityQueue

The tester is allowed to depend on concrete student classes and oracle classes so that its construction hook can select them. The restriction applies to dependencies between queue implementations, not to those testing dependencies.

jdeps reports dependencies on classes, not individual method calls. A dependency on System does not identify whether your code calls System.arraycopy, and an array's clone() call need not appear as a distinctive class dependency. Inspect your source for those prohibited calls as well as inspecting the dependency report.

No java.util.Arrays Dependencies (or similar; 100 points)

You are also NOT allowed to use the java.util.Arrays class. You can also check for the presence of this dependency using jdeps as described in an earlier requirement — you don't want to see java.util.Arrays anywhere in the output. The System.arraycopy method and the array clone() method are also not allowed for similar reasons. You can use C-s and C-r in Emacs to search your source files for any occurrences of these prohibited methods.

3.7. Submission Instructions

You will submit each part of your project on Odin from the parent directory of your cs1302-urgency-queue repository.

How to Submit

1. From inside cs1302-urgency-queue, run the provided compile.sh script to compile, check style, and regenerate documentation:

   ./compile.sh
   

   Run the applicable tests described in Compile, Test, and Retest. For Parts 2 and 3, require the completed implementation's tests to pass. For Part 1, distinguish the passing oracle checks from expected student stub failures.

2. Verify that doc is current and that its hosted website works.

3. Verify SUBMISSION.md has been updated.

4. Ensure your work is staged and committed using git:

   git status
   

   git add src/ doc/ SUBMISSION.md
   git commit -m "..."
   

5. Change to the directory immediately above cs1302-urgency-queue and execute the submission command for the part you are submitting:

   cd ..
   

   submit1302 cs1302-urgency-queue partN
   

   Replace partN with part1, part2, or part3.

6. Verify that a receipt file beginning with rec has been placed inside your cs1302-urgency-queue directory.

3.8. Frequently Asked Questions

What is an Urgency Queue?

An urgency queue is a collection that stores elements where each item has an associated priority or urgency. Unlike a standard FIFO queue where elements are dequeued in the order they arrived, an urgency queue always serves the most urgent item first. In this project, when two items have the same urgency, the tie is broken using FIFO order (the item enqueued earlier is dequeued first).

How do I test for expected exceptions?

Follow the exception type documented for the method and situation being tested. For example, when queue refers to an empty urgency queue, dequeue() must complete abruptly with IllegalStateException:

try {
    queue.dequeue();
    throw new AssertionError("Expected IllegalStateException");
} catch (IllegalStateException expected) {
    // The required exception was thrown.
} // try

If the method call completes normally, the assertion fails. A different exception escapes this catch clause and fails the test. For dequeueMany, test negative counts and counts greater than the queue's size separately because their required exception types differ. For an operation required to leave the queue unchanged on failure, also compare its state before and after the call.

Why can't I use java.util.Arrays?

The purpose of this assignment is to develop your understanding of fundamental data structures, reference manipulation, and algorithms from first principles. Using utility libraries like java.util.Arrays circumvents the core learning objectives of the course.