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 twodimensional 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 twodimensional, 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 twodimensional 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,
twodimensional 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 xaxis const int M = 30; // number of cells on yaxis 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(i1,j1); nn += cell(i1,j); nn += cell(i1,j+1); nn += cell(i,j1); // do not count cell(i,j) itself! nn += cell(i,j+1); nn += cell(i+1,j1); 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 onedimensional 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 forloop 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 (timecomplexity) 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
.
matrix
,
vector
,
integer_matrix
, and
integer_vector
.
The class array2
is implemented by
twodimensional 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 twodimensional arrays can be found on the corresponding manual page.
Exercise 6.  The eightqueensproblem 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

Exercise 7.  In the game TicTacToe 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”. 