Storing Intervals or Ranges

[Christoph Bartoschek]

Hi,

some time ago I've read a paper that advised to store intervals on discrete
values in the format [a;b[. One starts with the first element and finishes
with one past the last one.

However I do not remember the author, title or link of the paper. Does
anyone remember it?

Greetings
Christoph Bartoschek

 

[red floyd]

Hi,

some time ago I've read a paper that advised to store intervals on discrete
values in the format [a;b[. One starts with the first element and finishes
with one past the last one.

However I do not remember the author, title or link of the paper. Does
anyone remember it?

This is exactly how C++ standard algorithms work.

 

[Christoph Bartoschek]

This is exactly how C++ standard algorithms work.

Yes, but the paper gave some rationale why this is better than using [a;b]
or other schemes.

Christoph

 

[red floyd]

Hi,

some time ago I've read a paper that advised to store intervals on discrete
values in the format [a;b[. One starts with the first element and finishes
with one past the last one.

Such an interval is known as a "half-open" interval. Notational
nitpick, the general format for such a range is [a, b).

Not sure of the location of the paper, but the rationale is that
one-past-the-end provides a not present indicator, much like a NULL
pointer would.

 

[red floyd]

Hi,

some time ago I've read a paper that advised to store intervals on discrete
values in the format [a;b[. One starts with the first element and finishes
with one past the last one.

However I do not remember the author, title or link of the paper. Does
anyone remember it?

Google came up with this: http://www.siliconbrain.com/ranges.htm

 

[Christoph Bartoschek]

Such an interval is known as a "half-open" interval. Notational
nitpick, the general format for such a range is [a, b).

I used [a; b[ because this is the format we used in school (Germany). Forgot
to use the more international format.

Google came up with this: http://www.siliconbrain.com/ranges.htm

This is not the paper I remember. But thanks for the link.

Christoph

 

[Alf P. Steinbach]

* Christoph Bartoschek:

This is exactly how C++ standard algorithms work.

Yes, but the paper gave some rationale why this is better than using [a;b]
or other schemes.

The number of elements in the range is onePastLast-first. With zero
elements, an empty range, onePastLast == first. Which is very
convenient for pointers or more general iterators.

 

[James Kanze]

Christoph Bartoschek wrote:

some time ago I've read a paper that advised to store intervals on discrete
values in the format [a;b[. One starts with the first element and finishes
with one past the last one.

Such an interval is known as a "half-open" interval. Notational
nitpick, the general format for such a range is [a, b).

Which doesn't work for decimal numbers, in localities where the
decimal separator is a comma. I'll use "[a,b)" if I know that
I'm only addressing the Anglo-Saxon world, "[a;b[" for the rest
of the world. (Note that where I live, a complex is represented
as "(r;i)", and not "(r,i)", as well.)

 

[Andrew Koenig]

some time ago I've read a paper that advised to store intervals on
discrete
values in the format [a;b[. One starts with the first element and finishes
with one past the last one.

There are lots of reasons. Here is one that I personally consider to be
conclusive.

If you represent a range by its first and last elements (symmetric ranges),
then an empty range is an anomaly: You need to find way to represent not
just one but two distinct positions that do not correspond to any element.

If you represent a range by its first and one past its last elements
(asymmetric), then you always need a way to represent a position that
doesn't correspond to any element, but the difficulty in doing so is the
same regardless of the number of elements.

Moreover, assymetric ranges have the nice property that begin<=end at all
times, and begin==end if and only if the range is empty. With symmetric
ranges, begin==end if and only if the range has precisely one element, and
begin>end if the range is empty. This latter behavior is much less useful
if you are using iterators that support only == and != comparisons.

If this argument doesn't convince you, here are some others:

If you are using integer indices, you can use unsigned values to represent
an asymmetric range. You need signed values to represent a symmetric
range--to cater to the specific case of [0,-1] which is needed to represent
an empty range.

If you are using pointers to array elements, you have a problem in C or C++
representing an empty symmetric range because you are not generally allowed
to compute the address that precedes an array.

 

[Christoph Bartoschek]

I am already convinced that one should represent ranges as it is done in the
standard library. However this is my concrete case:

How to store rectangles in the integer plane?

A rectangle can be represented with the following struct:

static const int XDIM = 0;
static const int YDIM = 1;

struct Rectangle {
int min[2];
int max[2];
};

The question is how to interpret the ranges in x-dimension and y-dimension.
Everyone I asked assumed that the point (max[XDIM], max{YDIM]) is included
in the rectangle. But this has the same drawbacks as with one dimensional
ranges. For example the rectangles

{{0, 0}, {3, 3}}
{{4, 0}, {6, 3]]

cover the whole area from (0, 0) to (6, 3), although there seems to be a
hole from (3, 0) to (4, 3). Several algorithms (union, removing
overlaps, ...) are harder to implement with this scheme.

But should one use half-open ranges against the intuition?

Christoph