PROLOG SETS-AS-INTERVAL PREDICATES
Jocelyn Ireson-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.