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.

Instruction Files

Related Questions in computer science category