Results 1 to 4 of 4
Like Tree2Likes
  • 2 Post By JosAH

Thread: Sets Question

  1. #1
    Malv is offline Member
    Join Date
    Jun 2013
    Posts
    62
    Rep Power
    0

    Default Sets Question

    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:

    Java Code:
    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?

  2. #2
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,326
    Rep Power
    5

    Default Re: Sets Question

    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
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,305
    Blog Entries
    7
    Rep Power
    20

    Default Re: Sets Question

    Quote Originally Posted by jim829 View Post
    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
    gimbal2 and kjkrum like this.
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,326
    Rep Power
    5

    Default Re: Sets Question

    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
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

Similar Threads

  1. Maps and Sets
    By darkblue24 in forum New To Java
    Replies: 19
    Last Post: 03-25-2010, 06:13 PM
  2. Maps and Sets
    By RedKMan in forum New To Java
    Replies: 3
    Last Post: 02-16-2010, 09:36 AM
  3. Duplicates in more than two sets
    By JavaJ in forum New To Java
    Replies: 8
    Last Post: 12-03-2009, 04:07 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •