# 18 Segmented Arrays

Recall that Chapter 17, on conformal arrays, discusses how multiple arrays can be used to organize records containing different fields (or tables containing rows and columns). This chapter considers a special case of this problem in which all of the elements of the records and fields (or rows and columns) are of the same type.

# Motivation

Suppose you are working for a medical researcher who has collected data on the heights and weights of a variety of different people. You know from Chapter 17 that you could use two conformal arrays for this purpose, one containing the heights and one containing the weights (with the index used to identify the individual). However, since all of the measurements are `double`

values, it’s also possible to organize them in one array. Such an array is said to be *segmented* (or *packed*).

# Review

Suppose you have two arrays of the same size, both of which contain `double`

values. One array with twice as many elements could, obviously, hold all of the values in the two arrays. For example, suppose you have the following two arrays (each of length 4):

double[] heights = { 60.0, 62.0, 65.0, 70.0}; double[] weights = {100.0, 110.0, 120.0, 140.0};

Then, you could store all of the elements of both arrays in one array of length 8.

If you could then create an algorithm for finding/calculating the appropriate index, you could use this single array instead of the two individual arrays. Of course, the algorithm for finding/calculating the appropriate index is intimately related to the way in which the single array is organized. So, the two issues must be considered together.

# Thinking About The Problem

While there are many ways of putting the elements from two arrays into one array (with twice the size), there are two that are particularly sensible. Each deserves some consideration.

In the first, you would *concatenate* the two arrays. That is, you would put the elements of one after the elements of the other.^{[1]} This could be accomplished as follows:

int n = 4; for (int i = 0; i < n; ++i) { concatenated[i] = height[i]; } for (int i = 0; i < n; ++i) { concatenated[n + i] = weight[i]; }

The first loop assigns element `i`

of `height`

to element `i`

of `concatenated`

, and the second loop assigns element `i`

of `weight`

to element `n+i`

of `concatenated`

. In other words, the first loop assigns the four elements of `height`

to the first four elements of `concatenated`

, and the second loop assigns the four elements of `weight`

to the last four elements of `concatenated`

.

Though it’s not central to the point of this chapter, it should be clear to you that this same algorithm could be implemented with a single loop as follows:

int n = 4; for (int i = 0; i < n; ++i) { concatenated[i] = height[i]; concatenated[n + i] = weight[i]; }

Regardless of the implementation, the end result is an array that is organized as in Figure 18.1.

In the second, you would interleave the two arrays. That is, you would alternate elements from the two arrays.^{[2]} This could be accomplished as follows:

int n = 4; for (int i = 0; i < n; ++i) { interleaved[2 * i] = height[i]; interleaved[2 * i + 1] = weight[i]; }

The first statement in the loop assigns elements 0, 1, 2, and 3 (i.e., the values of `i`

) of `height`

to elements 0, 2, 4, and 6 (i.e., the values of `2*i`

) of `interleaved`

. The second statement in the loop assigns elements 0, 1, 2, and 3 (i.e., the values of `i`

) of `weight`

to elements 1, 3, 5, and 7 (i.e., the values of `2*i+1`

) of `interleaved`

. The end result is an array that is organized as in Figure 18.2.

While both of these approaches work, the interleaved approach is more appropriate for the problem at hand. To see why, consider Figure 18.3, which contains a more abstract conceptualization of the array in Figure 18.2. When interleaved, the fields of each record are kept together, making it easier to visualize the segmented array.

# The Pattern

In general, if you let `recordSize`

denote the number of fields in each record, `record`

denote the record of interest (0-based), `field`

denote the field of interest (also 0-based), and `index`

denote the index of the element in the segmented array, then you can easily convert back and forth between the two approaches.

First, given the `record`

and `field`

, you can calculate the `index`

as follows:

index = (record * recordSize) + field;

This is the same algorithm used in the loop to interleave the elements.

Second, given the `index`

, you can calculate the `record`

and `field`

as follows:

record = index / recordSize; field = index % recordSize;

Note that this algorithm uses the techniques for arithmetic on the circle from Chapter 4.

# Examples

Segmented arrays are most frequently used with `String`

objects because they can be used to represent many other data types. One very common use involves command-line arguments.

Recall that the `main()`

method of a Java application has a single `String[]`

parameter, commonly named `args`

. When an application is executed from the command line, all of the `String`

objects after the name of the main class are passed to the `main()`

method using this array. For example, given the following method:

public static int toIndex(int record, int field, int recordSize) { return (record * recordSize) + field; }

you could pass the heights and weights of multiple people into `main()`

as an interleaved array of `String`

objects named `args`

and “extract” information as needed. For example, if you wanted to assign the weight and height of person 1 to the variables `w`

and `h`

, respectively, you could do so as follows:

h = Double.parseDouble(args[toIndex(1, 0, 2)]); w = Double.parseDouble(args[toIndex(1, 1, 2)]);

`toIndex(1, 0, 2)`

evaluates to `2`

, so element `2`

of `args`

(i.e., `"62.0"`

using the data from Figure 18.2) would be passed to `Double.parseDouble()`

, and `62.0`

would be assigned to `h`

. Similarly, `toIndex(1, 1, 2)`

evaluates to `3`

, so element `3`

of `args`

(i.e., `"110.0"`

using the data from Figure 18.2) would be passed to `Double.parseDouble()`

, and `110.0`

would be assigned to `w`

.

You could, of course, include the same logic in a loop and extract all of the heights and weights in the command-line arguments into conformal arrays as follows:

int recordSize = 2; int records = args.length / recordSize; for (int r = 0; r < records; ++r) { height[r] = Double.parseDouble(args[toIndex(r, 0, recordSize)]); weight[r] = Double.parseDouble(args[toIndex(r, 1, recordSize)]); }

You could then work with the conformal arrays `height`

and `weight`

as you did in Chapter 17.

# Looking Ahead

If you take a course on systems programming you will probably work with packed integers, a pattern that is related to segmented/packed arrays. The difference is that, rather than working with the elements of an array, you will work with portions of the integer (as, for example, was briefly discussed at the end of Chapter 3 on digit manipulation and in Chapter 10 on bit flags).

For example, because of the way the eye processes light, many visual output devices represent colors using a red component, a green component, and a blue component, each of which can take on 256 different possible values. Since each component can be represented in 8 bits, it is possible to represent a color using a single 32-bit `int`

(with 8 bits to spare).

Suppose you want to ignore the highest-order (i.e., left-most) 8 bits, use the next 8 bits for the red component, the next 8 bits for the green component, and the lowest-order (i.e., right-most) 8 bits for the blue component. Suppose, further, that you want to create an `int`

that contains the following shade of purple:

int bb, gg, rr; rr = 69; gg = 0; bb = 132;

In order to create the packed 32-bit integer, you need to shift the bits in the red component to the left by 16, the bits in the green component to the left by 8, and leave the bits in the blue component where they are (i.e., in the least-significant bits). Then, you need to combine them into a single `int`

using bitwise “inclusive or” operators}. This can be accomplished as follows:

int color; color = 0; color |= (rr << 16) | (gg << 8) | (bb << 0);

This `int`

will, of course, have a value (4522116 in this case), but it is of no interest. What’s important, is that this `int`

has several distinct components.

To extract the red, green, and blue components from the packed `int`

you must invert the process. That is, you need to do a bitwise “and” with an appropriate mask, and then shift the bits to the right (to move them to the least-significant positions).

The masks can be defined as follows:

public static final int RED = (255 << 16); public static final int GREEN = (255 << 8); public static final int BLUE = 255;

Then, the components can be extracted as follows:

rr = (color & RED) >> 16; gg = (color & GREEN) >> 8; bb = (color & BLUE);