Re: [PATCH] [merge-tracking] Code clarity fix

"Jonathan Gilbert" <o2w9gs702@sneakemail.com> writes:

> I have been watching this thread for some time now, and it seems that a
> much simpler algorithm could be used for what's needed. Basically, we want
> to merge two ranges if they are touching in any way, right? And it's safe
> to assume that the "end" field will always be >= the "start" field, right?
>
> If so, then consider the following code:
>
> static svn_boolean_t
> range_contains_revision(svn_merge_range_t *range, svn_revnum_t revision)
> {
> return (range->start <= revision) && (range->end >= revision);
> }
>
> static svn_boolean_t
> ranges_are_adjacent(svn_merge_range_t *in1, svn_merge_range_t *in2)
> {
> return (in1->end + 1 == in2->start) || (in2->end + 1 == in1->start);
> }
>
> static svn_boolean_t
> combine_ranges(svn_merge_range_t **output, svn_merge_range_t *in1,
> svn_merge_range_t *in2)
> {
> if (range_contains_revision(in1, in2->start)
> || range_contains_revision(in2, in1->start)
> || ranges_are_adjacent(in1, in2))
> {
> (*output)->start = MIN(in1->start, in2->start);
> (*output)->end = MAX(in1->end, in2->end);
> return TRUE;
> }
>
> return FALSE;
> }
>
> Basically, if the ranges are "touching", then either one of them will start
> in the middle of the other one, or one of them will start immediately after
> the other one. In either case, the start & end can be computed in the same
> way.
>
> Are there any holes in this? If not, I think it's a lot more readable than
> what's currently in mergeinfo.c on the merge-tracking branch. :-)

I haven't been following the merge tracking stuff, but detecting
overlapping ranges is notorious for being both tricky and simple: it's
tricky to get the algorithm right, but the right algorithm is simple.

static svn_boolean_t
combine_ranges(svn_merge_range_t **output,
               svn_merge_range_t *in1,
               svn_merge_range_t *in2)
{
   if (in1->start <= in2->end + 1 && in2->start <= in1->end + 1)
     {
       (*output)->start = MIN(in1->start, in2->start);
       (*output)->end = MAX(in1->end, in2->end);
       return TRUE;
     }
   else
     return FALSE;
}

A discussion of the algorithm is here:

http://c2.com/cgi-bin/wiki/fullSearch?TestIfDateRangesOverlap

-- 
Philip Martin
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org