CODEWITHSUNDEEP
javaalgorithmarraylist
Marcel Doe
Marcel Doe

Reputation: 57

Retrieve multiple elements in an ArrayList that are closest to an integer

I have an ArrayList consisting of Objects. In those Objects, I have a field called "level."

I also have the level of a player. I'm trying retrieve the elements in an ArrayList closest to the players level, but only if the players level is more than the "level" in the object.

For example:

        static {
        foodSources = new ArrayList<FoodSource>();
        foodSources.add(new FoodSource("foodSource1", 10));
        foodSources.add(new FoodSource("foodSource2", 10));
        foodSources.add(new FoodSource("foodSource3", 10));
        foodSources.add(new FoodSource("foodSource4", 12));
        foodSources.add(new FoodSource("foodSource5", 15));
        foodSources.add(new FoodSource("foodSource6", 15));
        foodSources.add(new FoodSource("foodSource7", 15));
        foodSources.add(new FoodSource("foodSource8", 20));
        foodSources.add(new FoodSource("foodSource9", 25));
    }

If the players level is 10, it would retrieve foodSource1, foodSource2, and foodSource3.

If the players level is 11, it would retrieve foodSource1, foodSource2, and foodSource3.

However, if the players level is 12, it would only retrieve foodSource 4.

I'm trying to find an efficient method of doing this. I have considered binary searching the ArrayList, but as far as I know you can only retrieve one element with that.

I have only started programming again about a month and a half ago, so I'm not sure what features within Java I could use here.

Thanks.

Upvotes: 1

Views: 65

Answers (4)

Michael Kreutz
Michael Kreutz

Reputation: 1256

You could create a Map<Integer, List<FoodSource>> levelToFoodSourceMap where you store the relationship between level and available food sources for that level. In addition you could write a method, which given a level returns you the closest lower level to the player level, e.g. 

int closestLowerLevel = findClosestLevel(12);
List<FoodSource> foodSources = levelToFoodSourceMap.get(closestLowerLevel);

Access to the map is in constant time and findClosestLevel might be implemented in O(log(n)).

Upvotes: 2

David Conrad
David Conrad

Reputation: 16359

You could use binary search to find the first entry and then iterate through the list to find the remaining entries. TreeMap has good support for that, but it only maps from one key (one level) to one value, so you'd have to use a List for the values.

void append(TreeMap<Integer, List<FoodSource>> map, int level, FoodSource source) {
    map.putIfAbsent(level, new ArrayList<>());
    map.get(level).add(source);
}

TreeMap<Integer, List<FoodSource>> map = new TreeMap<>();
append(map, 10, new FoodSource("foodSource1", 10));
append(map, 10, new FoodSource("foodSource1", 10));
append(map, 12, new FoodSource("foodSource1", 12));
append(map, 15, new FoodSource("foodSource1", 15));

List<FoodSource> sources = map.floorKey(12).getValue();

However, Guava has a TreeMultimap that handles that for you. The only problem is, it keeps the values in a set rather than a list, so there's no ordering of the items at a given level.

TreeMultimap<Integer, FoodSource> map = TreeMultimap.create();
map.put(10, new FoodSource("foodSource1", 10));
map.put(10, new FoodSource("foodSource1", 10));
map.put(12, new FoodSource("foodSource1", 12));
map.put(15, new FoodSource("foodSource1", 15));

Set<FoodSource> sources = map.get(map.keySet().floor(12));

In each case, floor means get the greatest key less than or equal to the given level, (and could be replaced with ceiling to get the smallest key greater than or equal to the given level).

Upvotes: 0

lettomobile
lettomobile

Reputation: 316

removeIf

You can use this function I wrote which is based on the method mentioned above. The algorithm removes first the objects with a too high level and then the ones with a too low level, at the end you will have a new ArrayList with the desired objects.

Code

public static ArrayList<FoodSource> find(ArrayList<FoodSource> foodSources, int level) {
    ArrayList<FoodSource> fr = new ArrayList<>(foodSources);
    // Removes objects with too high level
    fr.removeIf(n -> n.getLevel() > level);
    int max = 0;
    for (FoodSource foodSource : fr) {
        if (foodSource.getLevel() > max)
            max = foodSource.getLevel();
    }
    int finalMax = max;
    // Removes objects with too low level
    fr.removeIf(n -> n.getLevel() < finalMax);
    return fr;
}

Note how I created a new ArrayList to not modify the original.

Upvotes: 0

Rubydesic
Rubydesic

Reputation: 3476

The correct data structure for doing this is a TreeMap, which is a binary tree.

This answer provides the information you're looking for.

If you do not use a TreeMap, you will have to settle for O(n) search.

int toSearch = 11;
int min = Integer.MAX_VALUE;
List<FoodSource> found = new ArrayList<>();
for (FoodSource source : foodSources) { 
    int dist = Math.abs(toSearch - source.level);
    if (dist < min) {
        min = dist;
        found.clear();
        found.add(source);
    } else if (dist == min) {
        found.add(source)
    }
}

(This will also retrieve foodSource4, because it is equidistant, unsure what behaviour you desire in that scenario)

Upvotes: 2

Related Questions