Set utilities

AAA_Set_Utils.txt

Set utilities

GeneratePowerSetJTests.java

package com.blogspot.groglogs.test.setutils;

import com.blogspot.groglogs.setutils.SetUtils;
import org.junit.Test;

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;

public class GeneratePowerSetJTests {

    Set<Integer> set;
    Set<Set<Integer>> powerSet, expected;

    @Test
    public void nullEmpty() {
        set = null;
        powerSet = SetUtils.generatePowerSet(set);
        assertNull("null", powerSet);

        set = new HashSet<>();
        powerSet = SetUtils.generatePowerSet(set);
        assertEquals("empty", 1, powerSet.size());
        assertTrue("contains empty set", powerSet.contains(set));
    }

    @Test
    public void oneElement() {
        set = new HashSet<>();
        set.add(1);
        powerSet = SetUtils.generatePowerSet(set);
        expected = new HashSet<>();
        expected.add(set);
        expected.add(Collections.emptySet());
        assertEquals("one element", expected.size(), powerSet.size());
        for(Set<Integer> s : expected) {
            assertTrue("contains set", powerSet.contains(s));
        }
    }

    @Test
    public void moreElements() {
        set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        powerSet = SetUtils.generatePowerSet(set);
        expected = new HashSet<>();
        expected.add(set);
        Set<Integer> s1 = new HashSet<>();
        s1.add(1);
        s1.add(2);
        expected.add(s1);
        Set<Integer> s2 = new HashSet<>();
        s2.add(2);
        s2.add(3);
        expected.add(s2);
        Set<Integer> s3 = new HashSet<>();
        s3.add(1);
        s3.add(3);
        expected.add(s3);
        Set<Integer> s4 = new HashSet<>();
        s4.add(1);
        expected.add(s4);
        Set<Integer> s5 = new HashSet<>();
        s5.add(2);
        expected.add(s5);
        Set<Integer> s6 = new HashSet<>();
        s6.add(3);
        expected.add(s6);
        expected.add(Collections.emptySet());
        assertEquals("one element", expected.size(), powerSet.size());
        for(Set<Integer> s : expected) {
            assertTrue("contains set", powerSet.contains(s));
        }
    }
}

SetUtils.java

package com.blogspot.groglogs.setutils;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class SetUtils {

    /*
    Given a TreeSet of Integers, return a string representation according to the following rules:
    - if N is in the TreeSet but N-1 and N+1 are not, return N and comma separate it from the rest
    - if N is in the TreeSet and N-1 or N+1 are too, return a range
    eg:
    1,5,9 -> 1,5,9
    1,2,4,5,6,7,8 -> 1-2,4-8
    */
    public static String summarize(TreeSet<Integer> t){
        if(t == null) throw new IllegalArgumentException("TreeSet cannot be null!");

        StringBuilder sb = new StringBuilder();
        Iterator<Integer> it = t.iterator();
        Integer curr;

        //if there is at least one item, we get it and add it to the result
        if(it.hasNext()){
            curr = it.next();
            sb.append(curr);
        }
        else return sb.toString();

        boolean has_range = false;

        while(it.hasNext()){
            Integer i = it.next();

            //if current item is not equals to the previous + 1 we might have broken a sequence
            if(i != curr + 1){
                //if we had a sequence, print the closing of it and add the new item after a comma
                if(has_range){
                    sb.append("-");
                    sb.append(curr);
                    sb.append(",");
                    sb.append(i);
                }
                //otherwise simply add the item after a comma
                else{
                    sb.append(",");
                    sb.append(i);
                }
                //in any case we no longer have a range now
                has_range = false;
            }
            //as long as item are in a sequence, nothing to do
            else{
                has_range = true;
            }

            //ALWAYS move the current unprocessed item forward!
            curr = i;
        }

        //if we have no more items we still need to check if we are ending in a range and in case add it!
        if(has_range){
            sb.append("-");
            sb.append(curr);
        }

        return sb.toString();
    }

    //helper for generatePowerSet
    private static <T> void generatePowerSet(Set<T> set, Set<Set<T>> powerSet){
        if(set.isEmpty()){
            return;
        }

        for(T elem : set){
            //must create a copy of current set first
            Set<T> next = new HashSet<>(set);
            next.remove(elem);

            if(!powerSet.contains(next)){
                powerSet.add(next);
                generatePowerSet(next, powerSet);
            }
        }
    }

    /**
     * Given a set, generate its powerset.
     * @param set the given set.
     * @param <T> the type of elements in the set.
     * @return the powerset of this set.
     */
    public static <T> Set<Set<T>> generatePowerSet(Set<T> set){
        if(set == null){
            return null;
        }

        /*
        We start by adding the input set to the result, then recursively with DFS we remove one element
        to generate all subsets and continue until we reach the empty set.
        Whenever we generate an already seen set, we skip to avoid repeating work.
         */

        Set<Set<T>> powerSet = new HashSet<>();

        powerSet.add(set);

        generatePowerSet(set, powerSet);

        return powerSet;
    }
}

SetUtilsJTests.java

package com.blogspot.groglogs.test.setutils;

import org.junit.Test;
import com.blogspot.groglogs.setutils.SetUtils;

import java.util.TreeSet;

import static org.junit.Assert.assertEquals;

public class SetUtilsJTests {

    TreeSet<Integer> input;
    String output;

    @Test
    //null or empty
    public void nullEmpty() {

        input = null;

        try{
            output = SetUtils.summarize(input);
        } catch(IllegalArgumentException e){
            System.out.println("null treeset got IllegalArgumentException: " + e.getMessage());
        }

        input = new TreeSet<>();
        output = "";

        assertEquals("empty treeset expected empty string", output, SetUtils.summarize(input));
    }

    @Test
    public void noRange() {

        input = new TreeSet<>();
        input.add(1);

        output = "1";

        assertEquals("1 treeset expected 1", output, SetUtils.summarize(input));

        input = new TreeSet<>();
        input.add(1);
        input.add(5);
        input.add(9);

        output = "1,5,9";

        assertEquals("1,5,9 treeset expected 1,5,9", output, SetUtils.summarize(input));

        input = new TreeSet<>();
        input.add(2);
        input.add(6);
        input.add(8);

        output = "2,6,8";

        assertEquals("2,6,8 treeset expected 2,6,8", output, SetUtils.summarize(input));
    }

    @Test
    public void onlyRange() {

        input = new TreeSet<>();
        input.add(1);
        input.add(2);

        output = "1-2";

        assertEquals("1,2 treeset expected 1-2", output, SetUtils.summarize(input));

        input = new TreeSet<>();
        input.add(1);
        input.add(2);
        input.add(3);

        output = "1-3";

        assertEquals("1,2,3 treeset expected 1-3", output, SetUtils.summarize(input));

        input = new TreeSet<>();
        input.add(3);
        input.add(4);
        input.add(5);

        output = "3-5";

        assertEquals("3,4,5 treeset expected 3-5", output, SetUtils.summarize(input));
    }

    @Test
    public void mixed() {

        input = new TreeSet<>();
        input.add(1);
        input.add(2);
        input.add(4);
        input.add(5);
        input.add(6);
        input.add(7);
        input.add(8);

        output = "1-2,4-8";

        assertEquals("1,2,4,5,6,7,8 treeset expected 1-2,4-8", output, SetUtils.summarize(input));

        input = new TreeSet<>();
        input.add(1);
        input.add(2);
        input.add(3);
        input.add(7);

        output = "1-3,7";

        assertEquals("1,2,3,7 treeset expected 1-3,7", output, SetUtils.summarize(input));

        input = new TreeSet<>();
        input.add(1);
        input.add(3);
        input.add(4);
        input.add(7);

        output = "1,3-4,7";

        assertEquals("1,3,4,7 treeset expected 1,3-4,7", output, SetUtils.summarize(input));

        input = new TreeSet<>();
        input.add(2);
        input.add(4);
        input.add(5);
        input.add(6);
        input.add(8);
        input.add(9);

        output = "2,4-6,8-9";

        assertEquals("2,4,5,6,8,9 treeset expected 2,4-6,8-9", output, SetUtils.summarize(input));
    }
}

Full description at:

• https://groglogs.blogspot.com/2021/07/java-generate-power-set-of-set.html
• http://groglogs.blogspot.ch/2018/05/java-summarize-treeset.html