CS 10 | Problem solving | Spring 2022 CS 10: Problem Solving via Object Oriented Programming Spring 2022 About Schedule Software Prioritizing [prev] [next] We saw how to keep things in last-in/first-out or first-in/first-out order. But what if we actually have specific priorities, such that the "most important" thing in should be the first out? That's what priority queues are for. Priority queues Java's priority queue Reading from a file ArrayList implementations All the code files for today: ArrayListMinPriorityQueue.java; MinPriorityQueue.java; Roster.java; SortedArrayListMinPriorityQueue.java; Student.java Slides from class Priority queues A priority queue is a queue which instead of being FIFO is Best Out. "Best" is defined by a priority. For a typical priority queue, low priority numbers are removed first. That may seem backwards, but think of "you are our number one priority!" That's better than being their number two or three priority. There are hundreds of applications of priority queues. They come up quite commonly in computer systems (high-priority print jobs, various priority levels of jobs running on a time sharing system, ...). They are used in finding shortest paths and other search problems. And a priority queue gives you an easy way to sort — put everything into the priority queue, then take them out one at a time. They come out in sorted order. Min-priority queues also form the heart of discrete event simulators, which simulate systems in which things happen at various moments in time. The simulation runs through time, where the time of each occurrence is nondecreasing (i.e., the simulated time either increases or stays the same—it never backs up). An event can cause another event to occur at some later time. A min-priority queue keeps track of the events that have yet to occur, with the key of an element being the time that its event is to occur. When an event is created, the insert method adds it to the min-priority queue. The extractMin method tells us the next event to occur, removing it from the queue so that we don't try to process it more than once. Sometimes, the result of an event is to allow some other event, already scheduled, to occur even earlier; in this case, the decreaseKey method changes the time that the other event occurs to move it earlier. MinPriorityQueue.java contains the interface for a min-priority queue. Here, each element has a value, which we call its key. The way that we have defined the interface, the generic type is E extends Comparable — as we saw with BSTs, this lets us rely on a compareTo() method of the elements, to establish the priority order. The MinPriorityQueue interface supports the following operations: isEmpty, a predicate that tells whether the priority queue is empty. insert, which inserts an element into the priority queue. minimum, which returns the element in the priority queue with the smallest key, but leaves the element in the priority queue. extractMin, which returns the element in the priority queue with the smallest key and removes it from the priority queue. (Note - for some applications it is useful to also have a decreaseKey operation, which reduces the priority value in a given node, but this complicates the job of implementing a priority queue. You will see how to handle this if you take CS 31.) We can also define a max-priority queue, which replaces the latter operations by maximum and extractMax (and increaseKey if you include it). We will focus on min-priority queues, but they are really the same thing. Java's priority queue Java provides a class java.util.PriorityQueue, although surprisingly no interface for a general priority queue. This implementation is based on a heap, which we will see later. However, as usual Java chooses different names. The correspondence is: insert becomes add minimum becomes peek extractMin becomes remove isEmpty remains isEmpty Remember that with the Comparable interface, we use the one.compareTo(other) to decide if one is "less than" (the value is negative), "equal to" (the value is 0), or "greater than" (positive) the other. An example of a class implementing this interface, Student.java, just passes the work off to String.compareTo. public int compareTo(Student s2) {
return name.compareTo(s2.name);
} There is another way to compare two objects: the Comparator interface. The book discusses this. Write a custom class that implements the method compare(a, b) to give the same negative, zero, or positive result as in compareTo. Then pass an instance of this class to the constructor. (The "natural order", via compareTo, will be used for the no-argument constructor.) This is more flexible, because different orders can be designed for different purposes. That's also illustrated in Student.java, with such a class defined within the main. As with the Element inner class of SinglyLinked, there was no reason to bother making this class stand on its own (and good reasons not too). class NameLengthComparator implements Comparator {
public int compare(Student s1, Student s2) {
return s1.name.length() - s2.name.length();
}
}
Comparator lenCompare = new NameLengthComparator();
pq = new PriorityQueue(lenCompare); Java 8 went one step further in clutter reduction and code clarity, introducing anonymous functions. These functions provide a compact way to write a function in the middle of a piece of code, without bothering to give it a name (it's "anonymous") and package it up in a class like that. pq = new PriorityQueue((Student s1, Student s2) -> s1.year - s2.year); You can see basically the method head still there in parentheses, and the method body after the "right arrow" ->. In this case, we compare student years by subtraction, so again a negative number acts like less-than. Java recognizes that our anonymous function provides the signature required of the compare method of a Comparator, and thus packages it up for the priority queue to use that way. In general, anonymous functions ("lambda expressions") nicely compactify small helper functions that return values based on one or a few parameters. Anonymous functions are very powerful, helping drive a whole high-level stream mechanism for iteration over sequences. This example code actually demonstrates a couple easy applications of PQs. One is sorting, as discussed above. The other is basically what goes on in operating systems, when deciding what task to work on next. Each task has a priority associated with it, and the next most urgent thing pops out. That's illustrated here by giving priority based on class year (e.g., for registration in a course). Reading from a file Okay, let's finally break down and dive into reading inputs from a file. I swept this under the rug in the Shakespearean search engine (and side-stepped some issues), but you're going to have to do this soon, so I want to illustrate more thoroughly. The basic idea is simply to create an object that lets us get input from a file, and repeatedly ask it from the next thing from the file. But it quickly gets much uglier in practice. What if the file doesn't exist? What if someone modifies the file while we're reading? What if something we try to get from the file isn't in the format we expect. Exceptions and condition checking pervade I/O code. Roster.java provides an example of reading a file and handling many if not all of the issues, and roster.csv provides an example input file (you can directly open it in IntelliJ — it's just text). Save the CSV file in the "inputs" folder. The core bit is this: BufferedReader input = new BufferedReader(new FileReader(fileName));
String line;
int lineNum = 0;
while ((line = input.readLine()) != null) {
System.out.println("read @"+lineNum+"`"+line+"'");
} And the line number is there just for messages; not functionally necessary. We open a file given its name (e.g., "inputs/roster.csv"), and wrap that up in a "buffered reader" that allows us to get a line at a time. The while loop then gets a line at a time and does something with it (here just printing it). The readLine method returns null when there are no more lines to read. So the statement in the condition says "read a line and hold onto it in the line variable; only continue the loop body if that line isn't null". A little odd looking the first time you see it, combining assignment and test, but it's a pretty standard way to do this. Now, if you look at the actual code in Roster.java, you see lots more around this core idea, to handle the exceptional cases. We try-catch the attempt to open the file, in case it's not there. Note that this requires splitting up the declaration of the variable from its initial assignment, so that the declaration sits outside of the try-catch. We try-catch the loop to read from the file, in case something goes wrong during reading. We test the number of comma-separate pieces in a line, and we try-catch the extraction of an integer from the second piece. We try-catch the closing of the file. One note: if we didn't want to print out the message for IO error while reading, we could have dropped the "catch" clause and instead put a "finally" clause that would be executed in either case (exception or not). This clause would wrap up the whole block of code to close the file, to ensure an attempt at closing in normal or exceptional circumstances. But then the method would pass the IO exception on up the line. That's illustrated in readRoster2. Whew. Java has additional mechanisms for safely dealing with file I/O, but this illustrates the underlying principles. ArrayList implementations Unsorted arraylist The simplest way to implement a min-priority queue is by an arraylist whose elements may appear in any order: ArrayListMinPriorityQueue.java. The methods of this class are straightforward. The private method indexOfMinimum computes and returns the index in the array of the element with the smallest key. This method is called by the minimum and extractMin methods. extractMin seems a bit strange. Instead of removing the smallest element it moves the last element to the place where the smallest element was and then removes the last element. It does this because removing the last element is faster than removing an element from the middle of the arraylist. Let's look at the worst-case running times of the min-priority queue operations in this implementation. We express them in terms of the number n of elements that will ever be in the min-priority queue at any one time. isEmpty just returns a boolean indicating whether the size of the arraylist is zero. This method takes constant time, or Θ(1). insert just adds a new reference at the end of the arraylist, and so it takes Θ(1) amortized time. Both the minimum and extractMin methods call indexOfMinimum to find the element with the smallest key. This helper method takes Θ(n) time to search through n elements, and therefore so do minimum and extractMin. Sorted arraylist The biggest disadvantage of implementing a min-priority queue by an unsorted arraylist is that minimum and extractMin take Θ(n) time. We can get the running time of these operations down to Θ(1) if we keep the arraylist sorted between operations. SortedArrayListMinPriorityQueue.java gives this implementation. An important detail is that it is sorted in decreasing order, so that the last position is the minimum. The minimum method is simpler now: it just returns the element in position size-1 of the arraylist. The extractMin method removes and returns the element in position size-1. Thus both of these operations take Θ(1) time. The tradeoff is that, although minimum and extractMin now take only Θ(1) time, we find that insert takes O(n) time. So we have not improved matters by maintaining the array as sorted, unless we are making a lot more calls to minimum and extractMin than to insert. In practice, the number of calls to extractMin is often the same as the number of calls to insert, so we gain no overall advantage from keeping the array sorted.
