How to get one item from LinkedHashSet in Java?

Question

I am looking to write code that breaks a given set into disjoint subsets. For example, a set of football players, and we share them depending on the team to which they belong. I want, after all, a list of representatives, i.e. One player from each team.

All football players know all the other players in their team - this is very important for complexity. So, my current idea on how to do this is as follows (where set is currently LinkedHashSet<T> ):

 while (!set.isEmpty()) { E e = set.iterator().next(); makeRepresentative(e); set.remove(AllPlayersOnSameTeamAs(e)); } 

However, it seems strange to create a new iterator at every step of the while loop. It is assumed that LinkedHashSet has some kind of firstElement() function inside (for LinkedList behavior), but for some reason I cannot find how to do this. I also tried the foreach loop, but this led to java.util.ConcurrentModificationException .

How should I do it right?

Answer 1

 while (!set.isEmpty()) { Collection<E> toBeRemoved = new ArrayList<E>(); E first = set.iterator().next(); doSomethingWith(e); for (E e : set) { if (similar(first, e)) toBeRemoved.add(e); } set.removeAll(toBeRemoved); } 

After reading your editing and understanding better, here is a solution you may like:

 Collection<E> processed = new ArrayList<E>(); for (E e1 : set) { boolean similar = false; for (E e2 : processed) { if (similar(e1, e2)) similar = true; } if (!similar) { doSomethingWith(e1); processed.add(e1); } } set.clear(); 

Please note that, knowing nothing more about the definition of "similar," this problem is inherently quadratic. The only way to make it linear or sub-quadratic is if there was a way to smooth similar elements with the same key. In this case, you can use the second strategy above, but change the processed structure, and the part that will verify that the previous similar elements will be more effective (currently this step is linear in the number of similar groups that can be linear in common elements).

In addition, everything that is sub-quadratic will undoubtedly use more than read-only memory. If you want to have read only memory, this is the best thing you can do (this is definitely a quadratic time):

 while (!set.isEmpty()) { Iterator<E> iter = set.iterator(); E first = iter.next(); doSomethingWith(first); while (iter.hasNext()) { if (similar(first, iter.next())) iter.remove(); } } 

Note that using iter.remove () fixes the parallel modification problem you previously had.

Answer 2

I would do it in one go, tracking the teams I saw.

 Set<Team> processedTeams = new HashSet<>(); Set<Players> representatives = new HashSet<>(); for(e:players) { Team t = e.getTeam(); if(processedTeams.contains(t)) continue; processedTeams.add(t); representatives.add(e) }