Click here to Skip to main content
Click here to Skip to main content
Technical Blog

Tagged as

Bounds, and staying within them

, 9 Aug 2010 BSD
Rate this:
Please Sign up or sign in to vote.
Safely defining integer bounds at compile-time

How often have you written a line of code that looks something like this?

if (3 <= var && 14 >= var)

There might (read “should”) be named constant variables instead of the magic numbers there, but in essence it’s a very common piece of code for a very common type of test – is this value within pre-defined, constant bounds?

Some years ago, I was working on a project that had lots of tests like that, and I came across a surprisingly large number of errors one can commit with this simple code. For instance:

// non-paired constants
if (minTempUK <= var && maxTempUS >= var)

// wrong comparison
if (minTempUK < var && maxTempUK >= var)

// test wrong way around
if (maxTempUK <= var && minTempUK >= var)

// maxTempUK is compared to bool
if (minTempUK <= var <= maxTempUK)

// bitwise rather than logical AND
if (minTempUK <= var & maxTempUK >= var)

All of these are legal C++, and only the last two or three might generate compiler warnings. The last would still work properly, but is a bit iffy. If it isn’t a typo, someone needs to read up on operators. In most cases, these errors were typos (except the fourth, which was written by someone more used to other languages), but since they compiled, and sort of worked, they only showed up as bugs every now and then, at the edge cases. And because the code looks sort of okay, it was hard to spot the typos right away.

The thing is, there’s nothing wrong with writing this line of code...

if (minTempUK <= var && maxTempUK >= var) 

... as long as it’s written correctly. It’s not an intrinsically unsafe or “bad” construct.

But after having fixed a fair few bugs caused by simple mistakes like the ones above, I sat down and hacked out a little helper, which looked more or less like this:

template <typename T, T lower_, T upper_>
struct bounds
{
  // Type name for templated type
  typedef typename T type;

  // Return lower_ <= value <= upper_
  static bool in_bounds(const T& value)
  {
    return (lower_ <= value) && (value <= upper_);
  }
  // Return type-specific lower bound
  static inline type lower_bound()
  {
    return lower_;
  }
  //Return type-specific upper bound
  static inline type upper_bound()
  {
    return upper_;
  }
};
// Use type rather than named constant
typedef bounds<int, 3, 14> MyBounds;
...
if (MyBounds::in_bounds(var))
...
for (MyBounds::type i = MyBounds::lower_bound();
  MyBounds::in_bounds(i); ++i)

Very simple and basic, but quite useful, both because it keeps the lower and upper bounds together and treats them as a pair, and because it removes the risk of typos in the comparison. I added a static assert to validate the template parameters at compile time, and left it at that.

The mathematically astute will recognize this bounds type as a proper, bounded and closed interval, or “[lower_, upper_]“. In other words, it’s inclusive of the boundary values, and the comparison done is always “<=”. In code, however, we are more used to see left-closed, right-open intervals, or “[lower_, upper_)", where the left comparison is "<=" and the right is "<". What's up with that?

Well, there are very good reasons for the canonical C/C++ usage of half-open intervals, but this class is designed to represent boundaries, to see if a given value falls within a given interval. For this purpose, a half-open interval would be confusing - a variable could have the minimum value defined, but not the maximum.

But okay, it's not complicated to accommodate half-open intervals, nor is it necessarily slowing the code down. We just have to provide a way to indicate the desired comparators. It does, however, possibly invalidate that static sanity check I mentioned.

// Comparers for bounds checking
namespace less_than_comparison
{
  // Less-than comparison type for open range - (a<b)
  template <typename T>
  struct open
  {
    static inline bool less(const T& lhs, const T& rhs)
    {  return (lhs < rhs);  }
  };
  // Less-than comparison type for closed range - [a<b]
  template <typename T>
  struct closed
  {
    static inline bool less(const T& lhs, const T& rhs)
    {  return (lhs <= rhs);  }
  };
}
// Bounds checking type
template <typename T,                           // data type
  T lower_,                                     // lower limit
  T upper_ ,                                    // upper limit
  typename L = less_than_comparison::closed<T>, // left comparer
  typename U = less_than_comparison::closed<T> >// right comparer
struct bounds
{
private:
  // Validate ordering of template parameters at compile time
  template <bool b> struct bounds_validation{};
  template <> struct bounds_validation<true>
  { static void lower_larger_than_upper() {}; };
public:
  // Type name for templated type
  typedef T type;

  // Check if value is within bounds
  static bool in_bounds(const type& val)
  {
    bounds_validation<lower_ <= upper_>::lower_larger_than_upper();
    return L::less(lower_, val) && U::less(val, upper_);
  }
  // Get lower boundary
  static inline type lower_bound()
  {
    bounds_validation<lower_ <= upper_>::lower_larger_than_upper();
    return lower_;
  }
  // Get upper boundary
  static inline type upper_bound()
  {
    bounds_validation<lower_ <= upper_>::lower_larger_than_upper();
    return upper_;
  }
};

The validation problem is that [1,1] is valid and equal to {1}, (1,1) is valid but empty, but [1,1) and (1,1] are both nonsensical. Mathematically, they would be regarded as empty, just like (1,1) is, but I think that should one of them appear in my codebase, it's likely an error. Unfortunately, there is (yet) no way to check for those cases.

I say yet, because in C++0x we'll get decltype, which will let us check whether the comparators are the same (open, closed) or different (half-open), like this:

bounds_validation<
  ((lower_ <= upper_) && (decltype(L) == decltype(U))) ||
  ((lower_ < upper_) && (decltype(L) != decltype(U)))
  >::lower_larger_than_upper();

But until your compiler(s) supports decltype, you'll have to make do with the simpler check.

Apart from that little niggle, the class is complete here, and useful for all your min-max boundaries. (Provided, of course, that they are integers. I'll come back to this subject.)

Again, if you find it useful, or have suggestions for improvements, please let me know.


Tagged: bounds, C++, template

License

This article, along with any associated source code and files, is licensed under The BSD License

Share

About the Author

Orjan Westin

United Kingdom United Kingdom
Orjan has worked as a professional developer - in Sweden and England - since 1993, using a wide range of languages (C++, Pascal, Delphi, C, C#, Visual Basic, PHP, Python and x86 assembler), but tends to return to C++.

Comments and Discussions

 
GeneralNice article PinmemberSushant Joshi8-Sep-10 18:40 
QuestionMy vote of 3 [modified] Pinmembersysabod16-Aug-10 21:56 
AnswerRe: My vote of 3 [modified] PinmemberStefan6317-Aug-10 0:28 
GeneralRe: My vote of 3 Pinmembersysabod17-Aug-10 15:47 
AnswerRe: My vote of 3 PinmemberCool Cow Orjan18-Aug-10 2:41 
GeneralMy vote of 4 Pinmemberwtwhite9-Aug-10 18:15 
Great idea, and a clean, flexible implementation. Simple tools like this can give a big advantage in getting rid of these mundane sorts of bugs, provided they aren't intrusive or difficult to learn. (I also think we could be getting a lot more safety out of the type system... Although C 's myriad conversions does make it hard to reason about types.) Good stuff!
GeneralMy vote of 5 PinmemberTony's Toy9-Aug-10 17:18 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.141223.1 | Last Updated 9 Aug 2010
Article Copyright 2010 by Orjan Westin
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid