# How to Represent Ranges Symmetrically

June 11, 2014

We continue last week's discussion about how to reconcile the natural asymmetry in `while` statements with the symmetry between the beginning and end of a range.

If we want to represent a range symmetrically, we can use pointers to its first and last elements:

```     p = first;
while (p <= last) {
// Process the element to which p points
++p;
}
```

However, this approach requires that for an empty range, `first` and `last` must be off-the-end and off-the-beginning pointers, respectively; and these pointers are required in no other case.

Because we need off-the-end pointers anyway, we can use one to represent the end of the range instead of a pointer to the last element:

```
p = begin;
while (p != end) {
// Process the element to which p points
++p;
}
```

However, this strategy breaks symmetry.

What we really want is a way to delimit a range of elements that treats the beginning and end symmetrically, and that never requires us to refer to any position beyond the range. One way to do so is to use "pointers" to the spaces adjacent to elements. For example, consider this sequence:

```
8  1  6
```

We usually think of this sequence as having three components, each of which is an integer. However, we can also imagine four "boundaries:" the one before 8, the one between 8 and 1, the one between 1 and 6, and the one after 6. Any two of these boundaries, taken together, will represent a subsequence of this sequence in a particular direction. If the subsequence is empty, the two boundaries will be equal.

Suppose we have two such boundaries, which we shall call `lower` and `upper`, and assume that `lower <= upper`. Then we can write:

```     b = lower;
while (b != upper) {
// Process the element immediately to the right of b
++b;
}
```

More interestingly, we can process the same elements of the sequence in reverse order by writing:

```
b = upper;
while (b != lower) {
// Process the element immediately to the left of b
--b;
}
```

These two code fragments are related in a way that earlier examples are not: We can obtain the second from the first by replacing `upper` by `lower`, `lower by upper`, `++ by --`, and `right by left`. All of these replacements change an asymmetric operation into its mirror image. In other words, if we represent a range by a pair of boundaries, where a boundary is the (invisible) space adjacent to an element, we can arrange to traverse ranges in either direction while maintaining symmetry.

Unfortunately, neither the C nor C++ languages, nor the underlying hardware, has a well-defined natural way of referring to the position adjacent to an element. What we have available is the idea of a pointer, which refers to a particular place in memory — not to the boundary between two regions of memory. Accordingly, we need to devise an abstraction that maps boundaries into pointers in a consistent way. We shall do so next week.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.