A Bug When vector3d is used with irrArray

[dude3d]

The problem that I found in irrArray is in binary_search_const() method to use (element < data[m] || data[m] < element) as (element == array[m]). This is not always true.

For vector3d, the ">" and "<" operators are defined as:

Code: Select all

		bool operator<(const vector3d<T>&other) const { return X<other.X && Y<other.Y && Z<other.Z;};
		bool operator>(const vector3d<T>&other) const { return X>other.X && Y>other.Y && Z>other.Z;};

For two vector3d A(100, 0, 30) and B(20, 0, 110), it's not true for both A>B and B>A, so that logic in irrArray would conclude that A==B. This is not true and the binary search fails due to this bug.

[Saturn]

Not a bug. The use of operator< instead of operator== is correct. The problem is, that you don't have a totally ordered set with your vectors, else it would work fine. And with partially ordered sets, binary search does not find the element you want, but rather one that is equivalent in the sense that operator< in both directions returns false.

Even if == was used here, the search were not successful in all cases. As binary_search would not know in what direction to search next for your vector. If you need an exact match, then you can't use a binary search for non totally ordered sets, it is a mathematically founded limitation.

[dude3d]

Hi Saturn,

Thank you for the reply. But I can not agree with you because in binary_search() method, sort() is called first and then binary_search_const() is called. So the set is sorted when binary_search_const() is called. Even so the search still fails due to the problem that I listed in my original post.

This is a use case that binary_search() fails. I think it should be treated as a bug.

Thanks.

[Saturn]

No, I'm sorry, but you don't understand the problem here. The question is not whether sort is called or not, but whether an arbitrary set of vectors can be brought in a total ordering. And vector3d<>::operator< can't do this. Your own sample illustrates it. What is the natural order of your vectors A and B? A, B or B, A? sort() has no way of sorting the vectors meaningfully and thus binary_search() can't work on it.

Just look it up in an algebra text book of your choice. This is an inherent mathematical problem, not a bug.

[vitek]

No, Saturn is most definitely correct. It is most definitely _not_ a bug. You've already established that A < B is false and B < A is false for A=(100, 0, 30) and B=(20, 0, 110). So, given these two vectors, how do you sort them? Does A come first or B?

If you don't define a strict ordering, then sort doesn't work. Here is a simple testcase.

Code: Select all

#include <vector3d.h>
#include <irrarray.h>
#include <assert.h>
#include <stdio.h>

using namespace irr;

void show(const core::array<core::vector3df>& a)
{
  u32 i;
  for (i = 0; i < a.size(); ++i)
    printf ("X=%f Y=%f Z=%f\n", a[i].X, a[i].Y, a[i].Z);
  printf ("\n");
}

int main ()
{
  core::array<core::vector3df> a;

  u32 i;
  for (i = 0; i < 3; ++i)
    a.push_back (core::vector3df(i, 0, 3 - i));

  show (a);
  a.sort ();
  show (a);

  for (i = 0; i < a.size() - 1; ++i)
    assert (a[i] < a[i+1] || a[i] == a[i+1]);

  return 0;
}

So now that you know that you can't sort a type that doesn't define a strict weak ordering, how do you expect to do a binary search?

Travis

[BlindSide]

Don't you think the > and < operators of vectors should compare the squared length or something?

[vitek]

Only if you consider vectors that have the same length to be equal. Otherwise it doesn't help.

The weak ordering requirement says that if !(A < B) and !(B < A) then (A == B) must be true. Consider A=(0, 1, 0) and B=(1, 0, 0). A < B is false and B < A is false, but B == A is also false [if you consider equality as all components of the vector have the same value].

Travis