Results 1 to 9 of 9
  1. #1
    jason3460 is offline Member
    Join Date
    Dec 2012
    Posts
    21
    Rep Power
    0

    Default Union and Intersection methods (SetADT)

    Hey, so i have this SetADT, and i need to add two methods, Union and Intersection.
    • The Union method will return a union of the two sets as an array to the calling program (no duplicates allowed).
    • The Intersection method will return the intersection of the two sets as an array to the calling program (no duplicates allowed).

    Can anyone guide me in the right direction to adding these two methods?

    SetADT.java
    Java Code:
    package DSA2;
    
    public class SetADT
    {
        //define fields
        private int pointer;
        private int[] setArray;
        
        //define methods
        public SetADT()
        {
            pointer = 0;
            setArray = new int[5];
        }
        
        public void add(int value)
        {
            if (!contains(value))
            {   //check available space
                //if not - increase the array size
                if (pointer == setArray.length)
                {
                    setArray = increaseSize();
                }
                
                setArray[pointer] = value;
                pointer++;
            }
        }
        
        @Override
        public String toString()
        {     
            StringBuilder sb = new StringBuilder();
            
            for(int index=0; index<pointer; index++)
            {  
                sb.append(setArray[index]);
                sb.append(", ");
            }
    
            return sb.toString();
        }//toString
        
        public boolean contains(int value)
        {
            for(int index=0; index < setArray.length; index++)
            {
                if(setArray[index]== value)
                {
                    return true;
                }
            }
            
            return false;
        }//contains
        
        private int[] increaseSize()
        {
            int size = setArray.length;
            int [] newArr = new int[size + 5];
            
            System.arraycopy(setArray, 0, newArr, 0, setArray.length);
            return newArr;
        }
        
        public int[] toArray()
        {
            int [] tmpArray = new int[pointer];
            System.arraycopy(setArray, 0, tmpArray,0, pointer);
            
            return tmpArray;
        }//toArray
        
    }
    Thanks in advance!

    Jason.

  2. #2
    jason3460 is offline Member
    Join Date
    Dec 2012
    Posts
    21
    Rep Power
    0

    Default Re: Union and Intersection methods (SetADT)

    Java Code:
    package DSA2;
     
    public class TestSet
    {
        public static void main(String[] args) 
        {
            SetADT set1 = new SetADT();
            SetADT set2 = new SetADT();
     
            set1.add(1);
            set1.add(2);
            set1.add(4);
            set1.add(5);
            set1.add(7);
     
            set2.add(1);
            set2.add(2);
            set2.add(3);
            set2.add(6);
            set2.add(7);
            set2.add(8);
     
     
            System.out.println(set1.toString());
     
            System.out.println();
     
            System.out.println(set2.toString());
     
            int [] setItems1 = set1.toArray();
     
            int [] setItems2 = set2.toArray();
     
            System.out.println(setItems1.length);
     
            System.out.println(setItems2.length);
     
        }
    }

    This is my test code, which adds several numbers to two different sets.

    I need to figure out how to implement the two methods, one producing the union, and the other the intersection of the two sets. I'm not sure how to do this, any help would be much appreciated.

    Thanks, Jason.

  3. #3
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,595
    Rep Power
    5

    Default Re: Union and Intersection methods (SetADT)

    You could just use one of the Set implementations. Sets may not contain duplicates so if you add the elements of both arrays to a single set, the result should be the union of the arrays. For intersections, add the elements of the arrays to two sets. Then iterate over the second set, noting when an element is in the first set. Those elements should constitute the intersection.

    If you're not allowed to use the Set implementations directly, you can emulate their behavior using a HashMap and a fixed object. The keys of the HashMap will comprise the set. Or you can just use a List and only add an element if the list does not contain the element.

    Disclaimer: I have not tested the above algorithms so they may not be 100% correct. If they are, they are probably not the most efficient way to accomplish the task.

    Regards,
    Jim
    Last edited by jim829; 05-07-2013 at 11:02 PM. Reason: Fixed egregious error
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,955
    Rep Power
    8

    Default Re: Union and Intersection methods (SetADT)

    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. #5
    jason3460 is offline Member
    Join Date
    Dec 2012
    Posts
    21
    Rep Power
    0

    Default Re: Union and Intersection methods (SetADT)

    I haven't learned about the Set implementations or HashMap and fixed keys, so i don't have a clue how to use these, the only way i can see how to do these two methods, is to use 'for' loops to iterate through the arrays/array, if I'm to combine both arrays into one single array and then iterate through, any help would be great, thanks.

  6. #6
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,595
    Rep Power
    5

    Default Re: Union and Intersection methods (SetADT)

    Well, then I suggest you work writing code to create a set. A set contains no duplicates. Then, once you get that done, use the set capability to apply the approach I suggested earlier. Again, this may not be the most efficient method of doing it but it should work.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  7. #7
    jason3460 is offline Member
    Join Date
    Dec 2012
    Posts
    21
    Rep Power
    0

    Default Re: Union and Intersection methods (SetADT)

    I'm not sure what you mean by creating a set, could you explain ?

  8. #8
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,595
    Rep Power
    5

    Default Re: Union and Intersection methods (SetADT)

    A set is a collection of elements which contains no duplicates. So if you add 1,2,3,4,3,2,1,3,4 to a set you would have 1,2,3,4. One way to construct a set is to sort the source array and then iterate thru the array, skipping over duplicates.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,512
    Blog Entries
    7
    Rep Power
    20

    Default Re: Union and Intersection methods (SetADT)

    If your ADT is set up correcty and implemented correctly; both the intersection and union are trivial; in pseudo code:

    Java Code:
    ADT intersection(ADT a, ADT b) {
       ADT inter= new ADT();
       for every element x in a:
          if (b contains x)
             inter.add(x);
       return inter;
    }
    
    ADT union(ADT a, ADT b) {
       ADT union= new ADT();
       for every element x in a:
          union.add(x);
       for every element x in b:
          union.add(x);
       return union;
    }
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Intersection of two Rectangles
    By Dex in forum New To Java
    Replies: 4
    Last Post: 03-25-2012, 02:28 PM
  2. SQL JOIN / UNION not sure what to do
    By Dcalladi in forum New To Java
    Replies: 1
    Last Post: 02-24-2012, 04:16 AM
  3. Volume of Intersection
    By afifi in forum Advanced Java
    Replies: 0
    Last Post: 01-07-2011, 10:42 AM
  4. Rectangle Intersection
    By Gwindow in forum Java 2D
    Replies: 1
    Last Post: 04-24-2008, 03:53 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
  •