How to represent a mathematical domain in IR?

Question

I would like to define an object representing a mathematical domain from a list of constraints, but I don't have a clear idea on how to do that.

For example, I start from IR and I have the following constraints :

• x > 0
• x is not in ]3,5]
• x is not in [7,12[

Then, my domain is ]0,3] U ]5,7[ U [12,+oo .

How can I nicely store that in a C++ structure ? Have you ever did that before ? Moreover, I want to be able to check easilly if the domain is empty.

Answer 1

Answering my own question.

Actually, I followed the idea of sbabbi using a list of intervals coming from boost/numeric/interval, representing the union of intervals.

Here is an example :

typedef boost::numeric::interval_lib::rounded_math<double> RoundedPolicy;
typedef boost::numeric::interval_lib::checking_base<double> CheckingPolicy;
typedef boost::numeric::interval_lib::policies<RoundedPolicy,CheckingPolicy> IntervalPolicies;
typedef boost::numeric::interval<double,IntervalPolicies> interval;

//...

bool is_interval_empty(const interval& inter)
{
  return boost::numeric::empty(inter);
}

void restrict(interval& domain, const interval& inter)
{
  for(std::list<interval>::iterator it = domain.begin(); it != domain.end(); ++it)
    *it = boost::numeric::intersect(*it, inter);
  domain.remove_if(is_interval_empty);
}

void restrict(interval& domain, const interval& inter1, const interval& inter2)
{
  for(std::list<interval>::iterator it = domain.begin(); it != domain.end(); ++it)
  {
    domain.push_front(boost::numeric::intersect(*it, inter1));
    *it = boost::numeric::intersect(*it, inter2);
  }
  domain.remove_if(is_interval_empty);
}

//...

std::list<interval> domain;
for(unsigned long int i = 0; i < constraints.size(); ++i)
{
  if(constraints[i].is_lower_bound())
  {
    interval restriction(constraints[i].get_lower_bound(), std::numeric_limits<double>::infinity());
    restrict(domain, restriction);
  }
  else if(constraints[i].is_upper_bound())
  {
    interval restriction(-std::numeric_limits<double>::infinity(), constraints[i].get_upper_bound());
    restrict(domain, restriction);
  }
  else if(constraints[i].is_forbidden_range())
  {
    interval restriction1(-std::numeric_limits<double>::infinity(), constraints[i].get_lower_bound());
    interval restriction2(constraints[i].get_upper_bound(), std::numeric_limits<double>::infinity());
    restrict(domain, restriction1, restriction2);
  }
}

if(domain.size() == 0)
  std::cout << "empty domain" << std::endl;
else
  std::cout << "the domain exists" << std::endl;