4

I'm programming an algorythm which is going to receive rows from a database, those rows will be defined within an object that has attributes that identify them and a "ranking" attribute. I have to use a collection (or find a way) to keep all those objects sorted by the ranking value, HOWEVER if I receive another object that is equal to other already in the collection (except for the ranking), I need to update the ranking value (adding up both objects' rankings) and keep the collection sorted.

I was thinking about a TreeSet, but there's no way I can update a value that is not on the root...

Okay let's say my collection is like:

(name='Federer', id='131', ranking='3000')
(name='Nadal', id='234', ranking='2500')
(name='Del Potro', id='180', ranking='1800')

If I receive this:

(name='Nadal', id='234', ranking='1000')

The collection should end up like this:

(name='Nadal', id='234', ranking='3500')
(name='Federer', id='131', ranking='3000')
(name='Del Potro', id='180', ranking='1800')

Thanks a lot in advance.

Manu Carba
  • 139
  • 2
  • 8
  • 5
    Give us please the example of the structure, and what expected result the update gives and your attempt to solve this issue. :)) – Nikolas Charalambidis May 22 '18 at 21:40
  • You can try using a PriorityQueue, just keep in mind that you will need to re-insert Nadal with the new ranking. I can elaborate if it makes sense to you.. – ronhash May 22 '18 at 21:45
  • @ronhash how do I retrieve Nadal though? If he's not at the start of the queue. – Manu Carba May 22 '18 at 21:47
  • Why can you not use a `TreeSet` for this? – pavlos163 May 22 '18 at 21:51
  • @pavlos163 same problem as Queue. How do I do it if the Object I'm looking for is not on the root? – Manu Carba May 22 '18 at 21:52
  • couldn't you just sort the query in a way you could accumulate rakings by person "before" adding them to the TreeSet? – AlbertoLopez May 22 '18 at 21:54
  • You can do it, but at o(n)... I guess that's not what you're looking for? – ronhash May 22 '18 at 21:54
  • Maybe creating a HashTable/Map having value as the ranking and then iterate a view of it, selecting and deleting the highest entries as I have to show them? The whole algorythm is executed after a button is pressed (it's a search engine). But I'm not sure if this is an efficient way. I mean the amount of entries won't surpass 300. My teacher recommended me Trees though, maybe he wasn't aware of these conditions. – Manu Carba May 22 '18 at 21:57

3 Answers3

1

I've done some experimenting with TreeSet and TreeMap, but couldn't really find anything interesting for your situation. Depending on how often you add elements to the collection, it might be best to just use a HashMap and sort it when necessary.

For it to be more efficient, you could even keep track of some boolean flag that denotes that the HashMap is in a sorted state (if the Map is already sorted, then there's no need to sort it again if nothing has changed!).

var map = new HashMap<Element, Integer>();

map.put(new Element("Federer", 131), 3000);
map.put(new Element("Nadal", 234), 2500);
map.put(new Element("Del Potro", 180), 1800);

map.forEach((k, v) -> System.out.println(k + "=" + v));

System.out.println();

map.merge(new Element("Nadal", 234), 1000, Math::addExact);

map.entrySet()
   .stream()
   .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
   .forEach(System.out::println);

Output:

[Federer, 131]=3000
[Nadal, 234]=2500
[Del Potro, 180]=1800

[Nadal, 234]=3500
[Federer, 131]=3000
[Del Potro, 180]=1800

Note: I defined a class Element with a name and id field and use those fields when overriding Object#equals and Object#hashCode.

Jacob G.
  • 28,856
  • 5
  • 62
  • 116
0

You said in the comments that your teacher recommended trees, but I don't see how you could use TreeSet or TreeMap classes for that (at least as they are).

  • TreeMap keeps the ordering by keys (which in your case are ids), whereas you want to order the entries based on their rankings.
  • TreeSet, on the other hand, needs some property that would help it compare two entries against each other, to only keep the ones that are unique (since it is a set). If you want to compare based on rankings, then if two rankings are equal, the treeset will think that the two entries are equivalent (which might not be true). If you compare based on ids, then it will be sorted according to the ids and not rankings.

I think the easiest for you will be to store entries in a HashMap. And then when you need a sorted list, you can call values() on the hashmap, sort them and then display. You also mentioned that the number of entries won't surpass 300, so sorting should be very fast anyways.

kimalser
  • 303
  • 1
  • 4
  • 10
0

You can keep a live map of ranking by ID, and use that as the basis for a priority queue to keep items sorted:

Map<Integer, Integer> rankingById = new HashMap<>();
Queue<Integer> idsByRanking = new PriorityQueue<>(
        Comparator.comparing(rankingById::get).reversed());

void addItem(Item item) {
    Integer id = item.getId();
    idsByRanking.remove(id);
    rankingById.merge(id, item.getRanking(), Integer::sum);
    idsByRanking.add(id);
}

It's necessary to remove the item before updating the ranking so it can be reinserted at the correct position. See also: Updating Java PriorityQueue when its elements change priority

shmosel
  • 49,289
  • 6
  • 73
  • 138