Adding New Containers

It is straightforward to add new simple <#7353#>Container<#7353#> objects to LINK. The new classes must inherit from class <#7354#>SimpleContainer<#7354#> and must be templated with a single <#7312#>Item<#7312#> argument. <#7313#>Item<#7313#> will be assumed to have the following operators defined: 45 46 47 48. 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 <#7314#>ElementOps<#7314#>, which is the base class for both <#7355#>Container<#7355#> and <#7356#>Collection<#7356#>: <#7315#>
  • <#7316#>int compareItems(Item, Item)<#7316#>
  • <#7317#>int displayItem(ostream&, Item)<#7317#>.
<#7315#> These methods should be used instead of the comparison and output operators because certain very important element types such as <#7319#><#7357#>Vertex<#7357#><#7319#>* and <#7320#><#7358#>Edge<#7358#><#7320#>* must be treated as exceptions by the <#7359#>Container<#7359#> and <#7360#>Collection<#7360#> hierarchies. Mere pointer comparisons are unsatisfactory in these cases, so specialized methods for these are prototyped in ElementOps.h and given definitions in graphTemplate.cpp. <#7321#>
Figure 2.2: The <#7361#>ElementOps<#7361#> Class
#figure7321#

<#7321#> <#7362#>Containers<#7362#> and <#7363#>Collections<#7363#> may be compared using the overloaded C++ operators: 49, 50, 51, 52, 53, 54. The comparison is based on lexicographic ordering of the <#7364#>Container<#7364#>/<#7365#>Collection<#7365#> elements. In general, <#7326#>if two objects of class Collection or Container contain the same elements in the same order, then they are considered equal<#7326#>. Inequalities are decided based upon the lexicographic ordering of the individual elements. An example involving <#7366#>List<#7366#> comparisons is given in Section~#sec:list#7327>. Some examples to follow when implementing new <#7367#>SimpleContainer<#7367#> objects are found in List.h, List.cpp, Array.h, and Array.cpp in the 55 directory. The following virtual functions define the interface of the <#7368#>Container<#7368#> 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, <#7328#>Container;SPMlt;Item;SPMgt;::min()<#7328#> and <#7329#>Container;SPMlt;Item;SPMgt;::max()<#7329#> are implemented by iterating through all elements. If the data structure class stores data in sorted order, these should be overridden. <#7369#>2. Operations<#7369#>


<#7373#>

<#7375#>
Figure 2.2: The <#7361#>ElementOps<#7361#> Class
virtual 56<#7561#>Container<#7561#><#7579#>;SPMlt;<#7579#>item<#7581#>;SPMgt;<#7581#>()
<#7375#>
<#7380#>

The virtual destructor in the <#7563#>Container<#7563#> 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 <#7564#>Container<#7564#>).


<#7380#>


<#7373#>

<#7385#>

<#7387#>
Item info(ContainerNode *cn) const;
<#7387#>
<#7392#>

Return the data value stored in node <#7394#>cn<#7394#>.


<#7392#>


<#7385#>

<#7398#>

<#7400#>
int size() const = 0;
<#7400#>
<#7405#>

Return the number of stored elements.


<#7405#>


<#7398#>

<#7410#>

<#7412#>
Bool emptyQ() const = 0;
<#7412#>
<#7417#>

Return TRUE if there are no stored elements.


<#7417#>


<#7410#>

<#7422#>

<#7424#>
Bool fullQ() const = 0;
<#7424#>
<#7429#>

Return TRUE if there are no space left for additional elements.


<#7429#>


<#7422#>

<#7434#>

<#7436#>
Bool memberQ(const Item&e) const = 0;
<#7436#>
<#7441#>

Return TRUE if <#7587#>e<#7587#> is stored.


<#7441#>


<#7434#>

<#7446#>

<#7448#>
Item min() const;
<#7448#>
<#7453#>

Return the minimum data value stored (<#7589#>O(n)<#7589#>). Note that this method is virtual and should be redefined in any descendant class which can implement it more efficiently.


<#7453#>


<#7446#>

<#7458#>

<#7460#>
Item max() const;
<#7460#>
<#7465#>

Return the maximum data value stored (<#7591#>O(n)<#7591#>). Like <#7467#>min()<#7467#>, this should be overridden in any descendant class in which a more efficient implementation is possible.


<#7465#>


<#7458#>

<#7471#>

<#7473#>
DataType type() const = 0;
<#7473#>
<#7478#>

Return the type of this structure (<#7480#>DataType<#7480#> is an enumerated type defined in general.h).


<#7478#>


<#7471#>

<#7484#>

<#7486#>
Item get() = 0;
<#7486#>
<#7491#>

Remove and return the first element in iteration order.


<#7491#>


<#7484#>

<#7496#>

<#7498#>
void remove(Item e) = 0;
<#7498#>
<#7503#>

Find and remove <#7593#>e<#7593#> from the structure. If this is a linked structure, delete the <#7565#>ContainerNode<#7565#> containing <#7595#>e<#7595#>. Do not delete <#7597#>e<#7597#>.


<#7503#>


<#7496#>

<#7508#>

<#7510#>
void clear() = 0;
<#7510#>
<#7515#>

Remove all data from the structure, deleting <#7566#>ContainerNodes<#7566#> but not actual elements.


<#7515#>


<#7508#>

<#7520#>

<#7522#>
int iterate(Iterator<#7599#>;SPMlt;<#7599#>Item<#7601#>;SPMgt;<#7601#>& it, Item& e) const = 0;
<#7522#>
<#7527#>

This method is used by <#7567#>Iterator<#7567#> objects to obtain the successor of <#7603#>e<#7603#>. Good examples of different implementations of this method are found in Array.h and List.h. This method is declared to be 58 in this class to allow access through <#7568#>Container<#7568#> pointers. However, it should be declared private in the descendant classes. The only access should be with <#7569#>Iterator<#7569#> objects.


<#7527#>


<#7520#>

<#7532#>

<#7534#>
ostream& display(ostream&os) = 0;
<#7534#>
<#7539#>

This will be called when <#7541#>operator<#7605#>;SPMlt;<#7605#><#7607#>;SPMlt;<#7607#>(ostream&,Container<#7609#>;SPMlt;<#7609#>Item<#7611#>;SPMgt;<#7611#>&)<#7541#> is invoked.


<#7539#>


<#7532#>

<#7545#>

<#7547#>
Bool operator==(const Collection<#7613#>;SPMlt;<#7613#>Item<#7615#>;SPMgt;<#7615#>&) const = 0;  
Bool operator<#7617#>;SPMlt;<#7617#>=(const Collection<#7619#>;SPMlt;<#7619#>Item<#7621#>;SPMgt;<#7621#>&) const = 0;  
Bool operator<#7623#>;SPMlt;<#7623#> (const Collection<#7625#>;SPMlt;<#7625#>Item<#7627#>;SPMgt;<#7627#>&) const = 0;  
Bool operator<#7629#>;SPMgt;<#7629#>=(const Collection<#7631#>;SPMlt;<#7631#>Item<#7633#>;SPMgt;<#7633#>&) const = 0;  
Bool operator<#7635#>;SPMgt;<#7635#> (const Collection<#7637#>;SPMlt;<#7637#>Item<#7639#>;SPMgt;<#7639#>&) const = 0;  
Bool operator!=(const Collection<#7641#>;SPMlt;<#7641#>Item<#7643#>;SPMgt;<#7643#>&) const = 0;  
Bool operator==(const Container<#7645#>;SPMlt;<#7645#>Item<#7647#>;SPMgt;<#7647#>&) const = 0;  
Bool operator<#7649#>;SPMlt;<#7649#>=(const Container<#7651#>;SPMlt;<#7651#>Item<#7653#>;SPMgt;<#7653#>&) const = 0;  
Bool operator<#7655#>;SPMlt;<#7655#> (const Container<#7657#>;SPMlt;<#7657#>Item<#7659#>;SPMgt;<#7659#>&) const = 0;  
Bool operator<#7661#>;SPMgt;<#7661#>=(const Container<#7663#>;SPMlt;<#7663#>Item<#7665#>;SPMgt;<#7665#>&) const = 0;  
Bool operator<#7667#>;SPMgt;<#7667#> (const Container<#7669#>;SPMlt;<#7669#>Item<#7671#>;SPMgt;<#7671#>&) const = 0;  
Bool operator!=(const Container<#7673#>;SPMlt;<#7673#>Item<#7675#>;SPMgt;<#7675#>&) const = 0;  
<#7547#>
<#7551#>

Compare the <#7570#>Container<#7570#> with a <#7571#>Collection<#7571#> or <#7572#>Container<#7572#> argument. These methods are defined in Container.cpp and are common to all <#7573#>Container<#7573#> objects.


<#7551#>


<#7545#>