CSCI H343 Data Structures Fall 2023

Lecture: Arrays, Rotation, and Correctness Proofs

Arrays in Java

Create an array of length n

int n = 10;
int[] A = new int[n];

Set the element at a given position:

A[0] = 0;
A[1] = 1;
A[2] = 4;

for (int i = 3; i != n; ++i)
  A[i] = i * i;

Now we have an array that looks like the following

elements: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81
position: 0, 1, 2, 3,  4,  5,  6,  7,  8,  9

Get the element at a given position:

assert A[2] == 4;

Loop over all the elements of an array, front to back

int total = 0;
for (int y : A) {
  total += y;
}
System.out.println(total);

Def. a half-open interval, written [i,k), is a contiguous subarray that starts at position i and finishes one place before k.

The interval [3, 7) of our example array is

elements: 9, 16, 25, 36
position: 3,  4,  5,  6

Loop over a half-open interval of the subarray:

static int sum(int[] A, int begin, int end) {
  int total = 0;
  for (int i = begin; i != end; ++i) {
      total += A[i];
  }
  return total;
}
assert total == sum(A, 0, 5) + sum(A, 5, 10);

Rotate the elements of an array by 1 to the right, with wrap around.

    [1,2,3,4,5]
--> [5,1,2,3,4]

Rotation is used in

Testing

Let’s pick one of the rotate implementations to test. We’ll create a Rotate.java file in the src directory of our project.

public class Rotate {

    public static void rotate(int[] A) {
        rotate_1_swap_bkwd(A);
    }

    ...
}

To test the rotate method, we’ll create a RotateTest class as follows in a file named RotateTest.java in the test directory. We’ll need to import several items from the JUnit Jupiter library.

import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.BeforeEach;
import static org.junit.jupiter.api.Assertions.*;

public class RotateTest {
   ...
}

Testing Regular Cases

To get your bearings, its good to start with a test that captures the common case and that you already know the solution, such as the example above.

    @Test
    public void rotate_common_case() {
        try {
            int[] A = {1, 2, 3, 4, 5};
            int[] A_correct = {5, 1, 2, 3, 4};
            Rotate.rotate(A);
            assertArrayEquals(A, A_correct);
        } catch (Exception e) {
            fail(e.toString());
        }
    }

Testing Corner Cases

In the code for rotate_1_swap_bkwd, there’s a branch for length greater than 1. So let’s create tests that take different branches.

    @Test
    public void rotate_corner_cases() {
        // rotate an empty array
        try {
            int[] A = {};
            int[] A_correct = {};
            Rotate.rotate(A);
            assertArrayEquals(A, A_correct);
        } catch (Exception e) {
            fail(e.toString());
        }
		
        // rotate a 1-element array
        try {
            int[] A = {1};
            int[] A_correct = {1};
            Rotate.rotate(A);
            assertArrayEquals(A, A_correct);
        } catch (Exception e) {
            fail(e.toString());
        }

        // rotate a 2-element array
        try {
            int[] A = {1, 2};
            int[] A_correct = {2, 1};
            Rotate.rotate(A);
            assertArrayEquals(A, A_correct);
        } catch (Exception e) {
            fail(e.toString());
        }		
    }

Testing Big Inputs using Random Input Generation

We’ll need a way to check whether the rotate method did it’s job. We can do this by taking the specification for rotate and coding it up as the following Java method is_rotated that takes two arrays, a copy of the original one and the new one that was supposedly rotated. It returns true if A_new is the rotated version of A_orig.

static boolean is_rotated(int[] A_orig, int[] A_new) {
	if (A_orig.length < 2) {
        return Arrays.equals(A_orig, A_new);
	} else {
		boolean result = A_new[0] == A_orig[A_orig.length - 1];
		for (int i = 0; i != A_orig.length - 1; ++i) {
			result &= A_orig[i] == A_new[i + 1];
		}
		return result;
	}
}

Now we’re ready to test rotate on arbitrary arrays. We use the standard Java random number generator to choose an array length and to fill the array A with numbers. We then copy the array into A_orig, apply rotate to A, and then check the result by calling is_rotated with A_orig and A.

    @Test
    public void rotate_big() {
        // rotate a big array
        try {
            Random r = new Random(0);
            for (int t = 0; t != 50; ++t) {
                int n = r.nextInt(1000);
                int[] A = new int[n];
                for (int i = 0; i != n; ++i) {
                    A[i] = r.nextInt(100);
                }
                int[] A_orig = Arrays.copyOf(A, A.length);
                Rotate.rotate(A);
                is_rotated(A_orig, A);
            }
        } catch (Exception e) {
            fail(e.toString());
        }
    }