what is the best way to implement this problem?

[abir]

This question may not be very specific to C++ , rather than C++ is
used as a language to implement it.
I have a set of points (a vector of ) as input for a system, just like
blackboard drawing.
where the point is defined as
struct point{ int x,int y;};

my job is to create an animal (or a few) out of those points. i may
even fail to create an animal if it doesn't look like any which i
know.

animal is like
struct animal{
typedef std::vector<point>::const_iterator iterator;
//animal(const std::vector<point>& points)///1 complex constructor
virtual void show(){
for(iterator it = begin; it!= end;++it){
put_pixel(*it);
}
}
static std::vector<animal*> make_animals(const std::vector<point>&
p){///3
///complex algorithm.
}
protected:
animal(iterator begin,iterator end) : begin(begin), end(end){}//
<2 simple constructor
iterator begin; iterator end;
};
struct elephant : public animal{
std:air<iterator,iterator> get_trunk()const{
return std::make_pair(trunk_b,trunk_e);
}
protected:
iterator trunk_b,trunk_e;
};
struct horse : public animal{

}

my problem is that, i can't construct the animal in the animal
constructor, as it is a complex process (marked as 1 in the code) and
outcome may be a single animal or multiple or even none.
like a set of point may create an elephant or a pig (when the
algorithm gets confused).
so i thought to have a simple constructor which decouples the
algorithm to construct the object from the constructor (marked as 2).
In this case almost all of the processing logic goes to make_animals
(marked as 3) even the logic specific to elephant (like setting trunk
etc) etc, which sometimes i feel like anti-pattern.
Is it a usual solution for this kind of problem, or a better
alternative is there?
a second problem is that as make_animals is complex logic & also may
need to store state from call to call, so i am delegating it to a
class called animal_creator (alternative static can also be used).
like
static std::vector<animal*> make_animals(const std::vector<point>&
p,context& ctx){
return ctx.animal_creator.create(p);
}
however as only animal_creator can create all those animals, i need to
access private data member for them, which means that for all of the
animal class i need to make animal_creator friend. which i am not
liking very much.

Looking for a better alternative
thanks
abir

 

[Matthias Buelow]

my problem is that, i can't construct the animal in the animal
constructor, as it is a complex process (marked as 1 in the code) and
outcome may be a single animal or multiple or even none.
like a set of point may create an elephant or a pig (when the
algorithm gets confused).

Can't you find some common operations for all animals (like, some basic
animal-to-point construction) and put it in the base class, and then
implement the animal-specific stuff in derived classes?

 

[Daniel T.]

Your problem is a basic pattern matching problem. You have a set of
points and you have a sequence of points: the input pattern... and a
another container of sequences of points. It is your job to see how many
of the second container match the points in the first container. Each
sequence of points in the second container is associated with an animal.
Once you know which sequences from the second container match up, you
can create the correct animals.

Sorry, I had to run and didn't finish the above to my satisfaction...

At any rate, you have a sequence of points and a container of
sequences of points, and you want to see which sequences in the
container match the sequence you have. First you need a function that
can compare two sequences of points and determine if they are alike
(enough.)

bool alike(const vector<point>& a, const vector<point>& b);

and you need an association between a sequence of points and an
animal. You could do this in a number of ways, but the Prototype
pattern would probably be easist.

struct AnimalAssoc {
vector<point> pattern;
Animal* animal;
};

Now it is simply a matter of running through different patterns and
see which match.

vector<Animal*> animalsMade;
for ( AnimalAssocContainer::iterator it = animalFactory.begin();
it != animalFactory.end();
++it)
{
if (alike(myPattern, it->pattern))
animalsMade.push_back(it->animal->clone());
}

 

[abir]

Sorry, I had to run and didn't finish the above to my satisfaction...

At any rate, you have a sequence of points and a container of
sequences of points, and you want to see which sequences in the
container match the sequence you have. First you need a function that
can compare two sequences of points and determine if they are alike
(enough.)

bool alike(const vector<point>& a, const vector<point>& b);

and you need an association between a sequence of points and an
animal. You could do this in a number of ways, but the Prototype
pattern would probably be easist.

struct AnimalAssoc {
   vector<point> pattern;
   Animal* animal;

};

Now it is simply a matter of running through different patterns and
see which match.

vector<Animal*> animalsMade;
for ( AnimalAssocContainer::iterator it = animalFactory.begin();
      it != animalFactory.end();
      ++it)
{
   if (alike(myPattern, it->pattern))
      animalsMade.push_back(it->animal->clone());

}

Thanks for answering. The Prototype pattern is a good example of many
kind of pattern matching.
In my case also i had used it. But as my algorithm is more complex in
nature (they runs on some probabilistic model & graph search ), it is
more like given input match for a group of patterns, and choose best
k among them as valid pattern. At the second level, register them to
form the complete pattern.
For eg, to match an Unicorn, and a Lion i won't match them twice for
all parts (they have many similarity). similar part will be matched
only once. Secondly i don't match even parts separately. So unlike the
alike function suggested by you, my algorithm doesn't answer like is
this pattern is like 'leg' ? and is this pattern looks like 'trunk' ?
separately. Rather it answers given the input pattern, is it more
probable as 'leg' or 'trunk' in a single match (out of a prototype
set, it is multiclass classifier and can assign output to zero or more
classes)
So the for loop is no more decoupled in my case, which is causing main
problem.
I am tilting more towards Builder pattern, but still the logic looks a
big state machine instead of the simple for loop in your case.

So looking for a better way to distribute the responsibility of
matching by each of the parts
(and while the is relationship like (animal, horse, elephant etc )is
mostly structural, the matching is mostly based on has relationship )

Thanking you for answering.
abir