design question [long]

[Mark P]

I've written a class IntervalSet which is meant to contain intervals
(a,b) on the x-axis and which supports insertion, deletion, and various
types of range queries. Now I'd like to templatize this class so that
it can hold (pointers to) arbitrary objects as long as there's "some
way" to compute an interval based on the object. For example the class
might hold polygons located in a plane and the corresponding interval
would be their shadow on the x-axis produced by a separate light source
object.

The problem I'm struggling with is, what's the most general and flexible
way to take into account that the assoication of object to an interval
may be performed by a 3rd object (i.e., not the IntervalSet class and
not the contained object class).

The usage I envision might be something like this:

class Master
{
public:
void doStuff()
{
// perform operations on myISet;
}

// convert w to (x1,x2) interval - modify x1 and x2
void computeInterval(const Widget& w, int& x1, int& x2);

private:
IntervalSet<Widget*> myISet;
vector<Widget> allMyWidgets;
};

The idea is that there should be some way to get myISet to make use of
the function computeInterval so that when I try to insert a Widget* into
myISet, it will call computeInterval to figure out the corresponding
x-range.

One thought I had was to have Master derive from IntervalSet and
override a function from IntervalSet:

template <class T>
void computeInterval(const T& obj, int& x1, int& x2)

But I'm not sure inheritance is really the right idea here and I think
I'd rather have the interface be that IntervalSet is given an object of
an arbitrary 3rd class which knows how to compute x1 and x2. I'm not
sure how to implement this idea though. Would this be some sort of functor?

Any advice on this general problem or suggestions on specifics would be
greatly apprecaited.

Thanks,
Mark

 

[Victor Bazarov]

I've written a class IntervalSet which is meant to contain intervals
(a,b) on the x-axis and which supports insertion, deletion, and
various types of range queries. Now I'd like to templatize this
class so that it can hold (pointers to) arbitrary objects as long as
there's "some
way" to compute an interval based on the object. For example the
class might hold polygons located in a plane and the corresponding
interval would be their shadow on the x-axis produced by a separate light
source object.

The problem I'm struggling with is, what's the most general and
flexible way to take into account that the assoication of object to
an interval may be performed by a 3rd object (i.e., not the IntervalSet
class and
not the contained object class).

The usage I envision might be something like this:

class Master
{
public:
void doStuff()
{
// perform operations on myISet;
}

// convert w to (x1,x2) interval - modify x1 and x2
void computeInterval(const Widget& w, int& x1, int& x2);

private:
IntervalSet<Widget*> myISet;
vector<Widget> allMyWidgets;
};

The idea is that there should be some way to get myISet to make use of
the function computeInterval so that when I try to insert a Widget*
into myISet, it will call computeInterval to figure out the
corresponding x-range.

One thought I had was to have Master derive from IntervalSet and
override a function from IntervalSet:

template <class T>
void computeInterval(const T& obj, int& x1, int& x2)

But I'm not sure inheritance is really the right idea here and I think
I'd rather have the interface be that IntervalSet is given an object
of an arbitrary 3rd class which knows how to compute x1 and x2. I'm not
sure how to implement this idea though. Would this be some sort of
functor?

A functor has to be an object. Here is an example of using a static
member function of a type:


template<class T, class Computer = T>
class IntervalSet
{
map<T*, pair<int,int> > myset;

public:
IntervalSet();

void add(T* obj)
{
pair<int,int> i = Computer::compute(obj);
map[obj] = i;
}
};

class Widget
{
public:
static pair<int,int> compute(Widget* ptr)
{
ptr->compute();
}
virtual pair<int,int> compute(); // so you can derive
// and change it
};

class Polygon {};
class PolygonProjector
{
public:
static pair<int,int> compute(Polygon*); // whatever
};

int main()
{
IntervalSet<Widget> iw;
iw.add(new Widget);

IntervalSet<Polygon, PolygonProjector> ipp;
ipp.add(new Polygon);
}

Here is an example of using a functor:


template<class T, class Computer>
class IntervalSet
{
Computer puter;
map<T*, pair<int,int> > myset;

public:
explicit IntervalSet(Computer const& c) : puter(c) {}

void add(T* obj)
{
pair<int,int> i = puter(obj);
map[obj] = i;
}
};

class Polygon {};
class PolygonProjector
{
public:
pair<int,int> operator()(Polygon*); // whatever
};

int main()
{
PolygonProjector pp; // here is the functor
IntervalSet<Polygon, PolygonProjector> ipp(pp);
ipp.add(new Polygon);
}

V

 

[Mark P]

[C++ gold snipped]

Extraordinarily helpful. Thank you very much.

Mark