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

 

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(n²) 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.

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.

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(n²) if either of the Collectionsare unsorted, O(n) otherwise. (the O(n²) could be improved with a more involved implementation which builds frequency tables.

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(n²) if either of the Collectionsare unsorted, O(n) otherwise. (the O(n²) could be improved with a more involved implementation which builds frequency tables.

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 ($n\_r(e))$ is defined as ($n\_\mbox{this}(e) - n\_c(e)))$. O(n²) if either of the Collectionsare unsorted, O(n) otherwise. (the O(n²) 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)