TopScore or FilteringMap map, sorted on key

Question

For lack of a better name, I am calling the data structure I am looking for as a "TopScoreMap". Here is the requirement. First, the size of the map is fixed. For instance, the map only needs to retain top n entries that would be thrown at this map. Top n in terms of its keys. Since the map should be ordered on its keys, I chose to implement this based on java.util.TreeMap. Following is what I have implemented. This has passed a few test cases. My questions are :

1. Are there existing data structures that provide this functionality?

2. If not, is there a way to avoid iterations while performing put? looks like O(n^2), worst case.

class TopScoreMap {
  TreeMap<Integer, String> map = new TreeMap<Integer, String>();
  int max = 0;

  public TopScoreMap() {
    this(5);
  }

  public TopScoreMap(int maxCapacity) {
    this.max = maxCapacity;
  }

  public void put(int score, String player) {
    if (map.size() < max) {
      map.put(score, player);
    }
    else {
      Iterator<Integer> it = map.keySet().iterator();
      while (it.hasNext()) {
        int currentKey = it.next();
        if (currentKey < score) {
          map.remove(currentKey);
          map.put(score, player);
          return;
        }
      }
    }
  }

}

Answer 1

you might want to take a look at PriorityQueue, that way you don't need the iterator...but you should drop elements from the end if it grows over the limit

or maybe you should use SortedMap:

public class T1 {
    SortedMap<Integer, String>  m=new TreeMap<Integer, String>();
    void add(Integer i,String n){
        m.put(i,n);
        if(m.size()>3){
            m.tailMap(m.lastKey()).clear();
        }
        System.out.println(m);
    }
    public static void main(String[] args) {
        T1 t = new T1();
        t.add(1,"a");t.add(2,"b");t.add(3,"c");t.add(4,"d");t.add(0,"e");
    }
}

Answer 2

Instead of an iterator, you could just look at the lastKey of the underlying TreeMap. If the new entry is greater, accept it.

Something like:

  int lastKey = map.getLastKey();
  if (lastKey < score) {
    map.remove(lastKey);
    map.put(score, player);      
  }

Answer 3

With inputs from SO, here is what I did (not worrying about synchronization for now)

class ScoreMap {
    SortedMap<Integer, String> map = new TreeMap<Integer, String>(Collections.reverseOrder());
    int max = 5;

    public ScoreMap(int maxCapacity) {
      this.max = maxCapacity;
    }

    public void put(int score, String player) {
      map.put(score, player);
      if (map.size() > max) {
        map.remove(map.lastKey());
      }
    }
    //....
}