\begin{minipage}[t]{8in}
\begin{tabular}{ll}
virtual  & \verb+~+\MSetBase$<$Item,Impl$>$\index{MSet!\verb+~+\MSetBase$<$Item,Impl$>$}()
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Decrement the reference count of the \Container\ 
			which stores the elements (this container object
			is called \verb+store+).  $O(1)$. 
			If the count reaches 0, delete the object. $O(n)$\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & size\index{MSet!size}() const;
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the number of stored elements by calling 
			   \rar{store}{size()}.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & emptyQ\index{MSet!emptyQ}() const;
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return TRUE if there are no stored elements
				(call \rar{store}{emptyQ()}). \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & fullQ\index{MSet!fullQ}() const;
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return TRUE if there are no space left for 
			  additional elements (call \rar{store}{fullQ()}).\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & memberQ\index{MSet!memberQ}(const Item\&e) const;
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return TRUE if $e$ is stored
			     (call \rar{store}{memberQ()}).\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & sortedQ\index{MSet!sortedQ}(const Item\&e) const;
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return TRUE if \verb+store+ is stored
			     (call \rar{store}{sortexQ()}).\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
DataType  & type\index{MSet!type}() const;
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the type of this structure 
				({\em DataType} is
				an enumerated type defined in general.h).\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Item  & first\index{MSet!first}() const;
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the first element in \verb+store+
				(call \rar{store}{first()}).\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Item  & last\index{MSet!last}() const;
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return the last element in \verb+store+
				(call \rar{store}{last()}).\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & insert\index{MSet!insert}(Item e);
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}If the reference count of \verb+store+ is greater
			   than 1, then other collection objects are also 
			   using
			   it as their implementation.  Rather than changing
			   its contents, a copy will be made ($O(n)$), 
			   and the reference
			   counts will be updated.  Finally,
			   Call \rar{store}{insert(e)}. to insert $e$.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & append\index{MSet!append}(Item e);
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}After considering reference counts as above, 
			   call \rar{store}{append(e)}. to insert $e$ at
			   the end, if sorted order permits (see 
			   \SortedList).  \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & remove\index{MSet!remove}(Item e);
\end{tabular}\\
 
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}After considering reference counts as above, 
			   remove $e$ from \verb+store+.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & clear\index{MSet!clear}();
\end{tabular}\\
 	
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}After considering reference counts as above, 
			   remove all elements from \verb+store+.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & iterate\index{MSet!iterate}(Iterator$<$Item$>$\& it, Item\& e) const;
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Return \rar{store}{iterate(it,e)}.  Note that 
			  some typecasting is required, as {\em iterate()}
			  is not a publically-accessible member of any of
			  the descendants of \Container.\  The {\em iterate()}
			  method needn't ever be called by the programmer;
			  use \Iterator\ objects. \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Item  & ref\index{MSet!ref}(int i);
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Return the element with index $i$. $O(n)$\end{minipage}
\end{minipage}
\vspace{0.2in}
 

\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & rank\index{MSet!rank}(Item it);
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Return the index of item $it$. $O(n)$\end{minipage}
\end{minipage}
\vspace{0.2in}
 

\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & occurrences\index{MSet!occurrences}(Item);
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Returns the number of occurrences of the passed
			  item by iterating through all of the elements. 
			  $O(n)$\end{minipage}
\end{minipage}
\vspace{0.2in}
 

\begin{minipage}[t]{8in}
\begin{tabular}{ll}
int  & permutationQ\index{MSet!permutationQ}();
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Returns FALSE if duplicate elements exist.
			  $O(n)$ if \verb+store+ is a sorted \Container.
			  $O(n^2)$ otherwise.\end{minipage}
\end{minipage}
\vspace{0.2in}
 

\begin{minipage}[t]{8in}
\begin{tabular}{ll}
void  & concatenate\index{MSet!concatenate}(const Collection$<$Item$>$\&);
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Add the elements of the passed \Collection\ 
			  by iterating through them and using append().\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
ostream\&  & display\index{MSet!display}(ostream\&os);
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} This
			 will be called when 
			{\em operator$<$$<$(ostream\&,Collection$<$Item$>$\&)} 
			 is invoked.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool operator==(const Collection$<$Item$>$\&) const; 
  \\
Bool operator$<$=(const Collection$<$Item$>$\&) const; 
  \\
Bool operator$<$ (const Collection$<$Item$>$\&) const; 
  \\
Bool operator$>$=(const Collection$<$Item$>$\&) const; 
  \\
Bool operator$>$ (const Collection$<$Item$>$\&) const; 
  \\
Bool operator!=(const Collection$<$Item$>$\&) const;
  \\
Bool operator==(const Container$<$Item$>$\&) const; 
  \\
Bool operator$<$=(const Container$<$Item$>$\&) const; 
  \\
Bool operator$<$ (const Container$<$Item$>$\&) const; 
  \\
Bool operator$>$=(const Container$<$Item$>$\&) const; 
  \\
Bool operator$>$ (const Container$<$Item$>$\&) const; 
  \\
Bool operator!=(const Container$<$Item$>$\&) const;
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Return \rar{store}{operator...(..)}. \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & eq\index{MSet!eq}(const MSetBase$<$Item,Impl$>$\&s);
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} This alternative to \verb+operator==(...)+ is provided
			  for access from the TCL interface. \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool  & neq\index{MSet!neq}(const MSetBase$<$Item,Impl$>$\&s);
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} This alternative to \verb+operator!=(...)+ is provided
			  for access from the TCL interface. \end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
MSetBase$<$Item,Impl$>$ unions(Collection$<$Item$>$\& c);
\\
MSetBase$<$Item,Impl$>$ operator+(Collection$<$Item$>$\& c);
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Construct the union of the current multiset and $c$ as a
		{\em MSetBase$<$Item,Impl$>$} object.  The number of occurrences
		of an element in the union is the sum of the numbers of 
		occurrences in the two original multisets.  Note however that
		if the object receiving the return value of this method is
		a \SetBase\ or \Set\ object, duplicates are removed. 
		$O(n^2)$
		if either of the \Collections are unsorted, $O(n)$ otherwise.
		(the $O(n^2)$ could be improved with a more involved 
		implementation which builds frequency tables.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
MSetBase$<$Item,Impl$>$ intersection(Collection$<$Item$>$\& c);
\\
MSetBase$<$Item,Impl$>$ operator\^{}(Collection$<$Item$>$\& c);
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Construct the intersection of the current multiset and $c$
		as a {\em MSetBase$<$Item,Impl$>$} object.  The number of 
		occurrences of an element $e$ in the result is the minimum
		of the numbers of occurrences of $e$ in the two original
		mutlisets. 
		$O(n^2)$
		if either of the \Collections are unsorted, $O(n)$ otherwise.
		(the $O(n^2)$ could be improved with a more involved 
		implementation which builds frequency tables.\end{minipage}
\end{minipage}
\vspace{0.2in}


\begin{minipage}[t]{8in}
\begin{tabular}{ll}
MSetBase$<$Item,Impl$>$ difference(Collection$<$Item$>$\& c);
\\
MSetBase$<$Item,Impl$>$ operator-(Collection$<$Item$>$\& c);
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Construct the difference between the current multiset and 
		$c$ as a {\em MSetBase$<$Item,Impl$>$} object.  The number of 
		occurrences of an element $e$ in the result ($n\_r(e))$
		is defined as ($n\_\mbox{this}(e) - n\_c(e)))$.
		$O(n^2)$
		if either of the \Collections are unsorted, $O(n)$ otherwise.
		(the $O(n^2)$ could be improved with a more involved 
		implementation which builds frequency tables.\end{minipage}
\end{minipage}
\vspace{0.2in}


 \begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool    & subsetQ\index{MSet!subsetQ}(Collection$<$Item$>$\& c);
\end{tabular}\\

		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return TRUE if every occurrence of an element $e$ in the 
		 current multiset is
		 matched with an occurrence of the same element in $c$.
		 $O(n)$ if both \Collections\ are sorted, otherwise
		 $O(nq)$ where
		 $q$ is the complexity of \rar{store}{memberQ(e)}.\end{minipage}
\end{minipage}
\vspace{0.2in}

		
 \begin{minipage}[t]{8in}
\begin{tabular}{ll}
Bool    & properSubsetQ\index{MSet!properSubsetQ}(Collection$<$Item$>$\& c);
\end{tabular}\\
 
		
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in}Return TRUE is the current multiset is a subset of $c$ and
		 has fewer elements.
		 $O(n)$ if both \Collections\ are sorted, otherwise
		 $O(nq)$ where
		 $q$ is the complexity of \rar{store}{memberQ(e)}.\end{minipage}
\end{minipage}
\vspace{0.2in}

 \begin{minipage}[t]{8in}
\begin{tabular}{ll}
int     & occurrences\index{MSet!occurrences}(Item item);
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Iterate through the list and return the number of
			  occurrences of {\em item}. $O(n)$ \end{minipage}
\end{minipage}
\vspace{0.2in}


 \begin{minipage}[t]{8in}
\begin{tabular}{ll}
ostream\&           & display\index{MSet!display}(ostream\& os) const
\end{tabular}\\
 
			
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Display the multiset on the output stream $os$. 
			  $O(n)$\end{minipage}
\end{minipage}
\vspace{0.2in}

\begin{minipage}[t]{8in}
\begin{tabular}{ll}
Collection$<$Item$>$*  & newEmpty()\index{MSet!newEmpty()} const;
\end{tabular}\\

                        
 \parbox[b]{2in} \ \ 
\begin{minipage}[t]{4in} Dynamically allocates a new \MSetBase\ or 
			  \MSet\ object of the 
                          same type as the current one and returns it.
                          This is useful in copying structures when 
			  the only access to a 
                          \Collection\ is through a \Collection\ pointer
                          (i.e. the type of \Collection\ is not known). $O(1)$\end{minipage}
\end{minipage}
\vspace{0.2in}



