Update a POJO property with 'position' in a SortedMap(TreeMap)

Question

I am trying to simulate a game board where multiple players can submit their game scores.

The POJO viz. Entry.java represents an entry in the leaderboard. Note the overriden equals() method.

Position is the position in the leaderboard, 1 being the user with the highest score

public class EntryTreeMapOption {

private String uid;
private int score;
private int position;

public EntryTreeMapOption(String uid, int score) {

    this.uid = uid;
    this.score = score;

}

public EntryTreeMapOption() {

}

public String getUid() {
    return uid;
}

public void setUid(String uid) {
    this.uid = uid;
}

public int getScore() {
    return score;
}

public void setScore(int score) {
    this.score = score;
}

public int getPosition() {
    return position;
}

public void setPosition(int position) {
    this.position = position;
}

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((uid == null) ? 0 : uid.hashCode());
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    EntryTreeMapOption other = (EntryTreeMapOption) obj;
    if (uid == null) {
        if (other.uid != null)
            return false;
    } else if (!uid.equals(other.uid))
        return false;
    return true;
}

@Override
public String toString() {
    return "Entry [uid=" + uid + ", score=" + score + ", position=" + position + "]";
}}

I am using a TreeMap to store the entries, based on the score, they are sorted automatically

public class GameDefault2 {

    private TreeMap<EntryMapOption, String> leaderBoardEntryUserMap;

    {

        leaderBoardEntryUserMap = new TreeMap<>(Comparator.comparingInt(EntryTreeMapOption::getScore).reversed()
            .thenComparing(EntryTreeMapOption::getUid));
    }

    @Override
    public void submitScore(String uid, int score) {

        EntryMapOption newEntry = new EntryMapOption(uid, score);
        leaderBoardEntryUserMap.put(newEntry, uid);

    }

    @Override
    public List<EntryMapOption> getLeaderBoard(String uid) {

        List<EntryMapOption> userEntryList = .....
        .....
        .....

        return entriesOptionTwo;

    }

}

How do I set the 'position' field of an Entry ? e.g: Below are entries sorted as per the scores, how do I get the corresponding 'index/position' and set it in the entry ?

Entry [uid=user1, score=14, position=0]
Entry [uid=user2, score=8, position=0]
Entry [uid=user3, score=7, position=0]
Entry [uid=user4, score=7, position=0]
Entry [uid=user5, score=4, position=0]
Entry [uid=user6, score=3, position=0]
Entry [uid=user7, score=3, position=0]
Entry [uid=user8, score=1, position=0]

Now, user1 entry should have position=1, user2 entry should have position=2 and so on.

Answer 1

By my understanding, you should be able to convert your List to an Array using listArray = list.toArray(), then use

for (int i = 0; i < listArray.length; i++) { listArray[i].position = i + 1; }

To set their position to their index. (Plus one, because the winner should be first, not zeroth)

Answer 2

You can't do that automatically in a TreeMap, you will have to write that on your own, but this will not be cheap. On each update of a score (I actually mean remove that entry and then place it back into the map) you will need to traverse the entire map and update it accordingly. You can do that with the entrySet() iterator that says: The set's iterator returns the entries in ascending key order. Something like this:

Iterator<...> it = map.entrySet().iterator();

    int num = 1;

    while(it.hasNext()) {
        Entry en = it.next;
        en.getKey().setPosition(num++);
    }

Answer 3

Perhaps, you’re better off with a sorted List.

Consider

public class RankList<T> extends AbstractCollection<T> {

    private final Comparator<T> order;
    private final List<T> contents;

    public RankList(Comparator<T> order) {
        this.order = Objects.requireNonNull(order);
        contents = new ArrayList<>();
    }
    public RankList(Comparator<T> order, List<? extends T> initialContents) {
        this.order = Objects.requireNonNull(order);
        contents = new ArrayList<>(initialContents);
        contents.sort(order);
    }

    @Override
    public boolean add(T e) {
        int index = Collections.binarySearch(contents, e, order);
        if(index>=0) return false;
        contents.add(~index, e);
        return true;
    }

    public int addAndGetIndex(T e) {
        int index = Collections.binarySearch(contents, e, order);
        if(index>=0) throw new IllegalStateException("duplicate element");
        index = ~index;
        contents.add(index, e);
        return index;
    }

    @Override
    public boolean remove(Object o) {
        T t = (T)o;
        int index = Collections.binarySearch(contents, t, order);
        if(index<0) return false;
        contents.remove(index);
        return true;
    }

    @Override
    public boolean contains(Object o) {
        T t = (T)o;
        return Collections.binarySearch(contents, t, order)>=0;
    }

    public int indexOf(T element) {
        int ix = Collections.binarySearch(contents, element, order);
        return ix<0? -1: ix;
    }

    public List<T> asList() {
        return Collections.unmodifiableList(contents);
    }

    @Override
    public Iterator<T> iterator() {
        return contents.iterator();
    }

    @Override
    public int size() {
        return contents.size();
    }
}

By ensuring that the list is always sorted, you can exploit the sorted nature in lookup and insertion operations, so you’ll have the same O(log n) time complexity as TreeMap, the required space might be even less for larger number of elements due to the flat array storage. Wrapping the List in another class like RankList helps ensuring that the sorted property can’t get invalidated by accident when modifying the List.

It’s still required to remove and re-insert an element when changing its ordering property, but it’s still straight-forward, e.g.

RankList<EntryOption> rankList=new RankList<>(
    Comparator.comparingInt(EntryOption::getScore).reversed()
              .thenComparing(EntryOption::getUid));
ThreadLocalRandom r = ThreadLocalRandom.current();
for(int id=1; id<100; id++)
    rankList.add(new EntryOption(String.valueOf(id), r.nextInt(100)));

EntryOption justAnother = new EntryOption("101", r.nextInt(100));
int pos = rankList.addAndGetIndex(justAnother);
int rangeStart = Math.max(0, pos-2), rangeEnd=Math.min(rankList.size(), rangeStart+5);

System.out.println("entries around "+justAnother);
rankList.asList().subList(rangeStart, rangeEnd)
        .forEach(System.out::println);

System.out.println("update score of "+justAnother);

rankList.remove(justAnother);
justAnother.score+=20;
rankList.add(justAnother);

System.out.println("entries around "+justAnother);
pos = rankList.indexOf(justAnother);
rangeStart = Math.max(0, pos-2); rangeEnd=Math.min(rankList.size(), rangeStart+5);
rankList.asList().subList(rangeStart, rangeEnd)
        .forEach(System.out::println);

When you’re going to update all elements, however, it might be more efficient to perform the bulk update and instantiate a new RankList afterwards…

Or add something like

public void updateAll(Consumer<? super T> updateElementAction) {
    contents.forEach(updateElementAction);
    contents.sort(order);
}

to RankList if you can express the update action as Consumer, letting the list temporarily go unsorted and validate with a single sort operation afterwards.