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.

1. Creation

SetBase<Item,Impl> s;

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

SetBase<Item,Impl> s( (Collection<Item>&) c);

Create a set using the Container class Impl (where Impl contains elements of type Item) as an implementation. Initialize the collection with the elements of c. Note that although c may be a multiset, no duplicate elements are inserted into s. O(nq), where q is the complexity of the Container's memberQ() method.

SetBase<Item,Impl> s( (SetBase<Item,Impl>&) ss);

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

Set<Item> s( (Collection<Item>&) c);

Create a set using the implementation specified by DEFAULT_SET_IMPL in MSet.h. Initialize it with the elements of c. O(nq), where q is the complexity of the Container's memberQ() method.

Set<Item> s( (Set<Item>&) ss);

Create an empty multiset using the implementation specified by DEFAULT_SET_IMPL in MSet.h. Use reference counting to share the elements of ss. O(1)

2. Operations

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, check to ensure that e is not currently a member, then call storeinsert(e). to insert e.

void append (Item e);

After considering reference counts as above, check to ensure that e is not a member, then call storeappend(e).

void remove (Item e);

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

int occurrences (Item);

Return 1 or 0. O(1).

int permutationQ ();

Always returns TRUE. O(1).