CODEWITHSUNDEEP
javaalgorithmintersectionintervalsinterval-intersection
BlueLettuce16
BlueLettuce16

Reputation: 2093

Interval intersection

I wrote a class that checks whether two integer intevals overlap. However I don't like this solution to much. I think that it's possible to do it in a better and simpler way.

public class IntegerInterval implements Interval {
private Integer start;
private Integer end;

public IntegerInterval(Integer start, Integer end) {
    this.start = start;
    this.end = end;
}

public Integer getStart() {
    return start;
}

public Integer getEnd() {
    return end;
}

public boolean isOverlapping(IntegerInterval other) {
    if (other != null) {
        return isInInterval(start, other) || isInInterval(end, other)
                || isInInterval(other.start, this) || isInInterval(other.end, this);
    }
    return false;
}

public boolean isInInterval(Integer number, IntegerInterval interval) {
    if (number != null && interval != null) {
        if(interval.getStart() == null && interval.getEnd() != null) {
            return number.intValue() <= interval.getEnd().intValue();
        }
        if(interval.getStart() != null && interval.getEnd() == null) {
            return number.intValue() >= interval.getStart().intValue();
        }
        if(interval.getStart() == null && interval.getEnd() == null) {
            return true;
        }
        return interval.getStart() <= number && number <= interval.getEnd();
    }
    else if(number == null && interval != null) {
        return interval.getStart() == null && interval.getEnd() == null;
    }
    return false;
}

}

Upvotes: 1

Views: 6756

Answers (3)

Hui Zheng
Hui Zheng

Reputation: 10224

The following code should be simpler:

public boolean isOverlapping(IntegerInterval other) {
    if (other == null) return false; // for readability's sake, this condition is pulled out

    // overlap happens ONLY when this's end is on the right of other's start
    // AND this's start is on the left of other's end.
    return (((this.end == null) || (other.start == null) || (this.end.intValue() >= other.start.intValue())) &&
        ((this.start == null) || (other.end == null) || (this.start.intValue() <= other.end.intValue())));
}

UPDATE If compare by Date as @Adam actually asked, the code would be:

private static boolean dateRangesAreOverlaping(Date start1, Date end1,
                                               Date start2, Date end2) {
return (((end1 == null) || (start2 == null) || end1.after(start2)) &&
         ((start1 == null) || (end2 == null) || start1.before(end2)));

}

Upvotes: 3

SpaceTrucker
SpaceTrucker

Reputation: 13556

You should wrap start and end in a specific Comparable class that is able to encapsulate null. This way you only need to invoke compareTo in isInInterval and don't need to bother with null.

That class could also explicitly represent positive and negative infinity.

EDIT:
If you add a type parameter <T extends Comparable<T>> to the class declaration and declare the types of start and end type as Comparable<T> then you can use any type that implements Comparable with your Interval, not only Integer.

Upvotes: 2

Alexei Levenkov
Alexei Levenkov

Reputation: 100547

Assuming start < end. There should be 3 the checks for position of start relative to other: left, middle and right (right is for completeness as there is no intersection possible). So here are 2 remaining checks:

 (start <= other.start && end >= other.start) || 
 (start >= other.start && start <= other.end)  
 // start > other.end means no intersection as end > start > other.end

If you do checks for location of start as if than second chech can be just (start <= other.end):

 if (start <= other.start) return end >= other.start;
 else if (start <= other.end) return true;
 else return false;

Adjust "=" portions for your needs and add you null checks appropriately (i.e. use SpaceTrucker answer to make comaprison with null hidden inside class).

Upvotes: 1

Related Questions