Correct way to develop generic modifiers in Java

Question

In Java, we have functions of the sort:

public Collection<String> removeNulls(Collection<String> input) {
    List<String> output = new ArrayList<>();
    // ...
    return output;
}

Do note that I am not modifying the input in any way because a lot of time we happen to use ImmutableList for the List. More commonly, we try to ensure immutability in functions to whatever degree possible. However, a pitfall I see here is that, all my methods very often use their own implementation of Collection. If somebody using my library was using LinkedList or a Set or a SortedSet, an assumption like "lookups are O(1)" or "the list is always sorted" breaks whenever my function is called on their list:

Set<String> mySet = new SortedSet<>();
mySet.add(10);
mySet.add(9); // I know that my collection is now sorted
Collection<String> myFilteredSet = removeNulls(mySet); // It is no longer sorted
Set<String> mySet = Sets.newSortedSet(myFilteredSet); // Have to sort it again

In case of a LinkedList, this becomes even more subtle, if my function were to return a List, then I would continue to use the list. It won't have any compile-time errors, nor would the problem we visible to me. In the previous case the problem was atleast visible because I still had to convert the returned Collection (or List) to a Set and I knew what was up. The problem would only arise later on, if there was some heavy processing going on which depended on a LinkedList being used. An ideal way (that does not mean "recommended" though) would be:

public List<String> removeNulls(List<String> input) {
    List<String> output = (List<String>)input.getClass().newInstance();
    // ...
    return output;
}

This way, I am ensuring that atleast the same implementation of a type is being used. What, in your opinion, the solution to this problem?

EDIT

Just to clarify a bit, I do not actually have a removeNulls method and that is not what I am looking for. This question does not pertain to a real-life problem, but is more of a "something to think about". In other words, my question would be, given that you give me a collection, I have to return another collection that is somehow derived from it and does not modify the input, how do I ensure that my output collection adheres to the contracts (or specifically, the implementation) of the input collection?

Answer 1

I would argue that your approach needs to change.

There is little purpose in creating immutable collections if you need to adjust them later. Collections should be made immutable just prior to being exposed to the outside world (if necessary). Therefore, you should operate solely on modifiable collections and allow your method to adjust the argument.

If you receive an immutable collection from elsewhere, convert that into a modifiable collection and then follow the approach above.

Answer 2

The removeNulls method is a very "simple" example, and it's hard to imagine what further kinds of "modifiers" you may be working with.

From your description, it sounds that your actual intention might nicely be supported by the new Streams API in Java 8. For example, removing the null elements from a Stream could easily be accomplished with

// Filter out all null elements
collection.stream().filter((e) -> e != null).... // Further operations

The nice thing here is that your actual problem is handled internally: The characteristics of the stream are (as far as possible) preserved during the operations. For example, a stream that was sorted before will remain sorted.

---

An alternative way of handling such a situation for pre-Java-8 versions is to specify the output collection (or at least, give the option to do so). For the example: You could write the method as

public <T> Collection<T> removeNulls(Collection<? extends T> input, Collection<T> output)
{
    if (output == null) 
    {
        // Create some default collection or
        // report an error...
    }
    for (T t : input)
    {
        if (t != null)
        {
            output.add(t);
        }
    }
    return output;
}

// Convenience method
public <T> Collection<T> removeNulls(Collection<? extends T> input)
{
    return removeNulls(input, new ArrayList<T>());
}

To be called as

Set<String> mySet = new SortedSet<>();
mySet.add(10);
mySet.add(9); // I know that my collection is now sorted
Collection<String> myFilteredSet = removeNulls(mySet, new SortedSet<>());

(Note: One could even further exploit the power of type inference and generics here - this ist just to show the basic idea)

---

In any case, I consider it as very important to clearly specify any assumptions as pre- and postconditions in the JavaDoc, e.g.

/** 
 * Creates a new collection with the same contents as the given collection,
 * but without any <code>null</code> entries
 *
 * The order of output elements will be the same as the input elements
 * or alternatively:
 * No assumptions may be made about the order of the output collection
 *
 * @return The filtered collection
 */