### 2.2.2. Two-dimensional arrays (class `array2`)

Learning objectives

 Class `array2` Preconditions Range Checking

In the previous section we have briefly mentioned the type `array<array<int> >`, which arises when the individual elements of an array are arrays themselves. Whereas an ordinary array extends only in one direction along the real axis, such an array of arrays extends in two directions, one direction per index set.

The special case that the inner arrays are all equally large, that is, that all of them store the same number of elements, occurs particularly often. The index set then can be illustrated as in Figure 2.5 as a rectangle of integer coordinates of the plane. Such a structure is called a two-dimensional array.

For this case, namely that the index set is a rectangle of integer coordinates, LEDA offers the type `array2`. This type differs from the type `array<array<int> >` by its syntax for access to individual elements and by a somewhat lower memory consumption; if in contrast the inner arrays are not all equally large, the type `array<array<int> >` rather comes into consideration.

As an example for the use of an `array2` we implement a famous population simulation, Conway's game of life: Comical little animals of a certain genre live, die and spawn in a two-dimensional, rectangular world that is divided up into parcels. At most one little animal lives in every parcel. Every parcel has 8 neighbor parcels (apart from the parcels on the edge). Time elapses in discrete steps of one month each. The population changes as follows from month to month:

• For a populated parcel:

• Each little animal with one or no neighbor little animal dies from loneliness. (1)

• Each little animal with four or more neighbors perishes due to overspill population. (2)

• Each little animal with two or three neighbors survives because of the balance of the social structure. (3)

• For an unpopulated parcel: A new little animal arises from procreation on a parcel with exactly three neighbors. (It is insignificant which of the three neighbor little animals are involved in the procreation and what their sex is.) (4)

Figure 2.6 shows how the succeeding population arises from an original population in one iteration step; it contains examples for each of the four rules.

Conway's game of life is an example of a cellular automaton. For the implementation of this automaton, that is for the representation of its states, we use a two-dimensional array

`array2<bool> cell(N,M);`

Every element `cell(i,j)` of this array specifies whether on parcel (i,j) in the current population a little animal is living or not.

To calculate the new state of the automaton, that is the next population, we look in a function `compute_next_state()` from every parcel (i,j) into all 8 neighboring parcels and count in a function `count_neighbors()` how many little animals are living in the neighbor parcels. Here the question arises how we can treat the problem of the edge efficiently. For this purpose, we initialize the parcels of the edge with 0 and count only the inner parcels as belonging to the actual domain. So the parcels on the edge are sentinels who simplify the access code. We iterate only over the inner parcels.

We store the information whether or not a parcel will house a little animal in the next state in a temporary, two-dimensional array `cell_new`. We copy this array in one single statement

`cell = cell_new;`

to `cell` at the end of the computation.

A simple print output of the population is carried out by the function `print_cells()`, which is invoked by `main()` in the main loop every time. After this the program waits for user input to give him the possibility of pursuing the evolution of the population step by step on the screen. He can let the simulation run into the next state by entering an arbitrary character except for `q`. An input of `q` (Quit) quits the program.

A problem arises at the initialization of the parcels in the function `init_cells()`. Best would be to use a (pseudo-)random number generator here; however, we will get to know such a generator not until in Section 2.5. (See also Exercise 18.) Therefore, we initialize the array with always the same Boolean values by a simple rule here.

Filename: ConwaysGameOfLife.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```#include <LEDA/array2.h>
#include <iostream>

using leda::array2;
using std::cout;
using std::cin;

const int N = 30; // number of cells on x-axis
const int M = 30; // number of cells on y-axis

array2<bool> cell(N+2,M+2), cell_new(N+2,M+2);

void init_cells();
void print_cells();
void compute_next_state();

int main()
{
char user_input;

init_cells();

while(true) {
print_cells();
compute_next_state();
cin >> user_input; // let user manually step through states
if(user_input == 'q') // q = 'Quit'
break;
}
}

void init_cells()
{
// init boundary
for(int i = 0; i < N+2; i++)
cell(i,0) = cell(i,M+1) = false;
for(int j = cell.low2(); j <= cell.high2(); j++)
cell(cell.low1(), j) = cell(cell.high1(), j) = false;

// init interior
for(int i = 1; i < N; i++)
for(int j = 1; j < M; j++)
cell(i,j) = (( i + j ) % 2 ? true : false);
// (better use random_source here)
}

void print_cells()
{
cout << "\n\n\n";
for(int j = 1; j <= M; j++) {
for(int i = 1; i <= N; i++)
cout << (cell(i,j) ? '*' : ' ');
cout << "\n";
}
}

int count_neighbors(const int i, const int j)
{
int nn = 0; // number of neighbors of cell(i,j)

nn += cell(i-1,j-1);
nn += cell(i-1,j);
nn += cell(i-1,j+1);
nn += cell(i,j-1);
// do not count cell(i,j) itself!
nn += cell(i,j+1);
nn += cell(i+1,j-1);
nn += cell(i+1,j);
nn += cell(i+1,j+1);

return nn;
}

void compute_next_state()
{
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++) {
int num_neighbors = count_neighbors(i,j);
bool new_state = true; // assume there will be life
if(cell(i,j)) // if populated
switch (num_neighbors) {
case 0: case 1:
case 4: case 5: case 6: case 7: case 8:
new_state = false;
}
else // not populated
if(num_neighbors != 3)
new_state = false;
cell_new(i,j) = new_state;
}

cell = cell_new; // bitwise copy by LEDA rule 8
}
```

(We should run this program now on our machine and watch the output.)

The coordinates of the index rectangle must be specified at the definition of an `array2`. The above definition

`array2<bool> cell(N+2,M+2);`

with two arguments defines implicitly the rectangle [0..N+1] x [0..M+1]. (To remain solid with the definition of one-dimensional arrays, the number of elements per dimension is specified here.) All 4 coordinates can also be specified explicitly, like in

`array2<bool> cell(0,N+1,0,M+1);`

As a matter of course the lower bound of the interval does not have to be 0 here; it may well be any arbitrary (even negative) integer number.

The element at position (i,j) can be accessed via the overloaded function operator `cell(i,j)`. It returns a reference to this element.

According to the methods `low()` and `high()` of class `array`, class `array2` offers the methods `low1()`, `high1()`, `low2()`, and `high2()`, which return the smallest and largest index in the respective dimension, respectively. An example of the use of these methods is found in the second for-loop of `init_cells()`.

#### Preconditions

What would have happened here if we had done without the sentinel cells on the edge? Would we have been able to rely on the class `array2` being so clever to intercept an access to elements with a negative or too large index in `count_neighbors()` (and perhaps to simply return 0, then)?

The description of the array access operation `A(i,j)` on the manual page of class `array2` contains the precondition that the indices i and j must lie in the permitted domain inside the index rectangle. In principle, all integer numbers would be possible as indices, of course.

Frequently, a certain operation is defined on a certain LEDA type only for a subset of all arguments being possible in principle. The preconditions of an operation on a LEDA data type define exactly with which conditions the arguments of this operation must comply. These preconditions are listed on the appropriate manual page at the respective operation.

Generally, if a precondition is violated, then the result of the operation is undefined. Everything can happen! It may happen that the operation interrupts with an error message or returns an arbitrary result. It may happen that it does not interrupt at all. In the worst case the program may even crash.

Does LEDA check the preconditions of the operations? Sometimes yes and sometimes no. One can generally say that preconditions are never checked if this would increase the order of the running time of the operation (that is by more than a constant factor).

#### Automatic range checking

It isn't laborious to check whether an index lies within its permitted domain; this check can be executed with a constant number of operations. LEDA therefore performs an automatic range checking when accessing array elements. This increases the overall running time of the program by at most a small factor, but not the (time-complexity) order of the running time.

So if we had forgotten above to work with the sentinel cells and accessed a not existing element by means of a not permissible index, then LEDA would have discovered this at runtime and exited the program with a corresponding warning message.

This behavior is very useful in the development phase of a program. It can be, however, disturbing in the end product because it can unnecessarily inflate the running time when many array accesses are performed. Therefore the checking of all preconditions (not only the range check of array accesses) can be switched off by the compiler flag `-DLEDA_CHECKING_OFF`.

#### Tips for the use of two-dimensional arrays

• One should use two-dimensional arrays if one knows the number of elements one wants to store in advance (at least approximately) and if one must have fast access to the elements via two integer indices.
• In contrast, if the number of elements is unknown in advance or elements are inserted or deleted frequently, one of the combinations array of lists, list of arrays, set of arrays, array of sets, list of lists, list of sets, set of sets, or set of lists may be more helpful.
• For matrix operations the special LEDA types for matrices and vectors are recommendable: `matrix`, `vector`, `integer_matrix`, and `integer_vector`.

#### Implementation and further information

The class `array2` is implemented by two-dimensional C++ arrays. The access to an element takes constant time. If n·m objects of type `T` are stored in an `array2`, the space requirement is O(n·m·sizeof(T)).

More about two-dimensional arrays can be found on the corresponding manual page.

#### Exercises

 Exercise 6. The eight-queens-problem consists of placing eight queens on a chessboard so that no queen attacks another one. Write a program that calculates all possible solutions of this problem. Use an `array2` for the coding of the chessboard. Exercise 7. In the game Tic-Tac-Toe two players are facing each other on a field of 3 times 3 squares. They alternately mark crosses (player A) or circles (player B) on still free squares. A player wins if he can mark adjacent 3 crosses or 3 circles, respectively, in a line, column or diagonal. Figure 2.7 shows a game course in which player A wins in the 7th move.Write a program that proves that the score is a draw from the very first move on, that is, that the game always ends in a tie if both players always make an optimal move in every position, or watch the film “Wargames”.