|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Program 
defines the three methods,
__or__, __and__, and __sub__.
These methods correspond to 
, 
, and -, respectively.
Program: SetAsArray class __or__, __and__ and __sub__ methods.
The set union method takes two arguments, self and set.
The second argument is assumed to be a SetAsArray instance.
The method computes the SetAsArray obtained
from the union of the sets self and set.
The implementation given requires that the sets be compatible.
Two sets are deemed to be compatible if they have the same universe.
The result also has the same universe.
Consequently, the bool array in all three sets
has the same length, N.
The set union method creates a result array of the required size
and then computes the elements of the array as required.
The 
element of the result is true
if either the element of self
or the element of set is true.
Thus, set union is implemented using
the Boolean or operator,
or.
The set intersection method is almost identical to set union, except that the elements of the result are computed using the Boolean and operator, and. The set difference method is also very similar. In this case, an item is an element of the result only if it is a member of self and not a member of set.
Because all three methods are almost identical,
their running times are essentially the same.
That is, the running time of
the set union, intersection, and difference operations is O(N),
where 
.
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.