# How can this code become cleaner and less error prone? Especially the binary search part

How could this code become cleaner?
I think that the way I handle the interfaces and binary search could be improved.
I am trying to understand how to structure such a code 9and usage of APIs) in a cleaner and more efficient manner.

This code solves the problem of finding the max subset of non-overlapping intervals
I especially believe the way I handle the binary search result is error prone.

``````private boolean nonOverlapping(Pair interval, SortedSet<Pair> selectedIntervals) {
if(selectedIntervals.isEmpty())
return true;
if(selectedIntervals.contains(interval)){
return true;
}
Pair[] sortedSelections = selectedIntervals.toArray(new Pair[0]);
int pos = Arrays.binarySearch(sortedSelections, interval, new Comparator<Pair>() {

@Override
public int compare(Pair o1, Pair o2) {
return o1.getStart() - o2.getEnd();
}
});
pos = (-pos) -1;
if(pos == sortedSelections.length){
if(sortedSelections[pos - 1].getEnd() < interval.getStart()){
return true;
}

}
else if(sortedSelections[pos].getEnd() > interval.getStart()){
if(pos + 1 < sortedSelections.length){
if(sortedSelections[pos + 1].getEnd() < interval.getStart()){
return false;
}
}
if(pos - 1 >= 0){
if(sortedSelections[pos - 1].getEnd() < interval.getStart()){
return false;
}
}
return true;
}

return false;
}
``````
-
docs.oracle.com/javase/6/docs/api/java/util/… "The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.) The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0." – abuzittin gillifirca Jan 21 at 9:38
One small simplification is assigning `interval.getStart()` to a variable: `int intervalStart = interval.getStart()`, so you aren't calling the method every time and its easier to read. – Knownasilya Jan 21 at 15:41
If you can, I'd also put this method under `Pair` class, so you have `interval.overlaps( selectedIntervals );`. – Knownasilya Jan 21 at 15:56

I see three points of improvement:

1. The isEmpty check is redundant can be removed. The contains will handle the scenario your are checking for.
2. The Comparator really clutters things up, and since you already have a SortedSet coming in, I know you have another compareTo method somewhere else. If Pair is one of your classes, go ahead and make it implement Comparable so you don't have to worry about rewriting comparison logic everywhere.
3. Your conditional block could be simplified if you only look for your failure cases. In cases like this, I usually step back and start by writing our pseudo code for these complex boolean constructs and let loose with DeMorgan's law.

Here's a pastebin with my changes. It takes you down from 35 loc to 19 loc. http://pastebin.com/NpSHemqP

--edit-- Wrong sleep deprived academic reference.

-
Good use of comments. Minor mistake (`getStart` should be `getStart()`). And could the last inner `if` statement be rewritten as `return sortedSelections[pos].getStart <= interval.getEnd()`? – Dave Jarvis Jan 21 at 17:18
As for that '<=', OP is going to have to weigh in on what actually constitutes an overlap. Actually, I like the Pair.overlaps() proposal @Knownasilya made above. Then one could get free this code from that complexity. – matt.moser Jan 21 at 17:48

Write tests covering all branches and all border cases. Afterwards you can happily try to merge your if branches and start other optimizations.

-
This is my attempt to code a solution to a classic algorithmic problem.I understand how I can write cleaner code.So I don't see how your answer helps me here – user384706 Jan 20 at 9:33
Right from looking at the code I had the feeling that there might be some if branches able to be merged to one. I have no time to write some tests and check this. You could also try to minimize your logic with a Karnaugh map. If this is already the minimum amount of conditions, than there is nothing you can do (beside extracting a method or create temporary variable for your conditions to improve the readability.) – mnhg Jan 20 at 9:58