public interface UrgencyQueue<Type>
extends Queue<Type,UrgencyQueue<Type>>
An abstract data type that defines 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
Type). 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.
Some items in an urgency queue have special names:
most urgent item
Refers to the item at the front of the "line" of items
maintained by an urgency queue. The most urgent item can be examined
using peek(), and it can be be removed using dequeue().
least urgent item
Refers to the item at the back of the "line" of items
maintained by an urgency queue.
The figure below illustrates what an urgency queue with five items might look like
internally under two assumptions: i) each item has an integer associated with it;
and ii) the urgency queue uses the natural ordering for integers to
determine its urgency order. Multiple items with the same level of urgency
appear adjacent to each other and in the same order that they were
enqueued.
An urgency queue that uses the natural ordering for integers to determine its item order.
Ordering by Level of Urgency
Implementing classes MUST provide a way to compare items by their level of
urgency. This is typically done in one of two ways:
An implementing class can use <Type extends Comparable<Type>> for
its type parameter declaration to ensure that Type can only be
parameterized (i.e., replaced when used) with a class that implements
Comparable<Type> — this syntax expresses an upper bound
for the type parameter Type. If an implementing class does this, then its
code can directly determine the relative level of urgency between two
items of type Type using the
natural ordering defined by the item type's
compareTo(Type) method —
such classes MUST include at least one zero-parameter (default), public
constructor.
Here is a declaration for a class called ImplClass
that implements UrgencyQueue by imposing a comparable upper
bound:
public class ImplClass<Type extends Comparable<Type>> implements UrgencyQueue<Type> {
public ImplClass() {
} // ImplClass
} // ImplClass
Inside the instance methods of this class, any two items of type Type can
be compared using their compareTo(Type)
method. For example, if a and b are of type Type, then
the return value of a.compareTo(b) can determine their relative level
of urgency:
Determining Order: Comparable Upper Bound
int ret = a.compareTo(b)
Return Value
Order
ret < 0
a
is less urgent than
b
ret == 0
a
has the same level of urgency as
b
ret > 0
a
is more urgent than
b
A sample "oracle" implementation of this interface with a comparable
upper bound is provided by the OracleLinkedUrgencyQueue
class. Some code examples later in this documentation are provided that
use the this "oracle" implementation to illustrate some basic
urgency queue operations.
Comparator Constructor Parameter
An implementing class that does not impose a
comparable upper bound MUST
allow users to specify urgency ordering via a constructor
parameter of type Comparator<Type>
(i.e., a comparator) — such classes MUST include at least
one single-parameter, public constructor that accepts a
the Comparator<Type> object that will be used for ordering.
Although Type does not have an explicit upper bound requirement
in this scenario, the implementing class can still determine the
relative level of urgency between two items using the ordering imposed
by the comparator (i.e., it uses the comparator's
compare(Type, Type) method
to determine the order).
Here are the class and constructor declarations for a class called
ImplClass that implements UrgencyQueue by
requiring a comparator constructor parameter — it's not shown
in the code snippet, but the constructor should save a reference to
the supplied comparator object for later use by the instance
methods of the class:
public class ImplClass<Type> implements UrgencyQueue<Type> {
public ImplClass(Comparator<Type> cmp) {
} // ImplClass
} // ImplClass
Inside the instance methods of this class, any two items of type Type can
be compared using the comparator's compare(Type, Type)
method. For example, if a and b are of type Type, then
the return value of cmp.compare(a, b)) can determine their relative level
of urgency:
A sample "oracle" implementation of this interface with a comparator
constructor parameter is provided by the
OracleCustomLinkedUrgencyQueue
class. Some code examples later in this documentation are provided that
use the this "oracle" implementation to illustrate some basic
urgency queue operations.
Examples
The examples provided in this documentation utilize different item
types to illustrate urgency-based semantics. With that in mind, you
may need to import things when trying the examples out for
yourself — we will provide links to relevant classes and
interfaces in the exposition provided for each example.
Example 1: Comparable Upper Bound
Since Integer implements Comparable<Integer>, it can
be used as the item of an implementation that uses a
comparable upper bound to
determine relative order of urgency — here is a quick example
using the provided OracleLinkedUrgencyQueue class:
// new queue
UrgencyQueue<Integer> queue = new OracleLinkedUrgencyQueue<Integer>();
// enqueue some items
queue.enqueue(2);
queue.enqueue(1);
queue.enqueue(3);
queue.enqueue(0);
// define a "printNum" action
Consumer<Integer> printNum = (Integer num) -> {
System.out.printf("dequeued %d\n", num);
};
// dequeue and print all items
queue.dequeueMany(queue.size(), printNum);
Since the natural ordering defined by Integer.compareTo(java.lang.Integer)
considers the integer values directly, each item's level of urgency is
the same as its integer value. Here is the output:
dequeued 3
dequeued 2
dequeued 1
dequeued 0
Example 2: Another Comparable Upper Bound
Since the Person class provided in the
cs1302.oracle.model package implements
Comparable<Person>, it can also be
used as the item of an implementation that uses a
comparable upper bound to
determine relative order of urgency — here is a quick example
using the provided OracleLinkedUrgencyQueue class:
// new queue
UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
// define some items -- store items in a java.util.List<Person> object
Iterable<Person> people = List.<Person>of(
new Person(23, "Bob"),
new Person(23, "Sue"),
new Person(24, "Ash"),
new Person(22, "Cal")
);
// enqueue all items
queue.enqueueAll(people);
// define a "printPerson" action using a lambda expression
Consumer<Person> printPerson = (Person person) -> {
System.out.println(person);
};
// dequeue and print all items
queue.dequeueMany(queue.size(), printPerson);
Since the natural ordering defined by Person.compareTo(cs1302.oracle.model.Person)
considers both the Person.age() and Person.name() of a
Person object (in that order), each item's level of urgency is
based on both its integer age() value and its string name()
value. Here is the output — that is why Person[age=23, name=Sue]
is considered more urgent than Person[age=23, name=Bob]:
Sometimes users want more control over the ordering of items.
For example, while the natural ordering for Person
object considers both their age() and name(),
some users may only want to order Person objects by their
age() age(). This can be done by defining a comparator that imposes
the desired ordering, then using that comparator with an urgency
queue implementation that requires a
comparator constructor parameter
— here is a quick example using the provided
OracleCustomLinkedUrgencyQueue class:
Here are a few different ways to define a comparator for Person objects
that only considers their age() when performing comparisons
— the ordering imposed by all of these examples is related to the
natural ordering for integers since age() returns
an int:
// use a provided comparator
Comparator<Person> byAge = Person.Order.byAge();
// create your own comparator -- manually determine order
Comparator<Person> byAge = (Person a, Person b) -> {
return a.age() - b.age();
};
// create your own comparator -- use static utility method to determine order
Comparator<Person> byAge = (Person a, Person b) -> {
return Integer.compare(a.age(), b.age());
};
// create queue
UrgencyQueue<Person> queue = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
// define some people
Iterable<Person> people = List.<Person>of(
new Person(23, "Bob"),
new Person(23, "Sue"),
new Person(24, "Ash"),
new Person(22, "Cal")
);
// enqueue some people
queue.enqueueAll(people);
// define a "printPerson" action
Consumer<Person> printPerson = (Person person) -> {
System.out.println(person.age() + ": " + person.name());
};
// dequeue and print all items
queue.dequeueMany(queue.size(), printPerson);
Since the ordering imposed by the comparator only
considers the age() of a Person object,
each item's level of urgency in this scenario is simply
its integer age() value. Here is the output —
notice that Person[age=23, name=Bob] is considered more urgent
than Person[age=23, name=Sue] because of the imposed ordering
and the order in which both were enqueued:
24: Ash
23: Bob
23: Sue
22: Cal
Example 4: Reversing the Urgency Order
When you use an urgency queue implementation that requires a
comparator constructor parameter,
you get to decide what the ordering is. For example, here are a few different
ways to define a comparator for Person objects
that only considers their age(),
in reverse,
when performing comparisons
— the ordering imposed by all of these examples is related to the
natural ordering for integers since age() returns
an int:
// use a provided comparator
Comparator<Person> byAgeReversed = Person.Order.byAge().reversed();
// create your own comparator -- manually determine order
Comparator<Person> byAgeReversed = (Person a, Person b) -> {
return -1 * (a.age() - b.age());
};
// create your own comparator -- use static utility method to determine order
Comparator<Person> byAgeReversed = (Person a, Person b) -> {
return -1 * Integer.compare(a.age(), b.age());
};
// create queue
UrgencyQueue<Person> queue = new OracleCustomLinkedUrgencyQueue<Person>(byAgeReversed);
// define some people
Iterable<Person> people = List.<Person>of(
new Person(23, "Bob"),
new Person(23, "Sue"),
new Person(24, "Ash"),
new Person(22, "Cal")
);
// enqueue some people
queue.enqueueAll(people);
// define a "printPerson" action
Consumer<Person> printPerson = (Person person) -> {
System.out.println(person.age() + ": " + person.name());
};
// dequeue and print all items
queue.dequeueMany(queue.size(), printPerson);
Here is the output — as expected, when using a comparator that
considers only the age() of each Person
objects in reverse, the youngest
Person object is the most urgent:
22: Cal
23: Bob
23: Sue
24: Ash
Example 5: Another Comparator Constructor Parameter
Users may want to use an urgency queue to hold objects of a class
that does not have a natural ordering (e.g., the provided
Movie class). In such scenarios,
an urgency queue with a
comparator constructor parameter
is required.
To illustrate this concept, lets use a subset of the
the IMDb Top Movies list provided in
Movie.Data.IMDB_TOP_MOVIES. Here is some code that
gets the first 10 entries in that list and prints out their
year() and name() values:
// get some movie objects -- first 10 from IMDb top movies list
List<Movie> movies = Movie.Data.IMDB_TOP_MOVIES.subList(0, 10);
// define "printMovie" action
Consumer<Movie> printMovie = (Movie movie) -> {
Year year = movie.year(); // java.time.Year object
String name = movie.name();
System.out.printf("%s: %s\n", year, name);
};
// use the "printMovie" action to print each movie
for (Movie movie : movies) {
printMovie.accept(movie);
} // for
Here is the output:
1994: The Shawshank Redemption
1972: The Godfather
2008: The Dark Knight
1974: The Godfather Part II
1957: 12 Angry Men
1993: Schindler's List
2003: The Lord of the Rings: The Return of the King
1994: Pulp Fiction
2001: The Lord of the Rings: The Fellowship of the Ring
1966: The Good, the Bad and the Ugly
Now let us define a comparator for Movie objects that
considers their year() when performing
comparisons, then use that comparator with the provided
OracleCustomLinkedUrgencyQueue class:
// define movie comparator that orders by year
Comparator<Movie> byYear = (Movie a, Movie b) -> {
// Movie does not have a compareTo method, but java.time.Year does
return a.year().compareTo(b.year());
};
// create an urgency queue
UrgencyQueue<Movie> queue = new OracleCustomLinkedUrgencyQueue<Movie>(byYear);
// enqueue the items -- level of urgency based on cmp.compare(Movie, Movie)
queue.enqueueAll(movies);
// dequeue all items -- use "printMovie" action from earlier
queue.dequeueMany(queue.size(), printMovie);
Here is the output:
2008: The Dark Knight
2003: The Lord of the Rings: The Return of the King
2001: The Lord of the Rings: The Fellowship of the Ring
1994: The Shawshank Redemption
1994: Pulp Fiction
1993: Schindler's List
1974: The Godfather Part II
1972: The Godfather
1966: The Good, the Bad and the Ugly
1957: 12 Angry Men
User-specified Behavior
Some queue methods, such as dequeue(Consumer), dequeueMany(int, Consumer), and filter(Predicate) accept
behavioral parameters that enable part of their behavior
to be specified by the user. The parameter type of a behavioral parameter
is always a functional interface so that
user-specified behavior be described by supplying a reference
to an implementing object (i.e., an object that implements the interface).
Since the interfaces for behavioral parameters are functional,
users MAY create an implementing object using a
lambda expression or method reference in addition
to defining and instantiating an implementing class in the usual way.
Non-interference
To ensure that a queue behaves correctly both during and after a call to
a method that supports user-specified behavior
via a behavioral parameter, user-specified behavior MUST NOT
change the state of the calling queue object or any items held by the queue.
We may use the term non-interference or non-interfering
to describe this requirement in various places throughout this
documentation.
Inserts the specified item into this urgency queue. The
inserted item is placed such that it appears after any existing
items with the same or greater level of urgency and before any
existing items with a lesser level of urgency.
Returns a string representation of this urgency queue. The string
representation consists of each item in the queue, from most urgent
to least urgent, in the descending urgency order,
separated by the characters ", " (comma and space)
with opening and closing square ([, ])
at the beginning and end, respectively.
Each item of the queue is represented by the string value returned by
its toString() method.
Here is an example, assuming queue refers to an empty
UrgencyQueue<Person> object:
This method supports
user-specified behavior via
one or more of its parameters. Users MUST ensure that the
behavior that they specify is
non-interfering.
This method supports
user-specified behavior via
one or more of its parameters. Users MUST ensure that the
behavior that they specify is
non-interfering.
Builds and returns a new urgency queue consisting of the
items of this urgency queue that pass the test
specified by the given predicate. The term predicate
usually refers to some function that returns either
true or false. Here, it refers to the parameter
cond, which should refer to an object of a class that
implements the Predicate<Type> interface. More
formally, this method returns a new urgency queue
containing all items e in this queue such that
cond.test(e) returns true.
Enqueues the items contained in the specified Iterable
into this urgency queue. This method should return false if
the specified Iterable is empty. Otherwise, this method
either returns true or throws an exception upon failure.
This is a generic method; it declares its own type
parameter named SubType in addition to interface's
type parameter named Type. Since SubType is
declared with an upper bound of Type, all the items
in items are guaranteed to be type-compatible with
Type, even when Type and SubType are
not the same (which they can be).
Implementation Requirements:
The calling object must not be modified
if any item in items is null.
Returns an array containing all of the objects in this
UrgencyQueue in proper sequence (from first to last element,
by urgency). The generator parameter accepts a
reference to any method that takes an integer, which is the
size of the desired array, and produces an array of the desired
size.
Here is an example, assuming queue refers to
a nonempty UrgencyQueue<Person> object:
// print an existing, nonempty urgency queue
System.out.print("urgency queue: " + queue);
// setup an object that can generate a Person array
IntFunction<Person[]> newPersonArray = (int value) -> {
return new Person[value];
};
// get the urgency queue's items as an array
Person[] persons = queue.toArray(newPersonArray);
System.out.println("array length: " + persons.length);
System.out.println("first array element: " + persons[0]);
This method MUST NOT modify the calling object; however,
it SHOULD supply the size() of the calling queue object
when calling generator.apply(int) to create the new
array.
