class Taboo<T> -- sort passed in List<T> according to 'rules'

Question

I know as a matter of fact that there are many areas upon which my code could be improved. I was wondering if anyone can provide me with suggestions on how Taboo class and tests can be improved. Suggestions of any kind and scope are very welcomed. it would be even better if reasons can be provided along with the suggestions.

Problem:

class Taboo

Most of the previous problems have been about single methods, but Taboo is a class. The Taboo class encapsulates a "rules" list such as {"a", "c", "a", "b"}. The rules define what objects should not follow other objects. In this case "c" should not follow "a", "a" should not follow "c", and "b" should not follow "a". The objects in the rules may be any type, but will not be null.

The Taboo noFollow(elem) method returns the set of elements which should not follow the given element according to the rules. So with the rules {"a", "c", "a", "b"} the noFollow("a") returns the Set {"c", "b"}. NoFollow() with an element not constrained in the rules, e.g. noFollow("x") returns the empty set (the utility method Collections.emptySet() returns a read-only empty set for convenience).

The reduce(List) operation takes in a list, iterates over the list from start to end, and modifies the list by deleting the second element of any adjacent elements during the iteration that violate the rules. So for example, with the above rules, the collection {"a", "c", "b", "x", "c", "a"} is reduced to {"a", "x", "c"}. The elements in bold -- {"a", "c", "b", "x", "c", "a"} -- are deleted during the iteration since they violate a rule.

The Taboo class works on a generic type which can be any type of object, and assume that the object implements equals() and hashCode() correctly (such as String or Integer). In the Taboo constructor, build some data structure to store the rules so that the methods can operate efficiently -- note that the rules data for the Taboo are given in the constructor and then never change.

A rules list may have nulls in it as spacers, such as {"a", "b", null, "c", "d"} -- "b" cannot follow "a", and "d" cannot follow "c". The null allows the rules to avoid making a claim about "c" and "b".

Taboo class:

package assign1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Taboo<T> {

    public Map<T, Set<T>> rulesMap = new HashMap<>();

    /**
     * Constructs a new Taboo using the given rules (see handout.)
     *
     * @param rules rules for new Taboo
     */
    public Taboo(List<T> rules) {

        for (int i = 1; i < rules.size(); i++) {

            T firstItem = rules.get(i - 1);
            T secondItem = rules.get(i);

            if (firstItem != null && secondItem != null) {

                if (rulesMap.containsKey(firstItem)) {
                    rulesMap.get(firstItem).add(secondItem);
                } else {
                    Set<T> set = new HashSet<>();
                    set.add(secondItem);
                    rulesMap.put(firstItem, set);

                }
            }
        }
    }

    /**
     * Returns the set of elements which should not follow the given element.
     *
     * @param elem the given element (or the first of a pair of element)
     * @return elements which should not follow the given element
     */
    public Set<T> noFollow(T elem) {
        return rulesMap.get(elem);
    }

    /**
     * Removes elements from the given list that violate the rules (see
     * handout).
     *
     * @param list collection to reduce
     * @return the list reduced according to the rules
     */
    public List<T> reduce(List<T> list) {
        List<T> reducedList = new ArrayList<>(list);
        for (int secondItemPosition = 1; secondItemPosition < reducedList.size(); secondItemPosition++) {
            reducedList = removeViolation(secondItemPosition, reducedList);
        }
        return reducedList;
    }

    /**
     * this method does the actual comparison between the passed in list and 
     * the rules in the 'rulesMap'. This method calls itself recursively
     * @param secondItemPosition
     * @param list
     * @return 
     */
    private List<T> removeViolation(int secondItemPosition, List<T> list) {

        List<T> localCopyOfList = new ArrayList<>(list);

        T firstItem = localCopyOfList.get(secondItemPosition - 1);
        T secondItem = localCopyOfList.get(secondItemPosition);

        if (rulesMap.containsKey(firstItem)) {
            if (rulesMap.get(firstItem).contains(secondItem)) {

                localCopyOfList.remove(secondItemPosition);

                if (secondItemPosition < localCopyOfList.size()) {
                    localCopyOfList = removeViolation(secondItemPosition, localCopyOfList);
                }
            }
        }

        return localCopyOfList;
    }
}

Test class:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import static org.junit.Assert.*;
import org.junit.Test;

public class TabooTest<T> {

    @Test
    public void testConstructorWithInteger() {
        Map<Integer, Set<Integer>> integerMap = new HashMap<>();
        integerMap.put(1, new HashSet<>(Arrays.asList(2, 3)));
        integerMap.put(2, new HashSet<>(Arrays.asList(4)));

        List<Integer> integerList = new ArrayList<>(Arrays.asList(1, 2, 4, null, 1, 3));
        Taboo<Integer> taboo = new Taboo<>(integerList);

        assertEquals(integerMap, taboo.rulesMap);
    }

    @Test
    public void testConstructorWithString() {
        Map<String, Set<String>> stringMap = new HashMap<>();
        stringMap.put("hello", new HashSet<>(Arrays.asList("world", "morning")));
        stringMap.put("world", new HashSet<>(Arrays.asList("hello", "morning")));
        stringMap.put("morning", new HashSet<>(Arrays.asList("world", "hello")));

        List<String> stringList = new ArrayList<>(Arrays.
                asList("hello", "world", "morning", "hello", "morning", "world", "hello"));
        Taboo<String> taboo = new Taboo<>(stringList);

        assertEquals(stringMap, taboo.rulesMap);
    }

    @Test
    public void testConstructorWithEmptyMap() {
        Map<Double, Set<Double>> doubleMap = new HashMap<>();

        List<Double> doubleList = new ArrayList<>(Arrays.asList(1.1, null, 2.2, null, 3.3));
        Taboo<Double> taboo = new Taboo<>(doubleList);

        assertEquals(doubleMap, taboo.rulesMap);
    }

    @Test
    public void testNoFollowMethodWithString() {
        Set<String> stringSet = new HashSet<>(Arrays.asList("world", "morning"));

        List<String> stringList = new ArrayList<>(Arrays.
                asList("hello", "world", "morning", "hello", "morning", "world", "hello"));
        Taboo<String> taboo = new Taboo<>(stringList);

        assertEquals(stringSet, taboo.noFollow("hello"));
    }

    @Test
    public void testNoFollowingMethodWithNull() {

        List<String> stringList = new ArrayList<>(Arrays.
                asList("hello", "world", "morning", "hello", "morning", "world", "hello"));
        Taboo<String> taboo = new Taboo<>(stringList);

        assertNull(taboo.noFollow("mf"));

    }

    @Test
    public void testReduceMethodWithInteger() {
        List<Integer> reducedList = new ArrayList<>(Arrays.asList(10, 10));

        List<Integer> rulesIntegerList = new ArrayList<>(Arrays.asList(10, 20));
        Taboo<Integer> taboo = new Taboo<>(rulesIntegerList);
        List<Integer> passedInList = new ArrayList<>(Arrays.asList(10, 20, 10, 20));

        assertEquals(reducedList, taboo.reduce(passedInList));
    }

    @Test
    public void testReduceMethodWithString() {

        List<String> rules = new ArrayList<>(Arrays.asList("he", "she", "i", "she"));
        Taboo<String> taboo = new Taboo<>(rules);
        List<String> passedInList = new ArrayList<>(Arrays.asList("he", "she", "i", "she", "i", "she", "i"));

        List<String> reducedList = new ArrayList<>(Arrays.asList("he", "i", "i", "i"));

        assertEquals(reducedList, taboo.reduce(passedInList));


    }
}

Answer 1

Return unmodifiable collections

The method noFollow method returns a direct reference to the set contained inside the rulesMap.

public Set<T> noFollow(T elem) {
    return rulesMap.get(elem);
}

One of the issue with this approach is that a caller of that class can then modify this set and add their own rules, or even delete current rules, at wish.

Consider this:

public static void main(String[] args) {
    Taboo<String> taboo = new Taboo<>(Arrays.asList("1", "2"));
    System.out.println(taboo.noFollow("1")); // prints [2]
    taboo.noFollow("1").clear();
    System.out.println(taboo.noFollow("1")); // prints [], oops
}

To tacke this issue, you can return an unmodifiable set instead:

public Set<T> noFollow(T elem) {
    return Collections.unmodifiableSet(rulesMap.get(elem));
}

With this change, the above code would throw an UnsupportedOperationException, and not mess up with the rules.

Make sure to return non-null collections

Called with an element that is not present in the rule map, noFollow will return null. This is in contradiction of the problem:

NoFollow() with an element not constrained in the rules, e.g. noFollow("x") returns the empty set

Additionnally, it is always preferable to return an empty collection instead of null to avoid potential NullPointerException for the caller.

As such, consider modifying your method to:

public Set<T> noFollow(T elem) {
    Set<T> set = rulesMap.get(elem);
    return set == null ? Collections.emptySet() : Collections.unmodifiableSet(set);
}

Starting with Java 8, you could condense that a little with getOrDefault:

public Set<T> noFollow(T elem) {
    return Collections.unmodifiableSet(rulesMap.getOrDefault(elem, Collections.emptySet()));
}

Collections.emptySet() does not create a new instance of an empty set; this set is cached, so no new unnecessary objects are being created.

Note that this change will break one of your test, mainly testNoFollowingMethodWithNull. This test expected null to be returned. You'll need to update it to expect an empty set.

Consider iterators

Your implementation of reduce works with having a private inner method to do the hard work, that is called recursively. The issue with this approach is that it creates a lot of temporary new lists, and makes the code a bit difficult to read.

When traversing a collection to remove elements, an Iterator is generally the right tool for the job: it supports going forward and removing elements, which is exactly what we want here. Consider the following approach:

public List<T> reduce(List<T> list) {
    List<T> reducedList = new ArrayList<>(list);
    if (reducedList.size() < 1) {
        return reducedList;
    }
    Iterator<T> iterator = reducedList.iterator();
    T current = iterator.next();
    while (iterator.hasNext()) {
        T next = iterator.next();
        if (current != null && next != null && rulesMap.containsKey(current) && rulesMap.get(current).contains(next)) {
            iterator.remove();
        } else {
            current = next;
        }
    }
    return reducedList;
}

What it does is pretty straight-forward.

• If the list has less than 2 elements, there will be nothing to do so it exits early.
• Otherwise, it gets the first element, and then loops through the rest. When the next element is contained inside the no follow set, it removes the element and keeps the same current element. When this element is allowed, it keeps it and update the current element, moving forward.

Tests are testing too much, and not enough at the same time

You have three unit tests that asserts the content of the map rulesMap. You should not have that. The reason is that rulesMap is an implementation detail of your class that the public API is not concerned about. This map is never exposed to the client of the class, hence, its content should not be asserted with an unit-test. An unit test should focus on the public API of the class tested. As such, in this case, you are only interested in testing the two methods noFollow and reduce. Testing anything else is too much.

At the same time, you're not testing enough those public APIs. For example, you have no unit test that cover the requirements

A rules list may have nulls in it as spacers, such as {"a", "b", null, "c", "d"} -- "b" cannot follow "a", and "d" cannot follow "c". The null allows the rules to avoid making a claim about "c" and "b".

This should be tested independently for both noFollow and reduce in dedicated tests.