CODEWITHSUNDEEP
javaarraysboolean
Kat Demidova
Kat Demidova

Reputation: 57

array of booleans to represent a set of integers

Hey I was wondering if anyone could explain this further. This is not an assignment, it's just a solution to one of my tests I had. I've been trying to understand it but I'm not sure..

Basically the question for the answer given is:

[i]Write a class in Java called RangeSet which uses the data structure of an array of booleans to represent a set of integers using 3 methods: [list] []add - adds an item but leaves the set unchanged if the item is already a member of the set []remove - removes an item but leaves the set unchanged if the item is not a member of the set [*]contains - returns a boolean value which says whether an item is a member of the set [/list]

there should be one constructor for the class which takes an integer n and gives an object representing a set that can hold integers in the range 1 to n inclusive. The constructor should give an empty set. The set should be destructive. The methods should return true if the set was changed by operation and false if it was not.[/i]

Basically, here it is, a Set of integers limited to a range 1 to n, implemented by an array of booleans The methods add and remove return a boolean saying whether the set has been changed by their call, it is assumed all arguments to the methods add, remove and contains will be within the 1 to n range so there is no special code to deal with the cases when the argument is not in range.

class RangeSet
{
     private boolean[] arr;

     public RangeSet(int n)
    {
          arr = new boolean[n];
    }

     public boolean add(int n)
    {
        if(arr[n-1]) return false;
        arr[n-1]=true;
        return true;
     }

    public boolean remove(int n)
    {
        if(!arr[n-1]) return false;
        arr[n-1]=false;
        return true;
    }

     public boolean contains(int n)
     {
          return arr[n-1];
     }
}

So i'm wondering, how come arr = new boolean[n] and add(int n) are both represented by 'n' ? And doesn't the solution check the location of the newly entered integer instead of checking for an actual value? Thank you.

Upvotes: 0

Views: 2242

Answers (6)

nothingme
nothingme

Reputation: 55

In the add(n) method:

I get it if arr[n-1] is set to true because that's where the new element will be attached?

But how does it checking if there's no given element in the set with checking only the last position - (arr[n-1]) .. Doesnt that mean we are only checking the element in the last position and not the whole array to find if the given integer by the user is in the set?

Upvotes: 0

Mel Nicholson
Mel Nicholson

Reputation: 3225

The selection of the letter n for the parameter name generally means that the input is a number without additional meaning. There is a good argument to be made for naming the parameter to the constructor something more meaningful like max but this isn't that important. The important thing to understand is that the values are not related to each other even though they have the same name.

If arr[x-1] is true, then x is a member of the set. Otherwise it is not.

The condition of an if statement is any boolean. Comparisons are common, but no less valid than using a boolean directly like so:

boolean flag = false; 
//lots of code
if (x < 0) flag = true;
//lots more code that changes the value of x
if (flag) {
  //do the thing for negative values
} else {
  //do the thing for positive values
}

Your example is doing that same sort of thing, but for a whole array of flags.

Upvotes: 1

Stefano Sanfilippo
Stefano Sanfilippo

Reputation: 33116

That n is just a placeholder. What happens here is that you have N cells in your array and the n-th cell is set to true when you add the number n (provided that n <= N) to your set. So, arr[n-1] (-1 because Java arrays are zero-based) contains true if number n is in the set, false otherwise.

Note that if you try to insert n > N, you will get an exception.

Upvotes: 1

JB Nizet
JB Nizet

Reputation: 692181

n (in the constructor) and n (in the add method) are two different local variables that happen to share the same name. The names could be different, and it would be a bit less confusing, but given that the scope of the variable is limited to the constructor (or the method), using the same name is allowed and correct.

arr[n-1] is the boolean stored at the index n-1 of the array. So, if (arr[n-1]) is equivalent to:

boolean valueAtNMinusOne = arr[n-1];
if (valueAtNMinusOne == true)

but it's more concise, and as readable to a seasoned Java developer.

Upvotes: 1

Mateusz
Mateusz

Reputation: 3048

The n passed in constructor/method is only in the scope of it, i.e. n set by add() doesn't affect remove().

As you've got integers from <1; n>, you need n boolean values which will be true if the element of value n has already been inserted. That's what arr does. Java indexes array elements from 0 not 1, hence n-1.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727047

This implementation is spot-on, assuming that you're OK with bounds checking exceptions thrown by JVM rather than rolling your own. This is perfectly acceptable, because Java arrays always do bounds checking for you, so there is no danger of accessing something outside the bounds of the array and not get an exception.

The n inside

public RangeSet(int n)

and n inside

boolean add(int n)

are not related. Function parameters are similar to local variables, in the sense that their name means nothing outside the scope of a given function.

Also note that since the array is boolean you do not need explicit comparisons with true or false: using arr[n-1] and !arr[n-1] is sufficient.

Upvotes: 4

Related Questions