Skip to content

Instantly share code, notes, and snippets.

@cky
Created April 29, 2012 14:48
Show Gist options
  • Save cky/2550918 to your computer and use it in GitHub Desktop.
Save cky/2550918 to your computer and use it in GitHub Desktop.
Java comm(1) implementation
import java.util.List;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterators;
import com.google.common.collect.PeekingIterator;
public class Comm {
public static class Result {
public final ImmutableList<Integer> only1;
public final ImmutableList<Integer> only2;
public final ImmutableList<Integer> both;
public Result(ImmutableList<Integer> only1, ImmutableList<Integer> only2,
ImmutableList<Integer> both) {
this.only1 = only1;
this.only2 = only2;
this.both = both;
}
}
public static Result comm(List<Integer> list1, List<Integer> list2) {
ImmutableList.Builder<Integer> only1 = ImmutableList.builder(),
only2 = ImmutableList.builder(), both = ImmutableList.builder();
PeekingIterator<Integer> iter1 = Iterators.peekingIterator(list1.iterator()),
iter2 = Iterators.peekingIterator(list2.iterator());
while (true) {
if (!iter1.hasNext()) {
only2.addAll(iter2);
break;
}
if (!iter2.hasNext()) {
only1.addAll(iter1);
break;
}
int x = iter1.peek(), y = iter2.peek();
if (x < y) {
only1.add(x);
iter1.next();
} else if (y < x) {
only2.add(y);
iter2.next();
} else {
both.add(x);
iter1.next();
iter2.next();
}
}
return new Result(only1.build(), only2.build(), both.build());
}
public static void main(String... args) {
Result result = comm(ImmutableList.of(1, 2, 3, 5, 8, 13),
ImmutableList.of(2, 3, 5, 7, 11, 13));
System.out.printf("Only in list 1: %s%n" +
"Only in list 2: %s%n" +
"In both lists: %s%n",
result.only1,
result.only2,
result.both);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment