Using an expandable array to store the edges in each cell

We use a square array with one expandable array per cell, as shown in figure 4, to store which edges of each map pass thru each cell. Section 7.4 lists other possibilities. The expandable array data structure has the following properties.

• The grid is a square array of pointers, one per cell.

• Each pointer is initially null.

• When the first edge is inserted into a cell, then space for, say, three edges is allocated, and the cell pointer made to point to it. In C, the allocation would be done with the malloc routine. We must also allocate two counters to record the number of edges of each map in this cell.

• If a fourth edge is inserted into the cell, then reallocate a bigger array, and copy the old data over. In C, the realloc does all this in one operation. The efficiency question is how often this reallocation occurs. An example shows that this is not often. Imagine that every time we overflow, then we reallocate the array with twice the size. Now, add one million edges one by one. There will be only 20 reallocations. The average edge will be copied only once. In fact, one edge will be copied 20 times, 2 edges 19 times, ..., 250000 edges once, and 500000 edges not at all.

  In general, if the array size is grown by a factor each time (here ) from one element to a large size, then each element is copied an average of times (here 1).

=7in

  
Figure 4: Expandable Array for Storing Edges in Cells

This method does not waste space for multiple pointers or cell numbers, but requires only two extra words per non-empty cell, for the two counters. We can also randomly access edges in a cell. In fact, in the program, the syntax is that of indexing an array. Unlike linked lists, a popular alternative, expandable arrays keep the data for each cell contiguous, so that fewer disk accesses are required when paging the virtual memory that the allocator would use when real memory was insufficient. If the available space is so marginal that the expandable array overhead is intolerable, then one time versus space tradeoff is as follows. Modify the program to run once to accumulate only the number of edges in each cell, but not their names. Then allocate exactly the required space for each cell, and run the program again to do the calculations.

We do need space for the whole cell matrix even if most cells are empty. This space could be reduced by using a hash table.