You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@groovy.apache.org by Jochen Theodorou <bl...@gmx.org> on 2015/09/03 13:45:29 UTC
usage of NumberAwareComparator in extension methods and number oddities
(a bit code review)
Hi all,
NumberAwareComparator is used in several extension methods Groovy
provides to be able to compare things, that cannot really be compared.
That involves sorting (sort, toSorted), but also things like: retainAll,
removeAll, minus on Collection, intersect and disjoint.
NumberAwareComperator will basically use the same logic as <=>, but in
case it cannot be compared, it will compare using the hashcode, though
never issuing an equals here. Of course this logic is difficult to
understand and was mainly done to be able to sort things somehow for
things you cannot really sort. Also note that <=> purely depends on
compareTo, even throwing an exception if only equals would be needed.
The first question I have here is: Do we really want to keep providing a
very difficult to understand way of comparing things, you actually
cannot compare for sorting? Meaning for example, should [new Object(),
new Object()].sort() really give a random order, or should it result in
an exception? I am not sure anymore, that we do our users a good thing
providing this operation.
And of course there are these other methods, that only need equality,
but use NumberAwareComperator.
The method with the longest history in this is most probably
Collection#minus(Collection), well the List variant actually, but the
Collection variant is where the implementation moved to.
This method actually has two variants inside. First there will be a test
for the sameType being used and then.... frankly after so many
iterations the code looks just odd to me.
> //n*LOG(n) version
> Set<T> answer;
> if (Number.class.isInstance(head)) {
> answer = new TreeSet<T>(numberComparator);
> answer.addAll(self);
> for (T t : self) {
> if (Number.class.isInstance(t)) {
> for (Object t2 : removeMe) {
> if (Number.class.isInstance(t2)) {
> if (numberComparator.compare(t, (T)t2) == 0)
> answer.remove(t);
> }
> }
> } else {
> if (removeMe.contains(t))
> answer.remove(t);
> }
> }
> } else {
we get here after we have established, that all the elements are of the
"same" type. Either directly the same, or null, or a Number. So if the
head is a number, then all elements should be a number. "answer" is a
TreeSet with numberComparator (NumberAwareComparator). Now, since we use
the number comperator to make a TreeSet, this will mean this action
alone may already remove elements. But "answer" is not what the method
will return, it is "ansCollection", which will be build separately based
on answer later. The inner Number check is, if my assumption before is
right, surplus and the else-branch there never visited. And then we
iterate over all elements of self and all elements of removeMe to
eventually call answer.remove... That smells like n*n*logn complexity.
The statement about this being an n*logn would be wrong then.
I really wonder if something like this:
Set<T> answer;
if (head instanceof Number) {
answer = new TreeSet<T>(numberComparator);
answer.addAll(self);
Set<T> removeSet = new TreeSet<T>(numberComperator);
removeSet.addAll(removeMe);
answer.removeAll(removeSet);
}
would not be better. At least that should go near n*logn. And we do
something similiar in case head is no number:
> } else {
> answer = new TreeSet<T>(numberComparator);
> answer.addAll(self);
> answer.removeAll(removeMe);
> }
Only I am wondering.... if removeMe is a Set as well, then this may not
do what we want. Imagine removeMe being another TreeSet with its own
comparator and this implementation of removeAll:
> public boolean removeAll(Collection<?> c) {
> Objects.requireNonNull(c);
> boolean modified = false;
>
> if (size() > c.size()) {
> for (Iterator<?> i = c.iterator(); i.hasNext(); )
> modified |= remove(i.next());
> } else {
> for (Iterator<?> i = iterator(); i.hasNext(); ) {
> if (c.contains(i.next())) {
> i.remove();
> modified = true;
> }
> }
> }
> return modified;
> }
This means c.contains will be called and the different comparator may be
used for it. Proof:
> def toRemove = new TreeSet({a,b->-1})
> toRemove.addAll(["a","b"])
> def res = ["a"]*2 - toRemove
> assert res == ["a","a"]
>
> res = ["a"]*2+["b","c"] - toRemove
> assert res == ["c"]
Of course this Comparator does not behave nice, but the point is more
that our comparator is not used in the first case. It depends on the
size of the Set, or better said, the size of the TreeSet. Since equal
(according to number comparator) elements appear there only once, the
size in the first case will be 1, in the second case 3, while the sizes
of the self collections are 2 and 4. Frankly I cannot really understand
why the JDK has this in this way at all, or why TreeSet does not
override it. Sure, the version they choose is better for performance,
but I find this behaviour not right, considering how removeAll works on
for example lists. Anyway... this should not be a rant about the JDK ;).
Now... does it make sense to use NumberAwareComperator here at all? If
we want to support [1.0]-[1]==[], then yes. But the gravity of this is
unclear I would say:
> class MyNumber extends Number {
> def n
> int intValue(){n}
> long longValue(){n}
> float floatValue(){n}
> double doubleValue(){n}
> int hashCode(){-n}
> boolean equals(other) {
> if (other instanceof MyNumber) { return n==other.n}
> return false
> }
> int compareTo(MyNumber other) {
> return n <=> other.n
> }
> String toString(){"MyNumber($n)"}
> }
>
> def res = [1,new MyNumber(n:1)] - [1]
while the first loops to produce answer will correctly produce a TreeSet
containing only MyNumber, the later logic to produce ansCollection will
cause problems and nothing will be removed. ThatÄs because MyNumber(n:1)
is equal to 1, ehm, actually that is wrong. 1 is equal to MyNumber(n:1)
according to Groovy logic, but not the other way around.
assert 1 == new MyNumber(n:1)
assert new MyNumber(n:1) != 1
That is because we don't actually call Integer#compareTo. If that had
been the case, then both would not be equal. No, instead we fall back to
those number math classes, and they assume, that if you compare
something with an integer, then the other one needs to be converted to
an integer as well. And since my intValue() method here returns 1, they
are seen as equal, even though compareTo, equals and even the hashcodes
would not allow that. If I reverse the order in my list:
> def res = [new MyNumber(n:1),1] - [1]
then the result will be as expected and contains only MyNumber(n:1).
Funny thing here is... I added a compareTo method, but no Comparable
interface. So MyNumber is not comparable... Does it changes things if it
does? So I add "implements Comparable<MyNumber>" to the class and now I
get the same result, regardless of the order. Which is []. That is
because now 1 is always equal to MyNumber(n:1). That is because now in
both case IntegerMath is used. Does this mean any two custom numbers are
equal, if their intValue is? So let's take MyNumber again and make a
second class just the same, including Comparable, then call it MyNumber2
> assert new MyNumber2(n:1) == new MyNumber(n:1)
> assert new MyNumber(n:1) == new MyNumber2(n:1)
Well... if you did read, what I did write before, then this is no
surprise... But frankly... should it be like this? And if MyNumber2 does
not implement Comparable:
> assert new MyNumber2(n:1) != new MyNumber(n:1)
> assert new MyNumber(n:1) == new MyNumber2(n:1)
again because of the fallback logic to IntegerMath... and if both do not
implement it:
> assert new MyNumber2(n:1) != new MyNumber(n:1)
> assert new MyNumber(n:1) != new MyNumber2(n:1)
Well... that is more the expected result, still... and not to
forget:This is ==, not <=>. == uses <=> only for comparable cases. So:
> new MyNumber2(n:1) <=> new MyNumber(n:1)
> new MyNumber(n:1) <=> new MyNumber2(n:1)
will both throw a GroovyRuntimeException, if non does implement
Comparable. If MyNumber2 implements it, the first compare works using
IntegerMath and tells us they are equal. If both implement it, they are
both equal. That is basically the same as ==, but what does
NumberAwareComperator do for such cases?
> try {
> return DefaultTypeTransformation.compareTo(o1, o2);
> } catch (ClassCastException cce) {
> /* ignore */
> } catch (GroovyRuntimeException gre) {
> /* ignore */
> }
> // since the object does not have a valid compareTo method
> // we compare using the hashcodes. null cases are handled by
> // DefaultTypeTransformation.compareTo
> // This is not exactly a mathematical valid approach, since we compare object
> // that cannot be compared. To avoid strange side effects we do a pseudo order
> // using hashcodes, but without equality. Since then an x and y with the same
> // hashcodes will behave different depending on if we compare x with y or
> // x with y, the result might be unstable as well. Setting x and y to equal
> // may mean the removal of x or y in a sorting operation, which we don't want.
> int x1 = o1.hashCode();
> int x2 = o2.hashCode();
> if (x1 > x2) return 1;
> return -1;
compareTo is the path for <=>, so we can expect exceptions here. So now
with MyNumber being a Comparable, and MyNumber2 not:
> println ([new MyNumber(n:1), new MyNumber2(n:1)] - [new MyNumber2(n:1)])
> println ([new MyNumber(n:1), new MyNumber2(n:1)] - [new MyNumber(n:1)])
> println ([new MyNumber2(n:1), new MyNumber(n:1)] - [new MyNumber2(n:1)])
> println ([new MyNumber2(n:1), new MyNumber(n:1)] - [new MyNumber(n:1)])
In the first two cases nothing is removed, in the third case we get an
empty list and in the last case MyNumber is removed.
Since MyNumber2 does not implement Comparable here
DefaultTypeTransformation.compareTo will throw an exception, whenever we
have MyNumber2 as o1. The compare using hashcodes will never equal.
Well. There has been one part of that minus method we have not looked
at. This is called if the first element is not Comparable, even if all
extend Number:
> //n*n version
> List<T> tmpAnswer = new LinkedList<T>(self);
> for (Iterator<T> iter = tmpAnswer.iterator(); iter.hasNext();) {
> T element = iter.next();
> boolean elementRemoved = false;
> for (Iterator<?> iterator = removeMe.iterator(); iterator.hasNext() && !elementRemoved;) {
> Object elt = iterator.next();
> if (DefaultTypeTransformation.compareEqual(element, elt)) {
> iter.remove();
> elementRemoved = true;
> }
> }
> }
>
> //remove duplicates
> //can't use treeset since the base classes are different
> ansCollection.addAll(tmpAnswer);
so if MyNumber2 is the head element this code will be executed instead,
since MyNumber2 not implement Comparable.
DefaultTypeTransformation.compareEqual is the code path taken for "=="
which I talked about already. Remember, IntegerMath is the fallback for
Numbers.compareEqual will prevent the exception being thrown, even
though compareTo is called internally, but only if the left hand side is
a Comparable. So here equality checks are done instead.. for example
using the equals method. That explains why ([new MyNumber2(n:1), new
MyNumber(n:1)] - [new MyNumber2(n:1)]) gets the empty list... first part
is normaly equality, second part is fallback to IntegerMath. Of course
if the code used DefaultTypeTransformation.compareEqual(elt, element),
then this would behave different, but the result would be the same. The
major difference would be that MyNumber2#equals is not called. For ([new
MyNumber2(n:1), new MyNumber(n:1)] - [new MyNumber(n:1)]) we do
compareEquals with MyNumber2 and MyNumber first, resulting in the
element not being removed, so the result will be [MyNumber(n:1)]
But that did not give me the exception path... Looking at the code, with
numbers you won't get that path... or not? Well, with a subclass of
BigDecimal/BigInteger you can do that. But they implement
Comparable<BigDecimal>/Comparable<BigInteger>, so you are supposed to
make a method for that only... supposed to is not equal to people
actually doing that. Still I won't give an example of that now.
If you look at the sameType method, then it looks only at Number and
null and the exact same class. to enter the not so n*logn path and use
the number comperator. Point being here, the hashcode compares will not
normally happen for Numbers or null. And in case of all elements of both
Collections being of the same class, there should be no exception we
have the right to catch and fall back to hashcode logic. So we could
question here if NumberAwareComperator should be even used like it is
for this method.
So let's have a much shorter look at the other methods...
retainAll, intersect and disjoint: uses the comparator for all elements,
so it may use the hashcode logic. But at least they should be stable.
removeAll: same. Well, there is in theory the issue of self being a Set
and the special Set logic. But in this case, this method is not supposed
to be called.
Actually, there are two more methods using the Comperator behind the
scenes.... coercedEquals (used by several equals methods, minus and
another old friend: unique) and numberAwareCompareTo (used by
coerecedEquals and ObjectRange).
So we would have to look at those as well... but this mail got pretty
long already and I am out of time. So I put to discussion what I wrote
about for now.
bye blackdrag
--
Jochen "blackdrag" Theodorou
blog: http://blackdragsview.blogspot.com/
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Thibault Kruse <ti...@googlemail.com>.
I opened JIRA issues:
https://issues.apache.org/jira/browse/GROOVY-7636
https://issues.apache.org/jira/browse/GROOVY-76367
and created PR:
https://github.com/apache/incubator-groovy/pull/150
On Tue, Sep 8, 2015 at 3:19 PM, Thibault Kruse <ti...@googlemail.com> wrote:
>> // bug, returns 47?
>> // assert compareTo('aa1', '2' as Character) == 1
>
> those ones are fine actually, compareTo in Comparable only requires
> integers, not -1, 0, 1, and I'll assume that as long as the sign is
> valid, it's not a bug.
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Thibault Kruse <ti...@googlemail.com>.
> // bug, returns 47?
> // assert compareTo('aa1', '2' as Character) == 1
those ones are fine actually, compareTo in Comparable only requires
integers, not -1, 0, 1, and I'll assume that as long as the sign is
valid, it's not a bug.
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Thibault Kruse <ti...@googlemail.com>.
Created https://issues.apache.org/jira/browse/GROOVY-7581 for those.
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Thibault Kruse <ti...@googlemail.com>.
If you look at the commit I pointed to, it will be easier to discuss
the bugs. I list them here again. Class MyNumber is as you described
before, MyNumberComparable is the same implementing also Comparable
(see commit). I use numbers 49 and 50 because those are the int
representations of chars '1' and '2'.
MyNumberComparable numComp1 = new MyNumberComparable(49)
// works
checkCompareToSymmetricSmallerThan(numComp1, 50)
// Bug, NumberFormatException, comparison to all other Number types works
// checkCompareToSymmetricSmallerThan(numComp1, 50G)
// bug, returns 47?
// assert compareTo('aa1', '2' as Character) == 1
// bug, classCast exception
// assert compareTo('2' as Character, 'aa1') == 1
// bug, returns 47?
// assert compareTo("aa${1}", '2' as Character) == 1
// bug, classCast exception
//assert compareTo('2' as Character, "aa${1}") == 1
MyNumber number2 = new MyNumber(50)
// works
assert compareTo(49, number2) == -1
// bug: GroovyRuntimeException, but other way round works
//assert compareTo(number2, 49) == -1
Given there is no specification, the term "bug" might be stretching
it, but I believe from the rest of the code it can be inferred that in
those cases shown above the code does not behave as the programmer(s)
of the method intended for the method to behave. That's a bug for me.
In the absence of specifications all we can do is guess.
On Mon, Sep 7, 2015 at 2:53 PM, Jochen Theodorou <bl...@gmx.org> wrote:
>> So I would recommend fixing those, then adding some more tests with
>> other Comparables or Objects with compareTo, and make sure that it
>> behaves symmetrically and consistently.
>
>
> and what is the "expected" behaviour?
For DefaultTypeTransformation.compareTo I would say that it returns
values treating all numbers by their numeric value, being able to
compare all Strings/GStrings/Chars, and else comparing Comparables
only to Comparables, possibly considering instances having a compareTo
Method without implementing Comparable as duck-typed Comparables.
For NumberAwareComparator I would suggest the same behavior, throwing
Exceptions for any other case (e.g.
NumberAwareComparator.compare(new Object(), new Object()) should throw
an Exception, IMO).
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Jochen Theodorou <bl...@gmx.org>.
Am 07.09.2015 12:08, schrieb Thibault Kruse:
[...]
> I was not sure that it does, looking at the code, so I looked to
> extend the unit test.
> I found it has no unit test. Finding this makes me sad.
that's because the method is not really part of an API and is instead
tested through groovy scripts using the comparison operators and other
means. That does of course not mean those tests are extensive enough.
> Anyway, I wrote some tests, to find there are several issues with symmetry:
> https://github.com/tkruse/incubator-groovy/commit/aa8d201cbbca6823adbacf15cddfc7dd68881a13
> Given there were no tests, I am not too surprised to find bugs.
To have a bug we would first need a well defined behaviour
> So I would recommend fixing those, then adding some more tests with
> other Comparables or Objects with compareTo, and make sure that it
> behaves symmetrically and consistently.
and what is the "expected" behaviour?
bye blackdrag
--
Jochen "blackdrag" Theodorou
blog: http://blackdragsview.blogspot.com/
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Thibault Kruse <ti...@googlemail.com>.
On Mon, Sep 7, 2015 at 9:32 AM, Jochen Theodorou <bl...@gmx.org> wrote:
> Am 03.09.2015 18:29, schrieb Thibault Kruse:
>>
>> So the anti-commutativity is broken in my example because
>> NumberAwareComparator because DefaultTypeTransformation.compareTo does
>> not perform symmetric checks (only 'left' needs to implement
>> Comparable, not 'right').
>>
>> Maybe this could already be fixed by
>> DefaultTypeTransformation.compareTo requiring both arguments to be of
>> equivalent type, such as both being Comparables. And possibly as an
>> alternative fallback both being of the same class and having a
>> compareTo Method (which would break less groovy code I guess).
>
>
> DefaultTypeTransformation.compareTo does something like that actually, but
> not for numbers. And if you want to compare Double and Integer, it won't
> work that way.
I was not sure that it does, looking at the code, so I looked to
extend the unit test.
I found it has no unit test. Finding this makes me sad.
Anyway, I wrote some tests, to find there are several issues with symmetry:
https://github.com/tkruse/incubator-groovy/commit/aa8d201cbbca6823adbacf15cddfc7dd68881a13
Given there were no tests, I am not too surprised to find bugs.
So I would recommend fixing those, then adding some more tests with
other Comparables or Objects with compareTo, and make sure that it
behaves symmetrically and consistently.
>> This could further be relaxed to also allow comparing two instances
>> *of the same class* when they have a compareTo method. But comparing a
>> MyNumber with an Integer should IMO fail in
>> DefaultTypeTransformation.compareTo().
>>
>> Another problem of anti-commutativity arises due to the weird
>> hashCode() comparison that never returns 0, even when both hashCode
>> values are the same.
>> Maybe it would be better to compare the System hashcodes
>> System.identityHashCode(x) rather than the hashcodes from the objects.
>> Maybe that way even a 0 value could be returned then.
>
>
> if both objects have referential identity
> DefaultTypeTransformation.compareTo, will return 0. The method will also
> handle null. What should we do if the hashcodes are the same, but the
> objects are not? identityHashCode gives no guaranteee
I see. So probably better not to have any fallback in NumberAwareComparator.
But I cannot say whether in general it would be acceptable to Groovy
users if a new version of Groovy started throwing exceptions some
unhealthy cases of comparing Objects that should not be compared (or
should implement Comparable, or should use a custom Comparator).
On Mon, Sep 7, 2015 at 9:32 AM, Jochen Theodorou <bl...@gmx.org> wrote:
> Am 03.09.2015 18:29, schrieb Thibault Kruse:
>>
>> So the anti-commutativity is broken in my example because
>> NumberAwareComparator because DefaultTypeTransformation.compareTo does
>> not perform symmetric checks (only 'left' needs to implement
>> Comparable, not 'right').
>>
>> Maybe this could already be fixed by
>> DefaultTypeTransformation.compareTo requiring both arguments to be of
>> equivalent type, such as both being Comparables. And possibly as an
>> alternative fallback both being of the same class and having a
>> compareTo Method (which would break less groovy code I guess).
>
>
> DefaultTypeTransformation.compareTo does something like that actually, but
> not for numbers. And if you want to compare Double and Integer, it won't
> work that way.
>
>> This could further be relaxed to also allow comparing two instances
>> *of the same class* when they have a compareTo method. But comparing a
>> MyNumber with an Integer should IMO fail in
>> DefaultTypeTransformation.compareTo().
>>
>> Another problem of anti-commutativity arises due to the weird
>> hashCode() comparison that never returns 0, even when both hashCode
>> values are the same.
>> Maybe it would be better to compare the System hashcodes
>> System.identityHashCode(x) rather than the hashcodes from the objects.
>> Maybe that way even a 0 value could be returned then.
>
>
> if both objects have referential identity
> DefaultTypeTransformation.compareTo, will return 0. The method will also
> handle null. What should we do if the hashcodes are the same, but the
> objects are not? identityHashCode gives no guaranteee
>
>> Whether it makes sense at all to compare objects that way I don't know.
>>
>> Comparing 0.0d and 0 as same without breaking equals-consistency seems
>> impossible, not sure what to do about that.
>
>
> it is worse. compare 1.0G and 1.00G. BigDecimal.compare will say the are
> euqal, BigDecimal.equals will say no.
>
>
> bye blackdrag
>
> --
> Jochen "blackdrag" Theodorou
> blog: http://blackdragsview.blogspot.com/
>
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Jochen Theodorou <bl...@gmx.org>.
Am 03.09.2015 18:29, schrieb Thibault Kruse:
> So the anti-commutativity is broken in my example because
> NumberAwareComparator because DefaultTypeTransformation.compareTo does
> not perform symmetric checks (only 'left' needs to implement
> Comparable, not 'right').
>
> Maybe this could already be fixed by
> DefaultTypeTransformation.compareTo requiring both arguments to be of
> equivalent type, such as both being Comparables. And possibly as an
> alternative fallback both being of the same class and having a
> compareTo Method (which would break less groovy code I guess).
DefaultTypeTransformation.compareTo does something like that actually,
but not for numbers. And if you want to compare Double and Integer, it
won't work that way.
> This could further be relaxed to also allow comparing two instances
> *of the same class* when they have a compareTo method. But comparing a
> MyNumber with an Integer should IMO fail in
> DefaultTypeTransformation.compareTo().
>
> Another problem of anti-commutativity arises due to the weird
> hashCode() comparison that never returns 0, even when both hashCode
> values are the same.
> Maybe it would be better to compare the System hashcodes
> System.identityHashCode(x) rather than the hashcodes from the objects.
> Maybe that way even a 0 value could be returned then.
if both objects have referential identity
DefaultTypeTransformation.compareTo, will return 0. The method will also
handle null. What should we do if the hashcodes are the same, but the
objects are not? identityHashCode gives no guaranteee
> Whether it makes sense at all to compare objects that way I don't know.
>
> Comparing 0.0d and 0 as same without breaking equals-consistency seems
> impossible, not sure what to do about that.
it is worse. compare 1.0G and 1.00G. BigDecimal.compare will say the are
euqal, BigDecimal.equals will say no.
bye blackdrag
--
Jochen "blackdrag" Theodorou
blog: http://blackdragsview.blogspot.com/
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Thibault Kruse <ti...@googlemail.com>.
So the anti-commutativity is broken in my example because
NumberAwareComparator because DefaultTypeTransformation.compareTo does
not perform symmetric checks (only 'left' needs to implement
Comparable, not 'right').
Maybe this could already be fixed by
DefaultTypeTransformation.compareTo requiring both arguments to be of
equivalent type, such as both being Comparables. And possibly as an
alternative fallback both being of the same class and having a
compareTo Method (which would break less groovy code I guess).
This could further be relaxed to also allow comparing two instances
*of the same class* when they have a compareTo method. But comparing a
MyNumber with an Integer should IMO fail in
DefaultTypeTransformation.compareTo().
Another problem of anti-commutativity arises due to the weird
hashCode() comparison that never returns 0, even when both hashCode
values are the same.
Maybe it would be better to compare the System hashcodes
System.identityHashCode(x) rather than the hashcodes from the objects.
Maybe that way even a 0 value could be returned then.
Whether it makes sense at all to compare objects that way I don't know.
Comparing 0.0d and 0 as same without breaking equals-consistency seems
impossible, not sure what to do about that.
On Thu, Sep 3, 2015 at 5:17 PM, Jochen Theodorou <bl...@gmx.org> wrote:
> Am 03.09.2015 15:07, schrieb Thibault Kruse:
>>
>> That's a long read.
>
>
> and took hours to write
>
>> In a nutshell, it seems NumberComparator does
>> satisfy not the required anti-commutativity (
>> "The implementor must ensure that <tt>sgn(compare(x, y)) ==
>> -sgn(compare(y, x))</tt> for all <tt>x</tt> and <tt>y</tt>.") when
>> used for Non-Comparables:
>>
>> x = new MyNumber(n: 1)
>> y = new Integer(0)
>> assert comp.compare(x, y) == - comp.compare(y, x)
>> | | | | | | | | | |
>> | -1 | 0 | 1 | -1 0 MyNumber(1)
>> | | |
>> org.codehaus.groovy.runtime.NumberAwareComparator@3e77a1ed
>> | | false
>> | MyNumber(1)
>> org.codehaus.groovy.runtime.NumberAwareComparator@3e77a1ed
>>
>>
>> And it is not "consistent with equals", which means it should not be
>> used with sorted Sets or Maps ("should be used with caution").
>>
>> assert (comp.compare(new Float(0), new Integer(0)) == 0) == (new
>> Float(0).equals(new Integer(0)))
>> | | | | | | |
>> | |
>> | 0 0.0 0 true | 0.0
>> false 0
>> | false
>> org.codehaus.groovy.runtime.NumberAwareComparator@fe18270
>>
>> Both violating anti-commutativity and not offering equals-consistency
>> make NumberAwareComparator an accident waiting to happen.
>
>
> the tip of the iceberg, yes
>
>> So +1 for making that less Groovy-relaxed and more Java-strict. But I
>> would say that about many things, without care for breaking existing
>> code (Because that's the only way to move Groovy into more production
>> code in the world).
>>
>> The Collection.minus() problem looks too complex to understand at a
>> glance.
>
>
>
> The question is, for both, what the change should be. If we want to support
> being able to do "assert 1.00g == 1.0g", as well as "assert 1==1.0d" and if
> we want to mimic that with NumberAwareComperator, then we have to violate
> "consistent with equals" and "anti-commutativity"
>
>
> bye blackdrag
>
>
> --
> Jochen "blackdrag" Theodorou
> blog: http://blackdragsview.blogspot.com/
>
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Jochen Theodorou <bl...@gmx.org>.
Am 03.09.2015 15:07, schrieb Thibault Kruse:
> That's a long read.
and took hours to write
> In a nutshell, it seems NumberComparator does
> satisfy not the required anti-commutativity (
> "The implementor must ensure that <tt>sgn(compare(x, y)) ==
> -sgn(compare(y, x))</tt> for all <tt>x</tt> and <tt>y</tt>.") when
> used for Non-Comparables:
>
> x = new MyNumber(n: 1)
> y = new Integer(0)
> assert comp.compare(x, y) == - comp.compare(y, x)
> | | | | | | | | | |
> | -1 | 0 | 1 | -1 0 MyNumber(1)
> | | |
> org.codehaus.groovy.runtime.NumberAwareComparator@3e77a1ed
> | | false
> | MyNumber(1)
> org.codehaus.groovy.runtime.NumberAwareComparator@3e77a1ed
>
>
> And it is not "consistent with equals", which means it should not be
> used with sorted Sets or Maps ("should be used with caution").
>
> assert (comp.compare(new Float(0), new Integer(0)) == 0) == (new
> Float(0).equals(new Integer(0)))
> | | | | | | |
> | |
> | 0 0.0 0 true | 0.0
> false 0
> | false
> org.codehaus.groovy.runtime.NumberAwareComparator@fe18270
>
> Both violating anti-commutativity and not offering equals-consistency
> make NumberAwareComparator an accident waiting to happen.
the tip of the iceberg, yes
> So +1 for making that less Groovy-relaxed and more Java-strict. But I
> would say that about many things, without care for breaking existing
> code (Because that's the only way to move Groovy into more production
> code in the world).
>
> The Collection.minus() problem looks too complex to understand at a glance.
The question is, for both, what the change should be. If we want to
support being able to do "assert 1.00g == 1.0g", as well as "assert
1==1.0d" and if we want to mimic that with NumberAwareComperator, then
we have to violate "consistent with equals" and "anti-commutativity"
bye blackdrag
--
Jochen "blackdrag" Theodorou
blog: http://blackdragsview.blogspot.com/
Re: usage of NumberAwareComparator in extension methods and number
oddities (a bit code review)
Posted by Thibault Kruse <ti...@googlemail.com>.
That's a long read. In a nutshell, it seems NumberComparator does
satisfy not the required anti-commutativity (
"The implementor must ensure that <tt>sgn(compare(x, y)) ==
-sgn(compare(y, x))</tt> for all <tt>x</tt> and <tt>y</tt>.") when
used for Non-Comparables:
x = new MyNumber(n: 1)
y = new Integer(0)
assert comp.compare(x, y) == - comp.compare(y, x)
| | | | | | | | | |
| -1 | 0 | 1 | -1 0 MyNumber(1)
| | |
org.codehaus.groovy.runtime.NumberAwareComparator@3e77a1ed
| | false
| MyNumber(1)
org.codehaus.groovy.runtime.NumberAwareComparator@3e77a1ed
And it is not "consistent with equals", which means it should not be
used with sorted Sets or Maps ("should be used with caution").
assert (comp.compare(new Float(0), new Integer(0)) == 0) == (new
Float(0).equals(new Integer(0)))
| | | | | | |
| |
| 0 0.0 0 true | 0.0
false 0
| false
org.codehaus.groovy.runtime.NumberAwareComparator@fe18270
Both violating anti-commutativity and not offering equals-consistency
make NumberAwareComparator an accident waiting to happen.
So +1 for making that less Groovy-relaxed and more Java-strict. But I
would say that about many things, without care for breaking existing
code (Because that's the only way to move Groovy into more production
code in the world).
The Collection.minus() problem looks too complex to understand at a glance.
On Thu, Sep 3, 2015 at 1:45 PM, Jochen Theodorou <bl...@gmx.org> wrote:
> Hi all,
>
> NumberAwareComparator is used in several extension methods Groovy provides
> to be able to compare things, that cannot really be compared. That involves
> sorting (sort, toSorted), but also things like: retainAll, removeAll, minus
> on Collection, intersect and disjoint. NumberAwareComperator will basically
> use the same logic as <=>, but in case it cannot be compared, it will
> compare using the hashcode, though never issuing an equals here. Of course
> this logic is difficult to understand and was mainly done to be able to sort
> things somehow for things you cannot really sort. Also note that <=> purely
> depends on compareTo, even throwing an exception if only equals would be
> needed.
>
> The first question I have here is: Do we really want to keep providing a
> very difficult to understand way of comparing things, you actually cannot
> compare for sorting? Meaning for example, should [new Object(), new
> Object()].sort() really give a random order, or should it result in an
> exception? I am not sure anymore, that we do our users a good thing
> providing this operation.
>
> And of course there are these other methods, that only need equality, but
> use NumberAwareComperator.
>
> The method with the longest history in this is most probably
> Collection#minus(Collection), well the List variant actually, but the
> Collection variant is where the implementation moved to.
>
> This method actually has two variants inside. First there will be a test for
> the sameType being used and then.... frankly after so many iterations the
> code looks just odd to me.
>
>> //n*LOG(n) version
>> Set<T> answer;
>> if (Number.class.isInstance(head)) {
>> answer = new TreeSet<T>(numberComparator);
>> answer.addAll(self);
>> for (T t : self) {
>> if (Number.class.isInstance(t)) {
>> for (Object t2 : removeMe) {
>> if (Number.class.isInstance(t2)) {
>> if (numberComparator.compare(t, (T)t2) ==
>> 0)
>> answer.remove(t);
>> }
>> }
>> } else {
>> if (removeMe.contains(t))
>> answer.remove(t);
>> }
>> }
>> } else {
>
>
> we get here after we have established, that all the elements are of the
> "same" type. Either directly the same, or null, or a Number. So if the head
> is a number, then all elements should be a number. "answer" is a TreeSet
> with numberComparator (NumberAwareComparator). Now, since we use the number
> comperator to make a TreeSet, this will mean this action alone may already
> remove elements. But "answer" is not what the method will return, it is
> "ansCollection", which will be build separately based on answer later. The
> inner Number check is, if my assumption before is right, surplus and the
> else-branch there never visited. And then we iterate over all elements of
> self and all elements of removeMe to eventually call answer.remove... That
> smells like n*n*logn complexity. The statement about this being an n*logn
> would be wrong then.
>
> I really wonder if something like this:
>
> Set<T> answer;
> if (head instanceof Number) {
> answer = new TreeSet<T>(numberComparator);
> answer.addAll(self);
> Set<T> removeSet = new TreeSet<T>(numberComperator);
> removeSet.addAll(removeMe);
> answer.removeAll(removeSet);
> }
>
> would not be better. At least that should go near n*logn. And we do
> something similiar in case head is no number:
>
>> } else {
>> answer = new TreeSet<T>(numberComparator);
>> answer.addAll(self);
>> answer.removeAll(removeMe);
>> }
>
>
> Only I am wondering.... if removeMe is a Set as well, then this may not do
> what we want. Imagine removeMe being another TreeSet with its own comparator
> and this implementation of removeAll:
>
>> public boolean removeAll(Collection<?> c) {
>> Objects.requireNonNull(c);
>> boolean modified = false;
>>
>> if (size() > c.size()) {
>> for (Iterator<?> i = c.iterator(); i.hasNext(); )
>> modified |= remove(i.next());
>> } else {
>> for (Iterator<?> i = iterator(); i.hasNext(); ) {
>> if (c.contains(i.next())) {
>> i.remove();
>> modified = true;
>> }
>> }
>> }
>> return modified;
>> }
>
>
> This means c.contains will be called and the different comparator may be
> used for it. Proof:
>
>> def toRemove = new TreeSet({a,b->-1})
>> toRemove.addAll(["a","b"])
>> def res = ["a"]*2 - toRemove
>> assert res == ["a","a"]
>>
>> res = ["a"]*2+["b","c"] - toRemove
>> assert res == ["c"]
>
>
> Of course this Comparator does not behave nice, but the point is more that
> our comparator is not used in the first case. It depends on the size of the
> Set, or better said, the size of the TreeSet. Since equal (according to
> number comparator) elements appear there only once, the size in the first
> case will be 1, in the second case 3, while the sizes of the self
> collections are 2 and 4. Frankly I cannot really understand why the JDK has
> this in this way at all, or why TreeSet does not override it. Sure, the
> version they choose is better for performance, but I find this behaviour not
> right, considering how removeAll works on for example lists. Anyway... this
> should not be a rant about the JDK ;). Now... does it make sense to use
> NumberAwareComperator here at all? If we want to support [1.0]-[1]==[], then
> yes. But the gravity of this is unclear I would say:
>
>> class MyNumber extends Number {
>> def n
>> int intValue(){n}
>> long longValue(){n}
>> float floatValue(){n}
>> double doubleValue(){n}
>> int hashCode(){-n}
>> boolean equals(other) {
>> if (other instanceof MyNumber) { return n==other.n}
>> return false
>> }
>> int compareTo(MyNumber other) {
>> return n <=> other.n
>> }
>> String toString(){"MyNumber($n)"}
>> }
>>
>> def res = [1,new MyNumber(n:1)] - [1]
>
>
> while the first loops to produce answer will correctly produce a TreeSet
> containing only MyNumber, the later logic to produce ansCollection will
> cause problems and nothing will be removed. ThatÄs because MyNumber(n:1) is
> equal to 1, ehm, actually that is wrong. 1 is equal to MyNumber(n:1)
> according to Groovy logic, but not the other way around.
>
> assert 1 == new MyNumber(n:1)
> assert new MyNumber(n:1) != 1
>
> That is because we don't actually call Integer#compareTo. If that had been
> the case, then both would not be equal. No, instead we fall back to those
> number math classes, and they assume, that if you compare something with an
> integer, then the other one needs to be converted to an integer as well. And
> since my intValue() method here returns 1, they are seen as equal, even
> though compareTo, equals and even the hashcodes would not allow that. If I
> reverse the order in my list:
>
>> def res = [new MyNumber(n:1),1] - [1]
>
>
> then the result will be as expected and contains only MyNumber(n:1). Funny
> thing here is... I added a compareTo method, but no Comparable interface. So
> MyNumber is not comparable... Does it changes things if it does? So I add
> "implements Comparable<MyNumber>" to the class and now I get the same
> result, regardless of the order. Which is []. That is because now 1 is
> always equal to MyNumber(n:1). That is because now in both case IntegerMath
> is used. Does this mean any two custom numbers are equal, if their intValue
> is? So let's take MyNumber again and make a second class just the same,
> including Comparable, then call it MyNumber2
>
>> assert new MyNumber2(n:1) == new MyNumber(n:1)
>> assert new MyNumber(n:1) == new MyNumber2(n:1)
>
>
> Well... if you did read, what I did write before, then this is no
> surprise... But frankly... should it be like this? And if MyNumber2 does not
> implement Comparable:
>
>> assert new MyNumber2(n:1) != new MyNumber(n:1)
>> assert new MyNumber(n:1) == new MyNumber2(n:1)
>
>
> again because of the fallback logic to IntegerMath... and if both do not
> implement it:
>
>> assert new MyNumber2(n:1) != new MyNumber(n:1)
>> assert new MyNumber(n:1) != new MyNumber2(n:1)
>
>
> Well... that is more the expected result, still... and not to forget:This is
> ==, not <=>. == uses <=> only for comparable cases. So:
>
>> new MyNumber2(n:1) <=> new MyNumber(n:1)
>> new MyNumber(n:1) <=> new MyNumber2(n:1)
>
>
> will both throw a GroovyRuntimeException, if non does implement Comparable.
> If MyNumber2 implements it, the first compare works using IntegerMath and
> tells us they are equal. If both implement it, they are both equal. That is
> basically the same as ==, but what does NumberAwareComperator do for such
> cases?
>
>> try {
>> return DefaultTypeTransformation.compareTo(o1, o2);
>> } catch (ClassCastException cce) {
>> /* ignore */
>> } catch (GroovyRuntimeException gre) {
>> /* ignore */
>> }
>> // since the object does not have a valid compareTo method
>> // we compare using the hashcodes. null cases are handled by
>> // DefaultTypeTransformation.compareTo
>> // This is not exactly a mathematical valid approach, since we
>> compare object
>> // that cannot be compared. To avoid strange side effects we do a
>> pseudo order
>> // using hashcodes, but without equality. Since then an x and y
>> with the same
>> // hashcodes will behave different depending on if we compare x
>> with y or
>> // x with y, the result might be unstable as well. Setting x and y
>> to equal
>> // may mean the removal of x or y in a sorting operation, which we
>> don't want.
>> int x1 = o1.hashCode();
>> int x2 = o2.hashCode();
>> if (x1 > x2) return 1;
>> return -1;
>
>
> compareTo is the path for <=>, so we can expect exceptions here. So now with
> MyNumber being a Comparable, and MyNumber2 not:
>
>> println ([new MyNumber(n:1), new MyNumber2(n:1)] - [new MyNumber2(n:1)])
>> println ([new MyNumber(n:1), new MyNumber2(n:1)] - [new MyNumber(n:1)])
>> println ([new MyNumber2(n:1), new MyNumber(n:1)] - [new MyNumber2(n:1)])
>> println ([new MyNumber2(n:1), new MyNumber(n:1)] - [new MyNumber(n:1)])
>
>
> In the first two cases nothing is removed, in the third case we get an empty
> list and in the last case MyNumber is removed.
> Since MyNumber2 does not implement Comparable here
> DefaultTypeTransformation.compareTo will throw an exception, whenever we
> have MyNumber2 as o1. The compare using hashcodes will never equal. Well.
> There has been one part of that minus method we have not looked at. This is
> called if the first element is not Comparable, even if all extend Number:
>
>> //n*n version
>> List<T> tmpAnswer = new LinkedList<T>(self);
>> for (Iterator<T> iter = tmpAnswer.iterator(); iter.hasNext();)
>> {
>> T element = iter.next();
>> boolean elementRemoved = false;
>> for (Iterator<?> iterator = removeMe.iterator();
>> iterator.hasNext() && !elementRemoved;) {
>> Object elt = iterator.next();
>> if (DefaultTypeTransformation.compareEqual(element,
>> elt)) {
>> iter.remove();
>> elementRemoved = true;
>> }
>> }
>> }
>>
>> //remove duplicates
>> //can't use treeset since the base classes are different
>> ansCollection.addAll(tmpAnswer);
>
>
> so if MyNumber2 is the head element this code will be executed instead,
> since MyNumber2 not implement Comparable.
> DefaultTypeTransformation.compareEqual is the code path taken for "==" which
> I talked about already. Remember, IntegerMath is the fallback for
> Numbers.compareEqual will prevent the exception being thrown, even though
> compareTo is called internally, but only if the left hand side is a
> Comparable. So here equality checks are done instead.. for example using the
> equals method. That explains why ([new MyNumber2(n:1), new MyNumber(n:1)] -
> [new MyNumber2(n:1)]) gets the empty list... first part is normaly equality,
> second part is fallback to IntegerMath. Of course if the code used
> DefaultTypeTransformation.compareEqual(elt, element), then this would behave
> different, but the result would be the same. The major difference would be
> that MyNumber2#equals is not called. For ([new MyNumber2(n:1), new
> MyNumber(n:1)] - [new MyNumber(n:1)]) we do compareEquals with MyNumber2 and
> MyNumber first, resulting in the element not being removed, so the result
> will be [MyNumber(n:1)]
>
> But that did not give me the exception path... Looking at the code, with
> numbers you won't get that path... or not? Well, with a subclass of
> BigDecimal/BigInteger you can do that. But they implement
> Comparable<BigDecimal>/Comparable<BigInteger>, so you are supposed to make a
> method for that only... supposed to is not equal to people actually doing
> that. Still I won't give an example of that now.
>
> If you look at the sameType method, then it looks only at Number and null
> and the exact same class. to enter the not so n*logn path and use the number
> comperator. Point being here, the hashcode compares will not normally happen
> for Numbers or null. And in case of all elements of both Collections being
> of the same class, there should be no exception we have the right to catch
> and fall back to hashcode logic. So we could question here if
> NumberAwareComperator should be even used like it is for this method.
>
> So let's have a much shorter look at the other methods...
>
> retainAll, intersect and disjoint: uses the comparator for all elements, so
> it may use the hashcode logic. But at least they should be stable.
> removeAll: same. Well, there is in theory the issue of self being a Set and
> the special Set logic. But in this case, this method is not supposed to be
> called.
>
>
> Actually, there are two more methods using the Comperator behind the
> scenes.... coercedEquals (used by several equals methods, minus and another
> old friend: unique) and numberAwareCompareTo (used by coerecedEquals and
> ObjectRange).
>
> So we would have to look at those as well... but this mail got pretty long
> already and I am out of time. So I put to discussion what I wrote about for
> now.
>
> bye blackdrag
>
> --
> Jochen "blackdrag" Theodorou
> blog: http://blackdragsview.blogspot.com/
>