Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.
 


Video