Representing Ranges With Element Pointers
Last week, we observed that a pointer is not quite the right abstraction to use for representing a range of elements in a sequence. Instead, we imagined a type that we called a boundary. An object of such a type denotes the infinitesimal space between two adjacent elements of a sequence, or immediately before the first or after the last element; given a boundary object, we can access the element either before or after the boundary if such an element exists.
With boundaries defined in this way, every n-element sequence contains n+1 boundaries. Moreover, every element corresponds to two boundaries, namely the ones immediately before and after that element. However, not every boundary has a corresponding element — after all, the sequence might not have any elements at all. Instead, we can think of each boundary as being either the beginning boundary, the end boundary, or an interior boundary. Thought of in this way, every interior boundary has two elements that correspond to it, namely those before and after the boundary. If a boundary is not a beginning boundary, then there is an element before it; if it is not an ending boundary, there is an element after it.
This description leads to some conclusions about the relationship between boundaries and pointers to elements:
- For every pointer to an element, there are two operations, which we can call
after, each of which maps the pointer into one of the adjacent boundaries. These two operations are defined on every valid pointer.
- For every boundary, there are two operations, which we can also call
after, that map the boundary into one of the adjacent elements. There is no more confusion in using
afterin these two different contexts than there is in other uses of overloading.
- Unlike the pointer operations, the boundary operations do not always yield a pointer to an element. In particular,
beforeyields a pointer to an element only if its argument is not a beginning boundary;
afteryields a pointer to an element only if its argument is not an ending boundary.
- If we use
beforeto transform a pointer to an element into a boundary, we can use
afterto transform that boundary back into a pointer to the same element. Similarly, we can use
afterto transform a pointer into a boundary, and then use
beforeto recover the original pointer.
Together, these facts suggest that we can use a pointer to represent a boundary. We simply define a boundary as an abstract data structure that contains a pointer, and decree arbitrarily that such a data structure represents the boundary before the element to which the pointer points. If we adopt this strategy, then every element in an n-element sequence maps into one of the boundaries associated with that sequence, leaving one boundary untouched. This boundary is the one after the last element; we can reach that boundary by mapping the off-the-end pointer for the sequence.
In other words, this strategy yields a one-to-one correspondence between the boundaries associated with a sequence and the pointers to the sequence's elements augmented by the off-the-end pointer. It is then reasonable to say that
before is the mapping that we wish to use from pointer to boundary, and
after is the corresponding mapping from boundary to pointer.
Once we have defined the mapping between pointers and boundaries (and vice versa), we can think about how to take our earlier code that used boundaries and rewrite it to use pointers. We shall explore how to do so next week.