Oddity with java.util.SortedMap

[Captain Koloth]

The return types for keySet and entrySet are just Set, rather than
SortedSet. This could have been changed when Java 5 began to allow
overrides/implementations with covariant return types. Does anybody
know why it wasn't?

 

[John B. Matthews]

The return types for keySet and entrySet are just Set, rather than
SortedSet. This could have been changed when Java 5 began to allow
overrides/implementations with covariant return types. Does anybody
know why it wasn't?

Perhaps I'm overlooking something, but shouldn't one prefer the
superinterface?

<code>
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
* @author John B. Matthews
*/
public class MapTest {

public static void main(String[] args) {
final Map<String, List<String>> map =
new HashMap<String, List<String>>();
List<String> list = new ArrayList<String>(
Arrays.asList("Alpha", "Beta", "Gamma"));
map.put("Ordinals", list);

list = new ArrayList<String>(
Arrays.asList("Aleph", "Beth", "Gimel"));
map.put("Cardinals", list);

list = new ArrayList<String>(
Arrays.asList("Alpher", "Bethe", "Gammow"));
map.put("Physicists", list);

list = new ArrayList<String>(
Arrays.asList("Actinomyces", "Bordetella", "Giardia"));
map.put("Pathogens", list);

printMap(map);
System.out.println();

final Map<String, List<String>> tm = new
TreeMap<String, List<String>>(map);
printMap(tm);
}

private static void printMap(Map<String, List<String>> map) {
for (Map.Entry entry : map.entrySet()) {
System.out.println(entry.getKey()
+ " " + entry.getValue());
}
}
}
</code>

<console>
Physicists [Alpher, Bethe, Gammow]
Ordinals [Alpha, Beta, Gamma]
Cardinals [Aleph, Beth, Gimel]
Pathogens [Actinomyces, Bordetella, Giardia]

Cardinals [Aleph, Beth, Gimel]
Ordinals [Alpha, Beta, Gamma]
Pathogens [Actinomyces, Bordetella, Giardia]
Physicists [Alpher, Bethe, Gammow]
</console>

 

[Captain Koloth]

Perhaps I'm overlooking something, but shouldn't one prefer the
superinterface?

That depends. If you want to use SortedMap or SortedSet features that
are not general Map or Set features, then you don't want to type your
references as plain Map or Set.

Generally, you want to use the least specific type that will do the
job.

Not the least specific type, period, or else you'd have all your
references be of type Object.

And if all your references ARE of type Object, your coworkers and the
future maintenance programmers that have to deal with your code will
call you a petaQ, and rightly so!

 

[John B. Matthews]

That depends. If you want to use SortedMap or SortedSet features that
are not general Map or Set features, then you don't want to type your
references as plain Map or Set.

TreeMap implements the SortedMap methods; TreeSet implements the
SortedSet methods. The two subinterfaces seem parallel. I don't
understand what benefit would accrue to mixing them.

Generally, you want to use the least specific type that will do the
job.

Agreed. It seems the authors have done that.

Not the least specific type, period, or else you'd have all your
references be of type Object. And if all your references ARE of type
Object, your coworkers and the future maintenance programmers that
have to deal with your code will call you a petaQ, and rightly so!

The word "Object" did not appear in my example, so perhaps I am safe.
How did you know my coworkers speak Klingon?

 

[Tom Anderson]

TreeMap implements the SortedMap methods; TreeSet implements the
SortedSet methods. The two subinterfaces seem parallel. I don't
understand what benefit would accrue to mixing them.

The point is that the key set of a SortedMap is sorted, so it could/should
be a SortedSet.

That said, i can't think of anything you could do with a SortedSet key set
that you can't do another way. If we have:

SortedMap<String, Object> map ;

Then:

map.keySet().first() ; // can't be done
map.firstKey() ; // can

map.keySet().headSet("Bolivia") ; // can't be done
map.headMap("Bolivia").keySet() ; // can

If you had some method that took a SortedSet, and you wanted to apply it
to the keys of a SortedMap, then you'd be stuffed, but that's the only
situation i can think of.

I would say it would be more elegant if the key set was a SortedSet,
though. It more completely describes the properties of the map.

tom

 

[Lew]

The return types for keySet and entrySet are just Set, rather than
SortedSet. This could have been changed when Java 5 began to allow
overrides/implementations with covariant return types. Does anybody
know why it wasn't?

It would have broken the contract established for earlier code.

SortedMap implementors are free to document that they return SortedSet for
those methods. The methods documented to return Set are free to return a
SortedSet should they choose, they just can't promise to do so in the return type.

It isn't nice to just go and change the definition of SortedMap's methods just
because now you can. Code has been developed in the field for a long time
with the old contract. Look at the grief caused from the few changes to old
contracts that Java 5 did make. Only when the need was great or the benefit
overwhelming did such changes occur.

This is an object lesson for API developers, comprising virtually all Java
coders. Once you commit an API to a contract, you're committed in perpetuity.
That's why things like implementing Serializable are such serious decisions,
and why one must prefer the widest appropriate declared type for variables and
method returns.

 

[Captain Koloth]

It would have broken the contract established for earlier code.

Nope. SortedSet extends Set, so any code that used the keySet or
entrySet from, say, a TreeMap would still work. Nowhere is there a
contract that what these return is *not sorted*, and I expect set
views of SortedMaps will in fact be sorted whatever the compile-time
type of the reference used to hold them.

One minor issue would be whether you would be allowed to change the
Comparator of the map through the returned set. But SortedSet only
specifies a method to retrieve the comparator, not to set it, so
that's moot unless the comparator is itself mutable in some way. I
expect a mutable comparator, with methods that change its sorting
behavior, breaks the Comparator contract anyway. Trees would have to
be completely rebuilt if the comparison changed, and comparators would
need to accept some kinds of Listeners, and all kinds of other chaos
would ensue if you wanted mutable comparators to work. If all the
classes assume comparators are immutable (at least with respect to
sort order semantics) already then this issue is indeed moot.

 

[Tom Anderson]

Nope.

Yup.

You're only thinking about the contract from the point of view of the
caller. But the contract also exists for the SortedMap implementer, and it
defines what he's allowed to do. If i wrote a SortedMap under 1.4 that
returned a key set that wasn't a SortedSet, which was perfectly legal at
that point, i would take a very dim view of a change to the definition of
SortedMap in 1.5 that made it illegal.

tom

 

[Captain Koloth]

Nope.

You're only thinking about the contract from the point of view of the
caller.

That IS the contract.

But the contract also exists for the SortedMap implementer, and it
defines what he's allowed to do. If i wrote a SortedMap under 1.4 that
returned a key set that wasn't a SortedSet, which was perfectly legal at
that point, i would take a very dim view of a change to the definition of
SortedMap in 1.5 that made it illegal.

Why? It would be very easy to update it, since the backing Map is
sorted. You'd just need to implement first, last, subSet, tailSet, and
headSet, and you could make all of those (in presumably an anonymous
inner class of your map) punt to MySortedMap.this.firstKey(), lastKey
(), subMap(x,y).keySet(), tailMap(x).keySet(), and headMap(y).keySet
().

It would take all of five minutes.

Also, how common are third-party implementations of SortedMap, really?

 

[Lew]

On Nov 29, 2:21 pm,

Nope.

That IS the contract.

Only half of it. People who write code are just as important as those who use it.

Why? It would be very easy to update it, since the backing Map is

But you thus show that you realize that there would be a need for change if
the contract changed. And you don't know how easy it would be to update it,
since the implementation to change will itself be used by other code, which
then will need to change, thus requiring unit tests, regression tests,
deployment to a zillion production sites, possible new bugs to fix, delays to
other more critical feature improvements or repair, and a whole lot of cost to
Java projects overall. That would be egregiously irresponsible of Sun absent
a compelling reason. Look how long the adoption of Java 5 is taking with its
compelling changes - many, many projects have yet to upgrade and it's already
in End-of-Life. You can't just go imposing costs on your customers willy-nilly.

sorted. You'd just need to implement first, last, subSet, tailSet, and
headSet, and you could make all of those (in presumably an anonymous
inner class of your map) punt to MySortedMap.this.firstKey(), lastKey
(), subMap(x,y).keySet(), tailMap(x).keySet(), and headMap(y).keySet
().

It would take all of five minutes.

Not so.

Also, how common are third-party implementations of SortedMap, really?

At the time the contract was written, there weren't any. Having written the
contract, Java must not assume that continues to pertain. There could be
thousands of such implementations by now.

 

[Tom Anderson]

Yup.


That IS the contract.

What? No. That's not even a meaningful thing to say. A contract binds two
parties, thus you can think about it from two sides.

Why? It would be very easy to update it,

Perhaps. But you would have to update it - changing the definition of
SortedMap in this way would break existing correct code. That's not
something an API designer can do without a very, very good reason.

tom

 

[Arne Vajhøj]

That IS the contract.
No.


Why? It would be very easy to update it, since the backing Map is
sorted.

"change breaking contract" means "other code need to be changed
due to this change"

So "very easy to update" means the contract is broken.

It would take all of five minutes.

That is for hobby programming projects.

Elsewhere you don't make changes in 5 minutes and then
that is it.

Also, how common are third-party implementations of SortedMap, really?

I am sure a few exists.

Jakarta Collections is one example.

Arne

 

[Mike Schilling]

What? No. That's not even a meaningful thing to say. A contract
binds
two parties, thus you can think about it from two sides.


Perhaps. But you would have to update it - changing the definition
of
SortedMap in this way would break existing correct code. That's not
something an API designer can do without a very, very good reason.

And that's leaving out the case where "you" don't have the source code
to change, just a 3rd-party jar which now throws Errors (not even
Exceptions) when the "missing" methods are called.

 

[Lew]

How did you know my coworkers speak Klingon?

Huh, I thought that meant 10^15 Q, which would confer an awful lot of
godlike powers in Star Trek terms, or very, very narrow frequency
discrimination in radio terms.

 

[John B. Matthews]

Huh, I thought that meant 10^15 Q, which would confer an awful lot of
godlike powers in Star Trek terms, or very, very narrow frequency
discrimination in radio terms.

Interesting. Or perhaps a very high power Q-switched laser, which
intrigues the Klingons immensely. I had though briefly of pulmonary
perfusion (dQ/dt), but relativistic effects preclude rates in this
range.

 

[Captain Koloth]

Only half of it.

Nearly all of it, given it's rarely custom-subclasses.

 People who write code are just as important as those who use it.

That does not make sense. Both clients and subclassers are "people who
write code".

But you thus show that you realize that there would be a need for change if
the contract changed.

Qagh Sopbe'. Entirely beside the point, given how little change.

 And you don't know how easy it would be to update it,
since the implementation to change will itself be used by other code, which
then will need to change

QoH! It won't, since changing the implementation keySet return type to
SortedSet won't force change on clients of that code, and it's
unlikely for the implementation to be itself subclassed, and even more
unlikely for such a subclass to be overriding the superclass
implementation of keySet.

thus requiring unit tests, regression tests,
deployment to a zillion production sites, possible new bugs to fix, delays to
other more critical feature improvements or repair, and a whole lot of cost to
Java projects overall.

Tojo'Qa'! What a ridiculous slippery slope argument.

sorted. You'd just need to implement first, last, subSet, tailSet, and
headSet, and you could make all of those (in presumably an anonymous
inner class of your map) punt to MySortedMap.this.firstKey(), lastKey
(), subMap(x,y).keySet(), tailMap(x).keySet(), and headMap(y).keySet
().

It would take all of five minutes.

[calls me a liar]

Grrr! TlhIngan quv DatIchDI' Seng yIghuH!

If anyone here is a lying petaQ ... well, let's just say that it is
not I!

At the time the contract was written, there weren't any.  Having written the
contract, Java must not assume that continues to pertain.  There could be
thousands of such implementations by now.

VeQ! There are probably only a handful, if that.

 

[Captain Koloth]

Yup.

No. You dare to call me a liar, petaQ?

What? No.
Yes.

That's not even a meaningful thing to say.

It is more meaningful than anything you've said by far, yIntagh.

A contract binds two parties, thus you can think about it from two sides.

But we only need to worry about the side on the receiving end of the
changes. We can assume the side that WANTS the change is fine with it.

Perhaps. But you would have to update it - changing the definition of
SortedMap in this way would break existing correct code.

Very little of it, and in ways that would take all of five minutes to
fix.

 

[Captain Koloth]

No.

You dare to accuse me in public of lying, petaQ?

QoH! TlhIngan quv DatIchDI' Seng yIghuH!

other code need to be changed due to this change

What a tu'HomIraH remark! It only restates what was already said,
while sounding like it comes from a yIntagh with a fractured skull!

So "very easy to update" means

"no biggie", qoH!

That is for hobby programming projects.

Elsewhere you don't make changes in 5 minutes and then
that is it.

You certainly can if you're just adding firstKey, lastKey, tailSet,
headSet, and subSet to a Set on which you aren't currently even
calling those methods.

I am sure a few exists.

A few. And how many already return a SortedSet, just without the
return type being declared as such? Those can be subtracted. The only
change they need is to change the return type! A one minute change!

 

[Captain Koloth]

Nope, and only a yIntagh repeats the dishonorable insults of a taHqeq
towards a Klingon!

The side that wants the change, and the side that would have to deal
with the change. I think we can safely concern ourselves with only the
latter.

And that's leaving out the case where "you" don't have the source code
to change, just a 3rd-party jar which now throws Errors (not even
Exceptions) when the "missing" methods are called.

How common is this with SortedMap implementations? The only one I know
of would probably be updated very soon. And only a qoH would update
one before updating the other.

 

[Lew]

Nearly all of it, given it's rarely custom-subclasses.

Evidence of rarity? Java took the prudent approach, given the known
existence of subclasses and the presumption, since the API is there to
be used, that it might have been.

That does not make sense. Both clients and subclassers are "people who
write code".

It makes sense, as your statement evidences. For clarity s/code/the
API/ in my assertion.

Tom Anderson said, and Captain Koloth forgot to attribute to him:

Qagh Sopbe'. Entirely beside the point, given how little change.

I have already shown how it isn't necessarily a "little change".

You should do something about that phlegm. Why are you spouting
random nonsense amidst your comments?

QoH!

WTF?

What is this stupid nonsense?

It won't, since changing the implementation keySet return type to
SortedSet won't force change on clients of that code, and it's
unlikely for the implementation to be itself subclassed, and even more

You have completely disregarded the points made before, that there are
already known subclasses in wide use, thus it's not only likely but
certain to have been subclassed. You have made a statistical
assertion with absolutely no basis. Where are your facts?

unlikely for such a subclass to be overriding the superclass
implementation of keySet.

Evidence oh-so-conveniently omitted.

Tojo'Qa'! What a ridiculous slippery slope argument.

You've never worked on a large-scale project, have you?

It's *the* argument, as practiced in real life by real projects. The
slippery slope is the one you espouse, to make people change without
regard for their costs. I know from the jobs on which I work that
these are real concerns, as voiced by the software architects and
project managers, that affect how real budgets are spent, and real
work planned. Far from being "ridiculous", it's founded on real-world
experience, unlike what you've been saying. And speak English, not
gobbledygook.


Lew did not write:

[calls me a liar]

I didn't call you a liar, just wrong, Paul.

Grrr! TlhIngan quv DatIchDI' Seng yIghuH!

More nonsense. What is wrong with you?

If anyone here is a lying petaQ ... well, let's just say that it is
not I!

Not a liar, just mistaken.

Paul averred:

VeQ! There are probably only a handful, if that.

"Probably"? "Only a handful"? The one example already cited is in
wide use. How do you know how many implementations there are? Where
is your hard evidence?

Java's authors cannot make such assumptions.