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, which 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.
#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 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().
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).
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.
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.
Exercise 6. |
The eight-queens-problem consists of placing eight queens on a chessboard so that no queen attacks another one. Write a program which 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 which 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”. |