336b.md

Back to questions

Solution to 336b: Evolving the Set interface

See code at solutions/code/tutorialquestions/question336b

Compare your solution with the sample solution.

The default addAll method is straightforward:

default void addAll(E[] items) {
  for (E item : items) {
    add(item);
  }
}

From a performance point of view, its potential downfall is that it invokes add as many times as there are elements in items. To see the problem, suppose that items has size N and the set to which these items is being added to is initially empty. For the first few additions, the call to add in addAll will iterate over an empty or close-to-empty set. But as the number of elements in the set (thanks to having added many elements from items) approaches N, each call to add for the final elements of items will require iterating through close to N existing elements, giving O(N²) time complexity.

This explains why, for MemoryEfficientGenericSet, the code in your main method should have performed so poorly before you implemented a specialised version of addAll for this kind of set, because MemoryEfficientGenericSet stores set elements in a list, and adding a set element involves iterating over this entire list to see whether the element is already present.

The more targeted implementation of addAll for MemoryEfficientGenericSet overcomes this problem by temporarily using a HashSet, for which adding and lookup of elements is very efficient, to decide which elements are not already in the set. Using this hash set slightly goes against the memory-efficient intentions of the MemoryEfficientGenericSet class, but not too much since the hash set is only alive for the duration of the addAll method: it is not the case that every MemoryEfficientGenericSet needs to have an accompanying hash set alive at all times.

For the asUnmodifiableSet method, the sample solution shows the use of an anonymous inner class.

A potential pro of using an anonymous inner class (beyond how much code you need to write), is that this class is not available to any other classes in your program. If you write a separate class, UnmodifiableGenericSet, you can give this class package visibility so that it is visible only to the package that contains the GenericSet interface, but you cannot stop other classes in this package from being able to create their own UnmodifiableGenericSet instances. The anonymous class approach makes it impossible for other code to create instances of the class, because the class has no name that could be used in conjunction with new.

This is also a potential con of the approach: there could be a case where you would like the class that implement an unmodifiable version of the GenericSet interface to be more broadly available, in which case it would need to be in a separate class.