Segmented Arrays

Recall that Chapter 20, 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 20 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. 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. 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 5.

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 20.

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 4 on digit manipulation and in Chapter 12 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);