Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Implementing Sets

 

As discussed above, this chapter addresses the implementation of sets of integers. A set is a collection of elements. Naturally, we want to insert and withdraw objects from the collection and to test whether a given object is a member of the collection. Therefore, we consider sets as being derived from the SearchableContainer class defined in Chapter gif. (See Figure gif). In general, a searchable container can hold arbitrary objects. However, in this chapter we will assume that the elements of a set are integers.

   figure27552
Figure: Object class hierarchy

Program gif defines the Set interface. The Set interface extends the the SearchableContainer interface defined in Program gif. Five new methods are declared--Union, Intersection, Difference, Equals, and IsSubset. These methods correspond to the various set operations discussed above.

   program27569
Program: Set interface.

Program gif defines the AbstractSet class. The AbstractSet class extends the AbstractSearchableContainer class introduced in Program gif and it implements the Set interface defined in Program gif. As shown in Figure gif, all of the concrete set classes discussed in this chapter are derived from the AbstractSet class.

   program27595
Program: AbstractSet class.

The AbstractSet class defines a field called universeSize. This field is used to record the size of the universal set. The constructor for the AbstractSet class is given in Program gif. It takes a single argument, tex2html_wrap_inline66419, which specifies that the universal set shall be tex2html_wrap_inline66417.

The items contained in a set are integers. Therefore, the AbstractSet class defines abstract methods called as Insert, IsMember, and Withdraw, that take int arguments.

However, the methods of the SearchableContainer interface such as Insert, IsMember, and Withdraw, expect their arguments to be ComparableObjects. For this reason, the AbstractSet class provides a default implementation for each such method which converts its argument to an int and then invokes the like-named abstract method that takes an int argument.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.