Perform set operations using Java collection classes
All collection classes have methods to perform difference, addition and intersection operations. All these methods can be combined together to introduce set operations on the collection elements. If you are not familiar with set theory then the operations involved in set theory are intersection, union, difference and subset etc.
We shall see each of the set operation and its implementation in this article:
1) Union :
Union operation is the combination of two sets to form a third set which has elements from both the sets. The duplicate elements from child sets are not kept in the third set.
Implementation of Union:
- Iterate over both the collections in different for loops. Check if the element from child collection is already present in the final collection. If not present, add the element to final collection else continue.
- Add the elements from the child collections into a Set (HashSet, LinkedHashSet or TreeSet etc.) using the addAll method. This set represents the union of child collections with no duplicates.
- For list based collections, use the Apache commons ListUtils union method.
2) Intersection :
Intersection operation is the creation of a final set which contains the common elements among two or more child sets. If there are no common elements among the child sets, the final set is empty.
Implementation of Intersection:
- Iterate over one of the child and invoke contains() method on rest of child collections to check if the current element from first collection is present in rest of the child collections. If present in other collections for which intersection operation is to be performed then add the current element into a third collection else continue with iteration.
- For List based collections, use the intersection method from ListUtils class.
- There is a method named retainAll(Collection c) which performs intersection operation but it is optional and may not be implemented by all collection classes in Java.
3) Sum :
Sum operation is the final set left after taking union of child sets and then subtracting the intersection of child collections from the union.
Implementation of Sum:
- Calculate the union and intersection using the above methods and then remove the intersection elements from union elements to get the sum.
- For List based collections, use the sum function from ListUtils class.
4) Subtract or Complement :
Subtraction set operation is about removing the elements from one set which are present in another set.
Implementation of Subtract:
- Iterate over one of the child and invoke contains() method on rest of child collections to check if the current element from first collection is present in rest of the child collections. If present in other collections then remove the current element from the iterated collection. The iterated collection will contain the final set.
- For List based collections, use the subtract method from ListUtils class.
- There is a method named removeAll(Collection c) which performs subtract operation but it is optional and may not be implemented by all collection classes in Java.
5) Cartesian Product :
A set can also be constructed by creating pairs from multiple sets. In this case, one element from first set is taken and is paired with each element from other set. This operation is denoted by A X B.
Implementation of Subtract:
- Iterate over first collection and use the current object as the key and then iterate for other collection within the first iteration to get the value object. Insert the key and value into a HashMap, LinkedHashMap or TreeMap to get the final set.
The ListUtils has can provide ready made implementation of these operations for ArrayList and LinkedList etc.
The Google collections library named Gauva can also come handy for some of the operations listed above.