Как представить математическую область в IR?
Я хотел бы определить объект, представляющий математическую область, из списка ограничений, но у меня нет четкого представления о том, как это сделать.
Например, я начинаю с IR и у меня есть следующие ограничения:
- х> 0
- х не в] 3,5]
- х не в [7,12 [
Тогда мой домен] 0,3] U] 5,7 [U [12, + oo.
Как я могу красиво хранить это в структуре C ++? Вы когда-нибудь делали это раньше? Более того, я хочу иметь возможность проверить, если домен пуст.
Решение
Если вы не хотите использовать «сторонние» инструменты, такие как упомянутые в комментариях, вам придется написать свой собственный класс Interval.
Для этого вы можете сделать что-то вроде этого:
class Interval{
struct Range{
bool leftInclusive, rightInclusive;
double left, right;
bool operator<(Range other){return left<other.left;}
}
std::Set<Range> trueRanges;
void addTrueRange(Range r){
//check for overlaps
//merge if overlapping
//otherwise add to trueRanges
}
bool trueAt(double at){
//find the range with the highest left-bound lower than at
auto candidate = truethRanges.upper_bound(at);
if(candidate == trueRanged.end()) return false; // no range found
//on-point checking here
if(at <= candidate->left) return false;
if(at >= candidate->right) return false;
return true;
}
}
Проверка на месте здесь опущена, потому что вы не можете просто сказать doubleOne == doubleTwo потому что это приводит к ложным негативам. Так что вы должны сказать ABS(doubleOne-doubleTwo) < tinyValue,
Для поиска совпадений вы можете взглянуть на этот.
Другие решения
Отвечая на мой собственный вопрос.
На самом деле, я следовал идее sbabbi, используя список интервалов из boost/numeric/interval, представляющий объединение интервалов.
Вот пример:
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;