4.3 Implementing 2-D Arrays

We now turn our attention to the implementation of the 2-D array. There are several approaches that we can use to store and organize the data for a 2-D array. Two of the more common approaches include the use of a single 1-D array to physically store the elements of the 2-D array by arranging them in order based on either row or column, whereas the other uses an array of arrays. We are going to use the latter approach to implement the Array2D abstract data type and delay discussion of the former approach until later in the chapter.

When using an array of arrays to store the elements of a 2-D array, we store each row of the 2-D array within its own 1-D array. Then, another 1-D array is used to store references to each of the arrays used to store the row elements. Figure 4.3.1 shows the abstract view of a 2-D array and the physical storage of that 2-D array using an array of arrays.

Figure 4.3.1: A sample 2-D array: (a) the abstract view organized into rows and columns

and (b) the physical storage of the 2-D array using an array of arrays.

Some languages that use the array of arrays approach for implementing a 2-D array provide access to the individual arrays used to store the row elements. Having access to the given 1-D array, these languages use the subscript notation x[r][c] for referencing an individual element. To be consistent in our approach of hiding the implementation details, we do not provide access to any of the 1-D arrays used to store the elements of the 2-D array. Thus, our implementation requires the use of the subscript notation x[r,c].

Constructor

To implement the Array2D abstract data type, we begin with the constructor. The constructor creates a data field named _theRows to which an Array object is assigned. This is the main array used to store the references to the other arrays that are created for each row in the 2-D array.

Basic Operations

Note that the size of the array that is passed as arguments to the constructor is not saved in data fields. The numRows method can obtain the number of rows by checking the length of the main array, which contains an element for each row in the 2-D array:

To determine the number of columns in the 2-D array, the numCols method can simply check the length of any of the 1-D arrays used to store the individual rows:

The clear method can set every element to the given value by calling the clear method on each of the 1-D arrays used to store the individual rows. This is easily done by iterating over the array stored in _theRows, one element at a time:

Getting an Element

Access to individual elements within a 2-D array requires a 2-tuple or two-component subscript, one for each dimension. In mathematics, the 2-tuple subscript is generally notated as x_r,c. In modern programming languages, a 2-tuple subscript is given either as x[r][c] or x[r,c]. In Python, we can use the latter notation in conjunction with the __getitem__ and __setitem__ special methods that are applied using the subscript operator. This will allow for a more natural use of the two-dimensional array instead of having to invoke a named method.

The __getitem__ special method takes a single index argument as specified in the method definition. This does not restrict the subscript to a single index value, however. When a multi-component subscript is specified (y = x[i,j]), Python automatically stores the components in a tuple in the order listed within the brackets and passes the tuple to the ndxTuple argument of the __getitem__ special method.

The contents of the ndxTuple contain the row and column indices for the element of of the 2-D array being accessed.

After verifying both subscripts are within the valid range, we extract a reference to the 1-D array used to store the given row from the 1-D array _theRows.

With this reference stored in the local variable the1dArray, we can then apply the subscript operator to the 1-D array with the appropriate column index and return the contents of that element.

The complete implementation of the __getitem__ special method follows:

You may notice a second assert statement at the beginning of the __getitem__ method. This is needed because Python does not examine the number of components specified in the subscript before passing the tuple to the subscript operator special method. For example, there is nothing to prevent us from incorrectly supplying three components such as box[i,j,k] instead of two. In fact, Python would have no way of knowing that we only need two components for the 2-D array subscript. Thus, we must first check to make sure the subscript tuple passed to the method contains only two elements.

When making the assertion about the size of the ndxTuple, we assume a tuple is passed to the subscript operator and use the len function to verify its length. When a single-component subscript x[0] is supplied to a subscript operator method, as is done with the Array class, the argument is a single integer value. The len function can only be used with the container types and not individual values. It does generate its own error, however, when used improperly. Thus, Python's len function is used to ensure two components are supplied for all Array2D objects.

Setting an Element

The __setitem__ operator method can be implemented in a similar fashion to __getitem__.

There are two major differences, however. The first is that the __setitem__ special method requires a second argument to receive the value to which an element is set.

The second difference is that the __setitem__ special method modifies the indicated element with the new value instead of returning a value.

The source listing below provides a complete implementation of the Array2D class, which is part of the ezarrays module provided with the textbook.