8.5 Data Structures: Array Types

A record contains fields, each of which is potentially of a different type; such a composite type is often called heterogeneous. An array, on the other hand, contains elements all of which are of the same type; such a type is often called homogeneous. As with record types, we first declare an array type, which provides a template, or recipe, for creating arrays. Then we actually create an array--cause the compiler to allocate storage for it--with an array variable declaration.

Array Type Declaration

The array type FloatArray is declared below followed by the declaration of array X of type FloatArray:

    TYPE FloatArray IS ARRAY (1..8) OF Float;
    X : FloatArray;

The type declaration indicates our desire that each array be a collection of eight memory cells. The variable declaration causes a specific collection of eight cells to be associated with the name X; these memory cells are usually adjacent to each other in memory. Each element of array X can contain a single Float value, so a total of eight Float values can be stored and referenced using the array name X. (Note: The fact that an array's elements are in adjacent memory cells is not required by Ada, but it enables the compiler to get to all elements of an array just by knowing where the first element is stored.)

Referencing Elements of an Array

In order to process the data stored in an array, we must be able to reference each individual element. The array subscript (sometimes called array index) is used to differentiate between elements of the same array. For example, if X is the array with eight elements declared above, we refer to the elements of the array X as shown in Fig. 8.3.

Figure 8.3
The Eight Elements of the Array X

Figure 8.3

The subscripted variable X(1) (read as X sub 1) may be used to reference the first element of the array X; X(2), the second element; and X(8), the eighth element. The number enclosed in brackets is the array subscript. As we will see later, the subscript does not have to be a constant.

Example 8.5

Let X be the array shown in Fig. 8.3. Some statements that manipulate this array are shown in Table 8.1.

Table 8.1
Statements that Manipulate Array X

Statement			Explanation

Ada.Float_Text_IO.Put( X( 1));	Displays value of X( 1), or 16.0.
X( 4) := 25.0;			Stores value 25.0 in X( 4).
Sum := X( 1) + X( 2);		Stores sum of X( 1) and X( 2), or 28.0, in Sum.
Sum := Sum + X( 3);		Adds X( 3) to Sum.  The new Sum is 34.0.
X( 4) := X( 4) + 1.0;		Adds 1.0 to X( 4). The new X( 4) is 26.0.
X( 3) := X( 1) + X( 2);		Stores sum of X( 1) and X( 2), or 28.0, in X(
3).

The contents of array X are shown in Fig. 8.4 after execution of these statements. Only X( 3) and X( 4) are changed.

Figure 8.4
Array X After Modification

Figure 8.4

Example 8.6

Some declarations for a manufacturing plant operations program is shown below. The type declarations declare two scalar subtypes, EmpRange and HoursRange, and an enumeration type, Days, and two array types, EmpArray and DayArray. Two array variables, Vacation and PlantHours, are declared in the variable declaration section.

    NumEmp : CONSTANT Positive := 10;	       -- Number of employees
    SUBTYPE EmpRange IS Positive RANGE 1..NumEmp; -- subscript range
    SUBTYPE HoursRange IS Float RANGE 0.0..24.0;	 -- hours in a day
    TYPE Days IS
    	(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

    TYPE EmpArray IS ARRAY(EmpRange) OF Boolean;
    TYPE DayArray IS ARRAY(Days) OF NonNegFloat;

    Vacation : EmpArray;
    PlantHours : DayArray;

The array Vacation has ten elements (subscripts 1 through NumEmp); each element of array Vacation can store a Boolean value. The contents of this array could indicate which employees were on vacation (Vacation(i) is True if employee i is on vacation). If employees 1, 3, 5, 7, and 9 were on vacation, the array would have the values shown in Fig. 8.5.

Figure 8.5
Array Vacation

Figure 8.5

The array PlantHours has seven elements (subscripts Monday through Sunday). The array element PlantHours(Sunday) could indicate how many hours the plant was operating during Sunday of the past week. The array shown in Fig. 8.6 indicates that the plant was closed on the weekend, operating single shifts on Monday and Thursday, double shifts on Tuesday and Friday, and a triple shift on Wednesday.

Figure 8.6
Array PlantHours

Figure 8.6

SYNTAX DISPLAY
Array Type Declaration

Form:

TYPE array-type IS ARRAY subscript-type OF element-type;

Example:

SUBTYPE WordWidth IS Positive RANGE 1..32;
TYPE BitVector IS ARRAY ( WordWidth) OF Boolean;

Interpretation:

The identifier array-type describes a collection of array elements; each element can store an item of type element-type. The subscript-type can be any discrete type, that is, any predefined or user-defined integer or enumeration type or subtype. There is one array element corresponding to each value in the subscript-type. All elements of an array are of the same element-type.

Notes:

1. The element-type can be any predefined or user-defined scalar or composite type.

2. A floating-point type cannot be a subscript-type because it is not discrete, as it represents a continuous range of values.

3. It is unwise to use as a subscript-type a predefined type with a large range of values (e.g., Integer) because doing so would result in arrays with a gigantic number of elements. Generally, our subscript types will be either user-defined subtypes of Integer with fairly small ranges or user-defined enumeration types.

It is important to realize that an array type declaration does not cause allocation of storage space in memory. The array type describes the structure of an array only. Only variables actually store information and require storage. Storage space is not allocated until a variable of this type is declared.

Operations on Arrays

Two basic operations act on elements of an array: store and retrieve; also, as in records, assignment and equality test are available for array variables.

Store: The store operation inserts a value into the array. If A is an array, C is an expression that is compatible with the element type of A, and i is an expression that is compatible with the subscript type, the statement
A(i) := C;
stores the contents of C in element i of array A.
Retrieve: If C is a variable that is assignment compatible with the element type of A, the statement
C := A(i);
retrieves element i of array A and copies its value into C. For both of these statements the value of subscript i must be in the range of the array subscript type; otherwise, Constraint_Error will be raised.
Assignment: The assignment operator can also be used to copy the contents of one array to another if the arrays are compatible (of the same array type). If A and B are compatible arrays, the statement
A := B;
copies all values associated with array B to array A.
Equality Test: The equality and inequality operators can also be used to compare two arrays if they are compatible (of the same array type). If A and B are compatible arrays, the Boolean expression
A = B;
evaluates to True if and only if each element of A is equal to the corresponding element of B, and the Boolean expression
A /= B;
evaluates to True if and only if any elements of A are not equal to the corresponding elements of B.

The discussion above summarizes all the information that we need to know to use an array. We do not need to know how Ada stores the elements of an array in memory or how it implements the retrieve and store operators above.

Aggregate Array Assignment

As in the case of records, an entire array can be filled with values by three methods:

assignment to each element with an individual assignment statement, either randomly or sequentially;
copying one entire array to another with an array assignment statement, as discussed just above; and
storing values in an entire array using an aggregate, similar to that used in records.

It is the last method that concerns us now. Given an array A of type TestArray, the 100 Float values could, if they were all known in advance, be stored in A with a single statement such as

    A := ( 1.0, 27.0, 35.0, -4.0, 15.0, ...);

where the ellipsis must be replaced completely with the other 95 values. This is surely tedious, but it is better than writing 100 separate assignment statements. As in the case of records, named association can also be used:

    A := ( 1 => 1.0, 2 => 27.0, ...);

where the remaining 95 values also need to be supplied. Whereas in record aggregates we prefer named association, in array aggregates it can be cumbersome because an array can have a large number of elements. In using array aggregates we will generally use positional association unless there is a good reason not to do so.

A common and useful application of array aggregates is to initialize most or all elements of an array with the same value. Suppose that our array A were to be "cleared" so that all values were 0. This could be done in a loop:

    FOR I IN 1..MaxSize LOOP
	A( I) := 0.0;
    END LOOP;

or with a single aggregate assignment:

    A := ( 1..MaxSize => 0.0);

The aggregate assignment is certainly more concise, expresses the will of the programmer clearly, and may possibly execute faster. Suppose now that A were to be initialized such that its first 5 elements were as above, but the other 95 were to be 0. The assignment

    A := ( 1.0, 27.0, 35.0, -4.0, 15.0, OTHERS => 0.0);

does the trick. The OTHERS clause informs the compiler to store 0s in all those elements not expressly listed in the aggregate. If, say, only the first, third, and fifth elements were nonzero, named association could be used:

    A := ( 1 => 1.0, 3 => 27.0, 5 => 35.0, OTHERS => 0.0);

Finally, the assignment

    A := ( OTHERS => 0.0);

fills the entire array with 0s even more concisely: Because no other elements were explicitly filled, the OTHERS applies to all elements.

It is important to remember in using an aggregate that all elements of the array must be initialized by the aggregate; otherwise a compilation error results. OTHERS initializes all elements not otherwise given.

Exercises for Section 8.5

Self-Check

What is the difference between the expressions X3 and X( 3)?
For the following declarations, how many memory cells are reserved for data and what type of data can be stored there?
```
TYPE AnArray IS ARRAY( 1..5) OF Character;
Grades : AnArray;
```
When is the memory allocated--after the type declaration or after the variable declaration?
Write the variable and type declarations for all of the valid arrays below:
a. Subscript type Boolean, element type Float
b. Subscript type 'A'..'F', element type Integer
c. Subscript type Character, element type Boolean
d. Subscript type Integer, element type Float
e. Subscript type Character, element type Float
f. Subscript type Float, element type Character
g. Subscript type Day (enumeration type), element type Float

Programming

Given the following declarations:
```
A: ARRAY(1..5) OF Integer;
B: ARRAY(1..5) OF Integer;
C, D: ARRAY(1..5) OF Integer;

TYPE List IS ARRAY (1..5) OF Integer;

E: List;
F: List;
G, H: List;
```
Explain why each of the following statements is valid or invalid:
```
A := B;
C := D;
E := F;
G := H;
```
Check your results by writing and compiling a brief program incorporating these statements.