\begin{minipage}[t]{8in} \begin{tabular}{ll} virtual & \verb+~+\Collection$<$item$>$\index{Collection!\verb+~+\Collection$<$item$>$}() \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}The virtual destructor in the \Collection\ class ensures that the proper subclass destructor will be called when the object referenced or pointed to is deleted. The new data structure must define its own destructor (or inherit one from a parent \Collection).\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} int & size\index{Collection!size}() const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Return the number of stored elements.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} Bool & emptyQ\index{Collection!emptyQ}() const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Return TRUE if there are no stored elements.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} Bool & fullQ\index{Collection!fullQ}() const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Return TRUE if there are no space left for additional elements.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} Bool & memberQ\index{Collection!memberQ}(const Item\&e) const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Return TRUE if $e$ is stored.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} Bool & sortedQ\index{Collection!sortedQ}() const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Does the \Container\ used to store the elements store them in sorted order?\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} DataType & type\index{Collection!type}() const = 0; \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{Collection!first}() const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Return the first element in the \Container\ in which the \Collection\ stores its elements.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} Item & last\index{Collection!last}() const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Return the last element in the \Container\ in which the \Collection\ stores its elements.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} void & insert\index{Collection!insert}(Item e) = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Insert $e$ into the \Container\ in which the \Collection\ stores its elements.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} void & append\index{Collection!append}(Item e) = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Insert $e$ as the last element of the \Container\ which stores the elements if this is possible. Otherwise, i.e. the \Container\ is sorted, just call insert()\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} void & remove\index{Collection!remove}(Item e) = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Remove $e$ from the \Container\ in which the \Collection\ stores its elements.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} void & clear\index{Collection!clear}() = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Remove all elements from the \Container\ used to store the elements.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} int & iterate\index{Collection!iterate}(Iterator$<$Item$>$\& it, Item\& e) const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}This method is used by \Iterator\ objects to obtain the successor of $e$. Typically, a \Collection\ object will implement this by calling its {\Container}'s iterate() method.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} Item & ref\index{Collection!ref}(int i) = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in} Return the element with index $i$. \end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} int & rank\index{Collection!rank}(Item it) = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in} Return the index of item $it$. \end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} int & occurrences\index{Collection!occurrences}(Item) = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in} Returns the number of occurrences of the passed item. \end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} Bool & subsetQ\index{Collection!subsetQ}(Collection$<$Item$>$\& c) = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Return TRUE if every occurrence of an element $e$ in the current collection is matched with an occurrence of the same element in $c$. \end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} Bool & properSubsetQ\index{Collection!properSubsetQ}(Collection$<$Item$>$\& c) = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in}Return TRUE is the current collection is a subset of $c$ and has fewer elements.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} int & permutationQ\index{Collection!permutationQ}(); \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in} Returns FALSE if duplicate elements exist.\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} void & concatenate\index{Collection!concatenate}(const Collection$<$Item$>$\& = 0); \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{Collection!display}(ostream\&os) = 0; \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} Collection$<$Item$>$* & newEmpty()\index{Collection!newEmpty()} const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in} Dynamically allocates a new \Collection\ of the same type as the current one and returns it. This is useful in copying graphs and other situations, where the only access to the \Collection\ is through a \Collection\ pointer (i.e. the type of \Collection\ is not known). $O(1)$\end{minipage} \end{minipage} \vspace{0.2in} \begin{minipage}[t]{8in} \begin{tabular}{ll} Bool operator==(const Collection$<$Item$>$\&) const = 0; \\ Bool operator$<$=(const Collection$<$Item$>$\&) const = 0; \\ Bool operator$<$ (const Collection$<$Item$>$\&) const = 0; \\ Bool operator$>$=(const Collection$<$Item$>$\&) const = 0; \\ Bool operator$>$ (const Collection$<$Item$>$\&) const = 0; \\ Bool operator!=(const Collection$<$Item$>$\&) const = 0; \\ Bool operator==(const Container$<$Item$>$\&) const = 0; \\ Bool operator$<$=(const Container$<$Item$>$\&) const = 0; \\ Bool operator$<$ (const Container$<$Item$>$\&) const = 0; \\ Bool operator$>$=(const Container$<$Item$>$\&) const = 0; \\ Bool operator$>$ (const Container$<$Item$>$\&) const = 0; \\ Bool operator!=(const Container$<$Item$>$\&) const = 0; \end{tabular}\\ \parbox[b]{2in} \ \ \begin{minipage}[t]{4in} Compare the \Collection\ with a \Collection\ or \Container\ argument (by calling \verb+Container::operator...()+)\end{minipage} \end{minipage} \vspace{0.2in}