problem with TreeMap - element removal fails.

[tomek milewski]

Hello,
I can't solve some problem. I'm looking for mistake in my thinking or
any walkaround.

There is some sample code:

import java.util.TreeMap;
class A {
public A() {
}
public static final void main(String[] args) {
A a = new A();
TreeMap<A, Integer> map = new TreeMap<A, Integer>();
map.put(a, new Integer(1));
map.remove(a);
}
}

Executing last line of this code throws ClassCastException. Why element
can be putted into this TreeMap and can't be removed? I've been trying
some solutions but none has worked .

Thank You for any answer.

 

[Ingo R. Homann]

Hi,

import java.util.TreeMap;
class A {
public A() {
}
public static final void main(String[] args) {
A a = new A();
TreeMap<A, Integer> map = new TreeMap<A, Integer>();
map.put(a, new Integer(1));
map.remove(a);
}
}

Executing last line of this code throws ClassCastException.

Well, to make the TreeMap work correctly, it is necessary that the keys
implement Comparable. So it is obvious that your code cannot work.

Having said this, I must admit that at first I was a bit suprised that
TreeMap is defined as "TreeMap<K,V>" and not as "TreeMap<K extends
Comparable,V>". Then, you would get a compiler error instead of a
runtime error, which would be better. But I guess this is a
generics-problem: For a Map, it is generally not necessary that the key
implements Comparable (e.g. for a HashMap it is not necessary). So,
because a TreeMap should be assignable to a Map, it cannot be defined
different.

Having said this (and thinking more about it), I think it would be good
if the runtime error would be thrown in the constructor (fail early)!

Ciao,
Ingo

 

[Piotr Kobzda]

Well, to make the TreeMap work correctly, it is necessary that the keys
implement Comparable. So it is obvious that your code cannot work.

Keys of TreeMap don't have to implement Comparable when you provide a
keys Comparator to the map's constructor.

That is true reason of why:

TreeMap is defined as "TreeMap<K,V>" and not as "TreeMap<K extends
Comparable,V>".

Having said this (and thinking more about it), I think it would be good
if the runtime error would be thrown in the constructor (fail early)!

Impossible. TreeMap constructors have no knowledge on its generic
parameters types neither its future elements types.


piotr

 

[Chris Uppal]

import java.util.TreeMap;
class A {
public A() {
}
public static final void main(String[] args) {
A a = new A();
TreeMap<A, Integer> map = new TreeMap<A, Integer>();
map.put(a, new Integer(1));
map.remove(a);
}
}

Executing last line of this code throws ClassCastException. Why element
can be putted into this TreeMap and can't be removed?

It's because your class A does not implement the Comparable interface. If you
don't provide an explicit Comparator (as the parameter to the TreeMap's
constructor) then the TreeMap will attempt to use its keys' "natural ordering",
as defined by their own compareTo() methods. Since you don't provide that
method (and don't implement the corresponding interface), it fails at runtime.

Arguably it should fail when the first entry is added, rather than when it
first needs to compare two entries -- that would have been less confusing in
this case. (Also a ClassCastException would be more use if its toString()
mentioned what the failed target class/interface was.)

The new Java generics type system is not powerful enough to express the fact
that the key type must implement Comparable /unless/ an explicit comparator is
provided[*], which is why the compiler doesn't prevent you from making this
mistake.

-- chris

([*] At least, I don't think it's powerful enough. Maybe some horror of
twisted generic declarations could be concocted which had that effect -- if it
is possible then we're fortunate that Sun didn't inflict it on us ;-)

 

[Ingo R. Homann]

Hi,

Keys of TreeMap don't have to implement Comparable when you provide a
keys Comparator to the map's constructor.

OK, yes, that's another possibility.

Impossible. TreeMap constructors have no knowledge on its generic
parameters types neither its future elements types.

There is a workaround for this (which I do not like):

class Foo<T> {
public Foo(Class<T> c) {
// check c by reflection
}
}

All this would of course not be necessary if generics were not
implemented by type erasure...

Ciao,
Ingo