Next: SetBase and Set Up: The Graph Hierarchy Previous: Interface

## MSetBase and MSet

Figure 3.25: MSetBase and MSet

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:

1.
  Multiset and Set objects should be stored in sorted Containers.
2.
  Sequence objects must be stored in unsorted Containers.

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.

1. Creation

Figure 3.25: MSetBase and MSet
MSetBase<Item,Impl> | ms;

Create an empty multiset using the Container class Impl (where Impl contains elements of type Item) as an implementation.

MSetBase<Item,Impl> | ms( (Collection<Item>&) c);

Create a multiset using the Container class Impl (where Impl contains elements of type Item) as an implementation. Initialize the collection with the elements of c. O(n)

MSetBase<Item,Impl> | ms( (MSetBase<Item,Impl>&) m);

Create a multiset using the Container class Impl (where Impl contains elements of type Item) as an implementation. Use reference counting to share m's implementation. O(1)

MSet<Item> | ms;

Create an empty multiset using the implementation specified by DEFAULT_SET_IMPL in MSet.h. Initialize it with the elements of c. O(n)

MSet<Item> | ms( (Collection<Item>&) c);

Create a multiset using the implementation specified by DEFAULT_SET_IMPL in MSet.h. Initialize it with the elements of c. O(n)

MSet<Item> | ms( (MSet<Item>&) m);

Create a multiset using the default Container class as an implementation. Use reference counting to share m's implementation. O(1)

2. Operations

virtual | `~`MSetBase<Item,Impl> ()

Decrement the reference count of the Container which stores the elements (this container object is called `store`). O(1). If the count reaches 0, delete the object. O(n)

int | size () const;

Return the number of stored elements by calling storesize().

Bool | emptyQ () const;

Return TRUE if there are no stored elements (call storeemptyQ()).

Bool | fullQ () const;

Return TRUE if there are no space left for additional elements (call storefullQ()).

Bool | memberQ (const Item&e) const;

Return TRUE if e is stored (call storememberQ()).

Bool | sortedQ (const Item&e) const;

Return TRUE if `store` is stored (call storesortexQ()).

DataType | type () const;

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

Item | first () const;

Return the first element in `store` (call storefirst()).

Item | last () const;

Return the last element in `store` (call storelast()).

void | insert (Item e);

If the reference count of `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 storeinsert(e). to insert e.

void | append (Item e);

After considering reference counts as above, call storeappend(e). to insert e at the end, if sorted order permits (see SortedList).

void | remove (Item e);

After considering reference counts as above, remove e from `store`.

void | clear ();

After considering reference counts as above, remove all elements from `store`.

int | iterate (Iterator<Item>& it, Item& e) const;

Return storeiterate(it,e). Note that some typecasting is required, as iterate() is not a publically-accessible member of any of the descendants of Container. The iterate() method needn't ever be called by the programmer; use Iterator objects.

Item | ref (int i);

Return the element with index i. O(n)

int | rank (Item it);

Return the index of item it. O(n)

int | occurrences (Item);

Returns the number of occurrences of the passed item by iterating through all of the elements. O(n)

int | permutationQ ();

Returns FALSE if duplicate elements exist. O(n) if `store` is a sorted Container. O(n2) otherwise.

void | concatenate (const Collection<Item>&);

Add the elements of the passed Collection by iterating through them and using append().

ostream& | display (ostream&os);

This will be called when operator<<(ostream&,Collection<Item>&) is invoked.

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; |

Return storeoperator...(..).

Bool | eq (const MSetBase<Item,Impl>&s);

This alternative to `operator==(...)` is provided for access from the TCL interface.

Bool | neq (const MSetBase<Item,Impl>&s);

This alternative to `operator!=(...)` is provided for access from the TCL interface.

MSetBase<Item,Impl> unions(Collection<Item>& c); |
MSetBase<Item,Impl> operator+(Collection<Item>& c); |

Construct the union of the current multiset and c as a 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(n2) if either of the Collectionsare unsorted, O(n) otherwise. (the O(n2) could be improved with a more involved implementation which builds frequency tables.

MSetBase<Item,Impl> intersection(Collection<Item>& c); |
MSetBase<Item,Impl> operator^(Collection<Item>& c); |

Construct the intersection of the current multiset and c as a 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(n2) if either of the Collectionsare unsorted, O(n) otherwise. (the O(n2) could be improved with a more involved implementation which builds frequency tables.

MSetBase<Item,Impl> difference(Collection<Item>& c); |
MSetBase<Item,Impl> operator-(Collection<Item>& c); |

Construct the difference between the current multiset and c as a MSetBase<Item,Impl> object. The number of occurrences of an element e in the result ( is defined as (. O(n2) if either of the Collectionsare unsorted, O(n) otherwise. (the O(n2) could be improved with a more involved implementation which builds frequency tables.

Bool | subsetQ (Collection<Item>& c);

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 storememberQ(e).

Bool | properSubsetQ (Collection<Item>& c);

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 storememberQ(e).

int | occurrences (Item item);

Iterate through the list and return the number of occurrences of item. O(n)

ostream& | display (ostream& os) const

Display the multiset on the output stream os. O(n)

Collection<Item>* | newEmpty() const;

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)

Next: SetBase and Set Up: The Graph Hierarchy Previous: Interface