Best way to make conjunctions and disjunctions over a collection in java

Question

What's the most efficient way to create an and and ormethods over two ArrayLists?

//not coded in java 

HashSet<String> first  = {"hello", "to", "you"}
HashSet<String> second = {"hello", "to", "me"}

HashSet<String> and = and(first, second) = {"hello", "to"}
HashSet<String> or = or(first, second) = {"hello", "to", "you", "me"}

I need to implement those two methods (pretty easy) but I would need to do it efficiently, because I will and and or over collections with hundreds of Strings. Any tip?

[`java.util.set`](http://docs.oracle.com/javase/7/docs/api/java/util/Set.html) offers an `addAll` (union, or 'or' method) and a `retainAll` (intersection, or 'and' method). So perhaps you're best off using `Set`s that support those operations if you can manage it, or else converting your lists to sets if it's not too expensive, and leveraging what already exists. — Chris Hayes, Jul 27 '14 at 19:33
Do you want to treat the lists as sets? Are you guaranteed that elements will appear only once? If not, what would you want to happen with (say) `{"a", "b", "a"}` and `{"b", "a", "b"}`? — Ted Hopp, Jul 27 '14 at 19:33

score 4 · Accepted Answer · edited May 23 '17 at 12:26

To avoid confusion I'll call the methods intersection and union as the meanings of AND and OR are a little ambiguous.

There is a retainAll method on Set that will do the job of the intersection. You need to take heed of my caveats in another answer (of mine) on SO.

There is an addAll method on Collection that will do the job of union.

Here is an example:

public static void main(String[] args) throws Exception {
    final Set<String> first = new HashSet<>(Arrays.asList("hello", "to", "you"));
    final Set<String> second = new HashSet<>(Arrays.asList("hello", "to", "me"));

    System.out.println(intersection(first, second));
    System.out.println(union(first, second));

}

public static Set<String> intersection(final Set<String> first, final Set<String> second) {
    final Set<String> copy = new HashSet<>(first);
    copy.retainAll(second);
    return copy;
}

public static Set<String> union(final Set<String> first, final Set<String> second) {
    final Set<String> copy = new HashSet<>(first);
    copy.addAll(second);
    return copy;
}

Note use usage of Set rather than List. This serves two purposes:

Set has O(1) contains as opposed to O(n) for a List. This helps in the intersection case.
Set guarantees uniqueness. This helps in the union case.

Also note that I copy the collections before carrying out the operations - as Java passes references by value not copying would cause the original collection to be changed.

If you need to preserve order, you will need to use a LinkedHashSet as a HashSet has no order.

Your link to your other answer is mistakenly a link to the `Set` javadoc. — Chris Hayes, Jul 27 '14 at 19:40
Sorry, yes. I used the more traditional usage - in your usage I have it backwards. — Boris the Spider, Jul 27 '14 at 19:54

score 0 · Answer 2 · answered Jul 27 '14 at 19:36

0

You can use Set for that, just need to cast.

List<String> list = new ArrayList<String>();
Set<String> set = new HashSet<String>(list);

And use its methods to do that

answered Jul 27 '14 at 19:36

Arian Kiehr

413
5
13

This isn't English this is programming - cast has a [very specific meaning](http://howtoprogramwithjava.com/java-cast/). – Boris the Spider Jul 27 '14 at 21:36

score 0 · Answer 3 · edited May 23 '17 at 10:30

0

You want to make the intersection and the union of two ArrayLists. I think that this is a duplicate question. I suggest to take a look at this thread: Intersection and union of ArrayLists in Java

edited May 23 '17 at 10:30

Community

1
1

answered Sep 03 '16 at 13:25

Abderrahmen

440
3
6

Best way to make conjunctions and disjunctions over a collection in java

3 Answers3