Results 1 to 9 of 9
 05072013, 02:10 PM #1Member
 Join Date
 Dec 2012
 Posts
 21
 Rep Power
 0
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 }
Jason.
 05072013, 05:36 PM #2Member
 Join Date
 Dec 2012
 Posts
 21
 Rep Power
 0
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.
 05072013, 05:37 PM #3Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 4,547
 Rep Power
 7
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,
JimLast edited by jim829; 05072013 at 11:02 PM. Reason: Fixed egregious error
The Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 05072013, 05:42 PM #4
Re: Union and Intersection methods (SetADT)
Crossposted: Union and Intersection methods (SetADT)
How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 05072013, 06:02 PM #5Member
 Join Date
 Dec 2012
 Posts
 21
 Rep Power
 0
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.
 05072013, 06:06 PM #6Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 4,547
 Rep Power
 7
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,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 05072013, 06:12 PM #7Member
 Join Date
 Dec 2012
 Posts
 21
 Rep Power
 0
Re: Union and Intersection methods (SetADT)
I'm not sure what you mean by creating a set, could you explain ?
 05072013, 06:21 PM #8Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 4,547
 Rep Power
 7
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,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 05072013, 07:18 PM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,951
 Blog Entries
 7
 Rep Power
 22
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; }
JosI have the stamina of a seal; I lie on the beach instead of running on it.
Similar Threads

Intersection of two Rectangles
By Dex in forum New To JavaReplies: 4Last Post: 03252012, 02:28 PM 
SQL JOIN / UNION not sure what to do
By Dcalladi in forum New To JavaReplies: 1Last Post: 02242012, 05:16 AM 
Volume of Intersection
By afifi in forum Advanced JavaReplies: 0Last Post: 01072011, 11:42 AM 
Rectangle Intersection
By Gwindow in forum Java 2DReplies: 1Last Post: 04242008, 03:53 PM
Bookmarks