The half-open interval, [a,b) |

*x*, such that

*a*≤

*x*and

*x*<

*b*.

We use them all the time. Here's one :

An iterator in C++, over a half-open interval. |

### Open and Closed

What does it mean for a set to be**open**? What does it mean for it to be

**closed**? And

**half-open**? What's up with that?

I'll save the formal definition for another time, but intuitively, we can think of an

*set as one where every member has a little bit of wiggle room. No matter how closely you zoom in to the edge of the set, there's always a little bit more before you get to the edge :*

**open**The open interval, (a,b) |

And a

*set? That's the set where if you start from the*

**closed***outside*side of the set, there's always a little bit of wiggle room before you get to the edge. No matter how close to the edge of the set you are, there's always just a little bit of gap before you can get inside.

A set is closed iff its complement is open. |

*? What's that? Given the strange definitions for open and closed, it should come as no surprise we have another strange definition : A*

**half-open***set is one that has one side*

**half-open****closed**, and one side

**open**!

Half open: one side closed, one side open. |

### Splitters and Joiners

Half open intervals are great for joining. Suppose we have two half-open intervals, [*a*,

*b*) and [

*b*,

*c*). Then their union is just [

*a*,

*c*) .

Further more, if we know that if

*x*is in [

*a*,

*c*), then it

*must*be in either [

*a*,

*b*) or [

*b*,

*c*).

You'll see this all the time when we write recursive algorithms on containers with iterators, we use an iterator to split the container into two smaller containers, which each member is in one, and only one, of the children.

### Rectangles

And what of the half-open*rectangles*?

Here's one:

1 ≤ x < 3 and 1 ≤ y < 3 |

Here's what it might look like in code :

A Half-Open rectangle class. |

Still not convinced? Consider an 800 x 600 bitmap, whose pixels are [0,800) x [0,600)

for ( int y = 0; y < height; y++ ){for ( int x = 0; x < width; x++ ){PlotPixel ( x, y, Color );}}

Or this unbound function:

Rectangle Intersect ( const Rectangle &a, const Rectangle &b )

{

return Rectangle (

return Rectangle (

max ( a.X0, b.X0 ), max ( a.Y0, b.Y0 ),

min ( a.X1, b.X1 ), min ( a.Y1, b.Y1 ) );

}

}

Next time you make an interval, rectangle, or cube class, why not try using the half-open convention? You'll almost certainly arrive at a smaller, more robust code.

## No comments:

## Post a Comment