\manpage {segment\_set} {I} {Sets of Parallel Segments}
 
\definition
    An instance $S$ of the parameterized data type \name\ is a 
    collection of items ($seg\_item$). Every item in $S$ contains as key a
    line segment with a fixed direction $\alpha$ (see data type segment) and
    an information from data type $I$, called the information type of $S$.
    $\alpha$ is called the orientation of $S$. We use $\<s,i\>$ to denote the
    item with segment $s$ and information $i$. For each segment $s$ there is
    at most one item $\<s,i\> \in S$.
 
\creation S 
 
\create {(double\ a)}
   { creates an empty instance \var\ of type \name\ with orientation
            $a$.  }
 
 
\create { }
   { creates an empty instance \var\ of type \name\ with orientation
            zero, i.e., horizontal segments. }
 
 
\operations 2.7 4.5
 
\op  segment key {(seg\_item\ it)}
           {  returns the segment of item $it$.\\
	  \precond $it$ is an item in \var. }
 
 
\op  I inf {(seg\_item\ it)}
           {  returns the information of item $it$.\\
	  \precond $it$ is an item in \var. }
 
 
\op  seg\_item insert {(segment\ s, \ I\ i)}
           {  associates the information $i$ with segment
	  $s$. If there is an item $\<s,j\>$ in \var  
	  then $j$ is replaced by $i$, else a new item
	  $\<s,i\>$ is added to $S$. In both cases the
	  item is returned. }	
 
 
\op  seg\_item lookup {(segment\ s)}
           {  returns the item with segment $s$ (nil if no
	  such item exists in \var). }
 
 
\op  list\<seg\_item\> intersection {(segment\ q)}
           {  returns all items $\<s,i\>\ \in\ S$ with
	  $s \cap q \neq \emptyset$.\\
	  \precond $q$ is 
	  orthogonal to the segments in \var. }
 
 
\op  list\<seg\_item\> intersection {(line\ l)}
           {  returns all items $\<s,i\>\ \in\ S$ with
	  $s \cap l \neq \emptyset$. \precond $l$ is 
	  orthogonal to the segments in \var. }
 
 
\op  void del {(segment\ s)}
           {  deletes the item with segment $s$ from \var. }
 
 
\op  void del\_item {(seg\_item\ it)}
           {  removes item $it$ from \var.\\
	  \precond $it$ is an item in \var. }
 
 
\opl void change\_inf {(seg\_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 segment\_set. }
 
 
\op  bool empty {()}
           {  returns true iff \var\ is empty. }
 
 
\op  int size {()}
           {  returns the size of \var. }
 
 
\implementation
Segment sets are implemented by dynamic segment trees based on BB[$\alpha$]
trees (\cite{Wi85,Lu78}) trees. Operations key, inf, change\_inf, empty, and 
size take time $O(1)$, insert, lookup, del, and del\_item take time 
$O(\log^2 n)$ and an intersection operation takes time $O(k + \log^2 n)$, 
where $k$ is the size of the returned list. Here $n$ is the current size of 
the set. The space requirement is $O(n\log n)$.
 
