This week's book giveaway is in the Spring forum.
We're giving away four copies of Spring in Action (5th edition) and have Craig Walls on-line!
See this thread for details.
Win a copy of Spring in Action (5th edition) this week in the Spring forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Efficient way to traverse SortedMap backwards  RSS feed

 
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?
 
author & internet detective
Posts: 38906
684
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?
 
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
Posts: 38906
684
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.
 
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.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!