按排序顺序存储条目并检索条目周围的条目 [英] Store entries in sorted order and retrieve entries around an entry

问题描述

我正在尝试模拟一个游戏板，其中多个玩家可以提交他们的游戏分数。

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

POJO即。 Entry.java表示排行榜中的条目。 请注意覆盖的equals（）方法。

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

排名是排行榜中的排名，1是用户
最高分

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 + "]";
}}

GameBoard类有几种方法：

The GameBoard class has a couple of methods :

• submitScore（String uid，int score）每个玩家都会调用此方法将他的分数提交给游戏板。每个玩家/用户只有一个条目，因此，如果玩家多次调用此方法，则会存储他的最新分数


• getLeaderBoard（String uid）

如果用户在排行榜中，则返回最多两个条目，其中
得分大于用户（用户是紧接在排行榜中的
用户上方，用户自己的条目和最多两个条目
，紧接在排行榜中的用户之后

If the user is in the leaderboard, returns max two entries that have larger score than the user (the users that are immediately above the user in the leaderboard), the user’s own entry and max two entries that are immediately after the user in the leaderboard

例如：

The leader board is :
Entry [uid=user1, score=14, position=1]
Entry [uid=user2, score=8, position=2]
Entry [uid=user3, score=7, position=3]
Entry [uid=user4, score=7, position=3]
Entry [uid=user5, score=4, position=4]
Entry [uid=user6, score=3, position=5]
Entry [uid=user7, score=3, position=5]
Entry [uid=user8, score=1, position=6]

For user5, entries returned should be :
Entry [uid=user3, score=7, position=3]
Entry [uid=user4, score=7, position=3]
Entry [uid=user5, score=4, position=4]
Entry [uid=user6, score=3, position=5]
Entry [uid=user7, score=3, position=5]

For user4, entries returned should be :
Entry [uid=user1, score=14, position=1]
Entry [uid=user2, score=8, position=2]
Entry [uid=user4, score=7, position=3]
Entry [uid=user5, score=4, position=4]
Entry [uid=user6, score=3, position=5]

For user6, entries returned should be :
Entry [uid=user4, score=7, position=3]
Entry [uid=user5, score=4, position=4]
Entry [uid=user6, score=3, position=5]
Entry [uid=user8, score=1, position=6]

For user7, entries returned should be :

Entry [uid=user4, score=7, position=3]
Entry [uid=user5, score=4, position=4]
Entry [uid=user7, score=3, position=5]
Entry [uid=user8, score=1, position=6]

我最初的做法是要使用TreeMap，可以选择这里。

My initial approach was to use a TreeMap, the alternative is discussed here.

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) {

        System.out.println("---------Current leader board---------");
        leaderBoardEntryUserMap.keySet().forEach(System.out::println);

        List<EntryMapOption> userEntryList = leaderBoardEntryUserMap.entrySet().stream()
                .filter(entry -> uid.equalsIgnoreCase(entry.getKey().getUid())).map(Map.Entry::getKey)
                .collect(Collectors.toList());

        if (userEntryList == null || userEntryList.isEmpty())
            return Collections.emptyList();

        // Incomplete and error prone
        EntryMapOption userEntry = userEntryList.get(0);

        List<EntryMapOption> entriesOptionTwo = new ArrayList<>();
        entriesOptionTwo.add(leaderBoardEntryUserMap.higherKey(userEntry));
        entriesOptionTwo.add(userEntry);
        entriesOptionTwo.add(leaderBoardEntryUserMap.lowerKey(userEntry));

        return entriesOptionTwo;

    }

}

问题上面的代码：

• 何时（理想情况下，在submitScore（）期间）以及如何计算位置。虽然它用于键，但我想知道Map.compute（）是否可以以任何方式提供帮助！


• 检查下面的代码'// Incomplete and error prone'comment
  虽然'higherKey（）'和'lowerKey（）'方便，但我不确定如何使用它们在特定条目下方和上方选择固定数量的条目

*****编辑-1 ******
@ Holger的修复解决了以下问题

*****Edit-1****** @Holger's fix solved the following issue

• 我无法弄清楚如何修复equals（）之间的不一致和比较（）。这导致缺少条目

推荐答案

地图的潜在问题

您的equals方法基于ID，但您的比较方法基于得分，这将导致JavaDoc出现问题。

Potential issue with the map

Your equals method is based upon the ID, but your compare method is based on the score, which will cause issues, from the JavaDoc.

请注意，如果此有序映射要正确实现Map接口，则树映射维护的排序（如任何有序映射，以及是否提供显式比较器）必须与equals一致。 （有关与equals一致的精确定义，请参见Comparable或Comparator。）这是因为Map接口是根据equals操作定义的，但是有序映射使用compareTo（或compare）方法执行所有键比较，因此从排序映射的角度来看，通过此方法被视为相等的键是相等的。即使排序与equals不一致，也可以很好地定义有序映射的行为。它只是没有遵守Map接口的一般合约。

Note that the ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

问题是比较方法会把搜索错误方向，因为它在不同的财产上订购。

The problem is that the compare method will take the search in the wrong direction, as it ordering on a different property.

在你的情况下，这可能不是一个问题，尽管你可能有2个相同的对象没有相同的分数导致未来的问题。

In your case this may be less of an issue, although you could have 2 equal objects which do not have the same score, leading to future issues.

在项目位于树中时更改分数也可能导致问题，因此您可能必须在每次分数更改时删除该项目，然后重新添加。

Changing the score while the item is in the tree may also cause issue, so you may have to remove the item each time their score changes, and re-add them.

这个过程的一个例子就是这个

An example of the process working would be this

import java.util.Comparator;
import java.util.TreeMap;

public class Test {

  static class Example {
    final int id;
    final int score;

    Example(int id, int score) {
      this.id = id;
      this.score = score;
    }

    @Override
    public boolean equals(Object obj) {
      if (!(obj instanceof Example)) {
        return false;
      }
      final Example other = (Example) obj;
      return other.id == id;
    }

    @Override
    public int hashCode() {
      return id;
    }

    public int getId() {
      return id;
    }

    @Override
    public String toString() {
      return id + " scored " + score;
    }

    public int getScore() {
      return score;
    }
  }

  public static void main(final String... args) {
    Example a = new Example(1, 10);
    Example b = new Example(2, 30);
    Example c = new Example(3, 1);
    Example d = new Example(4, 10);

    TreeMap<Example, Integer> x = new TreeMap<Example, Integer>(Comparator.comparingInt(Example::getScore).thenComparing(Example::getId));

    x.put(a, a.getScore());
    x.put(b, b.getScore());
    x.put(c, c.getScore());
    x.put(d, d.getScore());

    final Example h2 = x.higherKey(a);
    final Example h1 = h2 == null ? null : x.higherKey(h2);

    final Example l1 = x.lowerKey(a);
    final Example l2 = l1 == null ? null : x.lowerKey(l1);

    System.out.println(h1);
    System.out.println(h2);
    System.out.println(a);
    System.out.println(l1);
    System.out.println(l2);
  }
}

这篇关于按排序顺序存储条目并检索条目周围的条目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！