What does this square bracket and parenthesis bracket notation mean [first1,last1)?
A bracket - [ or ] - means that end of the range is inclusive -- it includes the element listed. A parenthesis - ( or ) - means that end is exclusive and doesn't contain the listed element. So for [first1, last1), the range starts with first1 (and includes it), but ends just before last1.
Assuming integers:
- (0, 5) = 1, 2, 3, 4
- (0, 5] = 1, 2, 3, 4, 5
- [0, 5) = 0, 1, 2, 3, 4
- [0, 5] = 0, 1, 2, 3, 4, 5
That's a half-open interval.
- A closed interval
[a,b]includes the end points. - An open interval
(a,b)excludes them.
In your case the end-point at the start of the interval is included, but the end is excluded. So it means the interval "first1 <= x < last1".
Half-open intervals are useful in programming because they correspond to the common idiom for looping:
for (int i = 0; i < n; ++i) { ... }
Here i is in the range [0, n).
The concept of interval notation comes up in both Mathematics and Computer Science. The Mathematical notation [, ], (, ) denotes the domain (or range) of an interval.
The brackets
[and]means:- The number is included,
- This side of the interval is closed,
The parenthesis
(and)means:- The number is excluded,
- This side of the interval is open.
An interval with mixed states is called "half-open".
For example, the range of consecutive integers from 1 .. 10 (inclusive) would be notated as such:
- [1,10]
Notice how the word inclusive was used. If we want to exclude the end point but "cover" the same range we need to move the end-point:
- [1,11)
For both left and right edges of the interval there are actually 4 permutations:
(1,10) = 2,3,4,5,6,7,8,9 Set has 8 elements
(1,10] = 2,3,4,5,6,7,8,9,10 Set has 9 elements
[1,10) = 1,2,3,4,5,6,7,8,9 Set has 9 elements
[1,10] = 1,2,3,4,5,6,7,8,9,10 Set has 10 elements
How does this relate to Mathematics and Computer Science?
Array indexes tend to use a different offset depending on which field are you in:
- Mathematics tends to be one-based.
- Certain programming languages tends to be zero-based, such as C, C++, Javascript, Python, while other languages such as Mathematica, Fortran, Pascal are one-based.
These differences can lead to subtle fence post errors, aka, off-by-one bugs when implementing Mathematical algorithms such as for-loops.
Integers
If we have a set or array, say of the first few primes [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ], Mathematicians would refer to the first element as the 1st absolute element. i.e. Using subscript notation to denote the index:
- a1 = 2
- a2 = 3
- :
- a10 = 29
Some programming languages, in contradistinction, would refer to the first element as the zero'th relative element.
- a[0] = 2
- a[1] = 3
- :
- a[9] = 29
Since the array indexes are in the range [0,N-1] then for clarity purposes it would be "nice" to keep the same numerical value for the range 0 .. N instead of adding textual noise such as a -1 bias.
For example, in C or JavaScript, to iterate over an array of N elements a programmer would write the common idiom of i = 0, i < N with the interval [0,N) instead of the slightly more verbose [0,N-1]:
function main() {
var output = "";
var a = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ];
for( var i = 0; i < 10; i++ ) // [0,10)
output += "[" + i + "]: " + a[i] + "\n";
if (typeof window === 'undefined') // Node command line
console.log( output )
else
document.getElementById('output1').innerHTML = output;
} <html>
<body onload="main();">
<pre id="output1"></pre>
</body>
</html>Mathematicians, since they start counting at 1, would instead use the i = 1, i <= N nomenclature but now we need to correct the array offset in a zero-based language.
e.g.
function main() {
var output = "";
var a = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ];
for( var i = 1; i <= 10; i++ ) // [1,10]
output += "[" + i + "]: " + a[i-1] + "\n";
if (typeof window === 'undefined') // Node command line
console.log( output )
else
document.getElementById( "output2" ).innerHTML = output;
}<html>
<body onload="main()";>
<pre id="output2"></pre>
</body>
</html>Aside:
In programming languages that are 0-based you might need a kludge of a dummy zero'th element to use a Mathematical 1-based algorithm. e.g. Python Index Start
Floating-Point
Interval notation is also important for floating-point numbers to avoid subtle bugs.
When dealing with floating-point numbers especially in Computer Graphics (color conversion, computational geometry, animation easing/blending, etc.) often times normalized numbers are used. That is, numbers between 0.0 and 1.0.
It is important to know the edge cases if the endpoints are inclusive or exclusive:
- (0,1) = 1e-M .. 0.999...
- (0,1] = 1e-M .. 1.0
- [0,1) = 0.0 .. 0.999...
- [0,1] = 0.0 .. 1.0
Where M is some machine epsilon. This is why you might sometimes see const float EPSILON = 1e-# idiom in C code (such as 1e-6) for a 32-bit floating point number. This SO question Does EPSILON guarantee anything? has some preliminary details. For a more comprehensive answer see FLT_EPSILON and David Goldberg's What Every Computer Scientist Should Know About Floating-Point Arithmetic
Some implementations of a random number generator, random() may produce values in the range 0.0 .. 0.999... instead of the more convenient 0.0 .. 1.0. Proper comments in the code will document this as [0.0,1.0) or [0.0,1.0] so there is no ambiguity as to the usage.
Example:
- You want to generate
random()colors. You convert three floating-point values to unsigned 8-bit values to generate a 24-bit pixel with red, green, and blue channels respectively. Depending on the interval output byrandom()you may end up withnear-white(254,254,254) orwhite(255,255,255).
+--------+-----+
|random()|Byte |
|--------|-----|
|0.999...| 254 | <-- error introduced
|1.0 | 255 |
+--------+-----+
For more details about floating-point precision and robustness with intervals see Christer Ericson's Real-Time Collision Detection, Chapter 11 Numerical Robustness, Section 11.3 Robust Floating-Point Usage.