6
\$\begingroup\$

For my game that I'm writing, I need, among other things, a data structure for storing best values. For this purpose, I tried to write a class that meets the most general needs, and yet does not seem overloaded.

Can the class be further improved in terms of code quality or performance? Is the interface (not to be confused with the keyword) sufficiently comprehensible?

ScoreList.java

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

public class ScoreList <T extends Comparable<T>> {
    private final List<T> scores;
    // determines if lowest or highest value will be treaten as best
    private final boolean highestIsBest;
    private final int entryLimit;

    public ScoreList(int entryLimit, boolean highestIsBest) {
        scores = new ArrayList<T>();
        this.highestIsBest = highestIsBest;
        this.entryLimit = entryLimit;
    }

    // returns false if score is to low (or high)
    public boolean add(T newScore) {
        if (scores.size() < entryLimit) {
            scores.add(newScore);
            sortScores();
            return true;
        }

        T lastScore = scores.get(scores.size() - 1);
        if (highestIsBest) {
            if (newScore.compareTo(lastScore) > 0) {
                scores.remove(lastScore);
                scores.add(newScore);
                sortScores();
                return true;
            }
        } else {
            if (newScore.compareTo(lastScore) < 0) {
                scores.remove(lastScore);
                scores.add(newScore);
                sortScores();
                return true;
            }            
        }
        return false;
    }

    public List<T> getScores() {
        return new ArrayList<T>(scores);
    }

    private void sortScores() {
        if (highestIsBest) {
            Collections.sort(scores, Collections.reverseOrder());
        } else {
            Collections.sort(scores);
        }
    }
}

Main.java

import java.util.Random;

// this class tests the functionality of ScoreList
public class Main {
    private static Random random = new Random();

    // two ScoreList-objects get created
    // one with highestIsBest = true, one with = false
    // random values are added
    // after that, the values of the ScoreList-objects get shown
    public static void main(String[] args) {
        // create first score list that treats highest values as best
        int numberOfEntries = 5;
        boolean highestIsBest = true;
        ScoreList<Integer> scoreList1 = new ScoreList<>(numberOfEntries, highestIsBest);

        // add values
        for (int i = 0; i < 10; i++) {
            int number = random.nextInt(20);
            if (scoreList1.add(number)) {
                System.out.println(number + " was added to scoreList");
            } else {
                System.out.println(number + " was not added to scoreList");
            }
        }
        System.out.println();

        // show score list
        System.out.print("order of scores: ");
        for(Integer entry : scoreList1.getScores()) {
            System.out.print(entry + " ");
        }
        System.out.println('\n');

        // create second score list that treats lowest values as best
        numberOfEntries = 5;
        highestIsBest = false;
        ScoreList<Integer> scoreList2 = new ScoreList<>(numberOfEntries, highestIsBest);

        // add values
        for (int i = 0; i < 10; i++) {
            int number = random.nextInt(20);
            if (scoreList2.add(number)) {
                System.out.println(number + " was added to scoreList");
            } else {
                System.out.println(number + " was not added to scoreList");
            }
        }
        System.out.println();

        // show score list
        System.out.print("order of scores: ");
        for(Integer entry : scoreList2.getScores()) {
            System.out.print(entry + " ");
        }
        System.out.println();
    }
}

Example Output

+++ ScoreList-object that prefers high values +++

0 was added to scoreList
19 was added to scoreList
11 was added to scoreList
19 was added to scoreList
9 was added to scoreList
4 was added to scoreList
3 was not added to scoreList
7 was added to scoreList
1 was not added to scoreList
10 was added to scoreList

order of scores: 19 19 11 10 9 

+++ ScoreList-object that prefers low values +++

13 was added to scoreList
1 was added to scoreList
12 was added to scoreList
2 was added to scoreList
9 was added to scoreList
15 was not added to scoreList
6 was added to scoreList
18 was not added to scoreList
10 was added to scoreList
11 was not added to scoreList

order of scores: 1 2 6 9 10 

Thank you for your attention!

\$\endgroup\$
6
\$\begingroup\$

You want a list of elements, sorted to descending order by highest perceived value where least valued element is removed if an add operation causes the list size to exceed it's limit.

private final boolean highestIsBest;

This adds unnecessary responsibilities to the score list. It shouldn't care what the perceived value of a score is. Just pass a Comparator<T> in the constructor (instead of requiring T to implement Comparable) and let the caller worry about reversing the comparator if "smaller is better" order is needed.

\$\endgroup\$
  • 1
    \$\begingroup\$ I like this approach, since it simplifies things even more. Specially, since the OP does not want both orders to be available in a single ScoreList instance. \$\endgroup\$ – dfhwze Jun 12 at 10:56
  • 1
    \$\begingroup\$ Actually, a Comparator<? super T> would suffice. \$\endgroup\$ – Stingy Jun 13 at 9:37
4
\$\begingroup\$

Deque

If you need both Stack and Queue operability, consider using a Deque.

Summary of Deque methods

-           First Element (Head)                   Last Element (Tail)
-           Throws exception     Special value     Throws exception     Special value
- Insert    addFirst(e)          offerFirst(e)     addLast(e)           offerLast(e)
- Remove    removeFirst()        pollFirst()       removeLast()         pollLast()
- Examine   getFirst()           peekFirst()       getLast()            peekLast()

Implementation

Your code is really convoluted for what you want to achieve. Use a deque instead of the list private final List<T> scores; Depending on highestIsBest, you'd either use the Head or Tail functions. The code below can be simplified using the deque operations described above.

 T lastScore = scores.get(scores.size() - 1);
        if (highestIsBest) {
            if (newScore.compareTo(lastScore) > 0) {
                scores.remove(lastScore);
                scores.add(newScore);
                sortScores();
                return true;
            }
        } else {
            if (newScore.compareTo(lastScore) < 0) {
                scores.remove(lastScore);
                scores.add(newScore);
                sortScores();
                return true;
            }            
        }
\$\endgroup\$
  • \$\begingroup\$ What functionality of Stack that the OP requires is provided by Deque but not by Queue? Unless I missed something, the OP doesn't require insertion/removal at both ends, which is the advantage of Deque over Queue. \$\endgroup\$ – Stingy Jun 13 at 9:42
  • \$\begingroup\$ Also, the code duplication you pointed out won't be eliminated by using a Deque instead of a Queue, because the difference between the two code blocks is not the point of element removal/insertion, but the comparison of the two scores. \$\endgroup\$ – Stingy Jun 13 at 9:57
  • \$\begingroup\$ @Stingy Exactly, my proposed solution allows for having both implementations in a single instance. But since the OP does not need this, I am in favor of the other answer. Much simpler design. \$\endgroup\$ – dfhwze Jun 13 at 10:29
3
\$\begingroup\$
  • Have you considered the possibility of ScoreList<T> implementing List<T> directly? This can be easily achieved by extending AbstractList. However, you would have to be careful not to violate the contract of List when implementing your desired functionality: For example, your add(T) method adds an element in a way different from any of the add methods declared in List (if it adds the element at all), so you cannot override/implement add(T) from List and do what you do in your own add(T) method. Instead, I would suggest that you follow the instructions in the documentation of AbstractList for implementing an unmodifiable List, and then add a separate method for inserting a score as you did in your original code. You could also consider allowing the removal of scores from the List by implementing remove(int), as described in the documentation of AbstractList.

    This would also eliminate the need for the method getScores(). Nevertheless, here's a suggestion related to this method: I think that Collections.unmodifiableList(List) would be more useful here than new ArrayList(List), because the former returns a read-only "view" of the original List rather than a completely new, independent List, meaning that changes to the original List will be reflected in the List returned by Collections.unmodifiableList(List), so the caller only needs to call the method getScores() once in the lifetime of the ScoreList in order to always have a read-only reference to the scores.

  • Your insertion mechanism is more complicated than it needs to be, because at every insertion, it sorts a List that is already sorted except for the last inserted element. Instead, you could find out the prospective position of the element to be added in advance with one of the two binarySearch methods in Collections, and then insert the new element at this position without sorting the List again.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.