How to do union, intersect, difference and reverse data in java

Question

I want to implement the union, intersect, difference and reverse operations in Java.

First I have 2 instances of ArrayList<Integer>

a = [0,2,4,5,6,8,10]
b = [5,6,7,8,9,10]

a union b should return c = [0,2,4,5,6,7,8,9,10]

a intersect b should return c = [5,8,10]

a difference b should return c = [0,2,4]

reverse a = [10,8,6,5,4,2,0]

Something like this.

How to implement that method in Java?

---

Update: I have to start with this template:

package IntSet;
import java.util.ArrayList;
import java.util.Collection;


public class IntSet {

private ArrayList<Integer> intset;

public IntSet(){
    intset = new ArrayList<Integer>();
}

public void insert(int x){
    intset.add(x);
}

public void remove(int x){
    //implement here
    intset.indexOf(x);
}

public boolean member(int x){
    //implement here
    return true;
}

public IntSet intersect(IntSet a){
    //implement here
    return a;
}

public IntSet union(IntSet a){
    //implement here
    return a;
}

public IntSet difference(IntSet a){
    //implement here
    IntSet b = new IntSet();
    return b; 
}

Answer 1

First, the operations you describe (except reverse) are set operations, not list operations, so use HashSet or (if you need an ordering) TreeSet.

    Set<Integer> a = new TreeSet<Integer>(Arrays.asList(new Integer[]{0,2,4,5,6,8,10}));
    Set<Integer> b = new TreeSet<Integer>(Arrays.asList(new Integer[]{5,6,7,8,9,10}));

    //union
    Set<Integer> c = new TreeSet<Integer>(a);
    c.addAll(b);
    System.out.println(c);

    //intersection
    Set<Integer> d = new TreeSet<Integer>(a);
    d.retainAll(b);
    System.out.println(d);

    //difference
    Set<Integer> e = new TreeSet<Integer>(a);
    e.removeAll(b);
    System.out.println(e);

    //reverse
    List<Integer> list = new ArrayList<Integer>(a);
    java.util.Collections.reverse(list);
    System.out.println(list);

Answer 2

//Union 
List<Integer> c = new ArrayList<Integer>(a.size() + b.size());
addNoDups(c,a);
addNoDups(c,b);

private void addNoDups(List<Integer> toAddTo,List<Integer> iterateOver) {
    for(Integer num:iterateOver){
        if(toAddTo.indexOf(num) == -1) {
            toAddTo.add(num);
        }
    }
}

//intersection
List<Integer> c = new ArrayList<Integer> (a.size() > b.size() ?a.size():b.size());
c.addAll(a);
c.retainAll(b);

//difference a-b
List<Integer> c = new ArrayList<Integer> (a.size());
c.addAll(a);
c.removeAll(b);

Answer 3

If you are using Sets (as you should, for all of those except reverse are Set operations), Guava provides these operations in it's Sets class.

Set<Integer> union = Sets.union(set1, set2);
Set<Integer> intersection = Sets.intersection(set1, set2);
Set<Integer> difference = Sets.difference(set1, set2);

All of these return unmodifiable views, backed by the original Sets.

See Guava Explained -> Collection Utilities -> Sets

If Lists are what you have, you can convert them to a Set by using the copy constructor present in all standard collections:

List<X> list = new ArrayList<>();
// fill up list here
Set<X> set = new HashSet<>(list);

Answer 4

A lot of the answers tell you to use libraries that will do the work for you. While this is the right solution for the real world, keep in mind hat you're doing homework, and your teacher probably wants you to understand how the functions are written, not just how to find libraries to do the work for you.

That said, you've got a good start with the code you've shown. Let's take the problem one step at a time.

First, do you know where the Java documentation is located? http://download.oracle.com/javase/1.4.2/docs/api/ this is critical, as this is how you find out what functions do what. Here's the link to Java 1.4. I didn't notice what version you're using, but Java is backward compatible, so this should be sufficient.

In the docs, find the ArrayList entry.

Now that we've got the API docs, we need to break down your question. you've posted code, so I'll address it function by function.

insert() : do you have to have an ordered list, or does order not matter? Or are you guaranteed that values will be provided to you in order? Have you learned sorting algorithms yet?

remove() : this function doesn't work. take a look at the ArrayList API and see how to remove an item from the list. Use that method.

member() : your member method doesn't work. You need to check every entry of the list and determine if the current member matches the function argument. Have you learned about for loops?

intersect() : ok, tell me in English what intersect is supposed to do. Don't use the teacher's description if you can help it - use your own words (note to others, this is an exercise for the OP to learn to program, so please don't go answering it for him)

difference() : again, tell me in English what it's supposed to do.

reverse() : again, give me the English description of what this is supposed to do.

Once you have english descriptions, describe an algorithm that can do the work. don't write it in Java yet. just write an algorithm, in english, describing how you would do the work manaully, with pen and paper.

at this point, try and convert the algorithm to Java code.

Answer 5

I just will leave it here. There is a new way with java-8 and streams

List<Integer> listA = Arrays.asList(0, 2, 4, 5, 6, 8, 10);
List<Integer> listB = Arrays.asList(5, 6, 7, 8, 9, 10);

List<Integer> intersection = listA.stream()
        .filter(listB::contains)
        .collect(Collectors.toList());

List<Integer> union = Stream.concat(listA.stream(), listB.stream())
        .distinct().sorted()
        .collect(Collectors.toList());

List<Integer> aDiffB = listA.stream()
        .filter(i -> !listB.contains(i))
        .collect(Collectors.toList());

System.out.println(intersection); // [5, 6, 8, 10]
System.out.println(union); // [0, 2, 4, 5, 6, 7, 8, 9, 10]
System.out.println(aDiffB); // [0, 2, 4]

Answer 6

This snippet will find the union of two collections using apache commons CollectionUtils.union method

Collection<String> totalFriends = CollectionUtils.union(yourFriends, myFriends);

Answer 7

The methods addAll, retainAll and removeAll are the methods most commonly used to implement union, intersect and difference in Java. With Streams in Java 8+, you do have some more options for intersect and difference using filter as pointed out in a previous answer.

If you're open to using a third-party library, the following code will work with primitive collections using Eclipse Collections when version 11.0 of the library is released.

@Test
public void unionIntersectDifferenceReverse()
{
    IntList list1 = IntLists.immutable.with(0, 2, 4, 5, 6, 8, 10);
    IntList list2 = IntLists.immutable.with(5, 6, 7, 8, 9, 10);

    MutableIntSet set1 = list1.toSet();
    MutableIntSet set2 = list2.toSet();

    IntSet union = set1.union(set2);
    IntSet intersection = set1.intersect(set2);
    IntSet difference = set1.difference(set2);

    IntList reversed = list1.toReversed();

    Assert.assertEquals(IntSets.mutable.with(0, 2, 4, 5, 6, 7, 8, 9, 10), union);
    Assert.assertEquals(IntSets.mutable.with(5, 6, 8, 10), intersection);
    Assert.assertEquals(IntSets.mutable.with(0, 2, 4), difference);
    Assert.assertEquals(IntLists.mutable.with(10, 8, 6, 5, 4, 2, 0), reversed);
}

This functionality was recently contributed to primitive Sets in Eclipse Collections. The linked blog describes how these methods are implemented on primitive sets.

The following code uses object collections with boxed Integers. This code will work with Eclipse Collections releases available today.

@Test
public void unionIntersectDifferenceReverseWithBoxedIntegers()
{
    ImmutableList<Integer> list1 = Lists.immutable.with(0, 2, 4, 5, 6, 8, 10);
    ImmutableList<Integer> list2 = Lists.immutable.with(5, 6, 7, 8, 9, 10);

    MutableSet<Integer> set1 = list1.toSet();
    MutableSet<Integer> set2 = list2.toSet();

    MutableSet<Integer> union = set1.union(set2);
    MutableSet<Integer> intersection = set1.intersect(set2);
    MutableSet<Integer> difference = set1.difference(set2);

    ImmutableList reversed = list1.toReversed();

    Assert.assertEquals(Sets.mutable.with(0, 2, 4, 5, 6, 7, 8, 9, 10), union);
    Assert.assertEquals(Sets.mutable.with(5, 6, 8, 10), intersection);
    Assert.assertEquals(Sets.mutable.with(0, 2, 4), difference);
    Assert.assertEquals(Lists.mutable.with(10, 8, 6, 5, 4, 2, 0), reversed);
}

Note: I am a committer for Eclipse Collections.