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.

Figure 2.5. A two-dimensional array

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:

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.

Figure 2.6. The rules of Conway's game of the life

The rules of Conway's game of the life

One iteration in Conway's game of life. Little animals 1 die from loneliness. Little animal 2 dies from overspill population. Little animal 3 survives. Little animals 4 are procreated.


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.

Figure 2.7. Tic-Tac-Toe

Tic-Tac-Toe


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”.




Imprint-Dataprotection