The IntervalList class represents a set of unsigned integers, represented as a series of intervals of integers that belong to the set. It is built on top of a class Interval that represents a single interval. There is also a text representation for IntervalLists. This representation can be used to read or write IntervalList objects to streams, and also can be used in the IntervalList constructor. This text representation looks exactly like the format the "rn" newsreader uses to record which articles have been read in a Usenet newsgroup (which is where we got it from; thank you, Larry Wall). In the text representation, an IntervalList is specified as one or more Intervals, separated by commas. An Interval is either an unsigned integer or two unsigned intervals with an intervening minus sign. Here is one possible IntervalList specification: 1-1003,1006,1008-1030,1050 White space is not permitted in this representation. IntervalList specifiers do not have to be in increasing order, but if they are not, they are changed to "canonical form", in which any overlapping intervals are merged and the intervals are sorted to appear in increasing order. An IntervalList is best thought of as a set of unsigned integers. Its methods in many cases perform set operations: forming the union, intersection, or set difference of two IntervalLists.

*origin*

and a *length,*

and represents the set of *length*

unsigned integers beginning with *origin.*

It also has a pointer that can point to another Interval. The constructorInterval(unsigned origin=0, unsigned length=0,permits all these members to be set. The copy constructor copies the origin and length values but always sets the next pointer to null. A third constructor

Interval* nxt = 0);

Interval(const Interval& i1,Interval* nxt);permits a combination of a copy and a next-pointer initialization. The members

unsigned origin() const;return the origin and length values.

unsigned length() const;

unsigned end() const;The

`end`

function returns the last unsigned integer that is a member of the Interval; 0 is returned for empty Intervals. There are a number of queries that are valuable for building a set class out of Intervals:int isAfter(const Interval &i1) const;

`isAfter`

returns true if this Interval begins after the end of interval *i1*

.int endsBefore(const Interval &i1) const;

`endsBefore`

returns true if this Interval ends strictly before the origin of interval i1.int completelyBefore(const Interval &i1) const;

`completelyBefore`

returns true if `endsBefore`

is true and there is space between the intervals (they cannot be merged).int mergeableWith(const Interval& i1) const;

`mergeableWith`

returns true if two intervals overlap or are adjacent, so that their union is also an interval.int intersects(const Interval& i1) const;

`intersects`

returns true if two intervals have a non-null intersection.int subsetOf(const Interval& i1) const;

`subsetOf`

returns true if the argument is a subset of this interval.void merge(const Interval& i1);

`merge`

alters the interval to the result of merging it with *i1.*

It is assumed that `mergeableWith`

is true.Interval& operator&=(const Interval& i1);This Interval is changed to the intersection of itself and of

*i1.*

IntervalList();The default constructor produces the empty IntervalList.

IntervalList(unsigned origin,unsigned length);This constructor creates an IntervalList containing

*length*

integers starting with *origin.*

IntervalList(const char* definition);This constructor takes a definition of the IntervalList from the string in

*definition,*

parses it, and creates the list of intervals accordingly. There is also a copy constructor, an assignment operator, and a destructor.int contains(const Interval& i1) const;The

`contains`

method returns 0 if no part of *i1*

is in the IntervalList, 1 if *i1*

is completely contained in the IntervalList, and -1 if *i1*

is partially contained (has a non-null intersection).IntervalList& operator|=(const Interval& src);Add a new interval to the interval list.

IntervalList& operator|=(const IntervalList& src);Sets the IntervalList to the union of itself and

*src.*

IntervalList operator&(const IntervalList& arg) const;The binary

`&`

operator returns the intersection of its arguments, which are not changed.IntervalList& subtract(const Interval& i1);Subtract the Interval

IntervalList& operator-=(const Interval& i1);

*i1*

from the list. That is, any intersection is removed from the set. Both the `subtract`

and `-=`

forms are equivalent.IntervalList& operator-=(const IntervalList &arg);This one subtracts the argument

*arg*

from the list (removes any intersection).int empty() const;Return

`TRUE`

(1) for an empty IntervalList, otherwise `FALSE`

(0).`next()`

or `++`

function returns a pointer to the next contained Interval; `reset`

goes back to the beginning.ptolemy@eecs.berkeley.edu