• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Efficient way to traverse SortedMap backwards

 
Ranch Hand
Posts: 1970
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 41860
908
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You could use and go backwards through the array.
 
Peter Chase
Ranch Hand
Posts: 1970
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 41860
908
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic