• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Tim Cooke
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Frank Carver
  • Henry Wong
  • Ron McLeod
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Himai Minh

Is TreeMap Broken?

 
author
Posts: 4323
39
jQuery Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Maybe I'm going crazy but I'm trying to work with a TreeMap that consistently throws a ClassCastException on elements that were actually placed in the map. I've vastly simplified what I'm doing so that you can all reproduce it:



which leads to error:



Any ideas why this fails?
[ October 12, 2006: Message edited by: Scott Selikoff ]
 
Ranch Hand
Posts: 2412
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I believe that the TreeMap, like TreeSet, requires that the elements be Comparable. In the case of the map, that would be the keys.

This is from the API for the no-argument constructor of TreeMap.

Constructs a new, empty map, sorted according to the keys' natural order. All keys inserted into the map must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any elements k1 and k2 in the map. If the user attempts to put a key into the map that violates this constraint (for example, the user attempts to put a string key into a map whose keys are integers), the put(Object key, Object value) call will throw a ClassCastException.
[ October 12, 2006: Message edited by: Keith Lynn ]
 
Scott Selikoff
author
Posts: 4323
39
jQuery Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So java sets don't implement comparable? I would think they would be easily comparable in some sense.
 
author and iconoclast
Posts: 24204
44
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Keith's got it, of course. I'll add that (1) this requirement is dropped if you supply a Comparator to the TreeMap's constructor, and (2) HashSets (or any other collection) make lousy keys, because their notion of identity will change as items are added and removed; the TreeMap ordering will quickly become corrupted if the Sets are changed during their tenure as keys.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[Scott]: So java sets don't implement comparable? I would think they would be easily comparable in some sense.

Like what? Consider sets of integers for example. How should [1,4] compare to [2,3]? There are various ways that one could implement this, but none strike me as "natural". So I think it's best to require the user to explicitly supply a Comparator if they want to do something like this. I don't see a sensible default here.

[EFH]: (2) HashSets (or any other collection) make lousy keys, because their notion of identity will change as items are added and removed;

Meh. I'd say that mutable objects in general make lousy keys. But they work fine if and only if you don't actually mutate them after they've been added to the Map. Which is what people normally do, but it would be nice if there were more reliable ways to guarantee this. The problem isn't Collections; it's mutaable objects. At least with collections you can use Collections.unmodifiableXXX() to make a... less mutable version. (I.e. an immutable version if the elements are immutable; otherwise, well, a less mutable version.)
 
Scott Selikoff
author
Posts: 4323
39
jQuery Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ack, I think I'll need to extend the collections classes to make it do what I want...
[ October 12, 2006: Message edited by: Scott Selikoff ]
 
Scott Selikoff
author
Posts: 4323
39
jQuery Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
About using sets as keys... I'm not sure of a better way to do it. The set does not change after its been added to the map. I'm managing sets of sets, and given a new set X, I need to determine if I've seen this set before, and if so, to retrieve the object associated with it.
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[Scott]: The set does not change after its been added to the map.

As long as that's true (and the elements in the set don't change either), you're fine.
 
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Scott Selikoff:
Ack, I think I'll need to extend the collections classes to make it do what I want...



No - as Ernest and Jim indicated, you just need to write a Comparator for your HashSets and feed it to the TreeMap.

But from your description of what you need to do, I'm wondering why you aren't using a HashMap, which wouldn't create those problems in the first place...
 
Been there. Done that. Went back for more. But this time, I took this tiny ad with me:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic