I have the following structure
struct Node
{
int x0,y0,g,h,f;
int *Grid[N][N];
Node* parent=NULL;
Node(int x=0,int y=0,int G=0,Node* node=NULL)
{
x0=x;
y0=y;
g=G;
parent=node;
}
}
and the multiset
definition as follows
multiset<Node*,GridLess>open_list;
Gridless
is the initial structure for comparison operator.
struct GridLess
{
bool operator()(const Node *a,const Node *b) const
{
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(*a->Grid[i][j]!=*b->Grid[i][j])
{
return *a->Grid[i][j]<*b->Grid[i][j];
}
}
}
return false;
}
};
My basic need was to find the Node
in the open_list
which has the same elements at same positions in grid using multiset::count
or multiset::find
which is completed by the above comparison operator.
Now I want to the Node
in the open_list
which has the same elements at same positions in grid as well as the same Node::g
and Node::f
This is what I tried to use and failed
struct GridLess
{
bool operator()(const Node *a,const Node *b) const
{
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(*a->Grid[i][j]!=*b->Grid[i][j])
{
return *a->Grid[i][j]<*b->Grid[i][j]||(*a->Grid[i][j]==*b->Grid[i][j]&&a->g<b->g)||((*a->Grid[i][j] == *b->Grid[i][j])&&(a->g==b->g)&&a->f<b->f);
}
}
}
return false;
}
};
Introducing two Nodes
in the open_list
with same grid but different g or f still results in count=2
.
I tried checking for just the Grid
and Node::g
with the following
return *a->Grid[i][j]<*b->Grid[i][j]||(*a->Grid[i][j]==*b->Grid[i][j]&&a->g<b->g);
Even that doesn't work.
I need a comparison operator for this problem and explanation of how it works.
EDIT
I figured I am not clear with the bool operator()
function as in when we write return a<b
I understand it will return true
if a<b
but what will it return if a==b
or a>b
if this could be explained together with the question it would be really helpful.
You comparison of the g
and f
members has to be outside of the loop. As long as it is inside the loop, you do not compare the g
and f
members in case the Grid
members are equal.
struct GridLess
{
bool operator()(const Node *a,const Node *b) const
{
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(*a->Grid[i][j]!=*b->Grid[i][j])
{
return *a->Grid[i][j]<*b->Grid[i][j];
}
}
}
return std::tie(a->g, a->f) < std::tie(b->g, b->f);
}
};