CSE 401: Compilers

Details / Set Data Type Run Time

The source code can be found on the instructional alphas in the two files /cse/courses/cse401/CurrentQtr/set/set.{cc,h}. Copy and use these two files if your implementation deviated significantly from mine. (These files may be updated as we shake out bugs.)

The class Set models sets of integers from the fixed Lb to Ub, where Lb and Ub are inclusive ranges.

This implementation uses bit vectors, which for non-sparse sets, is the most space efficient representation. we construct a bit vector from a (logical) array of bits. The logical array of bits is in turn constructed from an array of unsigned integers. if bit i is set, then i is in the set; otherwise i is not in the set.

To access bit i, we have to convert i to an index into the array of unsigned ints, and then figure out which bit within the unsigned integer to use. These two operations can be efficiently done using shifting and masking, which implement special cases of division and modulus for powers of two.

The set will never contain elements that have not been put there explicitly. This is to say that values outside of lb .. ub will all be 0, unless the client of this class (caller of the member functions) has somehow screwed up.

All high level operations on sets can be done DIRECTLY with Boolean operations. We do the Boolean operations in serial on words, but in parallel within the word, using wordwise boolean operations. This strategy efficiently disposes of 32 members of the set at a time. It does not get much more efficient for sets with a density that is unknown!

All sets use a fixed amount of storage. This is potentiallyi wasteful in both space and time if the range of the actual set (members lb and ub) is smaller than the worst case.

With some additional work this data structure could be extended to make more efficient use of storage for small sets by allocating just the right number of words needed.

We make extensive use of const. We use it in two ways. If the formal parameter declaration for x uses const, then the member function does not modify what x points to. If the member function declaration itself is attributed with const, then the member function does not modify what this points to.

The constructor must always be called when data for a Set is allocated, and prior to using the set the first time.

The destructor must always be called when data for a Set is being dellocated.

401admin@cs.washington.edu
(Last modified: 27Oct97)