3.8. The Java BitSet. 3.8. The Java BitSet. We could implement the mathematical set via the Java BitSet. This lets us have an arbitrarily large set but only of bits. We are limited to specify the bit position or value - we can add integers to the set.
We can see below that the new class has a single item of data - the BitSet which will be used and many methods. This is very typical of Java - creating a new type creates methods as well to process that type. We have a number of constructors for creating a new Set as well as methods for add and subtracting elements from the Set. We also have methods for the standard set operations such as union, difference and intersection. We will also add new methods to support the creation of new Sets from old sets plus elements - plus, minus.
import java.util.*;
public class Set
{
public BitSet thisSet;
public Set()
{ // A constructor
thisSet = new BitSet();
} // Just initialise the BitSet.
public Set(Set set)
{ // A constructor with an initial set.
thisSet = set.thisSet;
} // Assign the existing set to this one.
public Set(int element)
{ // A constructor with an initial element.
thisSet = new BitSet();
// Get the initial BitSet
thisSet.set(element);
} // and now set the element in this Set
void add(int element)
{ // A public method to add an element to this Set
thisSet.set(element);
} // Simply set the element in this Set
void subtract(int element)
{ // A public method to remove an element from this Set
thisSet.clear(element);
} // Simply clear the element in this Set
Set union(Set s)
{ // A public method to create a new set which is
// union of this Set and one passed as parameter.
Set s1 = new Set();
// Looks like a bug to me - why should I have to worry.
if(thisSet.size() > s.thisSet.size())
{ // Get a copy of this Set - don't change original.
s1.thisSet =(BitSet)thisSet.clone();
s1.thisSet.or(s.thisSet);
} // Now or in those elements.
else
{
s1.thisSet =(BitSet)s.thisSet.clone();
s1.thisSet.or(thisSet);
}
// Return the new union Set.
return (s1);
}
Set plus(int element)
{ // A public method to create a new set which is
// original set plus a new element
Set s1 = new Set();
// Get a copy of this Set - don't change original.
s1.thisSet =(BitSet)thisSet.clone();
s1.thisSet.set(element);
// add in the new element to the new Set.
return (s1);
} // Return the new Set.
Set difference(Set s)
{ // A public method to create a new set which is
// the difference in the two sets.
Set s1 = new Set();
s1.thisSet = (BitSet)thisSet.clone();
s1.thisSet.or(s.thisSet); s1.thisSet.xor(s.thisSet);
return (s1);
} // Return the new Set.
Set minus(int element)
{ // A public method to create a new set which is
// the old set minus the element specified.
Set s1 = new Set();
s1.thisSet = (BitSet)thisSet.clone();
s1.thisSet.clear(element);
// Get copy of Set and remove element
return (s1);
} // Return the new Set.
Set intersection(Set s)
{ // A public method to create a new set which is
// the intersection of this Set and one specified.
Set s1 = new Set();
s1.thisSet = (BitSet)thisSet.clone();
s1.thisSet.and(s.thisSet);
// Get copy of Set and perform intersection.
return (s1);
} // Return the new Set.
boolean equals(Set set)
{ // A public boolean method to test for equality
return(thisSet.equals(set.thisSet));
}
boolean notequals(Set set)
{ // A public boolean method to test for inequality
return(! thisSet.equals(set.thisSet));
}
boolean subset(Set set)
{ // A public boolean method to test
// if this Set is a subset of the one passed.
Set s1 = intersection(set);
return(s1.equals(this));
}
boolean superset(Set set)
{ // A public boolean method to test
// if this Set is a superset of the one passed.
Set s1 = intersection(set);
return(s1.equals(set));
}
boolean contains(int element)
{ // A public boolean method to test
// if this Set contains this element.
return (thisSet.get(element));
}
public String toString()
{ // A public method to help print out this Set
return(thisSet.toString());
}
}
The toString method can be part of every Java Object and is used when the Object is converted into a printable string (see examples of this in the Set testing code which follows). In this case, we have simply used the BitSet's toString method to print out this Set.
Here is some sample code to test the Set class. Notice that
we can use the methods in a very convenient manner - s1.add(12),
s2.subtract(120), s1.union(s2), s1.plus(212).minus(12),
if(s1.equals(s2)), if(s1.contains(12)), if(s1.subset(s2)).
Note as well that we can print out a set:
The second operand of the '+' operator above is converted
into a String by the toString method of the class. This is then
concatenated with the other two strings and then passed to the
output routine.
import local.units.sdsu.io.*;
import java.lang.*;
import java.util.*;
import java.io.*;
public class BitTest
{
// Mainline Variable Declarations
static PrintStream output = System.out;
static ASCIIInputStream input = new ASCIIInputStream(System.in);
public static void main(String argv[]) throws IOException
{
Set s1,s2;
s1 = new Set();
Format.print(output,"Initial empty set = " + s1 + "\n");
s1.add(12);
Format.print(output,"set 1 = " + s1 + "\n");
s1.add(1);s1.add(1030);
Format.print(output,"set 1 = " + s1 + "\n");
s2= new Set(5033);
Format.print(output,"set 2 = " + s2 + "\n");
s2.add(1);s2.subtract(12);
Format.print(output,"set 2 = " + s2 + "\n");
s2.subtract(1);
Format.print(output,"set 2 = " + s2 + "\n\n");
Format.print(output,"set 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
Format.print(output,"s1 union s2 = " + s1.union(s2) + "\n");
Format.print(output,"s2 union s1 = " + s2.union(s1) + "\n");
Format.print(output,"s1 difference s2 = " + s1.difference(s2) + "\n");
Format.print(output,"s2 difference s1 = " + s2.difference(s1) + "\n");
s1.add(5033);
Format.print(output,"set 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
Format.print(output,"s1 difference s2 = " + s1.difference(s2) + "\n");
Format.print(output,"s2 difference s1 = " + s2.difference(s1) + "\n");
Format.print(output,"s1 plus 24 = " + s1.plus(24) + "\n");
Format.print(output,"s2 plus 24 = " + s2.plus(24) + "\n");
Format.print(output,"s1 minus 24 = " + s1.minus(24) + "\n");
Format.print(output,"s2 minus 24 = " + s2.minus(24) + "\n");
Format.print(output,"s1 minus 5033 = " + s1.minus(5033) + "\n");
Format.print(output,"s2 minus 5033 = " + s2.minus(5033) + "\n");
s2.add(1023); s2.add(1);
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
Format.print(output,"s1 intersect s2 = " + s1.intersection(s2) + "\n");
Format.print(output,"s2 intersect s1 = " + s2.intersection(s1) + "\n");
s2.subtract(5033); s2.subtract(1);
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
Format.print(output,"s1 intersect s2 = " + s1.intersection(s2) + "\n");
Format.print(output,"s2 intersect s1 = " + s2.intersection(s1) + "\n");
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s1.equals(s2))Format.print(output,"Set 1 equals Set 2\n");
else Format.print(output,"Set 1 !equals Set2\n");
s2.subtract(1023);
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s1.equals(s2))Format.print(output,"Set 1 equals Set 2\n");
else Format.print(output,"Set 1 !equals Set2\n");
s2.add(1); s2.add(1030); s2.add(12); s2.add(5033);
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s1.equals(s2))Format.print(output,"Set 1 equals Set 2\n");
else Format.print(output,"Set 1 !equals Set2\n");
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s1.contains(12))Format.print(output,"Set 1 contains 12\n");
else Format.print(output,"Set 1 does not contain 12\n");
s1.subtract(12);
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s1.contains(12))Format.print(output,"Set 1 contains 12\n");
else Format.print(output,"Set 1 does not contain 12\n");
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s1.subset(s2))Format.print(output,"Set 1 is a subset of Set 2\n");
else Format.print(output,"Set 1 is not a subset of Set 2\n");
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s1.superset(s2))Format.print(output,"Set 1 is a superset of Set 2\n");
else Format.print(output,"Set 1 is not a superset of Set 2\n");
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s2.subset(s1))Format.print(output,"Set 2 is a subset of Set 1\n");
else Format.print(output,"Set 2 is not a subset of Set 1\n");
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s2.superset(s1))Format.print(output,"Set 2 is a superset of Set 1\n");
else Format.print(output,"Set 2 is not a superset of Set 1\n");
s1 = new Set();
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s1.subset(s2))Format.print(output,"Set 1 is a subset of Set 2\n");
else Format.print(output,"Set 1 is not a subset of Set 2\n");
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s1.superset(s2))Format.print(output,"Set 1 is a superset of Set 2\n");
else Format.print(output,"Set 1 is not a superset of Set 2\n");
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s2.subset(s1))Format.print(output,"Set 2 is a subset of Set 1\n");
else Format.print(output,"Set 2 is not a subset of Set 1\n");
Format.print(output,"\nset 1 = " + s1 + "\n");
Format.print(output,"set 2 = " + s2 + "\n");
if(s2.superset(s1))Format.print(output,"Set 2 is a superset of Set 1\n");
else Format.print(output,"Set 2 is not a superset of Set 1\n");
}
}
We could change the methods so that they translated
our "character" input and output parameters to and from the
internal BitSet format. For example, we could add the Unicode
equivalent value into the set.
public Set(char element)
{
thisSet = new BitSet();
thisSet.set((int)element);
}
void add(char element)
{
thisSet.set((int)element);
}
