3 Replies Latest reply: Aug 17, 2008 11:11 PM by 807589 RSS

    Sorting Tree Maps

    807589
      Hi all,

      I'm trying to figure out how to order a tree map by value that holds a frequency analysis of strings read in from a file. I guess it doesn't really matter how I did that, what I have is a TreeMap with values like

      cat 15
      chicken 32
      dog 1
      lion 1
      zebra 5

      So i need to make this

      chicken 32
      cat 15
      zebra 5
      dog 1
      lion 1

      How would be the best way to do this?

      Edited by: dsw7 on Aug 17, 2008 6:09 PM
        • 1. Re: Sorting Tree Maps
          807589
          So you're saying that you want to sort the entries of a Map by the (numerical) values, in descending order. The map happens to be a TreeMap, but you don't care about the sorting that the TreeMap provides.

          Probably the easiest thing would be to get the Set of Map.Entry objects using the entries() method, put those into a new List, and then write a java.util.Comparator to sort the list.
          • 2. Re: Sorting Tree Maps
            807589
            Thanks for the reply.

            Yes that's exactly what I need to do. From your answer it seems like maybe I'm using the wrong type of data structure for what I'm doing. TreeMap seemed good because I could easily tabulate the occurrences of each string using while loop with this inside:
            ...
            static TreeMap<String, Integer> idMap = new TreeMap<String, Integer>();
            ...
            Integer idCount = idMap.get(animalName); //returns null if the animal name isn't yet in idMap
            idMap.put(animalName, (idCount == null) ? 1 : ++idCount);

            but you're right the automatic sorting of TreeMap isn't what I want. Is there a better data structure to do this so that I'm not sorting then sorting again needlessly?

            Otherwise I'll use the Comparator class.

            Thanks

            Edited by: dsw7 on Aug 17, 2008 7:09 PM
            • 3. Re: Sorting Tree Maps
              807589
              Is there a better data structure to do this so that I'm not sorting then sorting again needlessly?
              If you don't want the alphabetic sort by key ("aardvark"->"zebra") just use an unsorted Map like a HashMap. Your code for checking if an entry exists and incrementing the value will work for any Map, not just a TreeMap. The numerical ordering "frequent->infrequent" is most easily calculated at the end (via a Comparator on the entry set as suggested) so it's not really needless.

              You could write your own Frequency class that keeps its entries sorted by value, but that would take work. I don't think any of the Java map implementations do this.

              Edited by: pbrockway2 on Aug 18, 2008 4:03 PM

              The Apache commons library does offer a TreeBidiMap but unless you want to be continually looking at the ordering-by-value while the map is being constructed, it would be easier to just do the sort at the end.