Re: interval intersection

August Karlstrom wrote:

> Chris Dollin wrote:
>> August Karlstrom wrote:
>>
>>
>>>bob@xxxxxxxxxxxxxx wrote:
>>>
>>>>what is the fastest way to find the intersection of two 1-dimensional
>>>>intervals?
>>>>
>>>>here's an example:
>>>>
>>>>interval 1: 0 to 50
>>>>interval 2: 25 to 80
>>>>
>>>>answer: 25 to 50
>>>>
>>>
>>>Here's an implementation in Oberon:

(snipped)

>> Isn't that a little heavweight?
>>
>> def intersection( x1, y1, x2, y2) = (max( x1, x2 ), min( y1, y2 ))
>
> In a high-level functional language with lots of predefined functions,
> of course the definition will be shorter (but also slower).

Each of `max` and `min` is a one-liner, so even if they're not predefined
the definition is /still/ lots shorter.

Whether or not it's /slower/ depends on lots and lots of things, such
as the type structure of the language, whihc aren't visible in the fragment
I wrote above. (For which I have a shortcoded implementation, so it's not
just handwaving.)

> > Also, your procedure doesn't assign to lower/upper if the result is
>> empty, making it easy (when not checking `empty`) to produce garbage;
>> also, since it doesn't deliver any useful result, it doesn't compose
>> (suppose I want the intersection of three intervals); and it requires
>> the invention of not only two integer variables for actual parameters,
>> but also a arguably-redundant boolean variable.
>
> OK, you certainly have a point here. The following version is probably
> better:
>
> (* Gets intersection of specified intervals. Calculates the
> intersection [a, b] of the intervals [a1, b1] and [a2, b2]. If the
> intersection is empty then a > b. *)
>
> PROCEDURE GetIntersection(a1, b1, a2, b2: LONGINT;
> VAR a, b: LONGINT);
> BEGIN
> IF a1 > a2 THEN a := a1 ELSE a := a2 END;
> IF b1 < b2 THEN b := b1 ELSE b := b2 END
> END GetIntersection;

Still doesn't compose.

> I admit that names like upper and lower may be a bit too verbose, but I
> don't think x and y are good names since it makes me think of
> two-dimensional coordinates. I prefer a and b.

I think you're right that x1/2 and y1/2 have too much of the coordinate
flavour.

> Note also that Oberon
> doesn't have built in functions for the minimum/maximum value of
> integers. But of course we can define them in some utility module M. In
> that case the function is as short as
>
> PROCEDURE GetIntersection(a1, b1, a2, b2: LONGINT;
> VAR a, b: LONGINT);
> BEGIN
> a := M.Max(a1, a2); b := M.Min(b1, b2)
> END GetIntersection;

I like that much better. (Min & Max needn't be in a different module,
of course, although they're sufficiently useful that they should be
shared somehow.)

--
Chris "it's all paraphernalia" Dollin
son of a gun, listen to the plants, breathless.
shifting sands - life in the fast lane.
.