Question:
I'm implementing the set of integers exercise from the deitel 6th edition book:
Create the IntegerSet class. Each IntegerSet object can store integers in the range 0 to 100. The set is represented by a boolean array. The element of array[i] is true if the integer i is in the set. The element of array[j] is false if the integer j is not in the set. The no-argument constructor initializes the Java array to 'empty set' (that is, a set whose array representation contains all false values).
Provide the following methods :
The union method creates a third set that is the theoretical union of two existing sets (that is, an element of the third array of the set is set to true if that element is true in either or both of the existing sets; otherwise, the element of the third set is set to false ).
The intersecction method creates a third set that is the theoretical intersection of two existing sets (that is, an array element of the third set is set to false if that element is false in either or both of the existing sets – otherwise, the element of the third set is set to true ).
The insertElement method inserts a new integer k into a set (setting a[k] to true ).
The deletElement method deletes the integer m (by setting a[m] to false ).
The toSetString method returns a string containing a space-separated list of numbers. Include only elements that are present in the set. Use -- to represent an empty set.
The isEqualTo method determines whether two sets are equal.
This is the code I've built so far, but some doubts have arisen. How can I declare a single IntegerSet object in the parameter and do the comparison for union or intersection, is that possible?
public class IntegerSet{
private int positions;
public boolean array[];
public IntegerSet(){
this.array = new boolean[101];
}
public boolean[] union(IntegerSet iSet1, IntegerSet iSet2){
boolean tConjunto[] = new boolean[101];
for(int i=0; i<array.length; i++){
if(iSet1 || iSet2){
tConjunto[i] = true;
}
return tConjunto;
}
}
public boolean[] intersection(IntegerSet iSet1, IntegerSet iSet2) {
boolean tConjunto[] = new boolean[101];
for(int i=0; i<array.length; i++){
if(iSet1 && iSet2){
tConjunto[i] = false;
}
return tConjunto;
}
}
public void insertElement(int k){
this.array[k] = true;
}
public void deletElement(int m){
this.array[m] = false;
}
public String toSetString(){
return "oi";
}
public boolean isEqualsTo(IntegerSet iSet1, IntegerSet iSet2) {
for (int i = 0; i < array.length; i++) {
if (iSet1 != iSet2) {
return false;
}
}
return true;
}
}
Answer:
The IntegerSet class represents a set, so – as I understand it – the methods for union and intersection should have these signatures:
public IntegerSet intersecction(IntegerSet outro)
public IntegerSet union(IntegerSet outro)
That is, they receive another IntegerSet and return another IntegerSet containing the result of the intersection (or union). For example, s3 = s1.union(s2) – the method returns a set that is the union of s1 with s2 (and the result is assigned to s3 ).
Another detail is that the positions variable is not used for anything. If the size is always the same, it's better to create a "constant" (a static final variable) for that.
Also, the methods for inserting and removing an element must not take the array as a parameter. The array you want to modify is the one declared in the class itself, these methods can only receive the index that will be modified.
An alternative solution would be:
public class IntegerSet {
private static final int TAMANHO = 101;
private boolean array[];
public IntegerSet() {
this.array = new boolean[TAMANHO];
}
private IntegerSet(boolean values[]) {
this.array = values;
}
// retorna a intersecção deste Set com outro
public IntegerSet intersecction(IntegerSet outro) {
boolean intersect[] = new boolean[TAMANHO];
for (int i = 0; i < TAMANHO; i++) {
intersect[i] = this.array[i] && outro.array[i];
}
return new IntegerSet(intersect);
}
// retorna a união deste Set com outro
public IntegerSet union(IntegerSet outro) {
boolean un[] = new boolean[TAMANHO];
for (int i = 0; i < TAMANHO; i++) {
un[i] = this.array[i] || outro.array[i];
}
return new IntegerSet(un);
}
public void insertElement(int pos) {
this.array[pos] = true;
}
public void deletElement(int pos) {
this.array[pos] = false;
}
public String toSetString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < TAMANHO; i++) {
if (this.array[i]) { // número i pertence ao set
if (sb.length() == 0) {
sb.append(i);
} else {
sb.append(" ").append(i);
}
}
}
return sb.length() == 0 ? "--" : sb.toString();
}
// verifica se este set é igual a outro
public boolean isEqualsTo(IntegerSet outro) {
for (int i = 0; i < TAMANHO; i++) {
if (this.array[i] != outro.array[i]) {
// achei um elemento diferente, os sets não são iguais
return false;
}
}
return true;
}
}
For the union and intersection I create a third array and fill its values according to the required rules. As they are boolean values, I can directly assign the result of operations && and || . In this case, for intersection I used && :
intersect[i] = this.array[i] && outro.array[i];
So, if both ( this.array[i] and outro.array[i] ) are true (that is, if the number i belongs to both sets), then it will be true in the third array as well. For the union, I use || :
un[i] = this.array[i] || outro.array[i];
In this case, if one of the two is true , it's enough to be in the third array.
Also notice that I created a private constructor for the class:
private IntegerSet(boolean values[]) {
this.array = values;
}
So I can create a set by passing a specific array to it. As it is private , it can only be used inside the class – in this case, I used it to pass the array I created in the methods for intersection and union. If you want anyone to be able to create a set with any array, just leave the constructor public (but in that case it would be good to check the size of the array before setting it).
The toSetString() method traverses the array and only considers those that are true . An additional check is made to see if there should be a space before the number, plus another check at the end to see if the set is empty.
And the isEqualsTo method takes another set and compares the respective arrays. If I find any different, I can already return that the sets are not the same. If you reach the end of the loop, then everyone is the same.
Testing:
IntegerSet s1 = new IntegerSet();
s1.insertElement(10);
s1.insertElement(20);
s1.insertElement(30);
IntegerSet s2 = new IntegerSet();
s2.insertElement(10);
s2.insertElement(15);
s2.insertElement(20);
s2.insertElement(25);
System.out.println("s1=" + s1.toSetString());
System.out.println("s2=" + s2.toSetString());
System.out.println("intersecção=" + s1.intersecction(s2).toSetString());
System.out.println("união=" + s1.union(s2).toSetString());
System.out.println("s1 e s2 iguais? " + s1.isEqualsTo(s2));
IntegerSet s3 = new IntegerSet();
s3.insertElement(30);
s3.insertElement(10);
s3.insertElement(20);
System.out.println("s1 e s3 iguais? " + s1.isEqualsTo(s3));
s3.deletElement(20);
System.out.println("s1 e s3 iguais? " + s1.isEqualsTo(s3));
System.out.println("set vazio: " + new IntegerSet().toSetString());
Exit:
s1=10 20 30
s2=10 15 20 25
intersecção=10 20
união=10 15 20 25 30
s1 e s2 iguais? false
s1 e s3 iguais? true
s1 e s3 iguais? false
set vazio: --