Re: interval intersection

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:

(* Gets intersection of specified intervals.  Calculates the
intersection [lower, upper] of the intervals [lower1, upper1] and
[lower2, upper2].  The flag empty is set to TRUE if the intersection
is empty. *)

   PROCEDURE GetIntersection(lower1, upper1, lower2, upper2: LONGINT;
                             VAR lower, upper: LONGINT;
                             VAR empty: BOOLEAN);
   BEGIN
      IF (upper1 < lower2) OR (upper2 < lower1) THEN empty := TRUE
      ELSE
         IF lower1 > lower2 THEN lower := lower1
         ELSE lower := lower2
         END;
         IF upper1 < upper2 THEN upper := upper1
         ELSE upper := upper2
         END;
         empty := FALSE;
      END
   END GetIntersection;



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).

> 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;


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. 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;


August
.

Relevant Pages

  • Re: Trees
    ... :class node <super var \ info in super var ... \ all nodes start out empty, ... newNode put: Lchild ... IF exit THEN ...
    (comp.lang.forth)
  • Re: Remove Empty Tags on page
    ... I am dealing with a page spit out by .NET that leaves empty ... The .NET will leave behind any combination of nested tags. ... whose textContent or innerText is empty? ... var node, nodes = document.getElementsByTagName; ...
    (comp.lang.javascript)
  • Re: [PHP] isset
    ... Put var has no data it still says it is set. ... in that particular line of code the isset is a pointless waste of cycles. ... these two lines are not the same infact, with the first, you will not get a E_NOTICE warning, but with the second you will. ... The empty function does not raise a notice if its argument does not exist. ...
    (php.general)
  • Re: Remove Empty Tags on page
    ... Even though the tags are not empty, ... var w = document.createTreeWalker( ... These two solutions work because in reverse document order, ...
    (comp.lang.javascript)
  • Re: RegExp as Finite State Machine
    ... but it is not online yet. ... ECMAScript values have such a representation.RegExpobjects, ... But how would you do intersection? ... var hOP = { ...
    (comp.lang.javascript)