The foundation of LINK is a group of templated C++ objects.
These objects are obtained by including their header files from
the \verb+LINK/basic+ directory (see Section~\ref{sec:file-hier}).
There are many examples of programs using the LINK basic objects in the
following sections.  

\section{\Containers}
\label{sec:container}

\Container\ is an abstract base class which is the parent of the following data
structure classes: \Array,\  \BinaryHeap,\  \BinarySearchTree,\  \DList,\  
\List,\  and \RedBlackTree.
This hierarchy of containers is useful because certain common operations 
such as iteration, comparison, and display can be presented to the 
programmer with a common interface,
even though the underlying mechanisms may differ.  In fact, the \Iterator\ 
objects described on page~\pageref{sec:iterator} can operate seamlessly on
both \Containers\ and \Collections\ (see~\ref{sec:collection}).

There are two basic varieties of \Container.
The first variety is templated only by a key field, and currently 
contains \Array,\  \List,\  \DList,\  \SortedArray,\  and \SortedList.
The second variety, dictionaries,
are templated by key and information fields.  This set of classes currently
includes \BinaryHeap,\  \BinomialHeap,\  \BinarySearchTree,\  and \RedBlackTree.
{\em These dictionary structures have not been tested}.

\subsection{Adding New \Containers}

It is straightforward to add new simple \Container\ objects to LINK.  The new
classes must inherit from class \SimpleContainer\ and must be templated 
with a single {\em Item} argument. {\em Item} will be assumed to have the 
following operators defined:
\verb+==+ \verb+<=+ \verb+!=+ \verb+<<+.  In the methods of the new data 
structure class, 
comparisons and output of data items should be carried out using the
following methods of the class {\em ElementOps}, which is the base class
for both \Container\ and \Collection: 
\begin{itemize}
	\item {\em int compareItems(Item, Item)} 
	\item {\em int displayItem(ostream\&, Item)}.
\end{itemize}

These methods should be used instead of the comparison and output operators
because certain very important element types such as {\Vertex}*
and {\Edge}* must be treated as exceptions by the \Container\ and \Collection\
hierarchies.  Mere pointer comparisons are unsatisfactory in these cases,
so specialized methods for these are prototyped in ElementOps.h 
and given definitions in graphTemplate.cc.

\begin{figure}[tbp]
\centerline{\psfig{figure=figures/elementOps.ps,height=2in,width=3.5in}}
\caption{The \ElementOps\ Class}
\label{fig:ElementOps}
\end{figure}

\Containers\ and \Collections\ may be compared using the overloaded C++
operators: \verb+==+, \verb+!=+, \verb+<=+, \verb+<+, \verb+>=+, 
\verb+>$+.  
The comparison is based on 
lexicographic ordering of the \Container/\Collection\ elements.  In 
general, {\em if two objects of class Collection or Container contain the
same elements in the same order, then they are considered equal}.  
Inequalities are decided based upon the lexicographic ordering of the 
individual elements.  An example involving \List\ comparisons is given
in Section~\ref{sec:list}.

Some examples to follow when implementing new \SimpleContainer\ objects are
found in List.h, List.cc, Array.h, and Array.cc in the 
\verb+/include/LINK/basic+ directory.

The following virtual functions define the interface of the \Container\ 
class.  Those that are pure virtual must be given
definitions in the new class, while those with definitions may or may not
be overridden.  For example, {\em Container<Item>::min()} and 
{\em Container<Item>::max()} are implemented by iterating through all 
elements.  If the data structure class stores data in sorted order, these
should be overridden.

\operations

\input{basic/ProgContainer.tbl.tex}
\label{page:container}

\subsection{Iterators}
\label{sec:iterator}

Iteration through \Containers\ and \Collections\ is performed 
by \Iterator\ objects.  These
class instances are constructed with the address of a \Container\ (or
\Collection).  Elements are retrieved subsequently using the $()$ operator,
which returns 1 while elements remain, then returns 0.
For example, consider Figure~\ref{fig:iterator1}.

\begin{figure}[tbp]
\input{examples/basic/ProgIterator1.tex}
\caption{Use of \Iterator}
\label{fig:iterator1}
\end{figure}

More than one iterator may operate on a given \Container\ at
once; however, removal of elements from within the iteration loop can
corrupt the iteration scheme.

Note that \Iterators\ make the definition of copy constructor member 
functions almost trivial.  Any new data structure class may define a
constructor which takes an argument of type ({\Container}$<$Item$>$\&).
The body of the constructor simply iterates through the elements of the
passed \Container\ and inserts them into the structure under 
construction.

\subsubsection{\ContainerNode}

\ContainerNode\ is an abstract base class which serves as parent to 
any node types used by container descendants.  Two examples are the
\ListNode\ class defined in List.h and the \BinaryHeapNode\ class
defined in BinaryHeap.h.

\creation

There are no public constructors defined for ContainerNode.
They can only be created by inserting items into a container.

\operations

\input{basic/ProgContainerNode.tbl.tex}


%===================List====================================
%\newpage

\subsection{\List}
\label{sec:list}

The \List\ class is the most basic linked data structure class in the 
system.  It is templated by element type and it stores its elements in
\ListNodes,\ which can be referenced through \ContainerNode\ pointers.  
Figure~\ref{fig:List1} contains a coding sample showing the 
construction of empty
\Lists\ and some operations with elements and \ContainerNodes.

\begin{figure}[tbp]
\input{examples/basic/ProgList1.tex}
\caption{\List\ objects}
\label{fig:List1}
\end{figure}

Note that receiveing \ContainerNode\ pointers as return values
is useful since they providing entry points into the list and 
enable operations such as {\em predecessor()} and 
{\em successor()} to run in constant time.
When we consider the doubly-linked list (\DList) class, this
feature will also permit constant time linking and unlinking of list nodes.

It is possible to construct new \List\ objects from existing ones using
both \verb+X(const X&)+ constructors and the assignment operator, as
shown in Figure~\ref{fig:List3} below.  
These operations iterate through the source \List, 
inserting elements in the same order into the destination \List.
Note that if this presents an efficiency problem, \Collections\
should be used.  These implement reference counting (see 
Section~\ref{sec:collection}).


\begin{figure}[tbp]
\input{examples/basic/ProgList3.tex}
\caption{\List\ constructors}
\label{fig:List3}
\end{figure}


\Lists\ are the default implementation for \Sequences,\ which will be 
discussed in Section~\ref{sec:sequence}.  The default implementation
for \Sets\ and \MSets\ (multisets) is \SortedList,\ a child class of \List.

{\em When the LINK interface switches to STk, \Lists\ will have special
significance since they will be implemented using the same underlying
memory structure as STk objects}.

\creation

\input{basic/ProgList.crt.tex}

\operations

\input{basic/ProgList.tbl.tex}

%% Users of the link library won't need this.  Programmers can Look at 
%% List.h
%\subsubsection{ListNodes}
%
%ListNode is a subclass of ContainerNode, and should contain subclasses for
%DListNodes and UListNodes.
%
%\creation
%
%There are no public constructors defined for ListNodes.
%They can only be created by inserting items into a list.
%
%\operations
%
%\input{basic/ProgListNode.tbl.tex}

\subsection{\SortedList}

The \SortedList\ class is a straightforward adaptation of \List\
in which elements are inserted in order and searches 
are peformed more efficiently.  \SortedList\ is currently the 
default set implementation (see Page~\pageref{sec:set}).  

As stated above in Section~\ref{sec:container},
the copy construction and assignment operations work the same
way with any combination of
\SimpleContainer\ objects.  The interaction between
\List\ and \SortedList\ in Figure~\ref{fig:List4} 
provides our first example of this.

\begin{figure}[tbp]
\input{examples/basic/ProgList4.tex}
\caption{\List\ and \SortedList}
\label{fig:List4}
\end{figure}

Note that the invariant of lexicographically-ordered storage of 
elements in \SortedList\ is never violated, despite the unordered
source \List. 

Like assignment and initialization, comparison of \Containers\ is
consistent despite \Container\ type.  Unlike assignment and initialization,
though, comparison is consistent accross both \SimpleContainer\ and
\Dictionary\ objects.  For an example, consider the code given 
in Figure~\ref{fig:List5}.

\begin{figure}[tbp]
\input{examples/basic/ProgList5.tex}
\caption{Comparisons of \Containers}
\label{fig:List5}
\end{figure}

\clearpage

The preceding example is interesting because it illustrates comparisons
between elements which happen to be \List\ and \SortedList\ objects.
Remember that two objects of class \Container\ or \Collection\
are considered to be equivalent if they contain equivalent objects in
equivalent order.  Nested iteration is used above to consider all 
possible comparison between three given lists.

In order for the iteration scheme to work, \Container\ pointers 
must have access through the virtual function mechanism to 
the {\em iterate()} method of each class
in the \Container\ hierarchy.  This means that \SortedList\ must
declare \List\ as a \verb+public+ base class even though private
inheritance would be more natural.  Therefore, \SortedList\ must
redefine certain inherited member functions to maintain the 
invariant that elements are stored in lexicographic order.  

The \List\ methods listed in Section~\ref{sec:list} are 
inherited by \SortedList;\ only those redefined are listed below.



\creation

\input{basic/ProgSortedList.crt.tex}

\operations

\input{basic/ProgSortedList.tbl.tex}

\subsection{\DList}

The \DList,\ or doubly-linked list, class is useful for implementing
algorithms in which it is essential that constant-time splicing and
unsplicing of list elements be supported.  The node type used
with this data structure differs from that of \List\ since it contains
a predecessor pointer. However, the \Container\ hierarchy ensures
that objects of class \List\ and \DList\ can interact easily.  
Copy construction, inter-assignment, and comparison of \Container\ 
objects are still automatic.  

Code using \DList\ objects is similar to that using \List\ objects;
most methods are the same (the exceptions are enumerated below).
As with the singly-linked \List\ object, \ContainerNode\ pointers
provide are used by the programmer to keep track of individual nodes,
as shown in Figure~\ref{fig:DList1}.

\begin{figure}[tbp]
\input{examples/basic/ProgDList1.tex}
\caption{\DList }
\label{fig:DList1}
\end{figure}

Some important applications such as bucket sorting require that 
nodes be spliced in and out of various doubly-linked lists very
frequently.  Such applications cannot be implemented efficiently
using singly-linked lists due to the search overhead required to
find predecessors of moving nodes.  The \DList\ class has additional
methods which allow insertion and removal of \ContainerNodes\ from
the \List\ (as opposed to elements), illustrated in 
Figure~\ref{fig:DList3}.

\begin{figure}[tbp]
\input{examples/basic/ProgDList3.tex}
\caption{Special \DList\ operations}
\label{fig:DList3}
\end{figure}

Once again, comparison and display of \SimpleContainer\ objects
is consistent.  The example in Figure~\ref{fig:DList2} 
provides another illustration.

\begin{figure}[tbp]
\input{examples/basic/ProgDList2.tex}
\caption{Comparisons of \List\ and \DList}
\label{fig:DList2}
\end{figure}

\DList\ objects have the same methods as \List\ objects with the 
following exceptions:

\creation

\input{basic/ProgDList.crt.tex}

\operations

\input{basic/ProgDList.tbl.tex}


%==================Deque====================================
%\newpage

\subsection{\Deque}

The \Queue\ and \Stack\ classes are derived from the abstract
base class \Deque,\ which inherits privately from \List\ to 
screen out all operations that allow access to elements other
than the first element.  \Deque\ pointers can be used to point
to either \Stack\ or \Queue\ objects.  This flexibility is helpful
in algorithms such as maximum flow, in which the algorithm user might 
wish to select at run time which storage protocal to use.

Several \List\ operations are allowed through the filter for use by
\Stacks\ and \Queues.\ Those accessible through \Deque\ pointers are
listed below.  
Note that the \verb+X(const X&)+ constructors for \Stacks\ and
\Queues\ are more restricted than those of other \Container\ classes.
Copies are constructed only from like objects, not arbitrary 
\Containers.

\input{basic/ProgDeque.tbl.tex}

\subsubsection{\Queue}

Instances of the \Queue\ class are singly-linked lists restricted to 
FIFO (``first in, first out'') access.  The methods differing from those
of \Deque\ (which are inherited) are listed below.

\creation

\input{basic/ProgQueue.crt.tex}

\operations

\input{basic/ProgQueue.tbl.tex}

%=====================Stack=================================

\subsubsection{Stack}
Like \Queue,\ the \Stack\ class is derived from \Deque\ and redefines 
certain methods.  The elements of the stack are stored using a LIFO
(``last in, first out'') protocol.

\creation

\input{basic/ProgStack.crt.tex}

\operations

\input{basic/ProgStack.tbl.tex}


%==================Array====================================

\newpage

\subsection{Arrays}

Array-based data structures are fast for some applications, but they are
relatively inflexible since the size of the array must be
specified when it is allocated.
The \Array\ class solves this problem by allocating a fixed size
initial array, and doubling it whenever it gets full.
To cost of recopying the current contents is amortized over
the size of the array.

\Array\ objects offer the ability to circumvent 
the standard \Container\ iteration scheme, though the latter still
works.  Since the elements are stored in a contiguous block, it is
much more efficient to iterate through them using pointer arithmetic. 
There is no need to package the data elements in structures from the
\ContainerNode\ hierarchy.
The example in Figure~\ref{fig:Array1} 
illustrates both forms of iteration on the elements
of an \Array\ object:

\begin{figure}[tbp]
\input{examples/basic/ProgArray1.tex}
\caption{Iteration and \Array\ objects}
\label{fig:Array1}
\end{figure}

\creation

\input{basic/ProgArray.crt.tex}

\operations

\input{basic/ProgArray.tbl.tex}

\subsection{\SortedArray}

When elements must be stored in order for efficient searching and 
convenient output, and the number of elements is likely to remain 
relatively stable, \SortedArray\ storage is a good option.  \SortedArray\
is a class derived from \Array\ that restricts insertion to ensure 
that the elements be stored in order.  Binary search then reduces
search time to $O(\log n)$.  \SortedArray\ is the storage medium used
for the vertex set of LINK's graphs.


\begin{figure}[tbp]
\input{examples/basic/ProgArray2.tex}
\caption{\Arrays\ and \SortedArrays}
\label{fig:Array2}
\end{figure}

The methods of \SortedArray\ are listed below.  Any \Array\ method 
not listed or redefined is inherited.

\creation

\input{basic/ProgSortedArray.crt.tex}

\operations

\input{basic/ProgSortedArray.tbl.tex}

%===============Priority Queues========================================

\newpage

\subsection{Priority Queue Dictionary Structures}

%****BoundedPriorityQueue() doesn't exist yet
\subsubsection{\BinaryHeap}

Priority queues are data structures which support fast insertion and
extract-minimum operations.
They are templated on both key and information fields, with the key field
defining where the information sits in the heap.

\begin{figure}[tbp]
\input{examples/basic/ProgBinaryHeap1.tex}
\caption{\BinaryHeap}
\label{fig:BinaryHeap1}
\end{figure}

\begin{figure}[tbp]
\input{examples/basic/ProgBinaryHeap2.tex}
\caption{Another \BinaryHeap\ example}
\label{fig:BinaryHeap2}
\end{figure}


\creation

\input{basic/ProgBinaryHeap.crt.tex}

\operations

\input{basic/ProgBinaryHeap.tbl.tex}

\subsubsection{\BinomialHeap}

\creation

\input{basic/ProgBinomialHeap.crt.tex}

\operations

\input{basic/ProgBinomialHeap.tbl.tex}

\subsection{General Dictionary Structures}

The general dictionary structures allow random access like \Containers\
but allow distinct lookup keys like the priority queue classes.  Theses
classes now include \BinarySearchTree\ and \RedBlackTree,\ though
neither has been well tested or documented.

\begin{figure}[tbp]
\input{examples/basic/ProgBinarySearchTree1.tex}
\caption{\BinarySearchTree}
\label{fig:BinarySearchTree1}
\end{figure}

The examples in Figures~\ref{fig:BinarySearchTree1} and 
\ref{fig:RedBlackTree1} illustrate the use of general dictionary classes.
However, these classes should be used only with caution and the
expectation that bugs may exist.  As with any LINK problem, please report
these problems to Jonathan Berry at \verb+berryj@dimacs.rutgers.edu+.

\begin{figure}[tbp]
\input{examples/basic/ProgRedBlackTree1.tex}
\caption{\RedBlackTree}
\label{fig:RedBlackTree1}
\end{figure}

\newpage

\section{\Collections}
\label{sec:collection}

The \Collection\ hierarchy, shown in Figure~\ref{fig:coll}, provides 
LINK with a flexible core of set and sequence classes that 
interact with each other easily, facilitating the representation of
a rich variety of graphs.

\begin{figure}

\centerline{\psfig{figure=figures/collection_hier.ps,height=3in,width=4.5in}}

\caption{The \Collection\ Hierarchy}
\label{fig:coll}
\end{figure}

\subsection{Discussion}

Objects of classes in the \Collection\ hierarchy can be thought of as
``shells'' surrounding a storage medium from the \Container\ class 
hierarchy.  These shells filter the messages sent to the underlying
\Container\ instance, thus providing a small, clean interface to the
\Container\ hierarchy.  Set primitive operations are defined for any
two objects of the \Collection\ hierarchy. 

\subsubsection{Organization}

Class \Collection\ itself is an abstract base class, meaning that there
are no true ``\Collection'' objects.  However, pointers and references to
sets and sequences of the \Collection\ hierarchy have access to a 
consistent interface, consisting of a set of member function prototypes
and a set of comparison operations.  The term {\em collection objects} 
is used to refer to instances of classes in the hierarchy.

The elements stored in collection objects are considered to come
from a totally ordered universe.  In order to compile an instantiation
of a  collection object with a new element type $A$, the following 
operations must be defined: 

\begin{itemize}
\item \verb+A::int operator==(const A&) const;+
\item \verb+A::int operator<(const A&) const;+
\item \verb+friend ostream& operator<<(ostream&, const A&);+
\end{itemize}

The  collection objects available to the programmer are listed below
and defined completely in the subsections to follow.
\begin{itemize}
\item \verb+MSetBase<Item, Impl> +:  Multiset (the implementation
			can be chosen by the programmer).
\item \verb+SetBase<Item, Impl> +:  Set (the implementation
			can be chosen by the programmer).
\item \verb+SequenceBase<Item, Impl> +:  Sequence (the implementation
			can be chosen by the programmer).
\item \verb+MSet<Iteml>+: Multiset which uses the DEFAULT\_SET\_IMPL defined
			  in MSet.h.
\item \verb+Set<Iteml>+: Multiset which uses the DEFAULT\_SET\_IMPL defined
			  in MSet.h.
\item \verb+Set<Iteml>+: Multiset which uses the DEFAULT\_SEQ\_IMPL defined
			  in Sequence.h.
\end{itemize}

The comparison methods of set objects (\MSetBase,\ \MSet,\ \SetBase,\
\Set) work under the 
assumption that the elements are stored in lexicographic order.
Therefore, in order for these operations to work correctly, the
underlying \Container\ implementation must store the elements in
sorted order, or at least be capable of iterating through the 
elements in sorted order.  With this restriction in mind, it is 
possible to introduce new \Container\ objects into LINK and use
them as \Collection\ implementations.

\subsubsection{Reference Counting}

Aside from implementing the core set and sequence operations, the 
\Collection\ hierarchy offers the programmer a major advantage
when compared to the \Container\ hierarchy. 

\begin{quote}	
	The copying of \Collections\ is implemented {\em efficiently} 
	if possible, i.e., if the source object is a descendant of
	the destination object, using
	a reference counting scheme.  This is of great importance when
	dealing with frequently passed groups of objects such as the 
	neighbors of a vertex.  In contrast, the initialization 
	of one \Container\ 
	with another always accomplished by iteration through all of the 
	elements.
\end{quote}

All class derivation in the \Collection\ hierarchy is public.  In general,
if a child class is derived publically from a parent class, it is 
convenient to say that a child class instance {\em is a} parent class
instance.  For example, a sequence {\em is a} multiset in which the 
the elements can appear in any specified order.  This rule can be 
used to determine whether or not a given copy operation will
involve an increment in 
reference count or the iteration through all of the elements.  Reference
counting occurs when the object being copied {\em is an} instance of
the destination object.  Otherwise the receiving object is incompatible
with the source object and each element must be copied.  
For example, consider the code fragment in Figure~\ref{fig:MSet0}.

\begin{figure}[tbp]
\input{examples/basic/ProgMSet0.tex}
\caption{Reference Counting in \Collections}
\label{fig:MSet0}
\end{figure}

The variable {\em array\_set} is a multiset object which uses a
\SortedArray\ to store its elements.  On the other hand, {\em list\_set1}
and {\em list\_set2} use \SortedList\ objects to store their elements.
The reference counting scheme, which uses pointer aliasing to avoid 
unnecessary copying, will not work with incompatible containers.

Under reference counting, it is possible for many \Collection\ objects
to have pointers to the same \Container\ object.  As long as no changes
are made to this underlying implementation, such aliasing is all right.
However, once a \Collection\ attempts to insert or remove elements, it
must be given its own copy of the elements. For examples, consider the
code in Figure~\ref{fig:MSet1}.

\begin{figure}[tbp]
\input{examples/basic/ProgMSet1.tex}
\caption{Reference Counting and Modifications in \Collections}
\label{fig:MSet1}
\end{figure}

When {\em mset2} attempts to append an additional element, sharing a 
common \Container\ with {\em mset1} is no longer an option.  A full
copy of the elements is made before the insertion.  In this manner,
the integrity of {\em mset1} is preserved.

Since \verb+X(const X&)+ constructors are called automatically upon
argument pass by value and function return by value 
(and since in the \Collection\ hierarchy they control the reference
counting along with the assignment operators), \Collection\ objects 
can be passed around efficiently.  This makes the efficient 
programmer's memory management job much easier.  For example,
consider the code in Figure~\ref{fig:MSet7}.

\begin{figure}[tbp]
\input{examples/basic/ProgMSet7.tex}
\caption{Passing and Returning Collection Objects}
\label{fig:MSet7}
\end{figure}

The return of a temporary object cannot be accomplished by reference,
so without reference counting, an efficient return would require dynamic
memory allocation.  But this is not necessary;  the return of \Collection\
objects is an efficient operation.

\subsubsection{Comparisons}

\Collection\ and \Container\ objects can be compared easily using the
operations defined in the \Container\ class on Page~\pageref{page:container}.
For example the code in Figure~\ref{fig:MSet2} illustrates a comparison between 
\MSet\ and \SortedList\ objects.
\begin{figure}[tbp]
\input{examples/basic/ProgMSet2.tex}
\caption{Comparisons Between \Collections\ and \Containers}
\label{fig:MSet2}
\end{figure}
\Collection\ objects are compared with each other in the same way, 
as shown in Figure~\ref{fig:MSet5}.

\begin{figure}[tbp]
\input{examples/basic/ProgMSet5.tex}
\caption{Comparisons between \Collections}
\label{fig:MSet5}
\end{figure}

\subsubsection{Set Primitive Operations}

The three set primitive operations (union, intersection, and difference)
are binary operations which take arbitrary \Collection\ objects as
arguments, treat them as multisets, and return the result as a multiset.

\begin{figure}[tbp]
\input{examples/basic/ProgMSet3.tex}
\caption{The Set Primitive Operations}
\label{fig:MSet3}
\end{figure}

\begin{figure}[tbp]
\input{examples/basic/ProgMSet6.tex}
\caption{Set Primitives with Set and Sequence Operands }
\label{fig:MSet6}
\end{figure}

\clearpage

The example in Figure~\ref{fig:MSet3} 
illustrates the three set primitive operations applied
to multisets, while the more extensive example shown in
Figure~\ref{fig:MSet6} shows the
treatment of sequences as sets during these operations.  Note that
the type of the object receiving the return value of each operation 
determines whether the result is a set or a multiset.


\subsubsection{Interface}

The following methods are available to pointers and references to 
\Collection\ objects.  Those that are pure virtual are defined in
class \MSet.

\input{basic/ProgCollection.tbl.tex}

%======================Set===============================

%\newpage

\subsection{\MSetBase\ and \MSet }
\label{sec:set}

\begin{figure}[tbp]
\input{examples/basic/ProgMSet4.tex}
\caption{\MSetBase\ and \MSet}
\label{fig:MSet4}
\end{figure}

Most of the methods declared pure virtual in the \Collection\ class
are given definitions in class \MSetBase.  The latter is the only
non-abstract class from which all other \Collection\ objects inherit.
It is templated both by element type and by implementation type in 
order to allow the programmer the flexibility of customizing sets
and sequences to for various applications.  The descendant classes of
\MSetBase\ inherit most of their functionality from it, and redefine
only those methods which distinguish them.   The comparison, set
primitive, subset, and output operations are inherited and used by
all other \Collections.  This allows various sets and sequences to
be used together very naturally, a property on which the graph hierarchy
depends.

Two fundamental assumptions about \Containers\ used as \Collection\
implementations apply:

\begin{enumerate}
\item	Multiset and Set objects should be stored in sorted \Containers.
\item	Sequence objects {\em must} be stored in unsorted \Containers.
\end{enumerate}

If two \Collections\ are stored in \Containers\ which store elements in
sorted order, then the comparison, set primitive, and subset operations
take linear time in the worst case.  Otherwise the respective time 
complexities worsen, and output will not be as neat.  However, 
\MSetBase\ objects using unsorted \Containers\ as implementations are
permitted.
On the other hand, sequences must be implemented using unsorted \Containers.
Otherwise, the only possible ordering of $n$ elements is lexicographic 
order.

\MSet\ objects are simply \MSetBase\ objects in which the default set 
implementation \Container\ (DEFAULT\_SET\_IMPL defined in general.h) 
is used to store the elements.

\creation

\input{basic/ProgMSet.crt.tex}

\operations

\input{basic/ProgMSet.tbl.tex}


\subsection{\SetBase\ and \Set}

Sets which contain no duplicate elements are obtained by defining 
\SetBase\ and \Set\ objects, which inherit very heavily from class
\MSetBase.  The only difference is that insertions are guarded by
a membership test to maintain the invariant the no duplicate elements
ever exist in a set.

The methods which differ from those of \MSetBase\ are listed below.

\creation

\input{basic/ProgSet.crt.tex}

\operations

\input{basic/ProgSet.tbl.tex}

\subsection{\SequenceBase\ and \Sequence}
\label{sec:sequence}

\Collections capable of storing data elements in any order are
\SequenceBase\ and \Sequence\ classes.  Like \SetBase\ and \Set\
these classes inherit the vast majority of their functionality
from \MSetBase.\  Unlike set objects, however, sequence objects
{\em must} use unsorted \Container\ objects as storage media.
Error checks in the \SequenceBase\ and \Sequence\ constructors
prevent the use of any \Container\ object which returns TRUE
when given the \verb+sortedQ()+ query.

\Sequence 
\begin{figure}[tbp]
\input{examples/basic/ProgSequence1.tex}
\caption{\Sequence}
\label{fig:Sequence1}
\end{figure}

The main advantage of derivation from \MSetBase\ is illustrated in
Figures~\ref{fig:Sequence1} and \ref{fig:Sequence2}.  
Since a sequence {\em is a }
multiset which happens to be stored in an unsorted \Container\ object,
it can appear as an operand on either side of the set comparison,
set primitive, and set construction methods.

\begin{figure}[tbp]
\input{examples/basic/ProgSequence2.tex}
\caption{Another \Sequence\ Example}
\label{fig:Sequence2}
\end{figure}

The methods which differ from those of \MSetBase\ are listed below.

\creation

\input{basic/ProgSequence.crt.tex}

\operations

\input{basic/ProgSequence.tbl.tex}


%\subsection{Large Example:  Using a LEDA Dictionary as a \Container.}
%****Will try hooking up their randomized search tree class.****


\section{Combinatorial Objects}

Permutations, subsets, and set partitions are combinatorial objects
are both useful in describing properties of graphs and objects with
interesting properties of their own.

One distinguishing property of combinatorial objects is that there are a finite
number of them of any given size, and that a lexicographic order can be
defined on them.
Thus they can be ranked and unranked, and constructed at random.


\subsection{Commonalities Among Combinatorial Objects}

Permutations and sets of subsets are grouped into a class called 
\SetFuncsn.  This is useful to help instantiate templates in an
orderly manner, though eventually compilers should reach a state
where this is no longer a concern.  The combinatorial objects 
described below are represented with
\Collections, \Collections of \Collections,  and operations on 
these.  In this way, all of the commonalities between \Collections
(copying, comparisons, set primitives, etc.) apply.

\subsection{Permutations}

A permutation of a set of objects is a particular arrangement of them.
Permutations can be throught of as either arrangements, or an operation
which rearranges a set of objects.
Permutations of the numbers $1,\ldots,n$ can describe a particular
arrangment of arbitrary objects (and hence are an operation).
The {\em Permutation} object describes such an arrangement, and can
be applied to a \Sequence of typed objects to obtain a permutation
of the latter.

\creation

\input{basic/ProgPermutation.crt.tex}

\operations

\input{basic/ProgPermutation.tbl.tex}

Permutation objects can be used to obtain permutation of typed 
objects like vertices and edges as follows.  The class \SetFuncsn,
provides the necessary interface.  Note that several of the methods
in this class produces results of exponential in the size of the 
input.

\input{basic/ProgSetFuncs.tbl.tex}

%=================Disjoint Set==========================

%\newpage

%\subsection{Set Partitions}

%\creation

%\input{basic-old/ProgDJSet.crt.tex}

%\operations

%\input{basic-old/ProgDJSet.tbl.tex}


%\newpage