Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Getting an arbitrary element from a set

Tags:

java

In many algorithm, you're supposed to iterate over a set of elements, while the set is not empty.

Since you might change the set while iterating it, you typically pull an element out of the set, and then do the iteration, possibly adding or removing elements to or from the set. Here is a typical Java code to do that.

Set<Integer> possibleFactors = Sets.newHashSet(2,3,4,5,6,7,8,100);
while (!possibleFactors.isEmpty()) {
    int factor = possibleFactors.iterator().next();
    for (int i=1;i<10;i++) possibleFactors.remove(i*factor);
}

edit: As asked in the comments, I'll give a better example. I'm iterating through files the user have chosen, and I'm filtering them by checking the permissions of each item. However, as an optimization, if the user don't have permission for a certain directory, I'll remove all the files in it from the set.

Set<Path> input = Sets.newHashSet(userSelectedPaths);
while (!input.isEmpty()) {
    Path path = input.iterator.next();
    input.remove(path);
    if (!expensivePermissionCheck(path)) {
        input.removeAll(path.getFiles());
    } else {
        processPath(path);
    }
}

However the first line in the loop looks weird. It creates a superfluous Iterable objects, when all I want is an arbitrary element from the set, I don't care in which order.

Except the performance, it looks kind of weird, and less readable.

Is there a better alternative? Maybe a different structure altogether?

edit: maybe a better formulation would be "How do I pop arbitrary element from a set?"

like image 303
Elazar Leibovich Avatar asked Sep 04 '11 11:09

Elazar Leibovich


1 Answers

The only access methods for the Set interface are via the iterator() method or the toArray() method.

If you have a SortedSet you can use first() or last() method to access one item directly.

like image 145
Howard Avatar answered Sep 30 '22 11:09

Howard