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

Array and Bit-Vector Sets

In this section we consider finite sets over a finite universe. Specifically, the universe we consider is tex2html_wrap_inline66417, the set of integers in the range from zero to N-1, for some fixed and relatively small value of N.

Let tex2html_wrap_inline66431 be the universe. Every set which we wish to represent is a subset of U. The set of all subsets of U is called the power set  of U and is written tex2html_wrap_inline66439. Thus, the sets which we wish to represent are the elements of tex2html_wrap_inline66439. The number of elements in the set U, written |U|, is N. Similarly, tex2html_wrap_inline66449. This observation should be obvious: For each element of the universal set U there are only two possibilities: Either it is, or it is not, a member of the given set.

This suggests a relatively straightforward representation of the elements of tex2html_wrap_inline66439--an array of bool values, one for each element of the universal set. By using array subscripts in U, we can represent the set implicitly. That is, i is a member of the set if the tex2html_wrap_inline57621 array element is true.

Program gif introduces the class SetAsArray. The SetAsArray class extends the AbstractSet class defined in Program gif. This class uses an array of length tex2html_wrap_inline66461 to represent the elements of tex2html_wrap_inline66439 where tex2html_wrap_inline66431.

Program: SetAsArray fields.

next up previous contents index

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