Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
There is a special family of operators for comparing sets. Consider two sets, say S and T. We say that S is a subset of T, written , if every element of S is also an element of T. If there is at least one element of T that is not also an element of S, we say that S is a proper subset of T, written . We can also reverse the order in which the expressions are written to get or , which indicates that T is a (proper) superset of S.
The set comparison operators follow the rule that if and then , which is analogous to a similar property of numbers: . However, set comparison is unlike numeric comparison in that there exist sets S and T for which neither nor ! For example, clearly this is the case for and . Mathematically, the relation is called a partial order because there exist some pairs of sets for which neither nor holds; whereas the relation (among integers, say) is a total order.
Program defines the methods Equals and IsSubset each of which take argument that is assumed to be a SetAsArray instance. The former tests for equality and the latter determines whether the relation holds between this and set. Both operators return a bool result. The worst-case running time of each of these operations is clearly O(N).
Program: SetAsArray class Equals and IsSubset methods.
A complete repertoire of comparison methods would also include methods to compute , , , and . These operations follow directly from the implementation shown in Program (Exercise ).