Last week, I refactored a program that I had described the previous week, which Edsger Dijkstra wrote to solve a problem that he posed in A Discipline of Programming. His approach used three variables containing indices, one of which referred to the position immediately after a boundary and the other two of which referred to positions immediately before a boundary. Please read my two previous articles before continuing.

When I refactored Dijkstra's code, I uniformly adopted the convention that an index indicates the position immediately after a boundary, never before it. This convention ran into a small disagreement with Dijkstra's strategy. He divided the sequence into three known and one unknown section, and repeatedly examined the last element of the unknown section to place it appropriately. Unfortunately, an index that denotes the position after a boundary never denotes the last element of a range except by coincidence.

As a result of this disagreement, we had to write code that began

while (xb < wb) {
      Examine bucket wb-1 …

and then evaluated wb-1 in several places. To avoid this redundant evaluation, we rewrote the code as

 
while (xb < wb) {
           
      Decrement wb.
      Examine bucket wb …
 

which worked well enough, but was slightly ungainly.

What should we do? One's first thought is to look at elements at the beginning of the unknown region rather than at the end; but that strategy creates new problems. Dijkstra chose to arrange the regions in the order "known red," "unknown," "known white," and "known blue." By examining the last pebble in the unknown region each time, he assured that it would never be necessary to move a pebble over more than one region. If we look at the first pebble in the unknown region and it turns out to be blue, what do we do? We can't put a white pebble there, as we could when it was the last unknown pebble; instead, we must put either a red pebble or another unknown pebble there. But we can't put a red pebble there because we might not have one. So we wind up having to swap it with an unknown pebble.

In that case, we now have a blue pebble next to the beginning of the white region, so to put everything back in order, we have to swap that blue pebble with the last white pebble. In other words, by looking at the first pebble in the unknown region instead of the last, we might sometimes have to swap the same pebble twice, thus making the revision a worse solution than the original.

This difficulty comes about because we wanted to look at the end of the unknown region that is furthest from the other two regions. This observation suggests that we can overcome the difficulty by changing the order or the regions to "known red," "known white," "unknown," and "known blue." To distinguish this strategy from the others, we shall choose new names for all of our variables:

• rr is the index of the first (as opposed to the last) red pebble;
• ww is the index of the first white pebble, or, equivalently, one past the last red pebble;
• xx is the index of the first unknown pebble;
• bb is the index of the first blue pebble; and
• N is an index that is one past the last blue pebble.

As before, we can make this description more precise:

• If rr <= k < ww, bucket k contains a red pebble.
• If ww <= k> < xx, bucket k contains a white pebble.
• If xx <= k < bb, bucket k has not yet been examined.
• If bb <= k < N, bucket k contains a blue pebble.

We start by setting rr, ww, and xx to the beginning of the sequence, and bb and N to one past the end of the sequence. As long as xx < bb, we shall examine the element to which xx refers.

If the element at xx is red, we must swap it with the element past the end of the red region, the index of which is conveniently in ww, and then increment ww and xx. If the element at xx is white, it suffices to increment xx. Finally, if the element is blue, we must swap it with the element before bb (i.e., the last unknown element) and decrement bb. In this case, we leave xx unchanged because it now refers to what was formerly the last unknown element. The code looks like this:

 
while (xx < bb) {
                 Examine bucket xx. If the pebble in that bucket is
                              Red: Swap buckets xx and ww; increment xx and ww.
                              White: Increment xx.
                              Blue: Decrement bb, swap buckets xx and bb.
               }
 

If you compare this code with Dijkstra's original solution, you will see that in an odd way they are nearly logical duals of each other. Dijkstra's code swaps two buckets and decrements two variables when it sees a blue pebble; ours swaps two buckets and decrements two variables when it sees a red pebble. When Dijkstra sees a red pebble, it swaps two buckets and increments one variable; when we see a blue pebble, we decrement one variable and swap two buckets. Finally, when we see a white pebble, we increment a variable; in the same circumstances, Dijkstra decrements one.

This substitution of increment and decrement makes sense when we realize that our boundaries are a mirror image of Dijkstra’s, as does the substitution of red for blue.
 Our code is no simpler than Dijkstra's, but it is also no more complicated. Nevertheless, I think this refactoring has improved on Dijkstra's original by regularizing the strategy for representing boundaries and regions: We always represent a range by its boundaries, and we always represent a boundary by an index that refers to the position immediately after the boundary. Alternatively, we can think of this strategy of representing a range by an index that refers to the range's first element (if any) and another index that refers to the element (if any) immediately after the end of the range.

A reader commented on last week's article:

I think the difficulty with Djikstra's code is in viewing the variables r, w, b as representing ranges. If you think of them as representing buckets then r = the bucket to put the next red ball into, b = the bucket to put the next blue ball into, and w = the current working (unknown) bucket. The fact that the ranges are asymmetric isn't relevant because the ranges are irrelevant; they are an artifact of the variables, not the meaning of them.

There is a problem with this point of view, and that is that Dijkstra is clear that he is using w to represent white, not working. He divides the buckets into four zones (his word), which he calls ER, X, EW, and EB. ER stands for "established red;" that is, those (contiguous) buckets that are known to contain red pebbles. EW and EB are analogous zones that are known to contain white and blue pebbles, respectively, and X is the zone with contents as yet unknown. Therefore, I think that Dijkstra has made it clear that he is using variables to represent ranges about which he wishes to reason, not elements on which he intends to take particular actions.

I do not take this distinction lightly. In A Discipline of Programming, Dijkstra talks extensively about the notion of an invariant, which is a claim about the state of a program that is expected to be true whenever the program's execution reaches a particular point. His discussion played such an important role in forming how I think about programming that I intend to continue next week by talking more explicitly about invariants.