Sets Question

[Malv]

Sets of things from small domains can be efficiently represented as bitmaps. So, for example, if we know that our set can contain just numbers between 0 and 9 then we can represent as a bitmap of length ten where a 1 at position i indicates that i is a member of the set. So, for example, the set: {1,2,5} can be represented by the bitmap: 0110010000.

Write a class, called BitMapSet, that implements the Set interface. Write BitMapSet so that it can b e used to represent sets of numbers between zero and 99. To make the coding easier use an array of Boolean to represent the bitmap.

So here's the Set interface:

public interface Set<T>{

    /**
     Adds an element to the set.
     Attempts to add duplicates result in no
     Change to the set.
     @param val The value to be added.
    **/
    public void add(T val);

    /** 
     Remvoves an element from the set.
     Does nothing if element is not present.
     @param val The value to be removed.
    **/
    public void remove(T val);

    /** 
        Returns true if val is member of the set.
        @param val The value to be searched for.
        @return true if the val is in the set.
    **/
    public boolean contains(T val);


    /**
       Returns an array representation of the set.
       @return an array representation of the set.
    **/
    public Object[] toArray();

    /** 
      Returns true if the set is empty.
    **/

    public boolean empty();
}

Question is :

How do I write BitMapSet so that it can be used to represent sets of numbers between 0 and 99? Means I were to create a Set that only allow int from 0 - 99?

use an boolean array to present the bitmap : from what I understand it's storing trues and falses in an array. So I were to supposed that true is 1 and false is 0. with this boolean array, I can then come up with something like 01000101. That's what I think.

Any comments to solve this?

[jim829]

Since the Set interface is a generic type you just implement it using the formal type parameter T. So then if you have say MySet you can inovke:

Set<Integer> set = new BitMapSet<Integer>();

According to the instructions, my interpretation is that the bit map set maintains a boolean array of an arbitrary size and unlike the JDK implementations may contain duplicates (containing some number of true or false values). But I encourage you to discuss this with your instructor.

Regards,
Jim

[JosAH]

Since the Set interface is a generic type you just implement it using the formal type parameter T. So then if you have say MySet you can inovke:

Set<Integer> set = new BitMapSet<Integer>();

According to the instructions, my interpretation is that the bit map set maintains a boolean array of an arbitrary size and unlike the JDK implementations may contain duplicates (containing some number of true or false values). But I encourage you to discuss this with your instructor.

That implies that you could also have a, say, BitMapSet<String> etc. I don't think it's wise to generify the BitMapSet iself; just make it implement the Set<Integer> interace.

kind regards,

Jos

[jim829]

I see what you mean. There is no implied or well defined linear relationship in an array of Strings so it wouldn't really make sense.

Regards,
Jim