Sort Map on Value

[Wojtek]

Lew wrote :

This idiom puzzles me. Why call 'super()' explicitly? Particularly since
the class extends 'Object'?

Coding fluff. I know that super() is called implicitly, however I
always put it in.

Is this consistent with 'equals()'?

No, it is consistent with compareTo() as per the interface.

 

[Lew]

No, it is consistent with compareTo() as per the interface.

There is more than one interface involved, here. You need to be
specific.

I asked because the 'SortedMap' and 'TreeMap' documentation is very
strident about keeping 'compareTo()' and 'equals()' consistent with
each other, or else the map "just fails to obey the general contract
of the Map interface."

 

[Wojtek]

Lew wrote :

There is more than one interface involved, here. You need to be
specific.

Well the compareTo() is from the interface, the hashCode() and equals()
are overriding Object methods.

I asked because the 'SortedMap' and 'TreeMap' documentation is very
strident about keeping 'compareTo()' and 'equals()' consistent with
each other, or else the map "just fails to obey the general contract
of the Map interface."

I did not post all the comments I have placed into this class.

I know I am breaking some rules to force sorting on the Value, yet
lookup on the key. BTW, the tests I have done show that this works.

The code sample of a hash map I saw uses hashCode() and equals() to
place and retrieve objects with no mention of compareTo(). And even if
the equals() uses a compareTo() internally, that would be against the
key:

@Override
public boolean equals( Object key )
{
return ivKey.equals( ((PersonMapKey) key).getKey() );
}

 

[Lew]

Well the compareTo() is from the interface, the hashCode() and equals()
are overriding Object methods.

You keep saying "the" interface as if only one were involved.

I know I am breaking some rules to force sorting on the Value, yet
lookup on the key. BTW, the tests I have done show that this works.

I figured you had tested it, nevertheless the warnings in the
documentation for 'SortedMap' and its implementations raise a concern
that there may be corner cases that your approach would break in those
types.

The code sample of a hash map I saw uses hashCode() and equals() to

This isn't about HashMap but TreeMap. Map and HashMap Javadocs don't
discuss keeping 'compareTo' consistent with 'equals'.

place and retrieve objects with no mention of compareTo(). And even if

The documentation for 'SortedMap' and 'TreeMap' very distinctly warns
that the implementations use 'compare' and 'compareTo' instead of
'equals', and very strongly advise that one keep the methods
consistent.

the equals() uses a compareTo() internally, that would be against the
key:

That does not pertain to what I'm saying. I'm discussing the use of
'compareTo' instead of 'equals', not by 'equals'.

  @Override
  public boolean equals( Object key )
  {
    return ivKey.equals( ((PersonMapKey) key).getKey() );
  }

That's all well and good, but your 'equals' is not consistent with
your implementation of 'compareTo', and therefore could raise trouble
for SortedMap implementations, according to the Javadocs.

That said, the documentation also says that a SortedMap can work this
way, just that you are breaking aspects of the Map contract.
Unfortunately they give no indication of exactly what sort of bugs you
might expect from this.

I would not be comfortable with the hack that you suggest.

 

[Wojtek]

Lew wrote :

I would not be comfortable with the hack that you suggest.

So I guess I am back to value+key (name+pKey) as the key.

Well, it was an interesting excercise...

 

[Daniel Pitts]

Lew wrote :

So I guess I am back to value+key (name+pKey) as the key.

Well, it was an interesting excercise...

But then how will you look up a Person by pKey?
What you might want instead is:
SortedSet<Person> sortedPersons;
Map<PersonKey, Person> persons;

Generally, you can think of a List or Set as "rows in a Database" (with
or without implicit ordering respectively), where as a Map is an "Index
on a column in the Database". This is very loosely speaking of course,
but it helps.

If you want to look up by value, use a Map, if you want to order a
specific way, use a SortedSet or a List+Collections.sort()

 

[Wojtek]

Daniel Pitts wrote :

But then how will you look up a Person by pKey?

If you look at the OP, the method which get/put the Person object has
both values in the parameters, and is the only place where these
operations take place. So both values are available.

Normally I would just use the name of the person as the key for
sorting, but the name COULD repeat, so I will concatinate it with a
value that never repeats.

I had thought of the vakue+key, but I was wondering if there was a
better way. Lew convinced me that there is not. At least not without
creating all sorts (ha! a pun) of extra objects to handle the issue.

 

[Tom Anderson]

Lew wrote :

Well the compareTo() is from the interface, the hashCode() and equals() are
overriding Object methods.

From java.lang.Comparable:

The natural ordering for a class C is said to be consistent with equals
if and only if e1.compareTo(e2) == 0 has the same boolean value as
e1.equals(e2) for every e1 and e2 of class C.

If you have John Smith 1 and John Smith 2, then equals will say no, but
compareTo will say yes, the above invariant will be false, and Doug Lea
will be very, very cross with you. Furious.

tom

 

[Wojtek]

Tom Anderson wrote :

Doug Lea will be very, very cross with you. Furious.

Well that settles that then...

 

[Wojtek]

Lew wrote :

The documentation for 'SortedMap' and 'TreeMap' very distinctly warns
that the implementations use 'compare' and 'compareTo' instead of
'equals', and very strongly advise that one keep the methods
consistent.


That does not pertain to what I'm saying. I'm discussing the use of
'compareTo' instead of 'equals', not by 'equals'.


That's all well and good, but your 'equals' is not consistent with
your implementation of 'compareTo', and therefore could raise trouble
for SortedMap implementations, according to the Javadocs.

Ok, so why is it that the interface Comparable does not also have

public boolean equals(Object o);

as part of its definition?

If you do something different inside compareTo(), then that difference
should be reflected in equals() should it not?

 

[Daniel Pitts]

Lew wrote :

Ok, so why is it that the interface Comparable does not also have

public boolean equals(Object o);

as part of its definition?

If you do something different inside compareTo(), then that difference
should be reflected in equals() should it not?

It would be nice, but it is not required.

 

[Lew]

Lew wrote :

Ok, so why is it that the interface Comparable does not also have

public boolean equals(Object o);

as part of its definition?

I don't know. I have not asked the Java library writers that
question, and if I did, it's possible they might not answer me.

If you do something different inside compareTo(), then that difference
should be reflected in equals() should it not?

Yes. So make sure that it is. The Jzvadocs for Comparable are quite
clear on that point, don't you agree?
<http://java.sun.com/javase/6/docs/api/java/lang/Comparable.html>

 

[Wojtek]

Lew wrote :

Lew wrote :



I don't know. I have not asked the Java library writers that
question, and if I did, it's possible they might not answer me.


Yes. So make sure that it is. The Jzvadocs for Comparable are quite
clear on that point, don't you agree?
<http://java.sun.com/javase/6/docs/api/java/lang/Comparable.html>

Yes.

But it would be more obvious if Comparable required equals().

One tends to get lazy and only implement the methods which are required
rather than implied. The Jzvadocs strongly suggest that equals be
equivalent to compareTo==0, but that would be driven home if equals was
required.

It is just a picky point...

 

[Lew]

One tends to get lazy and only implement the methods which are required
rather than implied. The Jzvadocs strongly suggest that equals be
equivalent to compareTo==0, but that would be driven home if equals was
required.

As Eric Sosman so ably pointed out, having 'equals()' in the interface would
do absolutely nothing to guarantee that the methods were consistent. All that
having the method in the interface does is guarantee that it's implemented,
not that it's consistent, and that condition would be trivially met even if
'equals()' were not overridden in a 'Comparable' implementation.

I'm sorry to break this to you, but we as programmers are simply stuck with
having to show good sense in this matter. Follow the Javadocs. The Javadocs
give us the information we need to avoid trouble. Thank goodness for the
Javadocs. I guess we just have to do as the Javadocs suggest and make sure
that 'Comparable#compareTo()' is consistent with 'equals()', or be willing to
accept the consequences if we don't.

Ain't responsibility a bitch?

 

[Wojtek]

Lew wrote :

As Eric Sosman so ably pointed out, having 'equals()' in the interface would
do absolutely nothing to guarantee that the methods were consistent. All
that having the method in the interface does is guarantee that it's
implemented, not that it's consistent, and that condition would be trivially
met even if 'equals()' were not overridden in a 'Comparable' implementation.

Which goes for ANY method which is overriden or implemented. There is
an implied contract between the writer of the classes and the
programmer who implements the methods. That is what the Javadocs are
for, to explain what the method is supposed to do and return.

But having "hidden" requirements makes things harder. If I create an
interface for one of my classes, but do not include a method in the
interface which is supposed to return a fairly important value, I can
hardly complain that someone did not extend/implement that method.

This is one of the reasons we do have methods in Interfaces, to ensure
that someone will implement it, and by contract, implement it with the
desired actions.

If a class/interface needs both compareTo and equals to return
equivalent results for proper operation, then that class/interface
should _require_ it by using both in its defnintion.

And speaking of Javadocs, the compareTo method has the following gem:

"It is strongly recommended, but not strictly required that
(x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class
that implements the Comparable interface and violates this condition
should clearly indicate this fact. The recommended language is "Note:
this class has a natural ordering that is inconsistent with equals.""

So, while interesting, this discussion is beside the point. My original
thought and the class I posted will work. Some future maintainer will
just have to read my Javadocs.

)

I'm sorry to break this to you, but we as programmers are simply stuck with
having to show good sense in this matter. Follow the Javadocs. The Javadocs
give us the information we need to avoid trouble. Thank goodness for the
Javadocs. I guess we just have to do as the Javadocs suggest and make sure
that 'Comparable#compareTo()' is consistent with 'equals()', or be willing to
accept the consequences if we don't.

Ain't responsibility a bitch?

Now you are just getting snarky. Like you I have been doing this for
over 30 years in more languages than I can remember. I realize the
importance of reading docs and so on.

But in the midst of a coding haze I do not always break off to read
docs. The assumption is that the name of the class/method/parameters
makes sense, and all the requirements are exposed at the code level.

AFAIK this is the first time that I have been bitten by this
assumption.

 

[Wojtek]

Eric Sosman wrote :

[...]
This is one of the reasons we do have methods in Interfaces, to ensure that
someone will implement it, and by contract, implement it with the desired
actions.

An interface cannot guarantee that an implementing class provides
a method; it can only guarantee that an implementing class *has* a
method, either implemented directly or inherited from a superclass.
(Or, I guess, "upherited" from concrete subclasses to an abstract
superclass.) The method in question is equals(), which every class can
inherit if it wants, so adding equals() to an interface doesn't "ensure"
anything at all.

If a class/interface needs both compareTo and equals to return equivalent
results for proper operation, then that class/interface should _require_ it
by using both in its defnintion.

Right, but there's no way to express the requirement in Java,
so the Java compiler cannot enforce the requirement or even warn about
possible breaches. You need to rely on programmer-to-programmer
communication channels, Javadoc among them.

And speaking of Javadocs, the compareTo method has the following gem:

"It is strongly recommended, but not strictly required that
(x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that
implements the Comparable interface and violates this condition should
clearly indicate this fact. The recommended language is "Note: this class
has a natural ordering that is inconsistent with equals.""

Not sure why you term this a "gem." It's just a straightforward
statement of purpose, one of those programmer-to-programmer messages
mentioned earlier. If you intend "gem" as sarcasm, I'm unable to see
what you're being sarcastic about.

Just tired I quess. Further reading supports the two being equivalent
as a requirement for Map regardless of the above, um, gem.

Insofar as feasible, yes. If you can think of a way to write code
that expresses requirements like

- x.equals(y) implies x.hashCode() == y.hashCode()

- x.equals(y) == (x.compareTo(y) == 0)

- Only the EDT can call this method

- This method must return "promptly" less the GUI freeze up

- Classes implementing this interface must provide their very
own versions of equals(), not something inherited

... then that's great, and an Excellent Good Thing. You'll have enabled
the compiler and tools to ferret out bugs sooner, before they do damage
and run up costs.

But the expressive power of programming languages, including Java,
is rather limited. They're good at expressing some things with great
precision, but completely helpless outside their carefully-circumscribed
scopes. There is no way (as far as I can tell) that Java can express
any of the requirements shown above, so if they're to be expressed at
all they must be expressed in some non-Java medium.

Code is only slightly self-documenting.

You are right of course. I rely on my experience and intuition and bang
away at the keyboard. Sometimes I make mistakes. Sometimes I run into
ambiguous problems, and then I come here. Javadocs are good, but they
need to be tempered with real world examples.

I did some programming in PHP and the online manual has a comments
section for each function. So not only do you get to read the
function's official documentation, you also get the comments for that
function, which almost always include examples.

Sort of a collaborative cookbook.

 

[Wojtek]

Eric Sosman wrote :

That's all well and good, but your 'equals' is not consistent with
your implementation of 'compareTo', and therefore could raise trouble
for SortedMap implementations, according to the Javadocs.

And this is where my confusion comes from.

Comparable does not NEED to have equals and compareTo==0 equivalent.

However SortedMap does and is quite specific about it:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/SortedMap.html

So the keys which SortedMap uses must implement Comparable and have
equals and compareTo==0 equivalency

 

[Daniel Pitts]

Eric Sosman wrote :

And this is where my confusion comes from.

Comparable does not NEED to have equals and compareTo==0 equivalent.

However SortedMap does and is quite specific about it:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/SortedMap.html

So the keys which SortedMap uses must implement Comparable and have
equals and compareTo==0 equivalency

If and only if you need it to be consistant with the Map guarantee that
key.equals(otherKey) implies map.get(key) == map.get(otherKey)

You are free to violate that for SortedMap if it makes sense in your
circumstances.

 

[Wojtek]

Daniel Pitts wrote :

If and only if you need it to be consistant with the Map guarantee that
key.equals(otherKey) implies map.get(key) == map.get(otherKey)

You are free to violate that for SortedMap if it makes sense in your
circumstances.

Yes, if I implement a custom Comparator. Thought about it...

 

[Eric Sosman]

Eric Sosman wrote :

No, I did not. Lew wrote. Please be more careful with
your attributions, Patricia.