5

In general, whenever you're representing a range of any kind, you have several choices for what kinds of values to choose for the beginning and ending of your range. For example, if you want to have a range containing the integers 1, 2, 3, 4, 5 you could choose these possible values:

  • begin = 0, end = 5 (aka begin < x <= end)
  • begin = 1, end = 5 (aka begin <= x <= end)
  • begin = 0, end = 6 (aka begin < x < end)
  • begin = 1, end = 6 (aka begin <= x < end (the C++ STL and many other libraries seem to choose this)).

I'm not sure what measures I should use to choose one of these options.

4
  • Ugh, this is a tough one. Tried to take out the subjective bits, but I'm not exactly clear how this is a question. Can you please review my edit and clarify?
    – user1228
    Dec 9, 2011 at 13:50
  • @Will: I was hoping someone would lead me to a paper by E.W. Dijkstra on the topic. I didn't know where to find it, and the paper gives a convincing answer to this question. I have since found the paper: cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html Dec 9, 2011 at 16:17
  • @Will: And I can see how this could easily be considered subjective. The paper talks about experiments in which other representations led to programmer error and gives examples of how the math just works out well for a certain representation. That's less subjective, but... Dec 9, 2011 at 16:20

4 Answers 4

5

I was hoping someone would give me a link to a nice paper that E.W. Dijkstra wrote on the topic. I managed to plug just the right search terms into Google, and found the link I was looking for. The paper is "Why numbering should start at 0" and also covers why ranges should be represented with a half open interval [begin, end).

The basic argument has several pieces:

  1. Direct experience with a programming environment (the programming language Mesa at Xerox PARC) that had support for all 4 different choices resulted in people standardizing on [start, end) because of frequent errors made with all the other choices.
  2. If you have an interval that starts at 0, having the start be -1 or something similar is just awkward and broken. This argues strongly for the interval starting at begin (i.e. all the begin <= x choices).
  3. The math for determining the interval size, for computing the start of the next adjacent interval, and a whole bunch of other similar things just works out nicely if end is one past start. For example, the size is end - begin. And end is the begin of the next adjacent interval. There are fewer chances for off-by-one errors in your calculations.
    • On a related note, the empty range is [begin, begin), and very obvious. It would have to be the rather awkward [begin, begin - 1] if it were closed on both sides. This is especially awkward of your range begins at 0.
1
  • half-open intervals also make it trivial to test if two intervals abut: [a, b) abuts [c, d) if b = c
    – Felk
    Nov 30, 2018 at 10:30
1

I personally would choose the option

  • begin = 1, end = 5 (aka begin <= x <= end)

I like to keep my structures as clear and similar to the human reasoning as possible. If you tell someone "the numbers between 1 and 5" both 1 and 5 are meant to be in the set.

Of course if there are good technical reasons to use something else why not but if there are none I would choose the option which is easier to understand at the first glance.

2
  • There is a really good reason to not have a closed end (i.e. not using [begin, end]). How do you represent the empty range when it begins at 0? It would be [0, -1], and that's just very awkward. I'm accepting my own answer for this. I think it wasn't the best question to ask in this forum anyway. Dec 11, 2011 at 6:11
  • @Ominfarious: this as I pointed out depends on the language. If you have a range object/record/... you could have no object (null pointer, reference, ...) or an object with valid values.
    – Matteo
    Dec 11, 2011 at 8:45
1

I'd say it depends on the (impicit or explicit) type of the interval you're trying to express. For floats and rationals, I think I'd prefer half-open intervals (so, essentially min <= value < max or min < value <= max). For integral values, the transformation between open, closed and half-open intervals is trivial, so I'd probably go with half-open intervals there as well.

1
  • I'm accepting my own answer. :-/ I was hoping someone would link me to a paper by Dijkstra that I knew existed but didn't know where was. Dec 11, 2011 at 6:10
0

Interesting question. I'd like to suggest since foreach loop is quite ubiquitous now, which to choose becomes less relevant. You can just loop through a collection without knowing which range convention the underlying implementation uses.

1
  • Well, sometimes. Sometimes you're not talking about items in a container. For example, Python has the range operator to allow you to loop through a contiguous list of integers, and it has this same thing to deal with (and it's solution is the same as the STLs). Dec 9, 2011 at 7:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.