The class AnagramGameDefault simulates an anagram game.
The submitScore() should recalculate the positions, the one with highest score has position 1, there can be several players on the same position.
The getLeaderBoard() fetches the entry for a user plus two above and two below.
The concerns I have :
I have used quite a stringent mutually exclusive locking by using 'synchronized'. I don't think this can be avoided as submitScore() and getLeaderBoard() rely heavily on sorting and correct positions of score but is there a possibility ? I read a bit about ReentrantLock but it's more suitable where there are multiple reads and lesser writes, in this case, even the reads need calculations.
public enum AnagramGameDefault{
INSTANCE;
private Map<String, Entry> leaderBoardUserEntryMap;
{
leaderBoardUserEntryMap = new LinkedHashMap<>();
}
public int calculateScore(String word, String anagram) {
if (word == null || anagram == null) {
throw new NullPointerException("Both, word and anagram, must be non-null");
}
char[] wordArray = word.trim().toLowerCase().toCharArray();
char[] anagramArray = anagram.trim().toLowerCase().toCharArray();
int[] alphabetCountArray = new int[26];
int reference = 'a';
for (int i = 0; i < wordArray.length; i++) {
if (!Character.isWhitespace(wordArray[i])) {
alphabetCountArray[wordArray[i] - reference]++;
}
}
for (int i = 0; i < anagramArray.length; i++) {
if (!Character.isWhitespace(anagramArray[i])) {
alphabetCountArray[anagramArray[i] - reference]--;
}
}
for (int i = 0; i < 26; i++)
if (alphabetCountArray[i] != 0)
return 0;
return word.length();
}
public void submitScore(String uid, int score) {
Entry newEntry = new Entry(uid, score);
sortLeaderBoard(newEntry);
}
private void sortLeaderBoard(Entry newEntry) {
synchronized (leaderBoardUserEntryMap) {
leaderBoardUserEntryMap.put(newEntry.getUid(), newEntry);
// System.out.println("Sorting for " + newEntry);
List<Map.Entry<String, Entry>> list = leaderBoardUserEntryMap.entrySet().stream()
.sorted(Map.Entry.comparingByValue(Collections.reverseOrder())).collect(Collectors.toList());
leaderBoardUserEntryMap.clear();
int position = 0;
int previousPosition = 0;
int currentPosition = 0;
for (Map.Entry<String, Entry> entry : list) {
currentPosition = entry.getValue().getScore();
if (!(currentPosition == previousPosition))
position++;
entry.getValue().setPosition(position);
leaderBoardUserEntryMap.put(entry.getKey(), entry.getValue());
previousPosition = currentPosition;
}
}
}
public List<Entry> getLeaderBoard(String uid) {
final int maxEntriesAroundAnEntry = 2;
if (!leaderBoardUserEntryMap.containsKey(uid))
return Collections.emptyList();
Entry userEntry = null;
final List<Entry> leaderBoard = new ArrayList<>();
List<Entry> lowerEntries = null;
List<Entry> higherEntries = null;
synchronized (leaderBoardUserEntryMap) {
printBoard();
userEntry = leaderBoardUserEntryMap.get(uid);
int userPosition = userEntry.getPosition();
int upperPosition = userPosition - maxEntriesAroundAnEntry;
int lowerPosition = userPosition + maxEntriesAroundAnEntry;
// Higher entries
higherEntries = leaderBoardUserEntryMap.values().stream()
.filter(entry -> (entry.getPosition() < userPosition && entry.getPosition() >= upperPosition))
.map(entry -> new Entry(entry.getUid(), entry.getScore(), entry.getPosition()))
.collect(Collectors.toList());
// Lower entries
lowerEntries = leaderBoardUserEntryMap.values().stream()
.filter(entry -> (entry.getPosition() > userPosition && entry.getPosition() <= lowerPosition))
.map(entry -> new Entry(entry.getUid(), entry.getScore(), entry.getPosition()))
.collect(Collectors.toList());
userEntry = new Entry(userEntry.getUid(), userEntry.getScore(), userEntry.getPosition());
// }
if (higherEntries != null && !higherEntries.isEmpty()) {
if (higherEntries.size() >= maxEntriesAroundAnEntry) {
higherEntries = higherEntries.subList(higherEntries.size() - maxEntriesAroundAnEntry,
higherEntries.size());
}
leaderBoard.addAll(higherEntries);
}
leaderBoard.add(userEntry);
if (lowerEntries != null && !lowerEntries.isEmpty()) {
if (lowerEntries.size() >= maxEntriesAroundAnEntry) {
lowerEntries = lowerEntries.subList(0, maxEntriesAroundAnEntry);
}
leaderBoard.addAll(lowerEntries);
}
}
return leaderBoard;
}
public void printBoard() {
System.out.println("---------Start : Current leader board---------");
leaderBoardUserEntryMap.forEach((key, value) -> {
System.out.println("BOARD ENTRY : " + key + " : " + value);
});
System.out.println("---------End : Current leader board---------");
}
}
The Entry POJO :
public class Entry implements Comparable<Entry> {
private String uid;
private int score;
private int position;
public Entry(String uid, int score) {
this.uid = uid;
this.score = score;
}
public Entry(String uid, int score, int position) {
this.uid = uid;
this.score = score;
this.position = position;
}
public Entry() {
}
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 + score;
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;
Entry other = (Entry) obj;
if (score != other.score)
return false;
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 + "]";
}
@Override
public int compareTo(Entry o) {
// TODO Auto-generated method stub
if (o == null)
return -1;
return Integer.compare(score, o.getScore());
}
}
The tester class :
public class AnagramGameDefaultDemo {
public static void main(String[] args) {
if (args == null || args.length < 1) {
System.out.println("Enter testing approach - 1 for single threaded, 2 for multi-threaded");
return;
}
switch (args[0]) {
case "1": {
new AnagramGameDefaultDemo().testSingleThreaded();
break;
}
case "2": {
new AnagramGameDefaultDemo().testMultithreaded();
break;
}
default: {
System.out.println("Enter proper option(1 or 2)");
break;
}
}
}
private void testMultithreaded() {
Map<String, String> stringAnagramMap = new HashMap<>();
CountDownLatch countDownLatchOne = new CountDownLatch(1);
stringAnagramMap.put("raw", "war");
stringAnagramMap.put("raw", "wars");
AnagramGamePlayer jake = new AnagramGamePlayer("jake", stringAnagramMap, countDownLatchOne);
new Thread(jake, "jake").start();
stringAnagramMap.clear();
stringAnagramMap.put("tool", "loot");
AnagramGamePlayer ace = new AnagramGamePlayer("ace", stringAnagramMap, countDownLatchOne);
new Thread(ace, "ace").start();
stringAnagramMap.clear();
stringAnagramMap.put("William Shakespeare", "I am a weakish speller");
AnagramGamePlayer max = new AnagramGamePlayer("max", stringAnagramMap, countDownLatchOne);
new Thread(max, "max").start();
stringAnagramMap.clear();
stringAnagramMap.put("School master", "The classroom");
AnagramGamePlayer tBone = new AnagramGamePlayer("tBone", stringAnagramMap, countDownLatchOne);
new Thread(tBone, "tBone").start();
stringAnagramMap.clear();
countDownLatchOne.countDown();
CountDownLatch countDownLatchTwo = new CountDownLatch(1);
stringAnagramMap.put("Punishments", "Nine Thumps");
AnagramGamePlayer razor = new AnagramGamePlayer("razor", stringAnagramMap, countDownLatchTwo);
new Thread(razor, "razor").start();
stringAnagramMap.clear();
stringAnagramMap.put("Dormitory", "Dirty Room");
AnagramGamePlayer chip = new AnagramGamePlayer("chip", stringAnagramMap, countDownLatchTwo);
new Thread(chip, "chip").start();
stringAnagramMap.clear();
countDownLatchTwo.countDown();
CountDownLatch countDownLatchThree = new CountDownLatch(1);
stringAnagramMap.put("Mother in law", "Hitler woman");
AnagramGamePlayer dale = new AnagramGamePlayer("dale", stringAnagramMap, countDownLatchThree);
new Thread(dale, "dale").start();
countDownLatchThree.countDown();
stringAnagramMap.clear();
}
private final class AnagramGamePlayer implements Runnable {
private Map<String, String> stringAnagramMap = new HashMap<>();
private String uid;
private CountDownLatch countDownLatch;
public AnagramGamePlayer(String uid, Map<String, String> stringAnagramMap, CountDownLatch countDownLatch) {
this.stringAnagramMap.putAll(stringAnagramMap);
this.uid = uid;
this.countDownLatch = countDownLatch;
}
@Override
public void run() {
AnagramGameDefault anagramGameDefault = AnagramGameDefault.INSTANCE;
try {
countDownLatch.await();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("Player " + uid + " started playing with " + stringAnagramMap);
stringAnagramMap.entrySet().forEach(entry -> {
anagramGameDefault.submitScore(uid,
anagramGameDefault.calculateScore(entry.getKey(), entry.getValue()));
printLeaderBoard(uid, anagramGameDefault.getLeaderBoard(uid));
});
System.out.println("Player " + uid + " completed playing");
}
}
private void testSingleThreaded() {
AnagramGameDefault anagramGameDefault = AnagramGameDefault.INSTANCE;
anagramGameDefault.submitScore("Jake", 3);
anagramGameDefault.submitScore("Ace", 7);
anagramGameDefault.submitScore("Max", 1);
anagramGameDefault.submitScore("T-Bone", 14);
anagramGameDefault.submitScore("Razor", 6);
anagramGameDefault.submitScore("Razor", 7);
anagramGameDefault.submitScore("He-Man", 4);
anagramGameDefault.submitScore("Men-at-Arms", 8);
anagramGameDefault.submitScore("BattleCat", 3);
anagramGameDefault.submitScore("Jake", 2);
anagramGameDefault.submitScore("BattleCat", 3);
anagramGameDefault.printBoard();
anagramGameDefault.submitScore("Men-at-Arms", 21);
anagramGameDefault.submitScore("Orko", 20);
anagramGameDefault.submitScore("Jake", 4);
anagramGameDefault.printBoard();
System.out.println();
printLeaderBoard("user5", anagramGameDefault.getLeaderBoard("user5"));
System.out.println();
printLeaderBoard("user4", anagramGameDefault.getLeaderBoard("user4"));
System.out.println();
printLeaderBoard("user15", anagramGameDefault.getLeaderBoard("user15"));
System.out.println();
List<Entry> entries = anagramGameDefault.getLeaderBoard("user1");
printLeaderBoard("user1", entries);
System.out.println("Changing state of the received entries");
entries.forEach(entry -> {
entry.setPosition(1);
entry.setScore(0);
});
anagramGameDefault.printBoard();
printLeaderBoard("user1", anagramGameDefault.getLeaderBoard("user1"));
}
private static void printLeaderBoard(String user, List<Entry> leaderBoard) {
if (user == null || leaderBoard.isEmpty()) {
System.out.println("Either user " + user + " doesn't exist or leader board is empty " + leaderBoard);
}
System.out.println("**********Printing leader board for " + user);
leaderBoard.forEach(System.out::println);
System.out.println("**********");
}
}
It seems the only shared state you have in the whole thing is leaderBoardUserEntryMap. You synchronize on it when updating in sortLeaderBoard. In getLeaderBoard for some reason you don't yet synchronize on it when checking if (!leaderBoardUserEntryMap.containsKey(uid)). That's minor, but you should do it as well. Later, you synchronize on it when constructing the leader board.
From this point of view your synchronization seems adequate.
What I find a bit problematic is that your Entry is mutable and stores position. This makes your update operation more problematic. You have to re-sort and re-set positions on every update. And you're locking all other update or even read operations. I'd avoid mutable objects in multithreaded code.
I'd use a SortedSet instead and let the implementation handle sorting. To find out the position of the element you'd just do set.headSet(element).size() + 1. So no need to store position at all.
I initially wanted to suggest using concurrent collection implementations like ConcurrentHashSet which would allow "full concurrency of retrievals and adjustable expected concurrency for updates". Basically, retrievals could be non-blocking, only updates were.
However, this won't help much as your "retrieval" logic (creating the leader board around target entry) is not so simple and involves several reads. So I think it's better not use concurrent collections but instead actually synchronize on the collection and make updates and retrievals as compact as possible. If you give up on the idea of having position in Entry then update is a trivial add. Then you'll only need to read entries around the entry as fast as possible (within the synchronized block). This should be quite fast with tree sets.