How to get one element from LinkedHashSet in Java?

Question

I'm looking to write code that partitions a given set into disjoint subsets. For example, a set of football players and we partition them depending on the team they belong to. I want in the end a list of representatives, i.e. one player from each team.

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

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

However, it feels weird to build a new iterator in every step of the while-loop. A LinkedHashSet is supposed to have some kind of firstElement() function internally (for its LinkedList behaviour), but for some reason I can't find how to do this. I also tried a foreach loop instead, but that resulted in a java.util.ConcurrentModificationException.

How am I supposed to do this correctly?

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 edit and understanding better, here's a solution you might 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();

Note that, without knowing anything more about the definition of "similar", this problem is inherently quadratic. The only way it could be made linear, or sub-quadratic, is if there was a way to hash similar elements to the same key. In that case, you could use the second strategy above, but modify the processed structure and the part that checks for previous similar elements to be more efficient (currently that step is linear in the number of similar groups, which could be linear in total elements).

Additionally, anything that's sub-quadratic will surely use more than constant memory. If you want constant memory, this is about the best you can do (it's definitely 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 concurrent modification problem you had previously.