Home



2019/08 - DS&A #5: Sets

Hey folks!

Today we'll be taking a look at what is probably the easiest data structure to understand and develop: The SET! The Set is, pretty much, an unordered collection of objects that doesn't allow for duplicates. If a list didn't allow you to access specific element via it's indices and didn't allow you to repeatedly add the same object(s) to it (Or at least ignored such attempts), it would essentially be a Set. For this example we'll be using Strings as the objects added to the data structyre. We'll also be adding four additional methods to demonstrate the computer-sciencey aspects of a Set, namely Union, Intersection, Set Difference and Symmetric Difference. They're just methods that you can use to return particular Sets from the results of two other Sets.

So let's beging with some basic starting code:

 public class Set {
    
    private ArrayList<String> listOfStrings;
    
    public Set() {
        listOfStrings = new ArrayList<String>();
    }
    
    public Set(ArrayList<String> initialSet) {
        listOfStrings = new ArrayList<String>(initialSet);
    }

 

First up we have the Union method. This method accepts another Set for comparison purposes. It then returns a new Set that is a combination of both this classes internal Set, and the comparsion Set (With no duplicates);

    public Set union(ArrayList<String> comparisonSet){
        Set combinedSet = new Set(listOfStrings);
        
        for(int i = 0; i < comparisonSet.size(); i++) {
            combinedSet.add(comparisonSet.get(i));
        }
        
        return combinedSet;
    }
  

 

The intersection of two sets will return all objects that are common to both Sets:

    public Set intersection(ArrayList<String> comparisonSet){
        Set combinedSet = new Set();
        
        for (int i = 0; i < listOfStrings.size();i++) {
            if(comparisonSet.contains(listOfStrings.get(i))) {
                combinedSet.add(listOfStrings.get(i));
            }
        }
        
        return combinedSet;
    }
    

 

The Set Difference is kinda like the opposite of the intersection, it returns a new Set that contains all objects that are in either Set, that aren't in both:

    //The difference of the two arrays, for the first list
    public Set setDifference(ArrayList<String> comparisonSet){
        Set firstDifferencesSet = new Set();
        
        for (int i = 0; i < listOfStrings.size();i++) {
            if(!comparisonSet.contains(listOfStrings.get(i))) {
                firstDifferencesSet.add(listOfStrings.get(i));
            }
        }
        
        return firstDifferencesSet;
    }
    

 

The Symmetric Difference is basically the same as a Union. The guide I was originally using to learn Set Theory didn't seem to make much of a distinction between the two, but here it is anyway:

    public Set symmetricDifference(ArrayList<String> comparisonSet){
        Set allDifferencesSet = new Set();
        
        for (int i = 0; i < listOfStrings.size();i++) {
            if(!comparisonSet.contains(listOfStrings.get(i))) {
                allDifferencesSet.add(listOfStrings.get(i));
            }
        }
        
        for (int i = 0; i < comparisonSet.size();i++) {
            if(!listOfStrings.contains(comparisonSet.get(i))) {
                allDifferencesSet.add(comparisonSet.get(i));
            }
        }
        
        return allDifferencesSet;
    }
    

 

Simple add and remove methods that don't allow duplicates to be added to our Set. They also return booleans to notify the caller whether the operation was successful or not:

    public boolean add(String newString) {
        if(listOfStrings.contains(newString)) {
            return false;
        }
        else {
            listOfStrings.add(newString);
            
            return true;
        }
    }

    public boolean remove(String newString) {
        if(listOfStrings.contains(newString)) {
            listOfStrings.remove(newString);
            return true;
        }
        else {
            
            return false;
        }
    }

 

A simple print method:


    public void printContents() {
        for(int i = 0; i < listOfStrings.size(); i++) {
            System.out.println(listOfStrings.get(i));
        }
        
    }
    

 

And finally our Main method with some tests:


    public static void main(String[] args) {
        
        ArrayList<String> setOne = new ArrayList<String>();
        setOne.add("One");
        setOne.add("Two");
        setOne.add("Three");
        setOne.add("Four");
        setOne.add("Five");
        setOne.add("Six");
        
        ArrayList<String> setTwo = new ArrayList<String>();
        setTwo.add("Four");
        setTwo.add("Five");
        setTwo.add("Six");
        setTwo.add("Seven");
        setTwo.add("Eight");
        setTwo.add("Nine");
        
        Set set = new Set(setOne);
        System.out.println("*****");
        set.union(setTwo).printContents();
        System.out.println("*****");
        set.intersection(setTwo).printContents();
        System.out.println("*****");
        set.symmetricDifference(setTwo).printContents();
        System.out.println("*****");
        set.setDifference(setTwo).printContents();
        System.out.println("*****");
        
    }
    

 

The Set is a fairly basic data structure, nice and simple to put together and understand. Eventually we'll get around to balancing binary tree's, which can get pretty complicated pretty quickly. But for now...

Good luck!