Section 15.1. Using the Methods of List

15.1. Using the Methods of List

Let's look at examples of the use of some of these methods in the to-do manager. In the last chapter we considered representing the organization of a single day's tasks in a queue-based class with shutdown capabilities. One useful way of enlarging the scope of the application is to have a number of objects of this type, each one representing the tasks that are scheduled for a day in the future. We will store references to these objects in a List, which (to keep things simple and to avoid grappling with the distasteful details of java.util.Calendar) will be indexed on the number of days in the future that it represents. So the queue of tasks scheduled for today will be stored at element 0 of the list, the queue scheduled for tomorrow at element 1, and so on. Example 15.1 shows the scheduler.

A list-based task scheduler

 public class TaskScheduler {   private List<StoppableTaskQueue> schedule;   private final int FORWARD_PLANNING_DAYS = 365;   public TaskScheduler() {     List<StoppableTaskQueue> temp = new ArrayList<StoppableTaskQueue>();     for (int i = 0 ; i < FORWARD_PLANNING_DAYS ; i++) {       temp.add(new StoppableTaskQueue());     }     schedule = new CopyOnWriteArrayList<StoppableTaskQueue>(temp);    //1   }   public PriorityTask getTask() {     for (StoppableTaskQueue daysTaskQueue : schedule) {       PriorityTask topTask = daysTaskQueue.getTask();       if (topTask != null) return topTask;     }     return null;    // no outstanding tasks - at all!?   }   // at midnight, remove and shut down the queue for day 0, assign its tasks   // to the new day 0, and create a new day's queue at the planning horizon   public void rollOver() throws InterruptedException{     StoppableTaskQueue oldDay = schedule.remove(0);     Collection<PriorityTask> remainingTasks = oldDay.shutDown();     StoppableTaskQueue firstDay = schedule.get(0);     for (PriorityTask t : remainingTasks) {       firstDay.addTask(t);     }     StoppableTaskQueue lastDay = new StoppableTaskQueue();     schedule.add(lastDay);   }   public void addTask(PriorityTask task, int day) {     if (day < 0 || day >= FORWARD_PLANNING_DAYS)       throw new IllegalArgumentException("day out of range");     StoppableTaskQueue daysTaskQueue = schedule.get(day);     if (daysTaskQueue.addTask(task)) return;                        //2     // StoppableTaskQueue.addTask returns false only when called on     // a queue that has been shut down. In that case, it will also     // have been removed by now, so it's safe to try again.     if (! schedule.get(0).addTask(task)) {       throw new IllegalStateException("failed to add task " + task);     }   } } 

Although the example aims primarily to show the use of List interface methods rather than to explore any particular implementation, we can't set it up without choosing one. Since a major factor in the choice will be the concurrency requirements of the application, we need to consider them now. They are quite straightforward: clients consuming or producing tasks only ever read the List representing the schedule, so (once it is constructed) the only occasion that it is ever written is at the end of a day. At that point the current day's queue is removed from the schedule, and a new one is added at the end (the "planning horizon", which we have set to a year in the example). We don't need to exclude clients from using the current day's queue before that happens, because the StoppableTaskQueue design of Example 14.1 ensures that they will be able to complete in an orderly way once the queue is stopped. So the only exclusion required is to ensure that clients don't try to read the schedule itself while the rollover procedure is changing its values.

If you recall the discussion of CopyOnWriteArrayList in Section 11.5.3, you may see that it fills these requirements very nicely. It optimizes read access, in line with one of our requirement. In the event of a write operation, it synchronizes just long enough to create a new copy of its internal backing array, thus filling our other requirement of preventing interference between read and write operations.

With the implementation chosen, we can understand the constructor of Example 15.1; writing to the list is expensive, so it is sensible to use a conversion constructor to set it up with a year's worth of task queues in one operation (line //1).

The getTask method is straightforward; we simply iterate over the task queues, starting with today's queue, looking for a scheduled task. If the method finds no outstanding tasks, it returns nulland if finding a task-free day was noteworthy, how should we celebrate a task-free year?

At midnight each day, the system will call the method rollOver, which implements the sad ritual of shutting down the old day's task queue and transferring the remaining tasks in it to the new day. The sequence of events here is important; rollOver first removes the queue from the list, at which time producers and consumers may still be about to insert or remove elements. It then calls the StoppableTaskQueue.shutDown which, as we saw in Example 14.1 returns the remaining tasks in the queue and guarantees that no more will be added. Depending on how far they have progressed, calls of addTask will either complete or will return false, indicating that they failed because the queue was shut down.

This motivates the logic of addTask: the only situation in which the addTask method of StoppableTaskQueue can return false is that in which the queue being called is already stopped. Since the only queue that is stopped is the day 0 queue, a return value of false from addTask must result from a producer thread getting a reference to this queue just before a midnight rollover. In that case, the current value of element 0 of the list is by now the new day 0, and it is safe to try again. If the second attempt fails, the thread has been suspended for 24 hours!

Notice that the rollOver method is quite expensive; it writes to the schedule twice, and since the schedule is represented by a CopyOnWriteArrayList (see Section 15.2.3), each write causes the entire backing array to be copied. The argument in favour of this implementation choice is that rollOver is very rarely invoked compared to the number of calls made on getTask, which iterates over the schedule. The alternative to CopyOnWriteArrayList would be a BlockingQueue implementation, but the improvement that would provide in the rarely-used rollOver method would come at the cost of slowing down the frequently-used getTask method, since queue iterators are not intended to be used in performance-critical situations.

Using Range-View and Iterator Methods Of the four List method groups above, Example 15.1 makes use of the methods of one group, positional access, in several places. To see how range-view and iterator methods could also be useful, consider how the TaskScheduler could export its schedule, or a part of it, for a client to modify. You would want the client to be able to view this subschedule and perhaps to insert or remove tasks, but you would definitely want to forbid the insertion or removal of elements of the list itself, since these represent the sequence of days for which tasks are being scheduled. The standard way to achieve this would be by means of an unmodifiable list, as provided by the Collections class (see Section 17.3.2). An alternative in this case would be to return a list iterator, as the snapshot iterators for copy-on-write collections do not support modification of the backing collection. So we could define a method to provide clients with a "planning window":

 ListIterator<StoppableTaskQueue> getSubSchedule(int startDay, int endDay) {  return schedule.subList(startDay, endDay).listIterator(); } 

This view will be fine for today, but we have to remember to discard it at midnight, when the structural changes of removing and adding entries will invalidate it.