9 Replies Latest reply on Apr 5, 2010 9:25 PM by YoungWinston

    how to avoid sorting a TreeMap

    807580
      I would like to add items into a TreeMap, but I do not want to change the sort ordering. In other words, I want to preserve the ordering of these items as they were added into the list, as a first-in/first-out style of sort ordering (and do not sort them by "natural ordering" or anything else).

      For example:
                import java.util.TreeMap;
                import java.util.Iterator;

                // Add the data into the TreeMap.
                TreeMap<String,Double> myComponents = new TreeMap<String,Double>();
                myComponents.put("milk", new Double(5.25));
                myComponents.put("eggs", new Double(1.23));
                myComponents.put("sausage", new Double(3.14));
                myComponents.put("ham", new Double(12.12));
                myComponents.put("soda", new Double(0.75));

                // Print the TreeMap's contents.
                Iterator iterator = myComponents.keySet().iterator();
                while (iterator.hasNext()) {
                     String myName = iterator.next().toString();
                     Double myCost = myComponents.get(myName);
                     System.out.println("myName=" + myName + ", myCost=" + myCost);
                }

      The actual output of the above code (with a "natural order" alphanumeric sort) is...
      myName=eggs, myCost=1.23
      myName=ham, myCost=12.12
      myName=milk, myCost=5.25
      myName=sausage, myCost=3.14
      myName=soda, myCost=0.75

      The desired output (to output the items using the original ordering) would be...
      myName=milk, myCost=5.25
      myName=eggs, myCost=1.23
      myName=sausage, myCost=3.14
      myName=ham, myCost=12.12
      myName=soda, myCost=0.75

      I do not need to use a TreeMap for this (in case other Java objects might be more useful), but I am using TreeMaps to enforce sort-ordering on other lists of data in this application, and it would be desirable to keep similar objects if possible.
        • 1. Re: how to avoid sorting a TreeMap
          800387
          Create a Comparator that uses the ordering/index of the backing list to determine the natural sort ordering of the TreeMap. Pass that Comparator to the constructor of your TreeMap.

          - Saish
          • 2. Re: how to avoid sorting a TreeMap
            807580
            I have created a Comparator for this TreeMap, but this list of items has no sort ordering for the Comaprator to use, but the Comparator will insist on sorting the items using its method calls. And there is no algorithm that can determine that item "milk" should sort before item "eggs" in this list. There is no "index of the backing list".

            My application is loading items from a series of XML files, and these items need to be displayed in the same order that the file contains those items...without re-ordering the items.

            I wish to avoid using an "ugly" solution...to add a fake "sort-order-index" value into these XML files, then load this data and insert (index+name) as the key value of the TreeMap, then have the application locate a desired item by scanning all TreeMap keys looking for the desired name value (and ignoring the index prefix on the (index+name) key values) and then extracting the value. This is quite ugly just to enforce a sort-ordering solution.
            • 3. Re: how to avoid sorting a TreeMap
              807580
              TreeMap is a sorted map, that is what it is designed to do. If you want a different map behaviour you should use a different map.
              I suggest you use LinkedHashMap which retains the order keys were added.

              A shorter way to write the same thing is.
              Map<String,Double> myComponents = new LinkedHashMap<String,Double>() {{
                  put("milk", 5.25);
                  put("eggs", 1.23);
                  put("sausage", 3.14);
                  put("ham", 2.12);
                  put("soda", 0.75);
              }};
              
              // Print the TreeMap's contents.
              for(Map.Entry<String, Double> entry: myComponents.entrySet()) {
                  System.out.println("myName=" + entry.getKey() + ", myCost=" + entry.getValue());
              }
              • 4. Re: how to avoid sorting a TreeMap
                YoungWinston
                s2v wrote:
                I would like to add items into a TreeMap, but I do not want to change the sort ordering. In other words, I want to preserve the ordering of these items as they were added into the list, as a first-in/first-out style of sort ordering (and do not sort them by "natural ordering" or anything else).
                I guess the question is: why are you using a TreeMap then? Seems to me that a Deque is what you want. However, if you do in fact need the items in both "sorted" and "unsorted" orders, why not use both? There isn't a huge space overhead, since the "items" in the collections are simply references.

                Winston
                • 5. Re: how to avoid sorting a TreeMap
                  807580
                  s2v wrote:
                  I would like to add items into a TreeMap, but I do not want to change the sort ordering.
                  So use a LinkedHashMap .
                  • 6. Re: how to avoid sorting a TreeMap
                    796440
                    shankar.unni wrote:
                    s2v wrote:
                    I would like to add items into a TreeMap, but I do not want to change the sort ordering.
                    So use a LinkedHashMap .
                    If only somebody had mentioned that [2 days ago in reply 3|http://forums.sun.com/thread.jspa?messageID=10964474#10964474].
                    • 7. Re: how to avoid sorting a TreeMap
                      807580
                      s2v wrote:
                      I would like to add items into a TreeMap, but I do not want to change the sort ordering. In other words, I want to preserve the ordering of these items as they were added into the list, as a first-in/first-out style of sort ordering (and do not sort them by "natural ordering" or anything else).
                      The question is, do you need a TreeMap in the first place?

                      Maybe some other data structure is better?
                      • 8. Re: how to avoid sorting a TreeMap
                        807580
                        Thank you for the useful responses...the LinkedHashMap seems to fit my application's needs.

                        It seems that my search was hindered by terminology. When I searched through the Java API for phrases like "sort" and "natural ordering" (which the various Java collections classes like Comparable and TreeMap use frequently), my search never found anything about LinkedHashMap.

                        It makes me wonder about how many other useful tools are right here in front me, if I knew the search phrase to find them :)
                        • 9. Re: how to avoid sorting a TreeMap
                          YoungWinston
                          s2v wrote:
                          It seems that my search was hindered by terminology. When I searched through the Java API for phrases like "sort" and "natural ordering" (which the various Java collections classes like Comparable and TreeMap use frequently), my search never found anything about LinkedHashMap.
                          It makes me wonder about how many other useful tools are right here in front me, if I knew the search phrase to find them :)
                          I agree; it would be nice to have a guide through what types of collection are good for what - especially when it comes to the 'Concurrent' lot (perhaps a link to a general document from the Collection and Map interfaces).

                          To be honest, after reading the paper on skip lists, I'm not sure I wouldn't use ConcurrentSkipList all the time over a LinkedList; but I have no idea what Java's implementation is like, nor what their thoughts are on the subject. I'm sure plenty of people can prove me wrong.

                          But, that said, the names for most of the collections are pretty standard, and a bit of Googling might do the trick. After all, it is your friend.

                          Winston