Module cs1302uga.gen
Package cs1302.gen

Interface Queue<T,Q extends Queue<T,Q>>

Type Parameters:
T - the type of items held in this queue
Q - the queue type
All Known Subinterfaces:
UrgencyQueue<Type>
All Known Implementing Classes:
OracleCustomLinkedUrgencyQueue, OracleLinkedUrgencyQueue, OracleQueue
public interface Queue<T,Q extends Queue<T,Q>>
Represents a standard queue. Queue<T, Q> is a generic, abstract data type that defines basic operations for a standard queue. From an external perspective, each queue object maintains a "line" of zero or more items (i.e., non-null references to objects of type T).
illustration of queue
A standard queue

Some items in a standard queue have special names:

first item

Refers to the item at the front of the "line" of items maintained by a queue. The first item can be examined using peek(), and it can be be removed using dequeue().

last item

Refers to the item at the back of the "line" of items maintained by this queue.

FIFO Semantics

Objects that implement Queue<T, Q> interface typically, but do not necessarily, order their items according to FIFO (first-in-first-out) semantics. Notable exceptions include implementations of the child interface UrgencyQueue<T, Q>, which order their items according to their relative level of urgency. If an implementing class does not order its items according to FIFO semantics, then it MUST explicitly state so in its documentation. Otherwise, users should assume FIFO semantics.

Examples

A sample "oracle" implementation of this interface with FIFO semantics is provided here. Some code examples are provided below that use the "oracle" implementation to illustrate some basic queue operations.

Example 1: Creating a new queue

To get started, we create a new "oracle" queue: 
// create a new queue
var queue = new OracleQueue<String>();
illustration of empty queue
An empty queue

Example 2: Enqueue an item to an empty queue

Let us enqueue an item to our empty queue — since FIFO semantics are assumed, the very first item that we enqueue becomes the first item and the last item in the queue: 
// confirm "before" state -- should be empty
System.out.println(queue);        // []
System.out.println(queue.size()); // 0

// perform operation
queue.enqueue("a");

// confirm "after" state
System.out.println(queue);        // [a]
System.out.println(queue.size()); // 1
illustration of queue with one item
A FIFO-based queue with one item
Note: In subsequent code examples, we will omit the code that checks the "after" state since the diagrams we include already illustrate that information.

Example 3: Enqueue a second item to a queue

Let us enqueue a second item into our queue — since FIFO semantics are assumed, the second item that we enqueue becomes the last item in the queue: 
System.out.println(queue);        // [a]
System.out.println(queue.size()); // 1

queue.enqueue("b");
illustration of queue with two items
A FIFO-based queue with two items

Example 4: Enqueue additional items to a queue

Let us enqueue two more items — since FIFO semantics are assumed, these items are placed after any existing items, and the last item enqueued becomes the last item in the queue: 
System.out.println(queue);        // [a, b]
System.out.println(queue.size()); // 2

queue.enqueue("c");
queue.enqueue("d");
illustration of queue with four items
A FIFO-based queue with four items

Example 5: Dequeue some items from a non-empty queue

Now we dequeue some items — since FIFO semantics are assumed, the current first item in the queue is always dequeued, if available: 
System.out.println(queue);        // [a, b, c, d]
System.out.println(queue.size()); // 4

System.out.prinln(queue.dequeue()); // a
System.out.prinln(queue.dequeue()); // b
illustration of queue after some dequeues
A FIFO-based queue after some dequeues

Example 6: Peek at the first item in a non-empty queue

Let us peek at the queue — since FIFO semantics are assumed, the current first item in the queue is always returned, if available, but not removed: 
System.out.println(queue);        // [c, d]
System.out.println(queue.size()); // 2

System.out.prinln(queue.peek()); // c
System.out.prinln(queue.peek()); // c
illustration of queue after some peeks
A FIFO-based queue after some peeks

Example 7: Enqueue additional items after some dequeues

Let us enqueue two more items — since FIFO semantics are assumed, these items are placed after any existing items, and the last item enqueued becomes the last item in the queue: 
System.out.println(queue);        // [c, d]
System.out.println(queue.size()); // 2

queue.enqueue("1"); // placed "after" d
queue.enqueue("2"); // placed "after" 1
illustration of queue after some more enqueues
A FIFO-based queue after some more enqueues

Example 8: Dequeue all items

System.out.println(queue);          // [c, d, 1, 2]
System.out.println(queue.size());   // 4

System.out.prinln(queue.dequeue()); // c
System.out.prinln(queue.dequeue()); // d
System.out.prinln(queue.dequeue()); // 1
System.out.prinln(queue.dequeue()); // 2
illustration of empty queue
An empty queue

Additional Examples

Some additional examples can be found in the method detail sections for several methods.

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).

Consider a FIFO-based queue that contains some Movie objects populated with IMDb data: 

var queue = new OracleQueue<Movie>();
queue.enqueueAll(Movie.Data.IMDB_TOP_MOVIES);
System.out.println(queue.size()); // 250
Now suppose that we want to describe the user-specified action behavior for a future call to dequeue(action) or dequeueMany(num, action)}. Since action has type Consumer, we can do this by creating a class that implements that interface: 
public class MoviePrinter implements Consumer<Movie> {

    @Override
    public void accept(Movie movie) {
        System.out.printf("%s (%s)\n", movie.name(), movie.year());
        System.out.println("* Directed by:");
        for (Movie.Member director : movie.directors()) {
            System.out.printf("  * %s\n", director.name());
        } // for
        System.out.println();
    } // accept

} // MoviePrinter
To specify that dequeue(action) should print the movie that it dequeues using a MoviePrinter object, we first construct a MoviePrinter object, then supply it as the implementing object for the behavioral parameter action in our call to dequeue: 
Consumer<Movie> printMovie = new MoviePrinter();
queue.dequeue(printMovie);
Here is the output: 
The Shawshank Redemption (1994)
* Directed by:
  * Frank Darabont
The same implementing object can be used in other calls that require an implementing object for a behavioral parameter to be supplied: 
queue.dequeueMany(2, printMovie);
Here is the output: 
The Godfather (1972)
* Directed by:
  * Francis Ford Coppola

The Dark Knight (2008)
* Directed by:
  * Christopher Nolan
Since the interfaces for behavior parameters are functional, users MAY also create an implementing object using a lambda expression or method reference. Here is an example that uses a lambda expression: 
Consumer<Movie> printMovieNumWriters = (Movie movie) -> {
   System.out.printf(
       "%s (%s): %d",
       movie.name(),
       movie.year(),
       movie.writers().size()
   );
};

queue.dequeueMany(2, printMovieNumWriters);
Here is the output: 
The Godfather Part II (1974): 2
12 Angry Men (1957): 1
Schindler's List (1993): 2
The Lord of the Rings: The Return of the King (2003): 3

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.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Removes all items from this queue.
    T
    dequeue()
    Removes and examines the first item in this queue.
    void
    dequeue(Consumer<T> action)
    Removes the first item in this queue, then performs the given action on that item.
    Q
    dequeueMany(int num)
    Builds and returns a new queue that contains the first num items dequeued from this queue.
    void
    dequeueMany(int num, Consumer<T> action)
    Removes the most urgent num items in this queue and performs the given action (using action.accept) on each item.
    boolean
    enqueue(T item)
    Inserts the specified item into this queue.
    <S extends T>
    boolean
    enqueueAll(Iterable<S> items)
    Enqueues the items contained in the specified Iterable into this queue.
    Q
    filter(Predicate<T> cond)
    Builds and returns a new queue consisting of the items of this queue that pass the test specified by the given predicate.
    T
    peek()
    Examines the first item in this queue.
    int
    size()
    Return the number of items in this queue.
    T[]
    toArray(IntFunction<T[]> generator)
    Returns an array containing all of the objects in this queue in proper sequence (from first to last element, by urgency).
    String
    toString()
    Returns a string representation of this queue.

  • Method Details

    • size

      int size()
      Return the number of items in this queue.
      Returns:
      the number of items in this queue
      Implementation Requirements:
      This method MUST NOT modify the calling object.

    • clear

      void clear()
      Removes all items from this queue.

    • enqueue

      boolean enqueue(T item)
      Inserts the specified item into this queue. If FIFO semantics apply, then the inserted item becomes the last item in this queue (i.e., it is placed after any existing items).
      Parameters:
      item - the item to insert
      Returns:
      true if this queue was modified as a result of this call; false otherwise
      Throws:
      NullPointerException - if item is null

    • peek

      T peek()
      Examines the first item in this queue. This method returns, but does not remove, the first item. If FIFO semantics apply, then users can safely assume that this item was inserted into the queue before any other items in this queue.
      Returns:
      the first item in this queue
      Throws:
      IllegalStateException - if there are no items in the queue
      Implementation Requirements:
      This method MUST NOT modify the calling object.

    • dequeue

      T dequeue()
      Removes and examines the first item in this queue. This method returns the item that it removes. If FIFO semantics apply, then users can safely assume that this item was inserted into the queue before any remaining items in this queue.
      Returns:
      the first item in this queue
      Throws:
      IllegalStateException - if there are no items in the queue

    • dequeue

      void dequeue(Consumer<T> action)
      Removes the first item in this queue, then performs the given action on that item.

      Here is some example code that illustrates how this method behaves, assuming FIFO semantics — you should assume that queue already exists: 

      // confirm state of queue
System.out.println(queue);        // [a, b, c, d]
System.out.println(queue.size()); // 4
      Consumer<String> printer = (String item) -> {
    System.out.println(item);
};

queue.dequeue(printer); // prints: a
queue.dequeue(printer); // prints: b
      List<String> list = new ArrayList<String>();
Consumer<String> append = (String item) -> {
    list.add(list);
};

action.accept("world");  // appends: world
queue.dequeue(append);   // appends: c
queue.dequeue(append);   // appends: d

System.out.println(list); // [c, d]
      Parameters:
      action - the action to be performed on the removed item.
      Throws:
      NullPointerException - if the specified action is null.
      IllegalStateException - if there are no items in the queue.
      See Also:
      API Notes:
      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.

    • dequeueMany

      Q dequeueMany(int num)
      Builds and returns a new queue that contains the first num items dequeued from this queue.

      Here is some example code that illustrates how this method behaves, assuming FIFO semantics — you should assume that oldq already exists: 

      // confirm state of old queue
System.out.println(oldq);        // [a, b, c, d]
System.out.println(oldq.size()); // 4

// dequeue two items from oldq
var newq = oldq.dequeueMany(2);

// confirm state of old queue
System.out.println(oldq);        // [c, d]
System.out.println(oldq.size()); // 2

// confirm state of new queue
System.out.println(newq);        // [a, b]
System.out.println(newq.size()); // 2
      Parameters:
      num - the number of items to remove and include in the new queue
      Returns:
      a new queue object containing the first num items dequeued from this queue
      Throws:
      IllegalArgumentException - if num < 0.
      IllegalStateException - if num > size().
      Implementation Requirements:
      The new object MUST be the same type as the calling object.

    • dequeueMany

      void dequeueMany(int num, Consumer<T> action)
      Removes the most urgent num items in this queue and performs the given action (using action.accept) on each item.
      Parameters:
      num - the number of items to remove.
      action - the action to be performed on the removed items.
      Throws:
      NullPointerException - if the specified action is null.
      IllegalArgumentException - if num < 0.
      IllegalStateException - if num > size().
      See Also:
      API Notes:
      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.

    • enqueueAll

      <S extends T> boolean enqueueAll(Iterable<S> items)
      Enqueues the items contained in the specified Iterable into this queue. This method should return false if the specified Iterable is empty. Otherwise, this method either returns true or throws an exception upon failure.

      Here is an example, assuming queue refers to an empty queue with FIFO semantics: 

      import java.util.List;
import java.util.Iterable;
      // create an iterable
Iterable<String> items = List.<String>of("a", "b", "c");

// confirm "before" state
System.out.println(queue);        // []
System.out.println(queue.size()); // 0

// enqueue the items
var newq = queue.enqueueAll(items);

// confirm "after" state
System.out.println(queue);        // [a, b, c]
System.out.println(queue.size()); // 3
      Type Parameters:
      S - the type of the items to be added.
      Parameters:
      items - the items to add to this queue.
      Returns:
      true if this queue is changed as a result of the call; false otherwise.
      Throws:
      NullPointerException - if items is null.
      IllegalArgumentException - if any of the items in the specified Iterable are null.
      Implementation Requirements:
      The calling object MUST NOT be modified if any item in items is null.

    • toString

      String toString()
      Returns a string representation of this queue. The string representation consists of each item in the queue, from first to last, separated by the characters ", " (comma and space) with opening and closing square brackets ("[", "]") at the beginning and end, respectively. Each item of the queue is represented by the string value returned by its toString() method. If FIFO semantics apply, then the items in the resulting string will appear in the same order they were enqueued.

      Here is an example, assuming queue refers to an empty queue with FIFO semantics: 

      queue.enqueue("a");
queue.enqueue("b");
queue.enqueue("c");

System.out.println(queue); // [a, b, c]
      Overrides:
      toString in class Object
      Returns:
      the string representation of this queue
      Implementation Requirements:
      This method MUST NOT modify the calling object.

    • toArray

      T[] toArray(IntFunction<T[]> generator)
      Returns an array containing all of the objects in this queue 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.
      Parameters:
      generator - a function which produces a new array of the desired type and the provided size.
      Returns:
      an array containing all of the items in this queue in proper sequence.
      Throws:
      NullPointerException - if generator is null.
      Implementation Requirements:
      This method MUST NOT modify the calling object.

    • filter

      Q filter(Predicate<T> cond)
      Builds and returns a new queue consisting of the items of this 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 UrgencyQueue containing all items e in this queue such that cond.test(e) returns true.
      Parameters:
      cond - the predicate used to test items of this queue.
      Returns:
      a reference to the filtered queue.
      Throws:
      NullPointerException - if the specified predicate is null.
      See Also:
      API Notes:
      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.
      Implementation Requirements:
      The new object MUST be the same type as the calling object. This method MUST NOT modify the calling object.