A bitset is a way of implementing a set where the set’s data is stored in an array of booleans such that index i in the array is set to true if i is in the set and false otherwise.
computer science
Description
Problem 7 from Chapter 8
A bitset is a way of implementing a set where the set’s data
is stored in an array of booleans such that index i in the array is set to true
if i is in the set and false otherwise. For instance, the set {0, 1, 4, 6} is
represented by the following array:
[true, true, false, false, true, false, true]
The indices 0, 1, 4, and 6 are true, and the others are
false.
Write a BitSet class that works for sets of integers that
contains the following methods:
BitSet(n) — a constructor that creates an empty set. The
parameter n specifies the largest element the set will be able to hold. This
parameter is thus the size of the boolean array. BitSet(list) — a constructor
that is given an ArrayList of integers and builds a set from it toString() —
returns a string containing the contents of the set bracketed by curly braces
with individual elements separated by commas and spaces. For example: {0, 1, 4,
6} is how the set above would be returned.
toList() — returns an ArrayList of integers containing the
elements of the set
contains(x) — returns true or false depending on whether the
set contains the element x
add(x) — inserts x into the set
remove(x) — removes x from the set
size() — returns the number of elements in the set
isEmpty() — returns true if the set is empty and false
otherwise
getMax() — returns the largest element that the set is able
to hold
union(s1, s2) — a static method that returns the union of
sets s1 and s2. [Be careful because the sets may have different sizes.]
intersection(s1, s2) — a static method that returns the
intersection of sets s1 and s2. [Be careful because the sets may have different
sizes.]
difference(s1, s2) — a static method that returns the
intersection of sets s1 and s2. [Be careful because the sets may have different
sizes.]
isSubset(s1, s2) — a static method that returns whether or
not s1 is a subset of s2.
