Sets/ADT

Abstract data type for the Sets data type.

Public methods

The Set type must provide the following basic methods for manipulating the Set:

• S.add(e) - add element e to set
• S.discard(e) / S.discard(e) - (quietly) remove element e from set
• e in S or S.contains(e) - returns true if container contains e
• len(s) or S.size() - return the number of elements in the set
• iter(S) or S.iterator() - returns an iterator over the set

These five methods will suffice to implement a large variety of other functions.

Removal methods

The following removal methods can be defined:

• S.remove(e) - removes an element e from the set, raise exception if empty
• S.pop() - removes an arbitrary element from the set, raise exception if empty
• S.clear() - removes all elements from the set

Utility methods

Need to define some regular ol utility methods:

• size
• isEmpty

Set operations

Set Operations Involving Two Sets

Some set operations involving two sets:

• equals - return true if two sets S and T have identical elements
• less than or equal to - return true if S is subset of T
• less than - return true if S is proper subset of T
• greater than or equal to - return true if S is superset of T
• greater than - return true if S is proper superset of T
• isDisjoint - returns true if S and T have no common elements

Set Operations Involving Constructing New Sets

Operations involving constructing new sets from existing sets:

• Union of S and T - returns all elements in either S or T or both
• intersection of S and T - returns all elements in both S and T
• Symmetric difference - returns all elements that are in S but not T, or T but not S
• Remove all - remove all items from this set that are in the passed set
• Retain all - retain only items from this set that are in the passed set