• Post Reply Bookmark Topic Watch Topic
  • New Topic

sorting a TreeMap  RSS feed

 
Donald Wynn
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I want to sort a TreeMap on the fly how can I do that without doing something like this...

TreeMap locUldCnts =
new TreeMap(new LocUldCntComparator());
 
Mark Herschberg
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Um, what exactly do you want to do?
As you add elements to the TreeSet they get placed into the tree in their sorted order. Or you can add a collection at once (but they effectively get added one at a time).
What you wrote just creates an empty collection and gives it a compartor; but there are no elements in the collection.
--Mark
 
Peter den Haan
author
Ranch Hand
Posts: 3252
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can't sort a TreeMap on the fly; once its sorting order is set, you cannot change it. You can do one of two things: (1) what you were doing in the first place: create a new TreeMapwith a different sorting order, and putAll() entries from the old Map; (2) use HashMap and keep a separate List with your keys. This List can be re-sorted at any time using Collections.sort(). Of course you will have to write more code to glue List and Map together.
- Peter
 
Donald Wynn
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Peter--
The only way for me to change the sorting order is create a new Hashtable and put all the elements from my TreeMap into it....Whats the most efficient way to do this...
 
Mark Herschberg
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Peter den Haan:
You can't sort a TreeMap on the fly; once its sorting order is set, you cannot change it.

Is that necessarily true? What if you never gave TreeSet a comparator, but instead relied on the objects to implement Comparable. The objects did so by holding a reference to another class which does the actual comparison calculation. Then if you switched the class which does the calculation, you've effectively switched comparators.... or does the TreeSet effectively cache the compare method?
To use Peter's suggestion, you put everything into a HashMap at the start. When you need to create a sorted order for them you put the keys into a some type of collection (e.g. ArrayList). When you need to change the ordering, you simply call Collections.sort() and pass it the last, as well as the comparator you want to use to sort.
--Mark
[ March 06, 2003: Message edited by: Mark Herschberg ]
 
Donald Wynn
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So could I pass a parm to a comparator and let the comparator sort based on the passed parm
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can't sort a TreeMap on the fly; once its sorting order is set, you cannot change it.

Is that necessarily true? What if you never gave TreeSet a comparator, but instead relied on the objects to implement Comparable. The objects did so by holding a reference to another class which does the actual comparison calculation. Then if you switched the class which does the calculation, you've effectively switched comparators.... or does the TreeSet effectively cache the compare method?

The TreeMap has already put its contents in a tree structure representing the original sorting order, and has no reason to change it. There's no ComparatorChangeListener registered, because the designers of the collections framework saw no use for such a thing. A Comparator's behavior is assumed to be consistent; if it's not, no guarantees are made as to the validity of the sort. I expect the TreeMap will just ignore the Comparator until the next time someone adds an element - at which point it will try to use the Comparator to place the new object (without trying to re-sort the existing stuff). Which will probably give very strange results.
 
Mark Herschberg
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Donald Wynn:
So could I pass a parm to a comparator and let the comparator sort based on the passed parm

Yes, but I wouldn't recommend it, as this behavior isn;t technically specified, as Jim noted.

Originally posted by Jim Yingst:
The TreeMap has already put its contents in a tree structure representing the original sorting order, and has no reason to change it. There's no ComparatorChangeListener registered, because the designers of the collections framework saw no use for such a thing. A Comparator's behavior is assumed to be consistent; if it's not, no guarantees are made as to the validity of the sort. I expect the TreeMap will just ignore the Comparator until the next time someone adds an element - at which point it will try to use the Comparator to place the new object (without trying to re-sort the existing stuff). Which will probably give very strange results.

I agree that there is no listener, so it will not resort immediately (which is good, because unless you can magically make the change for all elements at once, you'll have it do N sorts as you change each of N elements). However, the next time the sort method is invoked, it probably will sort using the new alorithm. I see no reason why it wouldn't work.
Still, I wouldn't trust this without testing it, and even then, I would still probably prefer to either create a new TreeSet, or simply call Collections.sort() on a list of keys.
--Mark
 
Donald Wynn
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can I build my collection first and then choose a sort order?? How would I do it if possible?
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I agree that there is no listener, so it will not resort immediately (which is good, because unless you can magically make the change for all elements at once, you'll have it do N sorts as you change each of N elements). However, the next time the sort method is invoked, it probably will sort using the new alorithm. I see no reason why it wouldn't work.
Well, a TreeMap doesn't have a sort() method. The only way it knows to sort is by keeping things sorted as they're added.
or simply call Collections.sort() on a list of keys.
like Collections.sort(map.getKeySet())? Doesn't compile, as the key set is a Set not a List. You can copy all the keys/values/entries into a separate List of some sort, and then sort it any way you want to - but these changes no longer have any effect on the TreeSet.
Can I build my collection first and then choose a sort order?? How would I do it if possible?
Yes, probably. But before I answer that - do you want a Map, or a List? That is, when you sort and re-sort everything, will you be sorting based on the keys, or the values? If you're still paying attention to the keys, then I'd probably create a new TreeMap using the new Comparator that sorts keys however you like. But if you're sorting based on the values rather than keys, you might as well forget about the key and the Map entirely. (Or maybe just keep a separate HashMap of the original mappings, but this has nothing to do with how you sort the list of values.)
 
Mark Herschberg
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Jim Yingst:
[QB]Well, a TreeMap doesn't have a sort() method. The only way it knows to sort is by keeping things sorted as they're added.
True, I guess you'd have to add/remove lg(N) unique elements, of the right values to traverse every branch of the tree to insure that all elements get resorted.

--Mark
 
Peter den Haan
author
Ranch Hand
Posts: 3252
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Mark Herschberg:
I agree that there is no listener, so it will not resort immediately [...] However, the next time the sort method is invoked, it probably will sort using the new alorithm. I see no reason why it wouldn't work.
It won't work because trees won't work that way. They are never ever sorted as a whole. That would be rather less than desirable as it would give O(N log N) performance on insertions or deletions.
Rather, when an element is inserted or deleted, the TreeMap performs a number of transformations which basically can affect all nodes between the modified node and the root node, and their neighbouring nodes. Since the depth of the tree is O(log N), these transformations also take O(log N) time. Provided that the tree was properly sorted to start with, you can prove that the end result is again a sorted and balanced tree.
As Jim said, if the tree becomes unsorted, for instance because you change the behaviour of the comparator, the tree algorithm's sorting order precondition won't be satisfied and it is unlikely ever to result in a sorted tree -- you will see seemingly random and unpredictable behaviour.
- Peter
[ March 07, 2003: Message edited by: Peter den Haan ]
 
Mark Herschberg
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Peter den Haan:
Rather, when an element is inserted or deleted, the TreeMap performs a number of transformations which basically can affect all nodes between the modified node and the root node, and their neighbouring nodes. Since the depth of the tree is O(log N), these transformations also take O(log N) time. Provided that the tree was properly sorted to start with, you can prove that the end result is again a sorted and balanced tree.
As Jim said, if the tree becomes unsorted, for instance because you change the behaviour of the comparator, the tree algorithm's sorting order precondition won't be satisfied and it is unlikely ever to result in a sorted tree -- you will see seemingly random and unpredictable behaviour.

Yes, I noted that in my post before yours, that you would have to do O(lgN) inserations. However, I beleive Sun's JDK uses a red-black tree algorithm, which will always be balanced. Now granted, if the sort method isn't homogenious across elements, it may not be sorted properly, but it will still be balanced. Hence, it will always take O(lgN) insertions.
--Mark
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!