How to write a Comparator when the order of elements does not matter

[luckiejacky]

bool Edge::operator<(const Edge& e) const
{
	return std::tie(this->v0, this->v1) < std::tie(e.v0, e.v1);
}

also when this->v0 == e.v1 && this->v1 == e.v0
How do I rewrite this comparator?
Thanks
Jack

[wolle]

Well I don't quite understand what you mean by "the order doesn't matter". Maybe you mean that both elements of this should be smaller than both elements of e?

In that case you can do this,

return std::max(this->v0, this->v1) < std::min(e.v0, e.v1);

[luckiejacky]

Hello,

I actually meant that
when I add the elements
in case 1: v0==v1 and v1==v0
and case 2: v0==v0 and v1==v1
, the items are deemed to be the same, and they won't add to the container as two separate items....
Thanks
Jack

[wolle]

in case 1: v0==v1 and v1==v0
and case 2: v0==v0 and v1==v1
, the items are deemed to be the same

That can easily be translated into code. This and e are equal when:

return ((this->v0==e.v1) && (this->v1==e.v0)) || ((this->v0==e.v0) && ((this->v1==e.v1));

An example. Say this holds (1,2) in any order and e also holds (1,2) in any order and they are to be considered equal regardless of order. Then you have these four cases of equality,

1: (1,2) (1,2)
2: (1,2) (2,1)
3: (2,1) (1,2)
4: (2,1) (2,1)

The equality in cases 1 and 4 can be detected with a "straight" component-wise comparison and cases 2 and 3 with a "crosswise" comparison. This is what the code snippet I supplied does.

Note that you can reduce the four cases to 1 by keeping the components of Edge sorted. Ensuring that v0 <= v1 already in the Edge constructor is likely to save you lots of trouble later on.

[luckiejacky]

Thanks for helping....
I just received a crash with this code.... (Comparator changed)
And sometimes, when the 3 edges are different in the first place, I just got one of them actually added into the container after all.

std::vector<Face>& faces = GetFaces();
	const std::vector<D3DXVECTOR3>& verts = GetVertices();

	std::set<Edge> newEdges;

	for (int i = 0; i < faces.size(); i++)
	{
		Edge newEdge0, newEdge1, newEdge2;
		newEdge0.v0 = faces[i].v0;
		newEdge0.v1 = faces[i].v1;
		newEdge1.v0 = faces[i].v1;
		newEdge1.v1 = faces[i].v2;
		newEdge2.v0 = faces[i].v2;
		newEdge2.v1 = faces[i].v0;

		D3DXVECTOR3 v0pos = verts[faces[i].v0];
		D3DXVECTOR3 v1pos = verts[faces[i].v1];
		D3DXVECTOR3 v2pos = verts[faces[i].v2];

		newEdge0.v0_pos = v0pos;
		newEdge0.v1_pos = v1pos;
		newEdge0.faceId = faces[i].id;

		newEdge1.v0_pos = v1pos;
		newEdge1.v1_pos = v2pos;
		newEdge1.faceId = faces[i].id;

		newEdge2.v0_pos = v2pos;
		newEdge2.v1_pos = v0pos;
		newEdge2.faceId = faces[i].id;

		newEdges.insert(newEdge0);
		newEdges.insert(newEdge1);
		newEdges.insert(newEdge2);

		faces[i].m_edges.push_back(newEdge0);
		faces[i].m_edges.push_back(newEdge1);
		faces[i].m_edges.push_back(newEdge2);
		

	}

Could you please shed some lights on this?
Thanks
Jack

[wolle]

Could you please shed some lights on this?

You want to store edges in an std::set and for that you need to define a < (less) relation between the edges. The set will keep the edges sorted according to the < relation but it will also use it to establish equality to prevent edges from being inserted more than once. Say we have two edges e1 and e2. Equality is established like so: e1==e2 when !(e1<e2) && !(e2<e1).

The edges e1 and e2 are line segments, each with endpoints v0 and v1. First we assume v0 <= v1. We look at the left endpoints and state that e1<e2 when e1.v0<e2.v0. But if we stop here, due to the way equality is established, we can get a false equality when e1.v0==e2.v0. To resolve this we also involve the right endpoints and state that in the case that e1.v0==e2.v0 then e1<e2 when e1.v1<e2.v1.

This essentially means we have used both the position and length of line segments to establish the < relation. Position as primary criterion and length as secondary. In code,

boolean less(Edge e1, Edge e2) {
    return (e1.v0<e2.v0) || ((e1.v0==e2.v0) && (e1.v1<e2.v1));
}

As I've said, it pays off to to keep v0 and v1 presorted according to v0 <= v1 but if you for some reason cannot have that there is no way around a sort (in one way or another, explicit or implicit). This is one way,

boolean less(Edge s1, Edge s2) {
    Edge e1,e2;
    e1.v0 = std::min(s1.v0, s1.v1);
    e1.v1 = std::max(s1.v0, s1.v1);
    e2.v0 = std::min(s2.v0, s2.v1);
    e2.v1 = std::max(s2.v0, s2.v1);
    return (e1.v0<e2.v0) || ((e1.v0==e2.v0) && (e1.v1<e2.v1));
}

It's not tested but it should work, at least in principle

[luckiejacky]

Good. It works. Thanks, I've learnt something.... Really thanks