Slightly Irregular
By Rod Stephens
Arrays are great for storing large amounts of data. A program can use an array to store a collection of items identified by their positions in the array.
For some programs, however, arrays can be quite wasteful because all of the dimensions in an array must contain the same number of items. All of the rows in a two-dimensional array, for example, must have the same number of columns.
This is not a problem when the program must store data in most of the array's positions. For example, if the array represents the items in a Word table or an Excel spreadsheet, it will probably be mostly full.
On the other hand, some programs use array-like structures that would contain many unused entries if stored as an array. For example, an airline might use a connectivity matrix to indicate the distances between cities connected by its flights. The array entry Distance(I, J) would hold the distance between cities I and J if the airline flies between them.
Stored as an array, this matrix would waste a lot of space. Half of the entries are unnecessary because Distance(I, J) = Distance(J, I) for all cities I and J. Entries like Distance(I, I) are not needed because the airline probably does not run flights from a city to itself. Finally, connectivity matrixes like this one tend to be sparse. If the airline serves 20 major cities, it might run flights between only 30 of all the possible city pairs.
This article describes several different array-like data structures that allow a program to save space under circumstances such as these.
Triangular Arrays
An adjacency matrix contains many duplicated entries because Distance(I, J) = Distance(J, I). A program can avoid wasting space for duplicate entries using a triangular array. This array contains entries Distance(I, J) only for I > J. Figure 1 shows a triangular array where meaningful entries are indicated with an X.
Figure 1. A triangular array.
While VBA does not provide for triangular arrays, a program can build one by packing values into a normal one-dimensional array. The program maps the position Distance(I, J) in the triangular array, to the position B(X) in the one-dimensional array B where X = I * (I - 1) \ 2 + J. For example, if I = 3 and J = 2, then X = 3 * (3 - 1) \ 2 + 2 = 5. Figure 2 shows a triangular array packed into the one-dimensional array.
Figure 2. Packing a triangular array into a one-dimensional array.
To make using this array simple, the program can implement a TriangularArray class. The Value property procedures defined by the class allow the main program to treat TriangularArray objects as if they were two-dimensional arrays.
Figure 3 shows the TriangularArray class code. Note that the Value property procedures automatically swap the row and column values if the column number is greater than the row number. That makes the class treat the (I, J) and (J, I) values in the same way.
Option Explicit
Private B() As String
Private NumRows As Integer
Private MaxItem As Integer
' Initialize the one-dimensional array B.
Public Sub Initialize(ByVal rows As Integer)
NumRows = rows
MaxItem = (rows - 1) * (rows - 2) \ 2 + (rows - 2)
ReDim B(0 To MaxItem)
End Sub
' Set the value for Array(row, col).
Public Property Let Value(ByVal row As Integer, _
ByVal col As Integer, ByVal new_value As String)
Dim X As Integer
' If col > row, swap them.
If col > row Then
X = row
row = col
col = X
End If
X = row * (row - 1) \ 2 + col
B(X) = new_value
End Property
' Get the value for Array(row, col).
Public Property Get Value(ByVal row As Integer, _
ByVal col As Integer) As String
Dim X As Integer
' If col > row, swap them.
If col > row Then
X = row
row = col
col = X
End If
X = row * (row - 1) \ 2 + col
Value = B(X)
End Property
|
Figure 3. The TriangularArray class.
The TriangForm UserForm shown in Figure 4 allows you to experiment with a triangular array. Enter and row and column and click the Get button to make the program retrieve an array value. Be sure the row and column numbers are between 0 and 4 and that they are not equal.
Enter a row, column, and value, and click the Set button to make the program set an array entry's value. The program will update its labels to show the array's two-dimensional logical contents and its true one-dimensional arrangement.
Figure 4. TriangForm uses the TriangularArray class to manage a triangular array.
Variant Arrays
Some programs need to manage array-like structures that do not need the full number of entries used by an array, but that also have an irregular format that cannot exploited by a triangular array. For example, consider a sales system where each row in an array represents a sale and each column in a row represents a line item in that sale. LineItem(7, 4) describes the fourth item in the seventh sale.
This type of irregular structure is easy to implement in a relational database system like Access. A SALES table holds sales information. A SalesId field ties each record in this table to one or more entries in a LINE_ITEM table. Each sale might include a different number of items giving the irregular array shown in Figure 5.
Figure 5. Some programs need to use irregular array structures.
Variant arrays allow a program to manage this kind of irregular structure with remarkable ease. A variable of type variant can contain many different kinds of data including an array of variants. Because each element in such an array is a variant, it can also contain an array of variants. To implement an irregular array, a program can use a variant array of variant arrays.
The program builds a variant array using the Array command. This command takes as parameters the values that should be placed in the array. Once an array of arrays named TheArray has been created, the program can access the (I, J) element using the syntax TheArray(I)(J). This is slightly different from the syntax used to access a normal two-dimensional array TheArray(I, J).
Figure 6 shows how the IrregVar UserForm initializes its array of arrays. The array values are taken from the label controls A11, A12, etc. IrregVar is shown in Figure 7.
Dim arrays(1 To 5) As Variant
' Initialize the irregular array.
arrays(1) = Array( _
A11.Caption, _
A12.Caption, _
A13.Caption, _
A14.Caption)
arrays(2) = Array( _
A21.Caption, _
A22.Caption)
arrays(3) = Array( _
A31.Caption, _
A32.Caption, _
A33.Caption)
arrays(4) = Array( _
A41.Caption)
arrays(5) = Array( _
A51.Caption, _
A52.Caption, _
A53.Caption, _
A54.Caption)
TheArray = Array( _
arrays(1), _
arrays(2), _
arrays(3), _
arrays(4), _
arrays(5))
|
Figure 6. This code creates a variant array of variant arrays that contain strings.
Figure 7. IrregVar uses a variant array of variant arrays to manage an irregular list.
Linked Arrays
An alternative data structure for managing irregular arrays uses linked lists. Last month's algorithm column, "Linked Lists," explained how to create a flexible list of items. A program can use a linked list of linked lists to implement an irregular array.
Objects of the IrregularArrayRow class represent rows in the data structure. Each of these objects contains a reference to the first array cell in its row, and a reference to the IrregularArrayRow object representing the next row. The program uses a linked list of these objects to manage the rows in the irregular array.
Public NextRow As IrregularArrayRow
Public FirstInRow As IrregularArrayCell
The IrregularArrayCell class holds the items in the columns of each row. This class includes a reference to the next cell (column) in its row. Each IrregularArrayRow object contains a linked list of IrregularArrayCell objects representing the values in the row.
Public Value As String
Public NextCol As IrregularArrayCell
Figure 8 shows conceptually a linked list of linked lists built using these classes.
Figure 8. An irregular array made with a linked list of linked lists.
The program can build a wrapper class that uses these classes to implement the irregular array. The Value property procedures provided by the wrapper allow a program to access the array entries in an easy manner. Figure 9 shows the code used by the IrregularListArray class to manage an irregular array.
Private TopRow As IrregularArrayRow
' Create the linked list of rows.
Public Sub InitializeRows(ByVal rows As Integer)
Dim i As Integer
Dim new_row As IrregularArrayRow
Set TopRow = Nothing
For i = 1 To rows
' Create a new row header.
Set new_row = New IrregularArrayRow
Set new_row.NextRow = TopRow
Set TopRow = new_row
Next i
End Sub
' Give this row the indicated number of columns.
Public Sub InitializeRow(ByVal row As Integer, _
ByVal cols As Integer)
Dim i As Integer
Dim new_cell As IrregularArrayCell
Dim row_hdr As IrregularArrayRow
' Find the row header.
Set row_hdr = TopRow
For i = 2 To row
Set row_hdr = row_hdr.NextRow
Next i
' Create the desired number of cells.
Set row_hdr.FirstInRow = Nothing
For i = 1 To cols
' Create a new cell.
Set new_cell = New IrregularArrayCell
Set new_cell.NextCol = row_hdr.FirstInRow
Set row_hdr.FirstInRow = new_cell
Next i
End Sub
' Get the value for Array(row, col).
Public Property Get Value(ByVal row As Integer, _
ByVal col As Integer) As String
Dim row_hdr As IrregularArrayRow
Dim cell As IrregularArrayCell
Dim i As Integer
' Find the row.
Set row_hdr = TopRow
For i = 2 To row
If row_hdr Is Nothing Then Exit For
Set row_hdr = row_hdr.NextRow
Next i
If row_hdr Is Nothing Then
MsgBox "Invalid row number"
Exit Property
End If
' Find the column.
Set cell = row_hdr.FirstInRow
For i = 2 To col
If cell Is Nothing Then Exit For
Set cell = cell.NextCol
Next i
If cell Is Nothing Then
MsgBox "Invalid column number"
Exit Property
End If
Value = cell.Value
End Property
' Save the value for Array(row, col).
Public Property Let Value(ByVal row As Integer, _
ByVal col As Integer, ByVal new_value As String)
Dim row_hdr As IrregularArrayRow
Dim cell As IrregularArrayCell
Dim i As Integer
' Find the row.
Set row_hdr = TopRow
For i = 2 To row
If row_hdr Is Nothing Then Exit For
Set row_hdr = row_hdr.NextRow
Next i
If row_hdr Is Nothing Then
MsgBox "Invalid row number"
Exit Property
End If
' Find the column.
Set cell = row_hdr.FirstInRow
For i = 2 To col
If cell Is Nothing Then Exit For
Set cell = cell.NextCol
Next i
If cell Is Nothing Then
MsgBox "Invalid column number"
Exit Property
End If
cell.Value = new_value
End Property
|
Figure 9. The IrregularListArray class uses a linked list of linked lists to manage an irregular array.
The IrregLst UserForm shown in Figure 10 demonstrates the IrregularListArray class. Enter rows, columns, and values, and use the command buttons to examine and modify the array.
Figure 10. IrregLst uses a linked list of linked lists to manage an irregular list.
Sparse Arrays
Some programs use arrays that contain so few nontrivial entries that even irregular array techniques waste a lot of space. For example, the airline connectivity matrix described at the beginning of this article might contain very few valid entries. If the airline serves 20 major cities, it might run flights between only 30 of the 190 possible pairs of cities. Using a 20 by 20 matrix to store the connectivity matrix would be wasteful. The array would contain 400 entries of which only 30 would be needed. Even a triangular array would contain 160 unused entries.
A variation on the linked list irregular array can make representing sparse arrays much more efficient. The previous version contains a linked list for every row in the array. If the array contains row 100, the linked list must contain row entries for all of the rows between 1 and 100 even if they are empty.
Similarly each row's linked list contains a column cell for every entry in the row. If the row includes column 100, the linked list must hold a cell for columns 1 through 100 even if they are not all used.
The new sparse array version uses a linked list of rows that contains only those rows with interesting values. Each row has a linked list of cells that contains only columns that are actually used. Using this structure, the program can omit unnecessary rows and cells. Figure 11 shows this kind of sparse array graphically.
Figure 11. This sparse array contains only 7 of the 400 entries it would contain if it were a normal 20 by 20 array.
The SparseArrayRow class represents a row much as the IrregularArrayRow class does. The only difference is that it contains an additional Row variable that contains the index of the row represented by the object. As the program searches through the linked list of rows, it uses Row to determine when it has found the row it needs.
Public Row As Integer
Public NextRow As SparseArrayRow
Public CellSentinel As New SparseArrayCell
The SparseArrayCell class is similar to the IrregularArrayCell class except it also contains a Col variable indicating the column it represents. After the program has found the row it wants, it searches the linked list of SparseArrayCell objects using their Col values to decide when it has found the required value.
Public Col As Integer
Public Value As String
Public NextCol As SparseArrayCell
The SparseArray class uses SparseArrayRow and SparseArrayCell objects to implement a sparse array. The code is a little more involved than the code used for an irregular array using linked lists. The SparseArray class must use the Row and Col values provided by the row and column objects to locate the value it needs to change.
This class also has a special value, MissingValue, that indicates the default value it should use for any array entries that are not represented by a cell object. If the program asks for the value of an entry that is not stored in the array, the class returns MissingValue. If the program sets an entry to have this value, the SparseArray class removes the entry's cell from the data structure. If that is the only cell in its row, the SparseArray also removes the row's entry in the linked list of rows. Listing 1 [at the end of the article] shows the most interesting code used by the SparseArray class.
Example UserForm Sparse shown in Figure 12 demonstrates the SparseArray class. Enter rows, columns, and values, and use the command buttons to examine and modify the array values.
Figure 12. Sparse uses the SparseArray class to give a few values an array-like interface.
Conclusion
Arrays are fine for storing items that lie naturally in a rectangular arrangement. When the items are not so conveniently arranged, triangular, irregular, and sparse arrays can give the convenience of row and column addressing without the large memory overhead required by a full array.
Private RowSentinel As New SparseArrayRow
' The value that represents an empty cell.
Private p_MissingValue As String
' Get the value for Array(row, col).
Public Property Get Value(ByVal Row As Integer, _
ByVal Col As Integer) As String
Dim row_hdr As SparseArrayRow
Dim cell As SparseArrayCell
Dim no_value As Boolean
' Find the row.
Set row_hdr = RowSentinel.NextRow
Do
If row_hdr Is Nothing Then Exit Do
If row_hdr.Row >= Row Then Exit Do
Set row_hdr = row_hdr.NextRow
Loop
' See if we have the right row.
If row_hdr Is Nothing Then
no_value = True
ElseIf row_hdr.Row > Row Then
no_value = True
Else
no_value = False
End If
If no_value Then
' There's no such row. Return
' the missing value.
Value = p_MissingValue
Exit Property
End If
' Find the column.
Set cell = row_hdr.CellSentinel.NextCol
Do
If cell Is Nothing Then Exit Do
If cell.Col >= Col Then Exit Do
Set cell = cell.NextCol
Loop
' See if we have the right column.
If cell Is Nothing Then
no_value = True
ElseIf cell.Col > Col Then
no_value = True
Else
no_value = False
End If
If no_value Then
' There's no such column in this row.
' Return the missing value.
Value = p_MissingValue
Exit Property
End If
Value = cell.Value
End Property
' Save the value for Array(row, col).
Public Property Let Value(ByVal Row As Integer, _
ByVal Col As Integer, ByVal new_value As String)
Dim row_hdr As SparseArrayRow
Dim nxt_row As SparseArrayRow
Dim cell As SparseArrayCell
Dim nxt_cell As SparseArrayCell
Dim no_value As Boolean
' Find the row before this one.
Set row_hdr = RowSentinel
Do
Set nxt_row = row_hdr.NextRow
If nxt_row Is Nothing Then Exit Do
If nxt_row.Row >= Row Then Exit Do
Set row_hdr = nxt_row
Set nxt_row = row_hdr.NextRow
Loop
' See if we have the right row.
If nxt_row Is Nothing Then
no_value = True
ElseIf nxt_row.Row > Row Then
no_value = True
Else
no_value = False
End If
' If we don't have the row and the new
' value is not blank, add the row.
If no_value Then
If new_value = p_MissingValue Then _
Exit Property
' Add a new row after row_hdr.
Set nxt_row = New SparseArrayRow
Set nxt_row.NextRow = row_hdr.NextRow
Set row_hdr.NextRow = nxt_row
nxt_row.Row = Row
End If
' Now we are pointing to the right row.
' Find the right column.
Set cell = nxt_row.CellSentinel
Do
Set nxt_cell = cell.NextCol
If nxt_cell Is Nothing Then Exit Do
If nxt_cell.Col >= Col Then Exit Do
Set cell = nxt_cell
Set nxt_cell = cell.NextCol
Loop
' See if we have the right cell.
If nxt_cell Is Nothing Then
no_value = True
ElseIf nxt_cell.Col > Col Then
no_value = True
Else
no_value = False
End If
' If we don't have the cell and the new
' value is not blank, add the cell.
If no_value Then
If new_value = p_MissingValue Then _
Exit Property
' Add a new cell.
Set nxt_cell = New SparseArrayCell
Set nxt_cell.NextCol = cell.NextCol
Set cell.NextCol = nxt_cell
nxt_cell.Col = Col
End If
' We now have the cell. Set its value.
If new_value <> p_MissingValue Then
' Save the new value.
nxt_cell.Value = new_value
Else
' Delete the entry.
Set cell.NextCol = nxt_cell.NextCol
' If there are no more items in the
' row, delete the row, too.
If nxt_row.CellSentinel.NextCol Is Nothing Then
Set row_hdr.NextRow = nxt_row.NextRow
End If
End If
End Property
|
Listing 1: Code used in SparseArray.
Downloads
Download a 13K zip file containing VBA UserForms demonstrating the techniques described in this article. These are designed for use in VBA, but you can adapt them for Visual Basic, too.
| 
