• Post Reply Bookmark Topic Watch Topic
  • New Topic

Efficient way to traverse SortedMap backwards

 
Peter Chase
Ranch Hand
Posts: 1970
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am using a TreeMap to implement SortedMap. My application needs to be able to traverse the entries in the SortedMap in either direction. The forwards direction is easy: you call entrySet() on the SortedMap then iterator() on the Set. But I do not know of any way to traverse backwards (Iterator does not have a prev() method, for example).
Is it possible to traverse a SortedMap backwards efficiently?
If it is not possible to do so with the JDK's standard collection classes, is there some other collection class, freely-available, that does make it possible?
If there is no such class available, is there at least a design for such a class, which I could implement?
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 35744
412
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You could use and go backwards through the array.
 
Peter Chase
Ranch Hand
Posts: 1970
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Jeanne Boyarsky:
You could use and go backwards through the array.

But surely the TreeMap will traverse its whole self in the process of generating the array. That is hardly efficient, is it? Or am I missing something?
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It looks like the closet the Collection framework lets you get to this would be writing a custom interator that used the headMap method, but the performance of that wouldn't be near as good as it would be if SortedMap has a getSortedEntrySet() method and SortedSet returned a ListIterator instead of just an Iterator.
If linear-time forward and reverse iteration for a large Map are important to you, look for an open source Red-Black Tree implementation on the web. Even if it doesn't already support reverse interation, you shouldn't have any trouble figuring out how to implement it.
 
Peter Chase
Ranch Hand
Posts: 1970
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by David Weitzman:
If linear-time forward and reverse iteration for a large Map are important to you, look for an open source Red-Black Tree implementation on the web. Even if it doesn't already support reverse interation, you shouldn't have any trouble figuring out how to implement it.

I had a look for such a thing, but didn't find one. My search was made difficult by the fact that TreeMap is a Red-Black Tree, so 99.99% of all hits on "Red Black Tree" get documents discussing TreeMap
I don't suppose anyone can point me to an open source Red-Black Tree...
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If the GPL license isn't a problem, there's an implementation in the GNU Classpath project.
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 35744
412
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Peter,
I thought you were trying to traverse the whole tree backwards (in which case it would be going through it once to get the list) and then you would just go through the array, leaving the original tree alone.
Sorry if I misinterpreted the question.
 
steve souza
Ranch Hand
Posts: 862
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
<<But surely the TreeMap will traverse its whole self in the process of generating the array. That is hardly efficient, is it? Or am I missing something? >>
Time it to see if it is "efficient". I'm always amazed how fast java is at doing most things. From experience going through an array is very fast and will probably never be a bottleneck worth worrying about for most developers. For example if it takes less than a millisecond to go through an array a second time then it is probably irrelevant to most apps if you can speed that up.
steve - http://www.jamonapi.com - a fast, free performance tuning and scalabiltity testing API.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!