PROLOG SETS-AS-INTERVAL PREDICATES
                              Jocelyn Paine
                  Shelved on the 21st of December 1987


This file defines predicates for manipulating sets of integers,
represented as lists of disjoint intervals. This is a compact way of
representing large sets, provided that they contain few gaps between
intervals.


Here are two examples of the representation:

Set                                         Representation

{ -32768 .. 32767 }                         [ -32768--32767 ]

{ 1,3,4,5,9,10,11,12,15,16,100,101,102}     [ 1--1, 3--5, 9--12, 15--16,
                                              100--102 ]


The predicates in this entry include ones for forming the union,
intersection, and difference of such sets, and for various operations on
single intervals.

For efficiency, I keep sets in a canonical form; one in which the
intervals are disjoint, and are in ascending order, and form a minimal
covering (i.e. there is no other representation of a set, using fewer
intervals). There is a predicate for converting a list of arbitrary
unordered intervals into a canonical form.


I have found the predicates useful when writing programs for
syntax-directed translation of character data. For example, some tag
field on a line may specify that the line is a record of type R1 if the
field lies in the set C1 of characters, or a record of type R2 if the
field lies in the set C2 of characters, and so on. Using these
predicates, I can check for ambiguous specifications by testing whether
C1 and C2 overlap; and I can generate quick tests for whether some
character is in C1 or C2 by knowing that the set are represented by as
few intervals as possible.


SIZE : 26 kilobytes.


CHECKED ON EDINBURGH-COMPATIBLE (POPLOG) PROLOG : yes.


PORTABILITY :

    Easy, no known problems.


INTERNAL DOCUMENTATION :

   Comments for each main predicate; the properties of the
   representation; summary of proofs of correctness.