Hello there,
Ive got the following code

http://dpaste.dzfl.pl/e391a268

This code throws me a "Range Exception" in Algorithm.d.

If I use a lower number of random vectors, like 100, the code terminates. Also, if I delete the template instruction like this :

sort(individuals);

I also don't get an exception. Does anybody know, why this is the case?

snow:

> http://dpaste.dzfl.pl/e391a268
>
> This code throws me a "Range Exception" in Algorithm.d.
>
> If I use a lower number of random vectors, like 100, the code terminates. Also, if I delete the template instruction like this :
>
> sort(individuals);
>
> I also don't get an exception. Does anybody know, why this is the case?

If I replace your vector with a tuple (that defines automatically a lexicographic opCmp) the problem seems to disappear:


import std.stdio, std.random, std.array,
       std.algorithm, std.range, std.typecons;

alias Vector3D = Tuple!(double,"x", double,"y", double,"z");
alias Individual = Vector3D[];

Vector3D getFitness(in ref Individual individual) pure nothrow {
    return individual[0];
}

bool myComp(in Individual x, in Individual y)  {
    return x.getFitness > y.getFitness;
}

Vector3D[] initializeRandomVectors(in uint count) {
    Vector3D[] result;
    foreach (immutable i; 0 .. count)
        result ~= Vector3D(uniform(0.0, 11.0),
                           uniform(0.0, 11.0),
                           uniform(0.0, 11.0));
    return result;
}

Individual[] initializeRandomIndividuals()  {
    return 1000.iota.map!(_ => 10.initializeRandomVectors).array;
}

void main() {
    auto individuals =  initializeRandomIndividuals;
    individuals.sort!(myComp, SwapStrategy.stable);
    "finished".writeln;
}


Bye,
bearophile

On 06/28/2013 07:00 AM, snow wrote:> Hello there,
> Ive got the following code
>
> http://dpaste.dzfl.pl/e391a268
>
> This code throws me a "Range Exception" in Algorithm.d.
>
> If I use a lower number of random vectors, like 100, the code
> terminates. Also, if I delete the template instruction like this :
>
> sort(individuals);
>
> I also don't get an exception.

Yes, what is thrown is an Error. (Error and Exception are different hierarchies under Throwable.)

> Does anybody know, why this is the case?

Your opCmp does not provide a complete ordering of objects:

	int opCmp(ref const Vector3D vec) {
		if (this.x > vec.x && this.y > vec.y && this.z > vec.z)
			return 1;
		
		if (this.x < vec.x && this.y < vec.y && this.z < vec.z)
			return -1;
		
		return 0;
	}

According to that function, the following two values are neither less than nor greater than the other:

    // passes:
    assert(!(Vector3D(1, 2, 3) < Vector3D(2, 1, 3)) &&
           !(Vector3D(1, 2, 3) > Vector3D(2, 1, 3)));

Ali

On Friday, 28 June 2013 at 17:07:22 UTC, Ali Çehreli wrote:
> On 06/28/2013 07:00 AM, snow wrote:> Hello there,
> > Ive got the following code
> >
> > http://dpaste.dzfl.pl/e391a268
> >
> > This code throws me a "Range Exception" in Algorithm.d.
> >
> > If I use a lower number of random vectors, like 100, the code
> > terminates. Also, if I delete the template instruction like
> this :
> >
> > sort(individuals);
> >
> > I also don't get an exception.
>
> Yes, what is thrown is an Error. (Error and Exception are different hierarchies under Throwable.)
>
> > Does anybody know, why this is the case?
>
> Your opCmp does not provide a complete ordering of objects:
>
> 	int opCmp(ref const Vector3D vec) {
> 		if (this.x > vec.x && this.y > vec.y && this.z > vec.z)
> 			return 1;
> 		
> 		if (this.x < vec.x && this.y < vec.y && this.z < vec.z)
> 			return -1;
> 		
> 		return 0;
> 	}
>
> According to that function, the following two values are neither less than nor greater than the other:
>
>     // passes:
>     assert(!(Vector3D(1, 2, 3) < Vector3D(2, 1, 3)) &&
>            !(Vector3D(1, 2, 3) > Vector3D(2, 1, 3)));
>
> Ali

I tried this now:
	int opCmp(ref const Vector3D vec) {
		if (this.x > vec.x && this.y > vec.y && this.z > vec.z)
			return 1;
		return -1;
	}
this should be a total ordering, because a Vector is always greater or smaller, than another, but I still get the same exception.

On 06/29/2013 05:46 AM, snow wrote:

> On Friday, 28 June 2013 at 17:07:22 UTC, Ali Çehreli wrote:

>> Your opCmp does not provide a complete ordering of objects:
>>
>>     int opCmp(ref const Vector3D vec) {
>>         if (this.x > vec.x && this.y > vec.y && this.z > vec.z)
>>             return 1;
>>
>>         if (this.x < vec.x && this.y < vec.y && this.z < vec.z)
>>             return -1;
>>
>>         return 0;
>>     }
>>
>> According to that function, the following two values are neither less
>> than nor greater than the other:
>>
>>     // passes:
>>     assert(!(Vector3D(1, 2, 3) < Vector3D(2, 1, 3)) &&
>>            !(Vector3D(1, 2, 3) > Vector3D(2, 1, 3)));
>>
>> Ali
>
> I tried this now:
>      int opCmp(ref const Vector3D vec) {
>          if (this.x > vec.x && this.y > vec.y && this.z > vec.z)
>              return 1;
>          return -1;
>      }
> this should be a total ordering,

Unfortunately, no. opCmp must return 0 when the values are considered equal.

> because a Vector is always greater or smaller, than another,
> but I still get the same exception.

Not knowing whether it applies to your case, the following is one almost correct way of writing opCmp:

    int opCmp(ref const Vector3D vec) {
        return cast(int)(x != vec.x
                         ? x - vec.x
                         : (y != vec.y
                            ? y - vec.y
                            : z - vec.z));
    }

The reason I said "almost" is due to the usual floating point equality comparison warnings. Values that are supposed to be equal may not compare equal due to accumulated earlier floating point calculation errors.

Ali

On Saturday, 29 June 2013 at 14:20:05 UTC, Ali Çehreli wrote:
> Not knowing whether it applies to your case, the following is one almost correct way of writing opCmp:
>
>     int opCmp(ref const Vector3D vec) {
>         return cast(int)(x != vec.x
>                          ? x - vec.x
>                          : (y != vec.y
>                             ? y - vec.y
>                             : z - vec.z));
>     }
>
> Ali

This is the closes thing to what the OP wrote, but it is a *very* (IMO) strange way to sort 3D elements.

In basic English, it's:
Whoever has the smallest X, or, if tied,
Whoever has the smallest Y, or, if tied,
Whoever has the smallest Z

OP: Is this how you wanted to sort?

This is strange to me because ordering is (usually) tied to a norm, where basically, opCmp returns whoever has the smallest norm. Yet this ordering isn't really tied to any norm.

OP: Can you confirm how you want to sort? Usually, 3DVector are sorted using any of Euclidian, Manhatan, Maximum or Minimum norm:
https://en.wikipedia.org/wiki/Norm_(mathematics)#Examples

If you can define a "norm" function, then opCmp becomes:
--------
int opCmp(in Vector3D iRhs)
{
    auto nLhs = this.norm();
    auto nRhs = iRhs.norm();
    return (nLhs > nRhs) - (nLhs < nRhs);
}
--------

This is standard "boilerplate" opCmp. It avoids branching too.

On Saturday, 29 June 2013 at 14:20:05 UTC, Ali Çehreli wrote:
> On 06/29/2013 05:46 AM, snow wrote:
>
> > On Friday, 28 June 2013 at 17:07:22 UTC, Ali Çehreli wrote:
>
> >> Your opCmp does not provide a complete ordering of objects:
> >>
> >>     int opCmp(ref const Vector3D vec) {
> >>         if (this.x > vec.x && this.y > vec.y && this.z >
> vec.z)
> >>             return 1;
> >>
> >>         if (this.x < vec.x && this.y < vec.y && this.z <
> vec.z)
> >>             return -1;
> >>
> >>         return 0;
> >>     }
> >>
> >> According to that function, the following two values are
> neither less
> >> than nor greater than the other:
> >>
> >>     // passes:
> >>     assert(!(Vector3D(1, 2, 3) < Vector3D(2, 1, 3)) &&
> >>            !(Vector3D(1, 2, 3) > Vector3D(2, 1, 3)));
> >>
> >> Ali
> >
> > I tried this now:
> >      int opCmp(ref const Vector3D vec) {
> >          if (this.x > vec.x && this.y > vec.y && this.z >
> vec.z)
> >              return 1;
> >          return -1;
> >      }
> > this should be a total ordering,
>
> Unfortunately, no. opCmp must return 0 when the values are considered equal.
>
> > because a Vector is always greater or smaller, than another,
> > but I still get the same exception.
>
> Not knowing whether it applies to your case, the following is one almost correct way of writing opCmp:
>
>     int opCmp(ref const Vector3D vec) {
>         return cast(int)(x != vec.x
>                          ? x - vec.x
>                          : (y != vec.y
>                             ? y - vec.y
>                             : z - vec.z));
>     }
>
> The reason I said "almost" is due to the usual floating point equality comparison warnings. Values that are supposed to be equal may not compare equal due to accumulated earlier floating point calculation errors.
>
> Ali

Thats a cool way, thanks. But the exception is still coming. Both solutions  throw -1,0 or 1. So my first solution should work, too. Sure that the exception is coming, because of the compare function?

On Saturday, 29 June 2013 at 14:54:13 UTC, snow wrote:
> On Saturday, 29 June 2013 at 14:20:05 UTC, Ali Çehreli wrote:
>> Not knowing whether it applies to your case, the following is one almost correct way of writing opCmp:
>>
>>    int opCmp(ref const Vector3D vec) {
>>        return cast(int)(x != vec.x
>>                         ? x - vec.x
>>                         : (y != vec.y
>>                            ? y - vec.y
>>                            : z - vec.z));
>>    }
>>
>> The reason I said "almost" is due to the usual floating point equality comparison warnings. Values that are supposed to be equal may not compare equal due to accumulated earlier floating point calculation errors.
>>
>> Ali
>
> Thats a cool way, thanks. But the exception is still coming.

Not for me, Ali's code works.

> Both solutions  throw -1,0 or 1.

What do you mean "throw -1,0 or 1" ?

> So my first solution should work, too. Sure that the exception is coming, because of the compare function?

Your code throws an exception for me, ali's doesn't. The only difference is the compare function. So *pretty* much sure, yes.

That said, in debug code, there *should* be an assert rather than a dumb range error. This requires an enhancement.

On 06/29/2013 07:52 AM, monarch_dodra wrote:

> This is strange to me because ordering is (usually) tied to a norm,
> where basically, opCmp returns whoever has the smallest norm. Yet this
> ordering isn't really tied to any norm.

Agreed. The opCmp that I have written makes sense when there is a hierarchy between the members as in "hour, minute, second".

Ali