Data Structure to Rank Objects

Question

I am looking for a data structure that will sort objects based on a given integer. Like so:

Object    Score
Object1   86
Object2   85
Object3   85 

Each object will be unique, but there can be duplicate scores. Was trying to devise a way on how a Map object could do this, but can't figure it out.

Structure can either sort the objects during/after an insertion or when I implicitly call for a sort.

Is there a structure out there that does this already? Or should I code it myself?

Answer 1

Try putting the objects in a SortedSet if you want unique values or a List if you want to see duplicates, along with a custom Comparator to sort them based on their "scores".

Providing your own Comparator will let you specify that the objects should be sorted on their score field and how.

The Comparator is also reusable and easy to swap in / out if you wanted to, say do a descending sort on the items.

So an example that might be:

  class ScoreComparator implements Comparator <ObjectHolder> {
    @Override
    public int compare(ObjectHolder o1, ObjectHolder o2) {
      return o1.getScore().compareTo(o2.getScore());
    }
  }

  class DescendingScoreComparator implements Comparator <ObjectHolder> {
    @Override
    public int compare(ObjectHolder o1, ObjectHolder o2) {
      return o2.getScore().compareTo(o1.getScore());
    }
  }


  class ObjectHolder {
    Object obj;
    Integer score;

    public ObjectHolder(Object o, Integer score) {
      this.obj = o;
      this.score = score;
    }

    public Object getObject() {
      return obj;
    }
    public Integer getScore() {
      return score;
    }
  }


  public void showExample() {
    SortedSet<ObjectHolder> sortedSet = new TreeSet<ObjectHolder>(new ScoreComparator());
    sortedSet.add(new ObjectHolder("addedFirst", 55));
    sortedSet.add(new ObjectHolder("addedSecond", 25));
    sortedSet.add(new ObjectHolder("addedThird", 75));
    sortedSet.add(new ObjectHolder("addedFourth", 25));
    sortedSet.add(new ObjectHolder("addedFifth", 95));

    // The resulting set will only have 4 items since sets don't allow duplicates
    for (ObjectHolder holder : sortedSet) {
      System.out.println(holder.getScore());
    }

    List<ObjectHolder> list = new LinkedList<ObjectHolder>();
    list.add(new ObjectHolder("addedFirst", 55));
    list.add(new ObjectHolder("addedSecond", 25));
    list.add(new ObjectHolder("addedThird", 75));
    list.add(new ObjectHolder("addedFourth", 25));
    list.add(new ObjectHolder("addedFifth", 95));

    Collections.sort(list, new ScoreComparator());

    // The resulting set will only have 5 items since lists allow duplicates
    System.out.println();
    for (ObjectHolder holder : list) {
      System.out.println(holder.getScore());
    }

    Collections.sort(list, new DescendingScoreComparator());

    System.out.println("\nWill print 5 items, but this time in descending order");
    for (ObjectHolder holder : list) {
      System.out.println(holder.getScore());
    }
  }

And here's the output of the above code:

Will print 4 unique items since sets don't allow duplicates

25 55 75 95

Will print 5 items since lists do allow duplicates

25 25 55 75 95

Will print 5 items, but this time in descending order

95 75 55 25 25