### WEBINAR:

On-Demand

Full Text Search: The Key to Better Natural Language Queries for NoSQL in Node.js

was surfing the web the other day, looking for Visual Basic questions to answer, when I stumbled across an old FAQ that explained why Visual Basic no longer has arrays with non-zero lower bounds. I don't really buy the

explanation given by Paul Vick at (it seems like the needs of the none outweighing the needs of the many to me) but it did start me thinking about arrays.

Visual Studio provides arrays of any data type. You can make one-, two-, and higher-dimensional arrays of integers, strings, objects, structures, or whatever. But there are a couple of useful kinds of arrays that Visual Studio doesn't provide. This article explains how you can implement three of these: triangular arrays, sparse arrays, and arrays with non-zero lower bounds.

When you create a typical array, Visual Studio allocates memory for a block of items that includes one entry for every possible combination of indexes. For example, the following code allocates an array of Booleans containing 1 million entries:

```
Dim is_connected(1000, 1000) As Boolean
```

In some applications, you don't really need all these entries. For example, suppose the application tests connectivity in an electric, airline, or other network and the method

is_connected(R, C) returns

true if there is a link connecting location

R with location

C. Assuming the network is non-directional (so that a link between

R and

C also means there is a link between

C and

R), then this array contains a lot of duplicated information. If

is_connected(R, C) is

true then

is_connected(C, R) is also

true.

You can avoid storing all of this duplicated information and save half of the array's space by using a triangular array. A

*triangular array* stores only the values for

is_connected(R, C) where

R >= C. It deduces the values of other entries by switching the order of R and C.

The TriangularArray class described here saves this space by mapping the entries in the array into a one-dimensional storage array.

Figure 1 shows a small triangular array on top and the linear storage of the array's values on the bottom.

| |

Figure 1. Triangle Tricks: The TriangularArray class stores entries for a triangular array (top) in a linear storage array (bottom). |

The only tricky part is figuring out the index in the storage array that corresponds to an entry in the triangular array.

Consider an item in array position (

R, C), where "R" is the row and "C" is the column. The rows above this one contain

1 + 2 + 3 + ... + R entries. You may recall that there is a simple formula for this kind of sum:

1 + 2 + ... + R = R * (R + 1) / 2.

Now notice that the number of items to the left of this one in its row is

C, so the total number of items that come before this one is

R * (R + 1) / 2 + C.

For example, consider item

E in

Figure 1. This item is at position (

2, 1) in the triangular array (be sure to start counting from index 0), so its position in the storage array is

2 * (2 + 1) / 2 + 1 = 3 + 1 = 4, which you can verify in

Figure 1.

The following code shows a TriangularArray class. I've removed some bounds checking code to make the code easier to read:

```
Public Class TriangularArray(Of T)
Private m_Width As Integer
Private m_Values() As T
' Allocate storage.
Public Sub New(ByVal width As Integer)
m_Width = width
ReDim m_Values(m_Width * (m_Width + 1) \ 2 - 1)
End Sub
' Return the item at position (row, column).
Default Public Property Item( _
ByVal r As Integer, ByVal c As Integer)
Get
Return m_Values(ItemIndex(r, c))
End Get
Set(ByVal value)
m_Values(ItemIndex(r, c)) = value
End Set
End Property
' Calculate the item's position in the array.
Private Function ItemIndex(ByVal r As Integer, _
ByVal c As Integer) As Integer
If r >= c Then Return r * (r + 1) \ 2 + c
Return c * (c + 1) \ 2 + r
End Function
End Class
```

The class's constructor takes the array's width as a parameter, and allocates enough space to hold all of the array's items.

The

Item property gets or sets an item in the array. It calls the

ItemIndex method to convert the item's row and column numbers into an index in the storage array and gets or sets the appropriate value.

The

Default keyword makes

Item the default property for the class. That means the main program can treat an object of the class as if it were an array and the "index" passed to the object is sent as a parameter to the property. (In C#, this property is the class indexer.)

The

ItemIndex method simply returns

R * (R + 1) / 2 + C as described earlier. If

R < C, it swaps the roles of

R and

C.

The sample program

TriangularArray (available with the

downloadable code for this article in both Visual Basic and C#), demonstrates the class for the array shown in

Figure 1. (For extra credit, try to figure out how to modify the class slightly to handle arrays that don't need to contain items on the diagonal where

R = C.)