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

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
c

Return unmodifiable collections

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

public Set 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 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 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 noFollow(T elem) {
    Set 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 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 reduce(List list) {
    List reducedList = new ArrayList<>(list);
    if (reducedList.size()  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.

StackExchange Code Review Q#132712, answer score: 4