Designing an Interface for a Hierarchical Object

Question

I need to create an interface for a hierarchical entity:

interface HierarchicalEntity<T extends HierarchicalEntity<T>> { T getParent(); Stream<T> getAncestors(); } 

It is very easy to implement the default getAncestors() method in terms of getParent() so that the first returns the Stream all the ancestors.

Implementation Example:

 default Stream<T> getAncestors() { Stream.Builder<T> parentsBuilder = Stream.builder(); T parent = getParent(); while (parent != null) { parentsBuilder.add(parent); parent = parent.getParent(); } return parentsBuilder.build(); } 

But I need to include this in the stream, and this is where the problem arises. The following line is incorrect since this is of type HierarchicalEntity , not T :

 parentsBuilder.add(this); // type mismatch! 

How can I redesign the interface to getAncestors() to include this in the result?

Answer 1

This is a recurring problem when creating self-referencing types. In the base type (or interface), you cannot match this compatibility with T

Of course, you can uncheck this to T if you are sure that all subtypes will fulfill this restriction. But you must complete this unchecked cast when you need a this reference like T

The best solution is to add an abstract method like

 /** All subtypes should implement this as: public T myself() { return this; } */ public abstract T myself(); 

Then you can use myself() instead of this when you need self-promotion like T

 default Stream<T> getAncestors() { Stream.Builder<T> parentsBuilder = Stream.builder(); for(T node = myself(); node != null; node = node.getParent()) { parentsBuilder.add(parent); } return parentsBuilder.build(); } 

Of course, you cannot ensure that subclasses correctly implement myself() as return this; , but at least you can easily check if they are executed at runtime:

 assert this == myself(); 

This comparative comparison is a very cheap operation, and if myself() correctly implemented as invariably returning this , HotSpot can prove in advance that this comparison will always be true and fully validate.

The disadvantage is that each specialization must have this redundant implementation of myself() { return this; } myself() { return this; } , but on the other hand, its completely free from unverified types. An alternative would be to declare abstract abstract in the base class as @SuppressWarnings("unchecked") T myself() { return (T)this; } @SuppressWarnings("unchecked") T myself() { return (T)this; } to limit the unverified operation to one place for the type hierarchy. But then you cannot check if this really has type T ...

Answer 2

As @SotiriosDelimanolis said, there is no way to fully provide this. But if you agree that the interface is used as constructed, you can assume that this is an instance of T and just discards it:

 parentsBuilder.add((T)this); 

If you want to avoid casting, you can add a method that must be overridden in a subclass:

 interface HierarchicalEntity<T extends HierarchicalEntity<T>> { T getParent(); T getThis(); default Stream<T> getAncestors() { // ... parentsBuilder.add(getThis()); // ... } } class Foo extends HierarchicalEntity<Foo> { // ... @Override public Foo getThis() { return this; } } 

Now we can get this as fonts, but there is no guarantee that getThis() was implemented correctly. It is possible to return any instance of Foo . So, select the poison, I think.

Answer 3

Adding this not done because a HierarchicalEntity<T> not necessarily a T ; it may be an unknown subtype. However, T always a HierarchicalEntity<T> , as you declared it.

Change the return type of getAncestors and Stream.Builder from T to HierarchicalEntity<T> to allow you to add this .

 default Stream<HierarchicalEntity<T>> getAncestors() { Stream.Builder<HierarchicalEntity<T>> parentsBuilder = Stream.builder(); T parent = getParent(); while (parent != null) { parentsBuilder.add(parent); parent = parent.getParent(); } parentsBuilder.add(this); return parentsBuilder.build(); } 

You might want to declare getParent to return a HierarchicalEntity<T> also for consistency.