12.1 Data Structures: Multidimensional Arrays

Example 12.1

One two-dimensional object we are all familiar with is a tic-tac-toe board. The declarations

    SUBTYPE MoveRange IS Positive RANGE 1..3;
    TYPE GameSymbol IS (X, O, E); -- for Tic Tac Toe; E indicates empty cell
    TYPE BoardArray IS ARRAY (MoveRange, MoveRange) OF GameSymbol;
    
    Empty     : CONSTANT GameSymbol := E;
    TicTacToe : BoardArray;

allocate storage for the array TicTacToe. This array has nine storage cells arranged in three rows and three columns. A single enumeration value may be stored in each cell. TicTacToe is a two-dimensional array as pictured in Figure 12.1.

Figure 12.1
A Tic-Tac-Toe Board Stored as Array TicTacToe

          Column
   
           1  2  3

       1   X  O  E
      
   Row 2   O  X  O <----- TicTacToe(2,3) 

       3   X  X  X

This array has nine elements, each of which must be referenced by specifying a row subscript (1, 2, or 3) and a column subscript (1, 2, or 3). Each array element contains a character value. The array element TicTacToe(2,3) pointed to in Fig. 12.1 is in row 2, column 3 of the array; it contains the enumeration value O. The diagonal line consisting of array elements TicTacToe(1,1), TicTacToe(2,2), and TicTacToe(3,3) represents a win for player X; each cell contains the value X.

SYNTAX DISPLAY
Array Type Declaration (Multidimensional)

Form:

    TYPE multidim IS ARRAY (subscript₁, subscript₂, ... , subscript_n) 
	OF element-type;

Example:

    TYPE YearByMonth IS ARRAY (1900..1999, Month) OF Real;
    TYPE Election IS ARRAY (Candidate, Precinct) OF Integer;

Interpretation:

Subscript_i represents the subscript-type of dimension i of array type multidim. The subscript-type may be any discrete type, that is, integer or enumeration type or subtype. The element-type may be any predefined type or a previously defined scalar or composite data type.

Although we will focus our discussion on arrays with two and three dimensions, there is no limit on the number of dimensions allowed in Ada. However, there may be a limit imposed by the particular implementation you are using. The amount of memory space allocated for storage of a multidimensional array can be quite large, as it is the product of the ranges.

Example 12.2

The array Table declared below

    Table : ARRAY (1..7, 1..5, 1..6) OF Float;

consists of three dimensions: the first subscript may take on values from 1 to 7; the second, from 1 to 5; and the third, from 1 to 6. A total of 7 x 5 x 6, or 210, floating-point numbers may be stored in the array Table. All three subscripts must be specified in each reference to array Table (e.g. Table(2,3,4)).

Storage of Multidimensional Arrays

Most Ada implementations store multidimensional arrays in adjacent memory cells to simplify accessing the individual elements. The elements of a two-dimensional array are often stored in order by row (i.e., first row 1, then row 2, and so on). This is called row-major order. To access a particular array element, the compiler computes the offset of that element from the first element stored. To perform this computation the compiler must know the size of each element in bytes and the number of elements per row. Both values are available from the array type declaration.

For example, the array TicTacToe would be stored in row-major form as shown in Figure 12.2. There are three elements per row and each element occupies one byte of storage. The offset for element TicTacToe(i,j) is computed from the formula

Offset = (i - 1) × 3 + (j - 1)

This formula gives a value of 0 as the offset for element TicTacToe(1,1) and a value of 5 as the offset for element TicTacToe(2,3).

Figure 12.2
Array TicTacToe in Memory, Row-Major Form

Figure 12.2

Not all compilers use a row-major form for a multidimensional array; Fortran compilers, for instance, store arrays in a column-by-column, or column-major, form. It is interesting to note that the Ada standard does not require a particular way of storing these structures: an Ada compiler can use row-major, column-major, or some other, unusual, form. Usually there is no particular reason for you to know the storage method; it is an abstraction just like floating-point numbers are.

Manipulation of Two-Dimensional arrays

A row subscript and a column subscript must be specified to reference an element of a two-dimensional array. The type of each of the two subscripts must be compatible with the corresponding subscript type specified in the array declaration. Assuming that Game_IO is an instance of Ada.Text_IO.Enumeration_IO for values of type GameSymbol, the loop

    FOR Column IN MoveRange LOOP
      Game_IO.Put (Item => TicTacToe(1,Column));
    END LOOP;

displays the first row of array TicTacToe (TicTacToe(1,1), TicTacToe(1,2), and TicTacToe(1,3)) on the current output line. The loop

    FOR Row IN MoveRange LOOP
      Game_IO.Put (Item => TicTacToe(Row, 1));
      Ada.Text_IO.New_Line;
    END LOOP;

displays the second column of TicTacToe (TicTacToe(1,2), TicTacToe(2,2), and TicTacToe(3,2)) in a vertical line.

Example 12.3

We can use aggregates in multidimensional arrays just as we did in one-dimensional arrays. We can use an aggregate assignment

    TicTacToe := (MoveRange => (MoveRange => EMPTY));

or even

    TicTacToe := (OTHERS => (OTHERS => EMPTY));

The double aggregate indicates that for each of the rows, all the columns are to be set to Empty.

We can use nested loops to access all elements in a multidimensional array in a predetermined order. In the next examples, the outer-loop control variable determines the row being accessed, and the inner-loop control variable selects each element in that row.

Example 12.4

Procedure Display_Board in Program 12.1 displays the current status of a tic-tac-toe board. A sample output of this procedure is shown in Figure 12.3.

Program 12.1
Procedure DisplayBoard

PROCEDURE Display_Board (TicTacToe : BoardArray) IS
-- Pre : Array TicTacToe is defined.
-- Post: Displays all elements of array TicTacToe.
 
BEGIN -- Display_Board 

  Ada.Text_IO.Put(Item => "-------");
  Ada.Text_IO.New_Line;
  FOR Row IN MoveRange LOOP
    -- Display all columns of current row  
    FOR Column IN MoveRange LOOP
      Ada.Text_IO.Put(Item => "|");
      Game_IO.Put(Item => TicTacToe (Row,Column));
    END LOOP;
    Ada.Text_IO.Put(Item => "|");
    Ada.Text_IO.New_Line;
    Ada.Text_IO.Put(Item => "-------");
    Ada.Text_IO.New_Line;
  END LOOP;

END Display_Board;

Figure 12.3 Sample Output of Display_Board

     -------
     |X|O|E|
     -------
     |O|X|O|
     -------
     |X|E|X|
     -------

Example 12.5

Function Is_Filled in Program 12.2 returns a value of True if a tic-tac-toe board is all filled up; it returns a value of False if there is at least one cell that contains the value Empty. We are assuming that all cells are initialized to Empty before the game begins. To move to a particular cell, the current player replaces the constant Empty in that cell with an X or an O. Function Is_Filled could be called before making a move to determine whether there were any possible moves left. The IF statement

    IF IsFilled(TicTacToe) THEN
     	Ada.Text_IO.Put(Item => "Game is a draw!");
    	Ada.Text_IO.New_Line;
    END IF;

displays an appropriate message when there are no moves.

Program 12.2
Function Is_Filled

FUNCTION Is_Filled (TicTacToe : BoardArray) RETURN Boolean IS
-- Pre : Elements of array TicTacToe are assigned values.
--       An empty cell contains the value Empty
-- Post: Returns True if array is filled; otherwise,
--       returns False.

BEGIN  -- Is_Filled 

  -- Set Board_Filled to False and return if any cell is empty. 
  FOR Row IN MoveRange LOOP
    FOR Column IN MoveRange LOOP
      IF TicTacToe(Row,Column) = Empty THEN
        RETURN False;       -- board is not filled  
      END IF;
    END LOOP;
  END LOOP;
  -- assertion: No empty cells were found.  

  RETURN True;                -- board is filled  

END Is_Filled;

Example 12.6

Procedure Enter_Move in Program 12.3 is used to enter a move into the array TicTacToe. Enter_Move calls procedure Robust_Input.Get (see Program 6.10) twice to enter a pair of values into the move coordinates, MoveRow and MoveColumn. If the cell selected by these coordinates is empty, its value is reset to the character stored in Player (X or O).

Program 12.3
Function Enter_Move

PROCEDURE Enter_Move (Player : GameSymbol;
                     TicTacToe : IN OUT BoardArray) IS
-- Pre : Player is "X" or "O" and array TicTacToe has at least
--       one empty cell.
-- Post: The value of Player is stored in the empty cell of
--       TicTacToe whose coordinates are read in; the rest
--       of array TicTacToe is unchanged.

  MoveRow    : MoveRange;    -- coordinates of selected cell
  MoveColumn : MoveRange;

BEGIN  -- Enter_Move

  LOOP
    Ada.Text_IO.Put(Item => "Enter your move row and then the column");
    Ada.Text_IO.New_Line;
    RobustInput.Get (MinVal => 1, MaxVal => 3, Item => MoveRow);
    RobustInput.Get (MinVal => 1, MaxVal => 3, Item => MoveColumn);

    IF TicTacToe(MoveRow, MoveColumn) = Empty THEN
      EXIT;
    ELSE
      Ada.Text_IO.Put(Item => "Cell is occupied - try again");
      Ada.Text_IO.New_Line;
    END IF;
  END LOOP;
  -- assertion: A valid move is entered

  TicTacToe(MoveRow, MoveColumn) := Player;  -- Define cell

END Enter_Move;

Exercises for Section 12.1

Self-Check

Declare a three-dimensional array type where the first subscript consists of letters from 'A' to 'F', the second subscript consists of integers from 1 to 10, and the third consists of the user defined type Day. Floating-point numbers will be stored in the array. How many elements can be stored in an array with this type?
Assuming the declarations below
```
    TYPE MatrixType IS ARRAY (1..5, 1..4) OF Float;
    Matrix : MatrixType,
```
answer the following questions:
a. How many elements are there in array Matrix?
b. Write a statement to display the element in row 3, column 4.
c. Assuming row-major storage, what is the offset for this element?
d. What formula is used to compute the offset for Matrix(i, j)?
e. Write a loop that computes the sum of elements in row 5.
f. Write a loop that computes the sum of elements in column 4.
g. Write a nested loop structure that computes the sum of all array elements.
h. Write nested loops that display the array after it has been rotated 90 degrees counterclockwise. Your program segment should display column 4 as the first output line, column 3 as the second output line, and so on.

Programming

Write a function that determines whether either player has won a game of tic-tac-toe. The function should first check all rows to see if one player occupies all the cells in that row, then all columns, and then the two diagonals. The function should return a value from the enumeration type (NoWinner, XWins, YWins).