Introduction to Algorithms: Array Shifting

Paul Taylor

22 January 2001

Every time you move a window around on your screen (or even move the mouse), a very low-level subroutine is being called to copy a chunk of stuff from one place to another, overwriting whatever was there before.

The code for shift is not as easy as it may seem. When you have completed this exercise, you will have undergone a "rite of passage" towards being a programmer, as opposed to someone who merely uses a computer.

You are not allowed to allocate a new array!

Like linear search, this is a very low-level operation, and one that not quite so low-level applications will call very frequently and expect to be done very quickly.

We shall learn logical techniques for proving correctness of these algorithms.

1 Writing the code

There is a file called Shift.java in your coursework directory. As for linear search, you should do all your work for this algorithm in this file, including what you learn about it from the TESTER and in lectures.

The class declaration is

public class Shift implements Shifting

and your shift method has the signature

   public void shift (
      int[] array,   //  work on this array, in place
      int source,    //  the index of the first cell from which to copy
      int dest,      //  the index of the cell into which to copy this value
      int len)       //  the number of cells to copy

At the top of the file you will find a diagram that shows which parts of the array are to be copied where, and which parts stay the same.

The loop invariant diagram should be included here!

Make a habit of drawing diagrams like this before you start to write JAVA code. As you see, it can be done adequately with ASCII characters. There is no point in trying to be elaborate or artistic.

What is the intended effect of the shift method? State, not only what has been changed, but also what has stayed the same. This is the post-condition. Get into the habit of stating it as a comment in your code.

As usual in this course, the part of the code that does the useful work of this method is a single loop, and you should use while, not for, because we want to write some logic or draw some diagrams in certain places in the code.

There are three things that the loop counter might count:

the position from which you are copying,
the position to which you are copying,
from 0 to len-1, or
there may be two counters, doing both of the first two.

Write all four versions of the code in the file.

Which is the clearest of the three, and why? Make a note of your reason as a comment in the code, and leave the other three versions there as comments.

Which version would be most efficient in machine code? It is one of the jobs of a compiler to generate machine-efficient machine code from your human-clear source code. Write your code for humans to read, and make the compiler do the work to make it efficient for the machine.

2 Running your program

When you have persuaded the JAVA compiler to accept your code, you can use the TESTER to perform individual runs as follows:

   run Shift.java size=20 source=15 dest=3 len=4

As before you can specify the actual values in the array, rather than getting random ones.

The TESTER provides random arguments (with which the first version of your code should work) when you use the command

    run Shift.java easy

You can watch your method at work by adding lines like

   Trace.printarray (array, a, b, c, ...);

to your code, where a, b, c, ... are pointers into the array. (You can give up to five pointers as arguments to Trace.printarray.) Do this immediately before, immediately inside and immediately after the loop. Use the trace command instead of run to invoke the TESTER in order to make these Trace.printarray statements effective.

3 The pre-condition

What numerical inequalities must be satisfied by source, dest, len and array.length for this to be meaningful? This is the pre-condition. Get into the habit of stating it as a comment in your code.

On this occasion, it is appropriate to test the pre-condition at the beginning of your method and

   throw new IllegalArgumentException ("bad arguments for shift");

if it is not satisfied. (Do not use System.out.print() or Trace.print().) You can make the message more informative if you wish.

This is the only Exception that you will throw when implementing the algorithms in this course.

Do not catch this exception. It indicates that your caller has a bug. Do not conceal bugs by indiscriminately catching exceptions. It is better to have your program (or your caller's program) crash during development than when it is in service and could do some damage.

4 Shifting towards the right

Does your code work with the following arguments?

trace Shift.java size=20 source=10 dest=13 len=6

In which direction is the shift being made (leftwards or rightwards) in the two cases?

What has gone wrong?

On what condition, involving source, dest and len does the shift work or not work?

Write a version of the code that would work in the case where the original did not. Would this work in the situation where the original one did, making it redundant, or do you need both versions to cover all cases?

As with the right-to-left search, you should take advantage of the symmetry of the problem to make your code as clear and simple as possible.

When you have code that you think will work in all situations, use the check command to test it thoroughly. No timings will be done for this algorithm.

5 Another way to do the two cases of shift

You probably implemented the two cases as separate loops contained in the two branches of a conditional.

Now, instead, define an extra variable step that takes the value +1 or -1 and re-write the code as a single loop, in which the loop variable j is incremented by

   j += step;

instead of by j++; or j--;. You will need to define step and the initial and final values of the loop variable within a conditional before (not containing) the loop.

Discuss these two programs - one with two versions of the loop in the branches of a conditional, the other with just one more complicated loop - in your small-group tutorial.

What advantage does the first have, in terms of speed?
What advantage does the second have, in terms of future maintainability of the program?

6 Loop invariant for shift

This is the model answer for the test that was set in Week 5 in 1998-9.

Given an array array[ ] of ints of length n, together with two pointers src and dest into it, and a number len, we are required to shift the segment of length len that starts at src, so that the copy starts at dest.

Be extremely careful before you read English meanings into the names of program variables - this does not say that src+len == dest! [When this was origianlly written, the variables were called from and to.]

For most of the discussion (as mathematicians say, "without loss of generality"), we assume that src > dest.

It is possible that the source and destination segments

overlap (src < dest+len), in which case part of the source gets overwritten, or
they may abut (src == dest+len), or
there may be a gap between them (src > dest+len), the entries in which are likely to stay the same.

(a): The loop invariant is described by the following diagram. The parts B and C get copied, whilst we guarantee that A and D will remain the same. There is no guarantee that any part of the source segment will remain the same. In the "typical" situation, B has already been copied, and C remains to be done. In the third case, there would be a third segment (the gap between the destination and source segments) that we could also guarantee would stay the same.

The diagram is based on the first case, because this draws attention to the possibility that the source segment may get overwritten. We are not assuming an overlap: the point is that we must not assume that the source stays intact (compare drawing diagrams "in general position" in geometry).

In practice, the program will leave the right part of the source intact - in the case of the left shift - whilst the right shift would leave the left part intact. Regard this as an accident. You do not guarantee anything. Some of the copied values might accidentally be equal to the values that they overwrite, but we wouldn't think of guaranteeing that!

Notice also that (to mis-quote Abraham Lincoln) the program shifts some of the values all of the way - not all of them some of the way, like a tube train going through a tunnel!

Always label the right of the boundaries. It is wrong to put the label on the boundary: an array consists of discrete cells indexed by integers (like days of the week), it is not continuous with pointers to infinitesimal instants of time! It is bad practice to label (the right of the lower boundary and) the left of the upper boundary (len-1): the length of the segment is given most simply by subtraction. (It is for the same reason that arrays in modern programming languages are indexed from 0 and not 1.) Do not introduce unnecessary difficulties into your program in the form of -1s that have nothing to do with the problem! In practice, programs are complicated enough as it is, without making them gratuitously worse.

For this diagram (and therefore the program) to be meaningful,

(b): the input values n, src, dest and len must all be ≥ 0, and src+len ≤ n.

In practice, a method in a library that implements this algorithm should check these conditions before doing anything to the array, and raise an exception if any of them is not true. As a point of programming style, always make all of these checks at the beginning. Think of it this way: if a surgeon is about to perform an operation on you, you want to be completely sure that s/he's fully qualified, before opening you up!

(c): The loop is initialised by int j=0;
(d): Since then dest == dest+j and src == src+j, the B part of the diagram is empty, so the typical situation is in fact the initial one: nothing (B) has been copied, and everything (C) remains to be copied. To achieve this instance of the loop invariant, we have to do nothing apart from setting j=0;
(e): The loop condition is while (j < len)
(f): The body of the loop is array [dest+j] = array [src+j]; j++;
(g): We need to assume that the loop condition (e) was true before executing the code inside the loop in order to know that the code is copying the appropriate values. Otherwise it would violate our guarantees about leaving A and D alone, and might even throw new ArrayBoundsException.

Being enclosed in a while (or if) does not prevent the code from being executed by the machine. Think of the condition as a ticket collector on a gate: there may be ways to dodge the check! There are tools (debuggers) that can interfere with how programs run in arbitrary ways. Also, if there is a label inside this block of code, and a goto that jumps to it (some programming languages and many obscure programmers can do much worse than this) then the machine may find itself inside the block without the condition being true. The ticket collector only stands at the gate: there are no "spot checks" inside the block!

So the force of the loop condition is not on the execution of the program, but on what we know (can prove) about it.

(h)

We show that the loop invariant (a) is restored after this code, and is therefore valid at the beginning of the next iteration of the loop, as follows:

The loop invariant says that A and D (and the gap, if any, between the source and destination segments) are unchanged from the initial situation to the top of the present loop. But the body of the loop doesn't touch them, so they are still unchanged at the bottom of the loop body.
Similarly, the part B that has already been copied stays there.
Also, the part C that remained to be copied was guaranteed by the loop invariant to be the same as it was initially, and is not overwritten by the body of the loop.
One element is transferred and the pointers are incremented, but by the loop condition they remain within the appropriate bounds.

In this way the next version of the diagram is the same as the typical one.

We prove that the loop terminates by observing that len-j is a non-negative integer, but is decreased by 1 on each iteration.

(i): When the loop condition (e) is false (so the loop exits), we have j==len, so the typical version of the loop invariant diagram coincides with the final one. Hence the whole segment has been copied as required and the guarantees about A and D have been honoured.
(j): If instead src < dest, the program attempts to do a right shift, but it may overwrite part of the source segment before it is copied to the destination, giving repetitions of part of the source instead of copying it correctly.
(k): The reasoning above with the loop invariant is no longer applicable, because parts B and C overlap, so we no longer know that C has remained intact.
(l): If, however, src+len ≤ dest, so the destination is on the right of the source with no overlap, the program works, and more or less the same reasoning applies, because C does remain intact.

Notice that, in (k), the reasoning is still valid: it is a case of P⇒ Q where both P (the assumptions or pre-conditions) and Q (the conclusions or post-conditions) are false.

There are two symmetries in this problem: between the left shift and the right shift, and between the source and destination.

The assignment that lies at the heart of this program is designed to exploit the second symmetry: the loop counter makes the correspondence between the source and destination cells obvious by not being biased towards one view or the other.

Any modern compiler should be capable of translating this clear idiom into

    int end_src = src + len;
    while (src < end_src)
       { array [dest++] = array [src++]; }

which is a well established idiom of machine code programming. Make the machine work for you, not vice versa!

This is www.PaulTaylor.EU/algorithms/shift.html and it was derived from algorithms/shift.tex which was last modified on 21 July 2007.