set_intersection of two interval sets

[PengYu.UT]

Hi,

I have the following definition for a closed-open interval (see
http://mathworld.wolfram.com/Interval.html). I have two sets of
intervals, say A and B. Any two intervals in A (or B) have no overlap,
and they are sorted.

std::vector<closed_open_interval<double> > A;
std::vector<closed_open_interval<double> > B;

'set_intersection' is the standard algorithm to compute the set
intersection. I'm wondering if there is any easy way to compute the
intersection of A and B using that function.

Thanks,
Peng

#ifndef ANALYTICAL_CLOSED_OPEN_INTERVAL_H
#define ANALYTICAL_CLOSED_OPEN_INTERVAL_H

#include <cassert>

namespace analytical
{

template <typename T>
class closed_open_interval {
public:
closed_open_interval(T a, T b) : _a(a),_b(b) { // _a is in the
interval, but _b is not.
assert(a < b);
}
T the_a() const { return _a; }
T the_b() const { return _b; }
bool operator<(closed_open_interval &that) const {
return _b <= that._a;
}
private:
T _a, _b;
};

}

#endif

 

[dasjotre]

Hi,

I have the following definition for a closed-open interval (seehttp://mathworld.wolfram.com/Interval.html). I have two sets of
intervals, say A and B. Any two intervals in A (or B) have no overlap,
and they are sorted.

std::vector<closed_open_interval<double> > A;
std::vector<closed_open_interval<double> > B;

'set_intersection' is the standard algorithm to compute the set
intersection. I'm wondering if there is any easy way to compute the
intersection of A and B using that function.

there is not a standard algorithm for that.

Thanks,
Peng

#ifndef ANALYTICAL_CLOSED_OPEN_INTERVAL_H
#define ANALYTICAL_CLOSED_OPEN_INTERVAL_H

#include <cassert>

namespace analytical
{

template <typename T>

instances of T are obviously some iterators, but what do
they iterate over. are intervals in A iterators in one
container and intervals in B iterators in other container
or do they belong to the same container?

class closed_open_interval {
public:
closed_open_interval(T a, T b) : _a(a),_b(b) { // _a is in the
interval, but _b is not.

I presume that all elements [_a, _b) are sorted
as well.

assert(a < b);
}
bool operator<(closed_open_interval &that) const {
return _b <= that._a;

if the intervals are not overlapped than surely comparing
the inclusive iterators is sufficient, like
return _a<that._a;

}
private:
T _a, _b;
};

}

#endif

I suppose you can make union of all elements that intervals
in A point to and another one of the same for elements in B
and make intersection of the two. Is that what you want?

regards

DS