Class OracleLinkedUrgencyQueue<ItemType extends Comparable<ItemType>>

java.lang.Object
cs1302.oracle.OracleLinkedUrgencyQueue<ItemType>
Type Parameters:
ItemType - the item type
All Implemented Interfaces:
Queue<ItemType, UrgencyQueue<ItemType>>, UrgencyQueue<ItemType>
public class OracleLinkedUrgencyQueue<ItemType extends Comparable<ItemType>> extends Object
An "oracle" implementation of UrgencyQueue that uses a linked list of Node objects to maintain its "line" of items and imposes a Comparable Upper Bound so that it can compare items. Since each item is compatible with ItemType and ItemType is required to implement Comparable<ItemType>, this class is able to directly determine the relative level of urgency between two items using the natural ordering defined by the item type's compareTo(ItemType) method.

  • Constructor Summary

    Constructors
    Constructor
    Description
    OracleLinkedUrgencyQueue()
    Construct an OracleLinkedUrgencyQueue.

  • Method Summary

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

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • OracleLinkedUrgencyQueue

      public OracleLinkedUrgencyQueue()
      Construct an OracleLinkedUrgencyQueue.

  • Method Details

    • enqueue

      public boolean enqueue(ItemType value)
      Description copied from interface: UrgencyQueue
      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.

      Examples

      The first example uses an ascending age comparator, so older people have greater urgency. Sally and Sue have equal urgency, and Sally remains first because she was enqueued before Sue.

      See the instructions for running the method examples. Each Java snippet is independent. 

      Comparator<Person> byAgeAscending = (Person a, Person b) -> {
    return Integer.compare(a.age(), b.age());
}; // lambda

UrgencyQueue<Person> queue0 = new OracleCustomLinkedUrgencyQueue<Person>(byAgeAscending);

System.out.println(queue0.enqueue(new Person(22, "Sally")));

queue0.enqueue(new Person(20, "Billy"));
queue0.enqueue(new Person(23, "Kuma"));
queue0.enqueue(new Person(22, "Sue"));

System.out.println(queue0);
      Expected output: 
      true
[Person[age=23, name=Kuma], Person[age=22, name=Sally], Person[age=22, name=Sue], Person[age=20, name=Billy]]

      The second example reverses the comparator: younger people now have greater urgency. The queue still preserves arrival order among people of the same age. 

      Comparator<Person> byAgeDescending = (Person a, Person b) -> {
    return Integer.compare(b.age(), a.age());
}; // lambda

UrgencyQueue<Person> queue1 = new OracleCustomLinkedUrgencyQueue<Person>(byAgeDescending);

System.out.println(queue1.enqueue(new Person(22, "Sally")));

queue1.enqueue(new Person(20, "Billy"));
queue1.enqueue(new Person(23, "Kuma"));
queue1.enqueue(new Person(22, "Sue"));

System.out.println(queue1);
      Expected output: 
      true
[Person[age=20, name=Billy], Person[age=22, name=Sally], Person[age=22, name=Sue], Person[age=23, name=Kuma]]

      The queue places the most urgent item first. With byAgeAscending, greater ages have greater urgency, so queue0 lists the oldest person first. With byAgeDescending, smaller ages have greater urgency, so queue1 lists the youngest person first. Sally and Sue have equal urgency under either comparator, so Sally remains before Sue because she was enqueued first.

      Parameters:
      value - the item to insert
      Returns:
      true if this urgency queue was modified as a result of this call

    • dequeueMany

      public UrgencyQueue<ItemType> dequeueMany(int num)
      Description copied from interface: UrgencyQueue
      Builds and returns a new urgency queue that contains the most urgent num items dequeued from this UrgencyQueue.

      Examples

      The following example removes the two most urgent items into a new queue.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
queue.enqueue(new Person(22, "Sally"));
queue.enqueue(new Person(20, "Billy"));
queue.enqueue(new Person(23, "Kuma"));
UrgencyQueue<Person> removed = queue.dequeueMany(2);

System.out.println("removed: " + removed);
System.out.println("remaining: " + queue);
System.out.println("distinct queues: " + (removed != queue));
System.out.println("same runtime class: " + (removed.getClass() == queue.getClass()));

UrgencyQueue<Person> empty = queue.dequeueMany(0);

System.out.println("zero result: " + empty);
System.out.println("distinct zero result: " + (empty != queue));
System.out.println("remaining after zero: " + queue);
      Expected output: 
      removed: [Person[age=23, name=Kuma], Person[age=22, name=Sally]]
remaining: [Person[age=20, name=Billy]]
distinct queues: true
same runtime class: true
zero result: []
distinct zero result: true
remaining after zero: [Person[age=20, name=Billy]]

      The result is a distinct queue of the same runtime class as the calling queue. Passing zero produces a new empty queue without removing any items.

      Parameters:
      num - the number of items to remove and return.
      Returns:
      a new urgency queue object containing the most urgent num items dequeued from this queue

    • filter

      public UrgencyQueue<ItemType> filter(Predicate<ItemType> cond)
      Description copied from interface: UrgencyQueue
      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<ItemType> interface. More formally, this method returns a new urgency queue containing all items e in this queue such that cond.test(e) returns true.

      Examples

      This example selects people aged at least 22 without removing items from the original queue.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
queue.enqueue(new Person(22, "Sally"));
queue.enqueue(new Person(20, "Billy"));
queue.enqueue(new Person(23, "Kuma"));
Predicate<Person> atLeast22 = (Person person) -> {
    return person.age() >= 22;
}; // lambda
UrgencyQueue<Person> selected = queue.filter(atLeast22);

System.out.println("selected: " + selected);
System.out.println("original: " + queue);
System.out.println("distinct queues: " + (selected != queue));
System.out.println("same first person: " + (selected.peek() == queue.peek()));
System.out.println("same runtime class: " + (selected.getClass() == queue.getClass()));
      Expected output: 
      selected: [Person[age=23, name=Kuma], Person[age=22, name=Sally]]
original: [Person[age=23, name=Kuma], Person[age=22, name=Sally], Person[age=20, name=Billy]]
distinct queues: true
same first person: true
same runtime class: true

      The predicate only examines an age. The result queue is new, but its items are copies of reference values referring to the original person objects; filtering does not clone those objects.

      Parameters:
      cond - the predicate used to test items of this queue.
      Returns:
      a reference to the filtered queue.
      See Also:

    • size

      public int size()
      Description copied from interface: UrgencyQueue
      Returns the number of items in this urgency queue.

      Examples

      The following example checks the number of items before and after insertion and removal.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();

System.out.println("empty: " + queue.size());

queue.enqueue(new Person(22, "Sally"));
queue.enqueue(new Person(23, "Kuma"));

System.out.println("after insertion: " + queue.size());

queue.dequeue();

System.out.println("after removal: " + queue.size());
      Expected output: 
      empty: 0
after insertion: 2
after removal: 1

      Each successful insertion adds one item, and this dequeue call removes one item.

      Specified by:
      size in interface Queue<ItemType, UrgencyQueue<ItemType>>
      Specified by:
      size in interface UrgencyQueue<ItemType>
      Returns:
      the number of items in this urgency queue.

    • peek

      public ItemType peek()
      Description copied from interface: UrgencyQueue
      Retrieves, but does not remove, the most urgent item in this urgency queue.

      Examples

      The following example retrieves the most urgent person without removing an item.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
queue.enqueue(new Person(22, "Sally"));
queue.enqueue(new Person(20, "Billy"));
queue.enqueue(new Person(23, "Kuma"));
Person first = queue.peek();

System.out.println("peeked: " + first);
System.out.println("size: " + queue.size());
System.out.println(queue);
      Expected output: 
      peeked: Person[age=23, name=Kuma]
size: 3
[Person[age=23, name=Kuma], Person[age=22, name=Sally], Person[age=20, name=Billy]]

      The second example attempts to peek at an empty queue. The call throws IllegalStateException, which the catch block handles by printing a message. The queue remains empty. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
try {
    queue.peek();
} catch (IllegalStateException exception) {
    System.out.println("Cannot peek at an empty queue.");
} // try

System.out.println("size: " + queue.size());
      Expected output: 
      Cannot peek at an empty queue.
size: 0

      The variable first refers to the person still held at the front of the queue. The separate empty-queue example catches the documented exception.

      Specified by:
      peek in interface Queue<ItemType, UrgencyQueue<ItemType>>
      Specified by:
      peek in interface UrgencyQueue<ItemType>
      Returns:
      the most urgent item in the queue.

    • toString

      public String toString()
      Description copied from interface: UrgencyQueue
      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.

      Examples

      This example prints the queue in descending urgency order.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
queue.enqueue(new Person(22, "Sally"));
queue.enqueue(new Person(20, "Billy"));
queue.enqueue(new Person(23, "Kuma"));

System.out.println(queue);
      Expected output: 
      [Person[age=23, name=Kuma], Person[age=22, name=Sally], Person[age=20, name=Billy]]

      The representation includes the items in queue order, enclosed in brackets and separated by a comma and space.

      Specified by:
      toString in interface Queue<ItemType, UrgencyQueue<ItemType>>
      Specified by:
      toString in interface UrgencyQueue<ItemType>
      Overrides:
      toString in class Object
      Returns:
      the string representation of this urgency queue

    • dequeue

      public ItemType dequeue()
      Description copied from interface: UrgencyQueue
      Retrieves and removes the most urgent item in this urgency queue.

      Examples

      The following example removes the most urgent person and prints the remaining queue.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
queue.enqueue(new Person(22, "Sally"));
queue.enqueue(new Person(20, "Billy"));
queue.enqueue(new Person(23, "Kuma"));
Person removed = queue.dequeue();

System.out.println("removed: " + removed);
System.out.println("remaining: " + queue);
System.out.println("size: " + queue.size());
      Expected output: 
      removed: Person[age=23, name=Kuma]
remaining: [Person[age=22, name=Sally], Person[age=20, name=Billy]]
size: 2

      The second example attempts to remove an item from an empty queue. The call throws IllegalStateException, which the catch block handles by printing a message. The queue remains empty. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
try {
    queue.dequeue();
} catch (IllegalStateException exception) {
    System.out.println("Cannot dequeue from an empty queue.");
} // try

System.out.println("size: " + queue.size());
      Expected output: 
      Cannot dequeue from an empty queue.
size: 0

      The removed variable refers to the person removed from the queue. An empty queue has no item to remove.

      Specified by:
      dequeue in interface Queue<ItemType, UrgencyQueue<ItemType>>
      Specified by:
      dequeue in interface UrgencyQueue<ItemType>
      Returns:
      the most urgent item in the queue.

    • dequeue

      public void dequeue(Consumer<ItemType> action)
      Description copied from interface: UrgencyQueue
      Removes the most urgent item in this urgency queue and performs the given action on the removed item.

      Examples

      This example supplies an action that prints the name of the removed person.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
queue.enqueue(new Person(22, "Sally"));
queue.enqueue(new Person(20, "Billy"));
queue.enqueue(new Person(23, "Kuma"));

Consumer<Person> printName = (Person person) -> {
    System.out.println("removed: " + person.name());
}; // lambda

queue.dequeue(printName);

System.out.println("remaining: " + queue);
      Expected output: 
      removed: Kuma
remaining: [Person[age=22, name=Sally], Person[age=20, name=Billy]]

      The action prints the name; it does not modify the calling queue or its items. The dequeue method performs the removal.

      Specified by:
      dequeue in interface Queue<ItemType, UrgencyQueue<ItemType>>
      Specified by:
      dequeue in interface UrgencyQueue<ItemType>
      Parameters:
      action - the action to be performed on the removed item.
      See Also:

    • dequeueMany

      public void dequeueMany(int num, Consumer<ItemType> action)
      Description copied from interface: UrgencyQueue
      Removes the most urgent num-many items in this urgency queue and performs the given action (using action.accept) on each item, in the urgency queue.

      Examples

      This example removes two people of equal urgency. The action observes them in their original arrival order.

      See the instructions for running the method examples. Each Java snippet is independent. 

      Comparator<Person> byAge = (Person a, Person b) -> {
    return Integer.compare(a.age(), b.age());
}; // lambda
UrgencyQueue<Person> queue = new OracleCustomLinkedUrgencyQueue<Person>(byAge);
queue.enqueue(new Person(23, "Kuma"));
queue.enqueue(new Person(23, "Ash"));
queue.enqueue(new Person(20, "Billy"));

Consumer<Person> printName = (Person person) -> {
    System.out.println(person.name());
}; // lambda

queue.dequeueMany(2, printName);

System.out.println("remaining: " + queue);
      Expected output: 
      Kuma
Ash
remaining: [Person[age=20, name=Billy]]

      The action is non-interfering: it only prints a name. Because the comparator compares ages only, Kuma and Ash have equal urgency despite their different names.

      Specified by:
      dequeueMany in interface Queue<ItemType, UrgencyQueue<ItemType>>
      Specified by:
      dequeueMany in interface UrgencyQueue<ItemType>
      Parameters:
      num - the number of items to remove.
      action - the action to be performed on the removed items.
      See Also:

    • clear

      public void clear()
      Description copied from interface: UrgencyQueue
      Removes all items from this urgency queue.

      Examples

      This example removes all items, then clears the already empty queue.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
queue.enqueue(new Person(22, "Sally"));
queue.enqueue(new Person(20, "Billy"));
queue.enqueue(new Person(23, "Kuma"));

System.out.println("before: " + queue);

queue.clear();

System.out.println("after: " + queue);
System.out.println("size: " + queue.size());

queue.clear();

System.out.println("after clearing again: " + queue);
      Expected output: 
      before: [Person[age=23, name=Kuma], Person[age=22, name=Sally], Person[age=20, name=Billy]]
after: []
size: 0
after clearing again: []

      Both calls complete normally. Clearing the queue does not require it to contain any items.

      Specified by:
      clear in interface Queue<ItemType, UrgencyQueue<ItemType>>
      Specified by:
      clear in interface UrgencyQueue<ItemType>

    • enqueueAll

      public <SubType extends ItemType> boolean enqueueAll(Iterable<SubType> values)
      Description copied from interface: UrgencyQueue
      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.

      Examples

      The first example inserts people from an iterable, then supplies an empty iterable.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
Iterable<Person> people = List.<Person>of(
    new Person(22, "Sally"),
    new Person(20, "Billy"),
    new Person(23, "Kuma")
);

System.out.println("added: " + queue.enqueueAll(people));
System.out.println(queue);
System.out.println("added empty: " + queue.enqueueAll(List.<Person>of()));
System.out.println("size: " + queue.size());
      Expected output: 
      added: true
[Person[age=23, name=Kuma], Person[age=22, name=Sally], Person[age=20, name=Billy]]
added empty: false
size: 3

      The second example gives the method its own type argument: Person. The queue has item type Object, but the supplied iterable contains Person objects. Its comparator treats all items as equally urgent, preserving their arrival order. 

      Comparator<Object> equalUrgency = (Object a, Object b) -> {
    return 0;
}; // lambda
UrgencyQueue<Object> queue = new OracleCustomLinkedUrgencyQueue<Object>(equalUrgency);
Iterable<Person> people = List.<Person>of(
    new Person(22, "Sally"),
    new Person(23, "Kuma")
);

System.out.println("added: " + queue.<Person>enqueueAll(people));
System.out.println(queue);
      Expected output: 
      added: true
[Person[age=22, name=Sally], Person[age=23, name=Kuma]]

      The third example supplies an iterable containing a null item. The call throws IllegalArgumentException and leaves the original queue unchanged, including rejecting the non-null person that precedes the null entry. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
queue.enqueue(new Person(22, "Sally"));
List<Person> people = new ArrayList<Person>();
people.add(new Person(23, "Kuma"));
people.add(null);
try {
    queue.enqueueAll(people);
} catch (IllegalArgumentException exception) {
    System.out.println("Rejected an iterable containing null.");
} // try

System.out.println("unchanged: " + queue);
System.out.println("size: " + queue.size());
      Expected output: 
      Rejected an iterable containing null.
unchanged: [Person[age=22, name=Sally]]
size: 1

      In the second example, ItemType is Object and SubType is Person. The explicit method type argument makes this distinction visible; it can also be inferred. The valid comparator deliberately treats every pair of objects as equally urgent, so insertion order is preserved. This call does not assign an UrgencyQueue<Person> to an UrgencyQueue<Object>. In the third example, ArrayList permits the null entry so that enqueueAll itself performs the rejection. No item from that iterable is added.

      Specified by:
      enqueueAll in interface Queue<ItemType, UrgencyQueue<ItemType>>
      Specified by:
      enqueueAll in interface UrgencyQueue<ItemType>
      Type Parameters:
      SubType - the type of the items to be added.
      Parameters:
      values - the items to add to this queue.
      Returns:
      true if this queue is changed as a result of the call; false otherwise.

    • toArray

      public ItemType[] toArray(IntFunction<ItemType[]> generator)
      Description copied from interface: UrgencyQueue
      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.

      Examples

      This example creates a Person array containing the queue items in urgency order.

      See the instructions for running the method examples. Each Java snippet is independent. 

      UrgencyQueue<Person> queue = new OracleLinkedUrgencyQueue<Person>();
queue.enqueue(new Person(22, "Sally"));
queue.enqueue(new Person(23, "Kuma"));

System.out.println("urgency queue: " + queue);

IntFunction<Person[]> newPersonArray = (int value) -> {
    return new Person[value];
}; // lambda
Person[] persons = queue.toArray(newPersonArray);

System.out.println("array length: " + persons.length);
System.out.println("first array element: " + persons[0]);
System.out.println("queue unchanged: " + queue);
      Expected output: 
      urgency queue: [Person[age=23, name=Kuma], Person[age=22, name=Sally]]
array length: 2
first array element: Person[age=23, name=Kuma]
queue unchanged: [Person[age=23, name=Kuma], Person[age=22, name=Sally]]

      The generator creates an array of the requested length. The queue remains unchanged, and the array components contain reference values referring to the same person objects.

      Specified by:
      toArray in interface Queue<ItemType, UrgencyQueue<ItemType>>
      Specified by:
      toArray in interface UrgencyQueue<ItemType>
      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.