\manpage {interval\_set} {I} {Sets of Intervals}
 
\definition
An instance $S$ of the parameterized data type \name\ is a
collection of items ($is\_item$). Every item in $S$ contains a closed
interval of the $double$ numbers as key and an information from data type $I$,
called the information type of $S$. The number of items in $S$ is called
the size of $S$. An interval set of size zero is said to be empty. We use
$\<x,y,i\>$ to denote the item with interval $[x,y]$ and information $i$,
$x$ ($y$) is called the left (right) boundary of the item. For each
interval $[x,y]$ there is at most one item $\<x,y,i\> \in S$.
 
\creation S 
 
\create { }
   { creates an instance \var\ of type \name\ and initializes \var\
            to the empty set. }
 
 
\operations 2.3 5 
 
\op  double left {(is\_item\ it)}
           {  returns the left boundary of item $it$.\\
	     \precond $it$ is an item in \var. }
 
 
\op  double right {(is\_item\ it)}
           {  returns the right boundary of item $it$.\\
	     \precond $it$ is an item in \var. }
 
 
\op  I inf {(is\_item\ it)}
           {  returns the information of item $it$.\\
	     \precond $it$ is an item in \var. }
 
 
\opl is\_item insert {(double\ x, \ double\ y, \ I\ i)}
           {  associates the information $i$ with interval
	     $[x,y]$. If there is an item $\<x,y,j\>$ in \var
	     then $j$ is replaced by $i$, else a new item
	     $\<x,y,i\>$ is added to $S$. In both cases
	     the item is returned. }
 
 
\op  is\_item lookup {(double\ x, double\ y)}
           {  returns the item with interval $[x,y]$
	     (nil if no such item exists in \var). }
 
 
\opl list\<is\_item\> intersection {(double\ a, \ double\ b)}
           {  returns all items $\<x,y,i\>\ \in\ S$ with
	     $[x,y] \cap [a,b] \neq \emptyset$. }
 
 
\op  void del {(double\ x, double\ y)}
           {  deletes the item with interval $[x,y]$ from \var. }
 
 
\op  void del\_item {(is\_item\ it)}
           {  removes item $it$ from \var.\\
	     \precond $it$ is an item in \var. }
 
 
\op  void change\_inf {(is\_item\ it, \ I\ i)}
           {  makes $i$ the information of item $it$.\\
	     \precond $it$ is an item in \var. }
 
 
\op  void clear {()}
           {  makes \var\ the empty interval\_set. }
 
 
\op  bool empty {()}
           {  returns true iff \var\ is empty. }
 
 
\op  int size {()}
           {  returns the size of \var. }
 
 
\implementation
Interval sets are implemented by two-dimensional range trees \cite{Wi85,Lu78}.
Operations insert, lookup, del\_item and del take time $O(\log^2 n)$,
intersection takes time $O(k + \log^2 n)$, where $k$ is the size
of the returned list. Operations left, right, inf, empty, and size
take time $O(1)$, and clear $O(n\log n)$. Here $n$ is always the 
current size of the interval set. The space requirement is $O(n\log n)$.
 
