###### Books / Patterns for Beginning Programmers / Chapter 21

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

#### In this chapter

## 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);
```