A sparse bitset is a large collection of boolean values where many of the values are off (or false). For maintaining these sparsely populated sets, the BitSet class can be very inefficient. Since the majority of the bits will be off, space will be occupied to store nothing. For working with these sparse bitsets, you can create an alternate representation, backed instead by a hashtable, or HashMap. Only those positions where a value is set are then stored in the mapping.

To create a sparse bitset, subclass BitSet and override the necessary methods (everything). The skeleton code should help get your started, so you can focus on the set-oriented routines.

The following UML diagram shows you the BitSet operations:

For more information on the BitSet class, see the appropriate section in the course notes.

Skeleton Code

• SparseBitSet.java
• Tester.java

Tasks

1. Either start with the skeleton code or create a SparseBitSet class. The skeleton provides a no-argument constructor only. Since the bitmap will be sparse, you shouldn't provide a constructor that will preallocate any space, as BitMap does. Besides a constructor, the skeleton defines the clear(), clone(), equals(), get(), hashCode(), set(), size(), and toSting() method.

   In the skeleton, the getBitSet() method returns the internal Set used to store the bits. You should use this method as you complete the other methods in the subclass. The actual HashSet used to store the bit values is created for you in the constructor.

2. Working alphabetically, the first method to complete is the and(BitSet set) method. This method performs a logical AND of the two bit sets. Only those bits in both sets are in the resulting set. Complete the and() method to combine the internal Set with that of the argument.

3. The next method to complete is the andNot(BitSet set) method. Instead of keeping bits present in both, the andNot() operation will remove bits from the current set that are also in the set passed as an argument. This is sometimes called a logical NAND operation.

4. Since the clear(), clone(), equals(), get(), and hashCode() methods are defined in the skeleton code, the next method to complete is the length() method. The length() method returns the logical size of the BitSet, which is defined to be the position of the highest set bit, plus one. Thus, if bit 127 was set, the length would be 128 as the bit counting starts at zero.

5. The last easy method to complete is the or(BitSet set) method. This method performs a logical OR operation of the two bit sets. Every bit set of either set is in the resulting set.

6. With the set(), size(), and toString() methods already defined for you, you're left to complete the xor(BitSet set) method. This method performs a logical exclusive or (XOR) operation. Only those bits on in one of the sets will be on in the resulting set.

   Unlike the other operations, the solution is not just a single method call of Set.

7. Compile your program and run the Tester program to see what happens. The Tester program creates a couple of sets and performs all the operations.

Where help exists, the task numbers above are linked to the step-by-step help page.

Solution Source

• solution/SparseBitSet.java
• solution/Tester.java

Demonstration

When you run the Tester program, your output should consist of the following:

Empty Set:
  Length: 0
  Size: 0
Filled Set:
  Contents: [100, 99, 128]
  Length: 129
  Size: 3
Is 99 present? :
  [100, 99, 128] true
  [100, 128] false
Are two sets equal? :
  Set 1: [100, 128]
  Set 2: [100, 99, 98]
  Equal? false
Or:
  [100, 99, 98, 128]
Xor:
  [99, 98, 128]
And:
  [100]
AndNot:
  [128]

If the output is different, go back and check your work.

Copyright © 1999 MageLang Institute. All Rights Reserved.