0
\$\begingroup\$

I've read so much arguing about "sort by value maps". Well, I wrote the following log(n) sort by value Map . And, by the way, a real Map , does not allow duplicate keys. Many of the maps I googled ignore that annoying problem. I assume this map is still log(n)...:

public static void sortByValue_logN() {

    class MyComp implements Comparator {
        Map<Object, Integer> sharedMap;

        public int compare(Object key1, Object key2) {
            if(key1.equals(key2)) { return 0; }

            Integer val1 = sharedMap.get(key1);
            Integer val2 = sharedMap.get(key2);

            if(val1 > val2) return -1; 
            return 1;
        }     

    }

    class TreeMapByValue<K> extends TreeMap<K, Integer> {
        Map<Object, Integer> sharedMap = new HashMap<Object, Integer>();
        TreeMapByValue(Comparator comp) {
            super(comp);
        }

        @Override
        public Integer put(K key, Integer val) {
            if(sharedMap.containsKey(key)) {
                super.remove(key);
                val += sharedMap.get(key);
            }
            sharedMap.put(key, val);

            super.put(key, val);

            return val;
        }
    }

    MyComp myComp = new MyComp();
    TreeMapByValue<Object> myMap = new TreeMapByValue(myComp);
    myComp.sharedMap = myMap.sharedMap;


    // all the rest is just testing the map
    Random rand = new Random();
    String[] story = { "The", "quick", "brown", "fox", "jumped" };

    for(int repeat = 0; repeat < 3; repeat++) {
        for(int i = 0; i < story.length; i++) {
            String key = story[i];
            int value = rand.nextInt(100);
            myMap.put(key, value);
            System.out.println(key + "-->" + value);
        }
    }

    for(Map.Entry<Object, Integer> entry : myMap.entrySet()) {
        System.out.println("key = " + entry.getKey() + "___value = " + entry.getValue());
    }
}

Surely (at least stylistically) something is bad about the above code.

I don't understand generics yet, so I am ok with ignoring that for now. I am also ignoring thread-safety issues as well.

My goal is to create a log(n) "sort by value" map that respects the property of not having duplicate keys. So, what is wrong with what I did?

\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

put seems quite broken, which in turn breaks get.

From the documentation,

V put(K key, V value)

Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for the key, the old value is replaced by the specified value. (A map m is said to contain a mapping for a key k if and only if m.containsKey(k) would return true.)

Returns: the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key, if the implementation supports null values.)

Let's take this code

  myMap.put("x", 1);
  int oldValue = myMap.put("x", 2);
  System.out.printf("%d %d%n", oldValue, myMap.get("x"));

I would expect it to print 1 2, but it prints 3 3.

\$\endgroup\$
2
  • \$\begingroup\$ Yes. I understand your point. I do need to make it conform to the api. I've never really done programming before. thanks. \$\endgroup\$ Commented Mar 17, 2015 at 23:01
  • \$\begingroup\$ Actually, I just realized a catastrophic failure? What I did breaks the "is a" relationship with TreeMap. I can't let anyone get a reference to an instance of "TreeMapByValue" because via reflection they can see the "is a" relationship with TreeMap (which TreeMapByValue is not). I know what to do. And, as a side-effect, now I don't need to worry about complying to the TreeMap API that you mentioned. got it. \$\endgroup\$ Commented Mar 18, 2015 at 17:10

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.