Chapter 9. Please recycle: Reusability

This chapter covers

• Generalizing a piece of software to a wider context
• Using generics to write reusable classes
• Using and customizing mutable collectors on data streams

In the previous chapters, you developed concrete classes that solved a specific problem. Now, assume you need to generalize your solution to a broader variety of problems. Ideally, you should discern the essential features of the problem, separate them from what’s merely incidental, and develop a solution for all the problems that share the same essential structure. Unfortunately, discerning the essential from the incidental is far from obvious. Roughly speaking, you should try to keep the key structure—that is, the part that may be useful in other contexts.

This final chapter assumes you’re familiar with generics, including bounded type parameters.

9.1. Establishing boundaries

In the first decades of OOP, reusability was considered one of the selling points of the paradigm. The promise was that all you ever had to do was write small, reusable components and combine them with existing reusable components pulled off the shelf. After some 50 years of practice (the first OO language was 1967’s Simula), some of this promise has been confirmed, and some has proven to be off target.

Programmers pull reusable components off the shelf all the time: they’re libraries and frameworks. A large part of today’s development focuses on web applications that benefit greatly from a set of standard services packaged as a framework. On the other hand, once you cross the boundaries of your framework into application-specific code, reusability quickly fades into the background, pushed aside by more pressing functional and nonfunctional concerns, such as correctness, performance, and time to market.

In this chapter, you’ll develop a library of objects that behave somewhat like water containers, with generality in mind. As is often the case with libraries, the question is: How general should it be? Should it extend from water containers to oil containers, or all the way to an intergalactic network of connectable planets with trade routes and population levels? To guide you in this choice, let’s consider a couple of scenarios that you probably want to capture with the generalized framework, and another scenario that you may not want to capture because it would stretch the generalization too far.

Scenario 1

The municipal water company using your Container library is reporting that total water amounts show discrepancies of up to 0.0000001 liters of water a year.

You track these unfortunate inconsistencies to floating-point rounding errors. Fixing them requires representing water amounts with rational numbers with arbitrarily large numerators and denominators (say, two BigInteger objects).

Supporting this change is relatively straightforward: the business logic remains the same, whereas you replace the type of the amount field by a type variable T, and you require T to implement an interface providing the appropriate arithmetic operations.

Scenario 2

A social network wants to track the total number of likes that all sets of related posts receive. Two posts are considered related if both of them have attracted a comment coming from the same user.

At first glance, scenario 2 seems to have little to do with water containers, until you realize that you can treat each post as a container. When two posts receive a comment by the same person, they become connected. Instead of addWater, the scenario calls for a method adding one or more likes to this post. Finally, instead of getAmount, you need a method that returns the total number of likes that all posts connected to this one collected.

The scenario is not too different from water containers after all: in both cases, the objects can be permanently connected with each other, and what really counts is the set of directly or indirectly connected objects. Moreover, in both cases, objects have a property that you can read or update locally, but the effect of an update depends on the group of connected items.

On the other hand, the specific ways you update the local property and the ways it influences the global property are a little different. In the following sections, you’ll see how you can reconcile them under a single contract. But first, here’s a third extension scenario.

Scenario 3

A mobile phone carrier needs to manage its network of antennas. The company can permanently connect antennas to each other, and it wants to know how many direct connections you need to traverse from each given antenna to each other antenna (aka the length of the shortest path).

In this scenario, you still have items that you can permanently connect with each other. But the main property of interest—connection distance between antennas— concerns two given items, and its value depends on which direct connections exist. In particular, the value of this property is not shared among a group of connected antennas. Hence, this scenario needs radically different connection representations and management. Supporting it would make your code so generic that customizing it for a concrete scenario would require more effort than writing a specific solution from scratch.

Based on these descriptions, you’ll develop a generic implementation of water containers that can accommodate scenarios 1 and 2, but not scenario 3.

9.2. The general framework

First, you’ll formalize with an interface the essential features of a generic container:

1. A generic container possesses an attribute of some type V (for value). Clients can read the attribute or update it locally on a container, but the actual effect of an update depends on the group of connected containers. For concrete water containers, it will be V = Double.
2. Clients can permanently connect generic containers to each other.

Conceptually, these two features are independent, so you might represent them with two different interfaces (say, Attribute and Connectable). However, because you’d end up using them together all the time, let’s put both features in a single interface called ContainerLike.

Having an attribute of type V (feature 1) simply translates to equipping the interface with two methods like the following:

public interface ContainerLike<V> {
   V get()               1 Generalization of getAmount
   void update(V value)  2 Generalization of addWater
   ...
}

The fact that the effect of an update depends on the group of connected containers doesn’t show in the API. As for connecting one generic container to another (feature 2), choosing the right method signature is trickier. Ideally, we’d like generic containers to be connectable to other generic containers of the same type, but we can’t exactly ask that in a Java interface. In the theory of programming languages, this is the well-known binary method problem.

public interface Comparable {
   int compareTo(thisType other);
}

Let’s examine a couple of different solutions for the signature of connectTo:

• void connectTo(Object other)—Similar to the signature of Object::equals. With this signature, you’re just giving up on type safety, not enlisting the compiler into helping you in any way. The body of connectTo would need to check the dynamic type of its argument and then perform a downcast before it could do anything with it.
• void connectTo(ContainerLike<V> other)—You’re getting some help from the compiler, but not quite enough. With this signature, connectTo accepts any other generic container that happens to have an attribute of the same type as this generic container. To perform its job, connectTo still needs to cast its argument to something more specific that exposes its representation for container connections.

Pop Quiz 1

Is it a good idea to insert a public boolean equals(Employee e) method into an Employee class? Why or why not?

A better alternative mimics the solution that Java chose for Comparable: introduce an extra type parameter T, representing the type of objects that generic containers can be connected to, and hope that the parameter will be used in the proper way. We can’t ask that T be the same class that’s implementing the interface, but we can ask that it be a (possibly different) class implementing the same interface.

Listing 9.1. ContainerLike: The generic interface for containers

public interface ContainerLike<V, T extends ContainerLike<V,T>{}> {
   V get();
   void update(V val);
   void connectTo(T other);
}

The intended use of ContainerLike is to be implemented as follows:

class MyContainer implements ContainerLike<Something, MyContainer> { ... }

just like the intended use of Comparable is:

class Employee implements Comparable<Employee> { ... }

If a class adheres to that scheme (that is, it sets T to be itself), its connectTo method won’t need to perform a downcast because it will receive as argument an object that’s already of the same type as “this,” which is exactly what the method needs to do its group-merging job.

Pop Quiz 2

If T is a type parameter, can you allocate an array of type T in Java? What about C#?

9.2.1. The attribute API

Next, we need to introduce an interface that represents the behavior of the attribute when we update its value with update and especially when we connect generic containers with connectTo.

To delimit the level of generality that we want to support, we make the following assumptions:

1. When locally updating the property, you can compute the new group value based only on the current group value and the new local value. In other words, the group value must contain enough information to perform the required update.
2. When merging two groups, you can obtain the new group value based only on the two old group values.

Compare assumptions 1 and 2 with the two generalized scenarios presented at the beginning of the chapter. Scenario 1 poses no problem because it’s a simple variation of the basic water container setting. In scenario 2, the property of interest is the total number of likes accrued by all connected posts—that’s their “group value.” Locally updating the property means adding likes to a particular post. As a result, the group value increases by the same amount, in accordance with assumption 1.

Let’s check whether assumption 2 holds. When two groups of posts are connected (that is, when a user who commented on the first group of posts comments on a post from the second group), you can merge their group values by adding them up. You need no further information to compute the new group value, so that confirms assumption 2.

Equipped with the above assumptions, let’s sketch the API defining the behavior of the attribute that all containers hold. To avoid confusion between the local value and the group value, let’s call the latter the group summary. First of all, you should distinguish the type V of the local value from the type S of the group summary. In some cases, they will be the same; for example, in scenario 2, both types would be Integer because they represent like counts. In the case of water containers instead, they’ll turn out to be different types, as I explain in section 9.5.

Now, introduce an interface Attribute<V,S> providing the operations that containers need to perform their contractual obligations, described earlier as features 1 and 2:

• A new generic container needs to initialize its group summary (method seed).
• The get method of a generic container needs a method to unwrap its summary into a local value of type V (method report).
• The update method of generic containers needs to update its summary (method update).
• The connectTo method needs a method that merges two summaries (method merge).

You end up with an interface similar to the following listing, whereas table 9.1 summarizes the dependencies between the methods of generic containers and those of the Attribute interface.

Listing 9.2. Attribute: The generic interface for the property of containers

public interface Attribute<V,S> {
   S seed();                          1 Provides the initial summary
   void update(S summary, V value);   2 Updates a summary with a value
   S merge(S summary1, S summary2);   3 Merges two summaries
   V report(S summary);               4 Unwraps a summary
}

Table 9.1. Relationships between the methods of generic containers and the methods of the Attribute interface

Notice how an Attribute object itself is stateless: it doesn’t contain the value of the attribute. That’s for the generic container to hold in a separate object of type S (for a group summary) or V (for a cached local value).

The Attribute interface bears a definite resemblance to the interface introduced in Java 8 to collect the outcome of a stream operation in a single result. The next section takes the opportunity to briefly present streams and mutable collectors.

9.2.2. Mutable collectors

Streams complement collections by providing a handy composable framework for sequential operations. Here, I’ll quickly introduce the framework and then focus on a specific feature that’s relevant to the water container example: mutable collectors. For a more comprehensive account of the framework, check out the resources at the end of this chapter.

You can turn standard collections into streams using the stream method. In turn, stream objects support a variety of intermediate and terminal operations. Intermediate operations turn a stream into another stream of the same type or a different type. Terminal operations produce some output that’s not a stream. One of the simplest terminal operations is forEach, which executes a code snippet on every element of the stream. Let listOfStrings be. . . what it says; the following fragment prints all strings in the list:

listOfStrings.stream().forEach(s -> System.out.println(s));

The argument of forEach is an object of type Consumer. Because the latter is a functional interface, you can instantiate it using the convenient Lambda-expression syntax. Let’s add an intermediate operation to print only the strings that are longer than 10 characters:

listOfStrings.stream().filter(s -> s.length() > 10)
                      .forEach(s -> System.out.println(s));

Sometimes you want to collect the result of a sequence of stream operations into a new collection. You can do that with the collect terminal operation, accepting a mutable collector as an object of type Collector. Static factory methods from the Collec tors class provide common collectors. For example, the following snippet gathers the filtered strings into a list:

List<String> longStrings =
             listOfStrings.stream().filter(s -> s.length() > 10)
                                   .collect(Collectors.toList());

Other standard collectors allow you to put the result into a set or a map. You can create your own collectors by implementing the Collector interface. To understand the various parts of the Collector interface, consider what you’d do with a plain old collection if you wanted to summarize it into a single mutable result. You’d have some sort of summary object, initialized with some default value and then updated on every element in the collection. After scanning all the elements, you might want to convert the summary into a different type—let’s call it the result type.

Collection<V> collection = ...
Summary summary = new Summary();     1 Initial summary
for (V value: collection) {
   summary.update(value);            2 Updates summary with value
}
Result result = summary.toResult();  3 Converts summary to result

The Collector interface abstracts these three steps, plus another step you need for parallel collectors. If the loop over all the values is assigned to multiple threads (that is, each thread takes care of a subset of the values), each thread builds its own summary, and you eventually need to merge these summaries before they can produce a final result. This merge operation is the fourth and final ingredient in a collector.

Calling S the type of the summary and R the type of the final result, you might expect the Collector interface to contain methods like the following:

   S supply();                           1 Initial summary
   void accumulate(S summary, V value);  2 Updates summary with value
   S combine(S summary1, S summary2);    3 Merges two summaries
   R finish(S summary);                  4 Converts summary to result

Notice the close similarity between this imaginary collector and the Attribute interface introduced earlier for abstracting the water level value of containers. However, the actual Collector interface introduces one more level of indirection by having each method return an object that performs the corresponding function. This is in line with the rest of the stream framework and with the functional programming style by which it’s inspired. The return types for all four methods are functional interfaces, that is, interfaces that each have a single abstract method. Table 9.2 outlines the characteristics of these four interfaces.

Table 9.2. Functional interfaces mutable collectors use. They’re among the more than 40 functional interfaces in the java.util.function package.

You use a fifth method to state whether this collector possesses two standard characteristics:

• Concurrency— Does this collector support concurrent execution by multiple threads?
• Order— Does this collector preserve the order of the elements?

An internal enumeration called Characteristics provides the flags corresponding to these features. Summarizing, you get the following methods:

public interface Collector<V,S,R> {
   Supplier<S> supplier();         1 Initial summary
   BiConsumer<S,V> accumulator();  2 Updates summary with value
   BinaryOperator<S> combiner();   3 Merges two summaries
   Function<S,R> finisher();       4 Converts summary to result
   Set<Characteristics> characteristics();  5 Whether it’s concurrent, ordered, etc.
}

This use of functional interfaces makes collectors easily interoperable with Lambda expressions and method references, two handy ways to implement functional interfaces. In the next section, I’ll introduce method references and guide you through the implementation of a concrete collector of strings.

Pop Quiz 3

What’s the role of the combiner method of a collector? When will you use it?

An Example: String Concatenation

Let’s wrap up with an example: a custom collector that concatenates a sequence of strings into a single string, using a StringBuilder as a temporary summary. As String Builder isn’t thread-safe, the collector won’t be concurrent.^[1] On the other hand, it preserves the order of the strings because it concatenates them in order. This arrangement is convenient because those are exactly the default characteristics for a collector, so you can return an empty set from the method characteristics.

¹

To make a concurrent collector, you could use StringBuffer instead of StringBuilder, or add explicit synchronization.

Now, if it wasn’t for Lambda expressions and method references, you’d have to put up with a lot of anonymous classes to define your collector. In fact, you’d need five anonymous classes: an outer class for the collector itself and four inner classes to instantiate the corresponding functional interfaces. Just consider the first method:

Collector<String,StringBuilder,String> concatenator =
   new Collector<>() {  1 Outer anonymous class
      @Override
      public Supplier<StringBuilder> supplier() {  2 Provides the initial summary
         return new Supplier<>() {  3 First inner anonymous class
            @Override
            public StringBuilder get() {
               return new StringBuilder();
            }
         };
      }
      ...  4 Overriding the other four methods of Collector
   };

ToIntFunction<Object> hasher = Object::hashCode;

int applyAsInt(T item)

Consumer<String> printer = System.out::println;

With method references, the previous snippet becomes much simpler. You can provide the supplier by a reference to the constructor of StringBuilder. The compiler takes care of wrapping the constructor into an object of type Supplier<StringBuilder>.

Collector<String,StringBuilder,String> concatenator = new Collector<>() {
   @Override
   public Supplier<StringBuilder> supplier() {
      return StringBuilder::new;  1 Reference to the constructor
   }
   ...  2 Overriding the other four methods of Collector
};

Even better, the class Collector provides a static method of that dispenses with even providing the outer anonymous class, leading to the following handy solution. Here, I’ve provided all four main methods of the interface as method references:

Collector<String,StringBuilder,String> concatenator =
   Collector.of(StringBuilder::new,     1 The supplier (reference to a constructor)

                StringBuilder::append,  2 The update function
                StringBuilder::append,  3 The merge function (another append method)

                StringBuilder::toString);  4 The finisher

Method references don’t allow you to specify the signature of the method you’re referring to, just its name. The compiler infers the signature from the context where the method reference occurs. Such context must identify a specific functional interface. For example, in the previous snippet, the update function reference resolves to the following method from StringBuilder:

public StringBuilder append(String s)

because the context calls for a BiConsumer<StringBuilder,String>. You may have noticed a mismatch here: append returns a value, whereas a BiConsumer returns void. The compiler happily lets you get away with it, just like you’re allowed to invoke a method returning a value and ignore that value. Table 9.3 summarizes this compatibility rule.

Table 9.3. Comparing the signatures and types of the method StringBuilder::append and the functional interface BiConsumer. SB is short for StringBuilder.

Tip

You can assign a reference to a non-void method to a void functional interface.

Moving to the merge function method reference in the snippet, its context requires a BinaryOperator<StringBuilder>, that is, a method accepting two StringBuilders (including this) and returning another StringBuilder. A different append method from the StringBuilder class can fill this role:

public StringBuilder append(CharSequence seq)

This case also requires a conversion because the method append accepts a CharSequence, whereas the target functional interface expects a StringBuilder. This conversion is permitted because CharSequence is a super-type of StringBuilder. Table 9.4 summarizes the situation.

Table 9.4. Comparing the signatures and types of the method StringBuilder::append and the functional interface BinaryOperator. SB is short for StringBuilder.

Tip

You can assign a reference to a method accepting an argument of type T to a functional interface whose method expects a subtype of T.

By the way, a collector very similar to this concatenator is included in the JDK as the object returned by the static method Collectors.joining().

Pop Quiz 4

Can you assign a method reference to a variable of type Object?

9.2.3. Adapting Attribute to functional interfaces

You can equip Attribute with the same type of adapter that you find in Collector: a static method that takes four functional interfaces and turns them into an object of type Attribute. With this method, clients can create concrete implementations of Attribute using four Lambda expressions or method references, like you just did with the string concatenator.

This adapter method takes the following form:

   public static <V,S> Attribute<V,S> of(Supplier<S> supplier,
                                         BiConsumer<S,V> updater,
                                         BinaryOperator<S> combiner,
                                         Function<S,V> finisher) {
      return new Attribute<>() {  1 Anonymous class
         @Override
         public S seed() {
            return supplier.get();
         }
         @Override
         public void update(S summary, V value) {
            updater.accept(summary, value);
         }
         @Override
         public S merge(S summary1, S summary2) {
            return combiner.apply(summary1, summary2);
         }
         @Override
         public V report(S summary) {
            return finisher.apply(summary);
         }
      };  2 End anonymous class
   }

9.3. A generic container implementation

You can now devise a generic implementation of ContainerLike that manages connections and groups, while delegating the behavior of the property to an object of type Attribute. A good choice and a nice exercise would be to base this implementation on Speed3 from chapter 3 because it exhibits the best overall performance.

First, recall the basic structure of Speed3, based on parent-pointer trees. Each container is a node in a tree, and only the root containers know the amount of water and the size of their group. Containers hold three fields, two of which are relevant only to root containers:

• The amount of water that the group holds (if this container is a root)
• The size of this group (if this container is a root)
• The parent container (or a self-loop, if this container is a root)

In fact, this is the beginning of Speed3:

public class Container {
   private Container parent = this;  1 Initially, each container is the root of its tree.
   private double amount;
   private int size = 1;

The generic version, called UnionFindNode, replaces the amount field with an object of type S, holding the group summary, and an object of type Attribute, holding the methods for manipulating summaries and values. The fields and constructor of Union FindNode are shown in the following listing.

Listing 9.3. UnionFindNode: Fields and constructor

public class UnionFindNode<V,S>
    implements ContainerLike<V,UnionFindNode<V,S>{}> {

   private UnionFindNode<V,S> parent = this;  1 Initially, each node is a root.
   private int groupSize = 1;

   private final Attribute<V,S> attribute;  2 Contains the methods for
   private S summary;                         manipulating the attribute

   public UnionFindNode(Attribute<V,S> dom) {
      attribute = dom;
      summary = dom.seed();
   }

The methods get and update identify the root of their tree (as in Speed3) and then invoke the appropriate attribute method to unwrap the summary or update the summary based on a new value, as shown in listing 9.4. The private support method find RootAndCompress is responsible for finding the root and flattening the path leading to the root to speed up future calls.

Listing 9.4. UnionFindNode: Methods get and update

   public V get() {  1 Returns current value of attribute

      UnionFindNode<V,S> root = findRootAndCompress();
      return attribute.report(root.summary);
   }
   public void update(V value) {  2 Updates attribute
      UnionFindNode<V,S> root = findRootAndCompress();
      attribute.update(root.summary, value);
   }

Finally, the method connectTo enforces the link-by-size policy I explained in chapter 3 and invokes the merge method of the Attribute to merge the summaries of the two groups being connected. As promised, connectTo doesn’t need to perform any cast on its argument, thanks to the expressive signature you chose earlier.

Listing 9.5. UnionFindNode: Method connectTo

   public void connectTo(UnionFindNode<V,S> other) {
      UnionFindNode<V,S> root1 = findRootAndCompress(),
                         root2 = other.findRootAndCompress();
      if (root1 == root2) return;
      int size1 = root1.groupSize, size2 = root2.groupSize;
          1 Merges the two summaries
      S newSummary = attribute.merge(root1.summary, root2.summary);

      if (size1 <= size2) {  2 The link-by-size policy
         root1.parent     = root2;
         root2.summary    = newSummary;
         root2.groupSize += size1;
      } else {
         root2.parent     = root1;
         root1.summary    = newSummary;
         root1.groupSize += size2;
      }
   }

Figure 9.1 summarizes the three classes I’ve presented so far. Together, they form a generic framework to generate container-like behaviors.

Figure 9.1. A UML class diagram for the generic water container framework

9.4. General considerations

Let’s stop this flurry of code for a second and think about the general process of generalizing a given set of functionalities to a wider context. Before this process starts, you need a clear motivation to generalize your code or specifications. It may be tempting to generalize a solution just because you envision it becoming an elegant framework, or perhaps just for the challenge! If you’re programming for fun or to learn a new language, those reasons are good enough. On the job, though, you better have a business-related motivation to turn a fine yet specific solution into a general framework that’s likely to be slower, more complicated, and harder to maintain. Good business-oriented motivations boil down to one of the following:

• The general solution can be a product in itself. You and your colleagues/ managers deem that your organization can release the general solution independently as a library or framework that other organizations can use.
• The general solution can cater to different functions in your product. Perhaps the general solution can replace and unify separate specific solutions that are part of your product.
• The general solution can support future evolutions of your product. You should handle this motivation with care. As I mentioned before, programmers and designers are inclined to overengineer and overgeneralize software. The extreme-programming YAGNI motto—You aren’t gonna need it—recognizes and challenges this tendency.

Once you identify a clear motivation, it’s time to establish one or more extra application scenarios (aka use cases) that the current implementation or specification doesn’t cover but should cover, according to your motivation. That’s what I did at the beginning of this chapter, presenting two target scenarios and one scenario that’s beyond the scope of the generalization.

These use cases guide you toward a general API, often in the form of one or more interfaces. In the case of water containers, this analysis led to the two interfaces ContainerLike and Attribute.

If you started with a concrete implementation, it’s time to adapt it to the general interfaces you designed in the previous step. That’s what you did when you started with the concrete Container class from version Speed3 (from chapter 3) and converted it to the generic class UnionFindNode. Now you’ll need some extra code—hopefully not too much—to recover the original functionality using the new generic framework. That’s the aim of the next section.

9.5. Recovering water containers    [Generic]

In this section, I’ll show you how to recover a concrete implementation of water containers, with their concrete water-level attribute, using the generic implementation you developed in the previous section. The result is a class that behaves pretty much like Speed3, except with a couple of abstraction levels added. That’s the cost for a generic implementation that you can easily adapt to a range of conditions.

9.5.1. Updated use case

The use case for the concrete implementation will be similar, but not identical, to the one I’ve been using in the rest of the book. The only difference is in the names of two methods: instead of the specific getAmount and addWater, you get the generic names get and update that the ContainerLike interface provides. As a result, the first lines of the standard use case become the following:

   Container a = new Container();
   Container b = new Container();
   Container c = new Container();
   Container d = new Container();

   a.update(12.0);  1 update is analogous to addWater.
   d.update(8.0);
   a.connectTo(b);
    2 get is analogous to getAmount.
   System.out.println(a.get()+" "+b.get()+" "+c.get()+" "+d.get());

The desired output from the previous fragment is the same as in the original use case:

6.0 6.0 0.0 8.0

9.5.2. Designing the concrete attribute

Every concrete class based on UnionFindNode needs to fix types V and S and supply an object of type Attribute<V,S>. For water containers, V = Double because that’s the natural type for water amounts. At first glance, it may seem that a summary of type S = Double also would work. After all, shouldn’t the group summary just be the total amount of water in the group? You might argue that you can then compute the amount per container by dividing the group amount by the size of the group, and the latter would be stored in the groupSize field of the root node. However, the Attribute object doesn’t have access to the UnionFindNode object it belongs to! As a result, it can’t access its groupSize field. You’re forced to replicate the group size information and store a separate copy inside the summary. That’s another cost due to the generality of the solution.

Instead of a simple S = Double, you need a custom class to play the role of the group summary. Let’s call it ContainerSummary. Every summary holds the total group amount and the size of the group. Besides a natural two-parameter constructor, I’ll add a default constructor, as shown in listing 9.6. In that way, I can later refer to it with a method reference (OK, “constructor reference” would be more precise) and fill in the “seed” operation of the Attribute interface.

Listing 9.6. ContainerSummary: Fields and constructors

class ContainerSummary {
   private double amount;
   private int groupSize;

   public ContainerSummary(double amount, int groupSize) {
      this.amount = amount;
      this.groupSize = groupSize;
   }
   public ContainerSummary() {  1 Default constructor
      this(0, 1);  2 Calls the other constructor with 0 water and 1 container in the group
   }

Next, the following listing contains the three methods that provide the remaining attribute operations.

Listing 9.7. ContainerSummary: Summary manipulation methods

    1 Analogous to addWater
   public void update(double increment) {
      this.amount += increment;
   }
    2 Used when connecting two containers

   public ContainerSummary merge(ContainerSummary other) {
      return new ContainerSummary(amount + other.amount,
                                  groupSize + other.groupSize);
   }
    3 Returns amount per container
   public double getAmount() {
      return amount / groupSize;
   }

Finally, you can use the static method of from the Attribute interface and four method references to instantiate the Attribute object that UnionFindNode needs. There’s a slight mismatch between the primitive type double that the methods in Container Summary use and the wrapper type Double that Attribute expects. But not to worry: auto(un)boxing makes sure that you can use method references involving primitive types even when the context calls for wrapper types.

You can then expose this Attribute object to the clients as a class constant, that is, a final static field, as in the following listing.

Listing 9.8. ContainerSummary: The Attribute field

   public static final Attribute<Double,ContainerSummary> ops =
      Attribute.of(ContainerSummary::new,  1 Reference to default constructor
                   ContainerSummary::update,
                   ContainerSummary::merge,
                   ContainerSummary::getAmount);

Figure 9.2 features a UML class diagram for ContainerSummary and its relationship to Attribute. Notice how the constructor and the three methods of ContainerSummary correspond to the four methods of the interface.

Figure 9.2. A UML class diagram for ContainerSummary and its relationship to Attribute. The first parameter of methods update, merge, and report is bound to this in the corresponding methods of ContainerSummary.

9.5.3. Defining the concrete water container class

Once you’ve defined the concrete summary and its support methods, you can recover the usual behavior of water containers with just three lines, by extending UnionFind Node and passing the appropriate Attribute object to its constructor, as shown in the following listing.

Listing 9.9. Generic: Water containers in three lines

public class Container extends UnionFindNode<Double,ContainerSummary> {
   public Container() {
      super(ContainerSummary.ops);
   }
}

That was pretty neat, but we did run into some limitations of Java generics. If you think about it, it’s a waste of space that all UnionFindNodes must carry a reference to the same Attribute object. If generics were reified instead of erased, that reference could have been a static field of UnionFindNode<Double,ContainerSummary>. In that way, all nodes of that type would have shared a single reference to the object responsible for manipulating summaries.

Incidentally, listing 9.9 is the shortest definition of a functioning water container class in the book. It’s even shorter than the one in the appendix, which is explicitly optimized for brevity! Of course, the version in this section is cheating; we’ve moved all the functionality to the generic framework. If you count all that code (classes Union FindNode and ContainerSummary, and interfaces ContainerLike and Attribute) the generic version is actually the longest in the book!

9.6. Social network posts

To witness the generality of your solution, let’s design another concrete container version, this time addressing the second scenario I presented at the beginning of this chapter: posts in a social network, connected by common commenters and counting total likes. In fact, this scenario turns out to be simpler than water containers. This time, it’s enough for the group summary to hold the total number of likes that the posts in the group accrue; there’s no need to know the size of the group. As a result, the summary is just a wrapper around an integer.

Listing 9.10. PostSummary: Field and constructors

class PostSummary {
   private int likeCount;

   public PostSummary(int likeCount) {
      this.likeCount = likeCount;
   }
   public PostSummary() {}  1 Allows for a method reference later

The default constructor fulfills the “seed” operation of Attribute. The methods shown in the following listing provide the other three operations. Once again, you can use the static method of to pack those four operations into an object of type Attribute.

Listing 9.11. PostSummary: Methods and static field

   public void update(int likes) {
      likeCount += likes;
   }
   public PostSummary merge(PostSummary summary) {
      return new PostSummary(likeCount + summary.likeCount);
   }
   public int getCount() {
      return likeCount;
   }
   public static final Attribute<Integer,PostSummary> ops =
      Attribute.of(PostSummary::new,  1 Reference to default constructor
                   PostSummary::update,
                   PostSummary::merge,
                   PostSummary::getCount);
}

Just like you did with water containers in the previous section, you can instantiate the class representing social network posts with the three lines in the following listing:

Listing 9.12. Post: Counting likes with the generic framework

public class Post extends UnionFindNode<Integer,PostSummary> {
   public Post() {
      super(PostSummary.ops);
   }
}

9.7. And now for something completely different

Rather than a single class, this last example features a stand-alone application with a GUI. It’s an opportunity to apply the principles outlined in this book on a larger scale. In the online repository,^[2] you can find a simple GUI application that plots a parabola, that is, a curve whose equation is in the form

²

The baseline version of the plotting app is in the package eis.chapter9.plot, whereas the generalized version sits in eis.chapter9.generic.plot.

You can see a screenshot in figure 9.3. The top panel plots the function for a fixed range of x values. The middle panel lists the value of the function for five fixed values of x. The bottom panel allows the user to interactively change the value of the three parameters, a, b, and c.

Figure 9.3. A screenshot of the plotting program

The baseline implementation is composed of four classes—one for each panel and one Main class that ties them together. It can plot only parabolas, and it contains a couple of defects:

• Code duplication— Both TablePanel and PlotPanel contain code that evaluates a parabola at a given point. It would be better to have that code in a single place.
• An ad-hoc communication scheme— When you change a parameter by moving a slider, the code responding to the event (aka the controller) asks all panels to repaint. This is not so bad, but imagine a full-blown version of this application, with tons of widgets that can change the visualization in different ways. If you keep this communication scheme, you need to make all widgets aware of all panels that visualize the function (aka views). Figure 9.4 depicts a typical flow of events in this architecture.

Figure 9.4. The communication scheme for the baseline plotting program. Parameters are stored in a plain array of doubles, shared among all components. In this scheme, each controller must know all views.

Let’s generalize this app so that it can plot arbitrary parametric functions with any number of parameters, that is, curves of equation

where a₁, . . . , a_n are parameters. To be clear, I’m not talking about accepting the function definition from text, which would require a parser. The generalized app should just be able to switch to a different type of function with as little programmer effort as possible. The program should automatically adapt the GUI to the type of function that it’s displaying. For example, the number of sliders in the bottom panel must equal the number of parameters. Along the way, we’ll also address the two design shortcomings I listed earlier.

9.7.1. An interface for parametric functions

The first step in the generalization process is to identify an interface—call it Parametric Function—representing a parametric function. To allow the application to fully adapt to a specific parametric function, the interface must include the following services:

• Providing the number of parameters.
• Providing the names of each parameter. This allows you to customize the labels “a,” “b,” and “c” in the parameter panel.
• Getting and setting the value of each parameter.
• Evaluating the function on a given value, for the current value of its parameters. This functionality solves the code duplication issue discussed earlier. The parametric function will be the only place responsible for computing the value of the function.

To translate these functionalities into Java, you have to index parameters from 0 to n – 1, and obtain an interface like the following:

public interface ParametricFunction {
   int getNParams();  1 Returns the number of parameters

   String getParamName(int i);  2 Returns the name of parameter i

   double getParam(int i);  3 Returns the value of parameter i

   void setParam(int i, double val);  4 Sets the value of parameter i

   double eval(double x);   5 Returns the value of this function at x
}

At this point, you recover the old concrete behavior with a Parabola class that implements this interface. (I’m skipping precondition checks for simplicity.)

public class Parabola implements ParametricFunction {
   private final static int N = 3;  1 Three parameters
   private final static String[] name = { "a", "b", "c" };
   private double[] a = new double[N];

   public int getNParams()           { return N; }
   public String getParamName(int i) { return name[i]; }
   public double getParam(int i)     { return a[i]; }
   public void setParam(int i, double val) { a[i] = val; }
   public double eval(double x)      { return a[0]*x*x + a[1]*x + a[2]; }
}

You can imagine how easy it is to define a different parametric function. For example, suppose you want to plot the hyperbola with equation

The following class does the trick:

public class Hyperbola implements ParametricFunction {
   private final static int N = 1;  1 One parameter
   private final static String[] name = { "a" };
   private double[] a = new double[1];

   public int getNParams()           { return N; }
   public String getParamName(int i) { return name[i]; }
   public double getParam(int i)     { return a[i]; }
   public void setParam(int i, double val) { a[i] = val; }
   public double eval(double x)      { return a[0] / x; }
}

If you compare Parabola and Hyperbola, you’ll notice immediately that they share a lot of code. The only substantial difference lies in their implementation of eval, which is where the specific function is actually defined. This suggests that an abstract class, inserted between the interface and the concrete classes, might carry most of the weight of these classes.

The abstract class—call it AbstractFunction—can be responsible for storing and managing parameters, and even for providing standard parameter names (the letters “a”, “b”, and so on). Basically, the abstract class takes care of everything, except computing the value of the function with eval, which is left abstract. Here’s a possible implementation for the abstract class (once again, omitting some checks for simplicity):

public abstract class AbstractFunction implements ParametricFunction {
   private final int n;
   protected final double[] a;  1 Accessible to subclasses for efficiency

   public AbstractFunction(int n) {  2 Constructor for the subclasses
      this.n = n;
      this.a = new double[n];
   }

   public int getNParams()       { return n; }
   public String getParamName(int i) {
      final int firstLetter = 97;  3 ASCII code for ’a’
      return Character.toString(firstLetter + i);
   }
   public double getParam(int i) { return a[i]; }
   public void setParam(int i, double val) { a[i] = val; }
}

The abstract class streamlines the definition of concrete functions. For example, here’s what Hyperbola looks like when taking advantage of AbstractFunction:

public class Hyperbola extends AbstractFunction {
    public Hyperbola() { super(1); }
    public double eval(double x) { return a[0] / x; }
}

9.7.2. A communication discipline

You can take the opportunity of this refactoring to also improve the communication scheme of the program. Now you have a central object, the parametric function, which holds the relevant data (the parameters) and provides the information to be displayed (the function values). It’s the ideal situation for applying the well-known model-view-controller (MVC) architectural pattern.

In the context of the plotting app, the parametric function is the model class, the three panels are views, and the event handlers responding to the sliders are controllers. Design the refactored app to adhere to the communication scheme that MVC originally intended:

• When the program starts, the three views register themselves as observers of the model. The model (the parametric function) holds references to them. To avoid cluttering the ParametricFunction interface with unrelated features, you can assign the responsibility for holding these references and sending notifications to a separate class—ObservableFunction in the repository— that wraps a parametric function and adds these functionalities.^[3]

  ³

  This mechanism is an example of the Decorator design pattern.

• When the user moves a slider in the parameter panel of the GUI, the controller updates the value of the corresponding parameter in the model. The controller doesn’t take any other action.
• Whenever the model receives a call to setParam to update the value of a parameter, it notifies all registered views that something in the model has changed.

Here are the main bits of the ObservableFunction class. First, it wraps a Parametric Function object, and at the same time it implements that interface. It also keeps track of its observers as a list of ActionListeners. The latter is a standard interface from the Java AWT windowing kit, whose only method is void actionPerformed(ActionEvent e). The ActionEvent parameter is meant to carry information about the event that’s being notified. You’ll support a single type of event: the user changing the value of one of the function’s parameters. That’s why you can use a single dummy event object for all notifications. Here’s the beginning of the ObservableFunction class:

public class ObservableFunction implements ParametricFunction {
   private final ParametricFunction f;  1 Inner parametric function
   private final List<ActionListener> listeners = new ArrayList<>();
   private final ActionEvent dummyEvent =
      new ActionEvent(this, ActionEvent.ACTION_FIRST, "update");

   public ObservableFunction(ParametricFunction f) { this.f = f; }

The core responsibility of ObservableFunction is to notify all observers when a call to setParam is made:

   public void setParam(int i, double val) {
      f.setParam(i, val);
      for (ActionListener listener: listeners) {  1 Notifies observers
         listener.actionPerformed(dummyEvent);  2 A dummy event carrying no actual info
      }
   }

All other methods are passed through to the inner ParametricFunction object. For example, here’s the implementation of getParam:

   public double getParam(int i) {  1 Passed through to inner function
      return f.getParam(i);
   }

Figure 9.5 depicts the new communication scheme. Because a single object—the model—is responsible for notifying all views, you can afford to split the three views of the previous version into a higher number of views. For example, instead of considering the whole TablePanel as a view, you can treat as views the five labels in the “y” column. After all, they’re the only part of that panel that the program needs to redraw when the user updates one of the parameters.

Figure 9.5. The communication scheme for the refactored plotting program. According to MVC, the controller interacts with the views only through the model. The arrows between ObservableFunction and ParametricFunction indicate that the former implements the latter, and in addition contains a reference to an inner ParametricFunction.

This communication scheme is more robust than the custom solution that the baseline plotting app used. It’s easier to add new views or controllers. To activate a new view, it’s sufficient to pass the model to it and register it as another model observer. You don’t need to modify any controllers. Symmetrically, it’s possible to add new controllers to the GUI (that is, new interactive widgets) without changing the view components.

9.8. Real-world use cases

As you’ve seen in this chapter, generics are a very powerful feature that enables defining type-safe data structures that can work with different data types. Types become parameters (generics are also known as parametric polymorphism) whose specification you defer until the time of declaration. Type parameterization promotes code resuability because it’s possible to avoid repeating the same algorithm over and over for different data types. To make this more concrete, I’ll present some further use cases:

• Probably one of the most important use cases of generics is a data container: vectors, lists, sets, trees, queues, stacks, and so on. Can you identify an important principle all these containers have in common? They’re agnostic to the type of the object they’re handling. They only take care of the organization of the objects: if you pop an item off the stack, the container doesn’t care about the type of the object that you popped.
• As you’ve seen in the previous chapter, multithreading has always been one of the major features of the Java language, and one that has evolved with new releases. What stands out in this evolution, though, is the concurrency utilities that the language designers added in Java 1.5, when they introduced generics to the language. Since the early days, it was possible to represent a threaded task by implementing the Runnable interface. That interface has a single run method that doesn’t accept any parameter or return any value. Hence, it’s limited to those cases where no result value is expected from the thread. On the other hand, the newer Callable interface is a generic interface that returns a parameterized type. To execute a task, you must submit an object implementing Callable to an ExecutorService to launch it. Can you guess what type the executor service returns? Another parameterized type: Future. The type Future<T> bears the semantics of an expectation, that you’re expecting some result of type T once the computation is complete.
• In the first use case I discussed how data structures use generics to organize data. It’s often the case, however, that you use generics for containers holding a single element of a parametric type. AtomicReference<T> is an example of a single-element container that you can use in a setting where it’s required to perform an atomic, thread-safe operation. Thus it’s possible to share the object among different threads without having to use synchronization. Another example is the recent Optional<T> class, which replaces the need to return null values and is featured in exercise 3 in this chapter.
• In a production codebase, it’s common to use a data access object (DAO) that provides an interface for accessing a persistence mechanism (such as a relational database). The purpose of the DAO is to provide operations on the persistence mechanism without exposing its internals to the client. Imagine writing a DAO to perform some CRUD operations on a database: create, delete, update, findAll, and so on. You might want to use this DAO to persist different entity types defined in your domain model. Using generics, it’s possible to parameterize the DAO and use these common operations for different entity types.

9.9. Applying what you learned

Exercise 1

Recall that Java generics are implemented via erasure and C# generics via reification. As a consequence, table 9.5 shows three instructions involving a type parameter T that are valid in C# but invalid in Java. What’s a Java workaround in each of those three cases? In other words, what’s an alternative way to obtain a similar effect?

Table 9.5. Some limitations of Java generics, compared to C#, of what you can do with a type parameter T. Note that the first example requires the type constraint “ where T: new()” to be correct C#.

Exercise 2

Using the generic UnionFindNode infrastructure, design a solution to the first scenario discussed at the beginning of this chapter: water containers with arbitrary precision rational water levels (in the mathematical sense of rational numbers).

Hint: Don’t reinvent the wheel. Start from an existing class for arbitrary precision rational numbers. There are a couple online.

Exercise 3

Design a Schedule<E> class handling generic events of type E, where E must be a subtype of the following interface:

public interface Event {
   void start();
   void stop();
}

The class Schedule<E> must provide the following methods:

• public void addEvent(E event, LocalTime startTime, LocalTime stop Time)—Adds an event to this schedule, with specified start and stop times. If the event overlaps with another event from this schedule, this method throws an IllegalArgumentException. If this schedule has already been launched (method launch), this method throws an IllegalStateException.
• public void launch()—From the moment you call this method, this schedule is responsible for invoking the start and stop methods of its events at the right time. You can’t add any more events to the schedule after launch.
• public Optional<E> currentEvent()—Returns the currently active event, if any. In case you missed it, Optional is the modern alternative to returning a null value. An Optional<E> can contain an object of type E or be empty. If the client has already launched this schedule, but there’s no active event at this time, this method returns an empty Optional. If the client hasn’t launched this schedule, this method throws an IllegalStateException.

In addition, implement a concrete class of events—say, HTTPEvent—whose start and stop actions spawn HTTP GET messags to specified URLs.

Exercise 4

Write a method that accepts a collection of objects and partitions them according to an equivalence predicate.

public static <T> Set<Set<T>{}> partition(
    Collection<? extends T> c,
    BiPredicate<? super T, ? super T> equivalence)

BiPredicate<U,V> is a standard functional interface whose only method is boolean test(U u, V v). You can assume that the equivalence predicate satisfies the rules of an equivalence relation—reflexivity, symmetry, and transitivity—just like the equals method from Object.

For example, say you want to group strings according to their length. You can define the corresponding equivalence as the following BiPredicate:

BiPredicate<String,String> sameLength = (a, b) -> a.length() == b.length();

You may then call the partition method on a set of strings:

Set<String> names = Set.of("Walter", "Skyler", "Hank", "Mike", "Saul");
Set<Set<String>{}> groups = partition(names, sameLength);
System.out.println(groups);

As a result, you should get those five strings gathered in two groups according to their length:

[[Walter, Skyler], [Saul, Mike, Hank]]

Hint: This exercise is closer to water containers than you may think.

Summary

• Modern programming combines powerful reusable frameworks with application-specific code.
• Generics help write reusable components.
• Reusable components may incur extra costs compared to an ad-hoc solution.
• Java 8 streams make heavy use of generics to offer a highly configurable data-processing framework.
• Generalizing a piece of software starts by defining a set of target scenarios.
• Reusable software components often revolve around a set of key interfaces.
• The original model-view-controller architecture prescribes responsibilities and communication protocols for desktop applications with GUIs.

Answers to quizzes and exercises

Pop Quiz 1

It’s not a good idea to insert a public boolean equals(Employee e) method into an Employee class. First, note that you’re overloading and not overriding the equals method from Object. As a consequence, employees end up with two different equality methods: an identity-based one inherited from Object, and a presumably content-based one with a more specific parameter type. When comparing two employees, you might end up calling either method, depending on the static type of the second employee:

Employee alex = ..., beth = ...;
alex.equals(beth);           1 Content-based comparison
alex.equals((Object) beth);  2 Identity-based comparison

This situation is prone to errors and likely not what the programmer intended.

Pop Quiz 2

No, in Java you can’t allocate an array of type T (new T[...]), where T is a type parameter. That’s because arrays store their type and use that information to check at runtime that every write or cast operation is legal. Due to erasure, the bytecode doesn’t store the actual value of T at runtime, so that mechanism can’t work. You shouldn’t confuse this limitation with the ability to declare a variable of type T[], which is perfectly legal.

In C#, you can allocate an array of type T because the type parameters are reified— their actual value is known at runtime.

Pop Quiz 3

Only parallel collectors use the combiner method of a collector. It returns an object that you can use to merge the partial results that different threads obtain as they’re cooperating to execute a stream operation.

Pop Quiz 4

You can’t directly assign a method reference to a variable of type Object, as in:

Object x = String::length;  1 Compile-time error

because the context doesn’t contain enough information to identify a specific functional interface. If you must do something like that, a cast might come in handy:

Object x = (ToIntFunction<String>) String::length;  2 Valid Java

Exercise 1

When you need runtime type information, and generics aren’t enough, reflection is usually the solution. For example, instead of “new T(),” you can carry around an object t of type Class<T> and then dynamically invoke a constructor using the following fragment:

Constructor<T> constructor = t.getConstructor();  1 Returns the default constructor
T object = constructor.newInstance();

Depending on the context, an alternative solution is to have the client provide a Supplier<T>, a functional interface that can wrap a constructor or any other way to produce objects of type T.

The recommended workaround to “new T[10]” involves using a collection instead of an array:

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

As you saw in chapter 4, with a List you get a variety of extra services, and you pay very little overhead (but you can’t write list[i]; life’s hard).

Finally, you can again emulate a runtime check similar to “exp instanceof T” via reflection. If you have an object t of type Class, you can check whether a given expression is a subtype of t via

t.isInstance(exp);

Exercise 2

As the class for arbitrary precision rational numbers, I picked BigRational by Robert Sedgewick and Kevin Wayne.^[4] It’s an intuitive implementation of immutable rationals that you can use like this:

⁴

You can find a copy in the online repository at https://bitbucket.org/mfaella/exercisesinstyle.

BigRational a = new BigRational(1, 3);  1 One-third
BigRational b = new BigRational(1, 2);  2 One-half
BigRational c = a.plus(b);
System.out.println(c);  3 Prints 5/6

You can equip water containers with amounts of type BigRational by modifying the Con tainer class presented in section 9.5. First, you redefine the group summary class, with an amount field of type BigRational and the same integral group size field. Whenever you need to perform arithmetics on water amounts, you need to use the methods of BigRational, like plus or divides. I’ll provide here a fragment of the group summary class, called RationalSummary. You can find the rest in the online repository.

class RationalSummary {
   private BigRational amount;
   private int groupSize;
   ...
   public void update(BigRational increment) {
      amount = amount.plus(increment);  1 BigRationals are immutable
   }
   ...
   public static final Attribute<BigRational,RationalSummary> ops =
      Attribute.of(RationalSummary::new,
                   RationalSummary::update,
                   RationalSummary::merge,
                   RationalSummary::getAmount);
}

Once you have the group summary class, you get the container class by extending UnionFindNode and passing the Attribute object to its constructor:

public class Container extends UnionFindNode<BigRational,RationalSummary> {
   public Container() {
      super(RationalSummary.ops);
   }
}

Exercise 3

The class Schedule must store a sorted sequence of non-overlapping events. To allow it to do so, define a support class—say TimedEvent—to keep together the event and its start and stop times. This can be a private internal class of Schedule.

A TreeSet<TimedEvent> with a custom order between elements can efficiently keep timed events sorted and detect overlaps at the same time. Recall that all implementations of the Set interface reject duplicate elements. TreeSet implements Set and bases all its operations on the order between its elements, including detecting duplicates (that is, it doesn’t invoke equals). To reject a timed event that overlaps with a previously inserted one, define the order so that overlapping events are equivalent (compareTo returns zero). In other words, use the following order:

• If event a comes entirely before event b, a is “smaller” than b, and vice versa.
• If two events overlap, they’re “equivalent” (compareTo returns zero).

Here is the gist of the TimedEvent class:

public class Schedule<E> {

   private class TimedEvent implements Comparable<TimedEvent> {
        E event;                     1 This class is private---no need to hide its fields.
        LocalTime startTime, stopTime;
        @Override
        public int compareTo(TimedEvent other) {
            if (stopTime.isBefore(other.startTime)) return -1;
            if (other.stopTime.isBefore(startTime)) return 1;
            return 0;  2 Overlapping events appear "equivalent."
        }
        ...  3 Trivial constructor omitted
    }

Each Schedule object holds the following fields:

• private volatile boolean active;—Set by launch and reset at the end of the helper thread that executes the schedule. The volatile modifier ensures visibility across threads.
• private volatile Optional<E> currentEvent = Optional.empty();— Maintained by the helper thread that executes the schedule. The currentEvent method returns its value.
• private final SortedSet<TimedEvent> events = new TreeSet<>();— The sequence of timed events.

Method addEvent adds a new timed event to the TreeSet and checks three illegal cases.

   public void addEvent(E event, LocalTime startTime, LocalTime stopTime)
   {
      if (active)
         throw new IllegalStateException(
            "Cannot add event while active.");
      if (startTime.isAfter(stopTime))
         throw new IllegalArgumentException(
            "Stop time is earlier than start time.");
      TimedEvent timedEvent = new TimedEvent(event, startTime, stopTime);
      if (!events.add(timedEvent))  1 Insertion fails in case of overlap
         throw new IllegalArgumentException("Overlapping event.");
   }

The actual execution of the schedule is forked out to another thread, so as not to block the launch method. You can find the code for launch and two examples of concrete event classes (PrintEvent and HTTPEvent) in the online repository.

Exercise 4

You can solve this exercise using an implementation of the generic container framework, such as UnionFindNode. The idea is to create a node for each element of the given collection and connect two nodes whenever their elements are equivalent according to the given predicate. After you’ve laid out all the connections, the groups of connected nodes form the desired output.

To eventually get the desired output, each node must know the set of nodes connected to it. Let’s put that information into the group summary. You need an implementation of Attribute<V,S> with both V and S equal to Set<T>. Once again, the adapter method Attribute.of comes in handy:

   public static <T> Set<Set<T>{}>
      partition(Collection<? extends T> collection,
                BiPredicate<? super T, ? super T> equivalent) {

      Attribute<Set<T>,Set<T>{}> groupProperty = Attribute.of(
             HashSet::new,  1 Reference to constructor
             Set::addAll,   2 Reference to method of interface

             (set1, set2) -> {  3 Merges two sets
                Set<T> union = new HashSet<>(set1);
                union.addAll(set2);
                return union;
             },
             set -> set);   4 No need to unwrap anything

The first actual operation involves creating a node for each element in the collection. You also need to keep track of which node belongs to which element. You can use a map for that:

      Map<T,UnionFindNode<Set<T>,Set<T>{}>{}> nodeMap = new HashMap<>();
      for (T item: collection) {
         UnionFindNode<Set<T>,Set<T>{}> node =
            new UnionFindNode<>(groupProperty);
         node.update(Set.of(item));  1 Initializes the group
         nodeMap.put(item, node);    2 Assigns the node to the current item
      }

Then, you turn each equivalence into a connection between two nodes:

      for (T item1: collection) {
         for (T item2: collection) {
            if (equivalent.test(item1, item2))
               nodeMap.get(item1).connectTo(nodeMap.get(item2));
         }
      }

Finally, you collect all groups into a set, which is the desired partition of elements:

       Set<Set<T>{}> result = new HashSet<>();
       for (T item: collection) {
          result.add(nodeMap.get(item).get());
       }
       return result;
   }

Further reading

• M. Naftalin, P. Wadler. Java Generics and Collections. O’Reilly, 2006. You won’t find the latest gimmicks in this Java 5 book, but a solid coverage of generics and their subtleties.
• J. Tulach. Practical API Design: Confessions of a Java Framework Architect. Apress, 2008. Writing effectively reusable code is closely tied to defining proper APIs. This is one of the few books devoted entirely to that topic.
• R.-G. Urma, M. Fusco, and A. Mycroft. Modern Java in Action. Manning Publications, 2019. As mentioned in chapter 8, this book includes one of the best accounts of the stream library.
• J. Skeet. C# in Depth. Manning Publications, 2019. An up-to-date presentation of the evolution of C# across versions, including a reasoned comparison between the implementation of generics in C#, C++, and Java.