Reputation: 19050
In addition to this question Find number range intersection I want to get the intersection range of 2 time ranges. So my question is
What is the efficient mathematical/algorithmic way to get the time range of the intersection of two number ranges ?
Upvotes: 1
Views: 1355
Reputation: 5714
If someone needs the javascript version is here:
function findRangeIntersection(a1, a2, b1, b2) {
if (Math.max(a1, b1) <= Math.min(b2, a2)) {
return Math.min(a2, b2) - Math.max(a1, b1);
}
return Number.NaN;
}
Upvotes: 0
Reputation: 1479
This pseudo-C should do the trick:
R_TYPE Intersection(P_TYPE start1, P_TYPE start2, P_TYPE end1, P_TYPE end2)
{
if(max(start1, start2) <= min(end1, end2))
{
return( min(end1, end2) - max(start1, start2) );
}
return(DISJOINT);
}
R_TYPE is your 'custom' return type, P_TYPE is your 'custom' parameter type. You can set them to any valid signed scalar number type (int, float, etc.) Use #define DISJOINT ...
to set DISJOINT to some value that would normally be out of range (-1 or MAX_INT, etc.)
If you have some custom DATE_TIME_TYPE
, you'll have to change this to accommodate that. For instance, if you define a struct like:
typedef union
{
unsigned char date_time[7];
struct
{
unsigned char second;
unsigned char minute;
unsigned char hour;
unsigned char day;
unsigned char month;
unsigned int year;
}
}DATE_TIME_TYPE;
You might still be able to get by doing a straight comparison between values (assuming little-endian and 8-bit addressing), but you'll have to account for carries and underflow when subtracting individual days, minutes, etc.
Upvotes: 2
Reputation: 799550
Subtract each of the endpoints of the first range from each of the endpoints of the second range. If you have:
All results are 0: the most degenerate ranges ever
vectors = (
((1, 3), (2, 4), '2-3'),
((1, 4), (2, 3), '2-3'),
((1, 2), (3, 4), 'Disjoint'),
((2, 4), (1, 3), '2-3'),
((2, 3), (1, 4), '2-3'),
((3, 4), (1, 2), 'Disjoint'),
)
for a, b, c in vectors:
print c, a, b
for x in a:
for y in b:
print x, y, x-y
Upvotes: 0
Reputation: 19050
public BTraceStatsTimeRange getOverlap(BTraceStatsTimeRange other) {
if (!intersect(other)) {
return NULL;
}
long startOther = other.start;
long endOther = other.end;
long minEnd = Math.min(end, endOther);
long maxStart = Math.max(start, startOther);
return new BTraceStatsTimeRange(Math.min(minEnd, maxStart), Math.max(
minEnd, maxStart));
}
I am tired today .... ;-)
Upvotes: 2