For instance, we have a Tree class of type T: i.e. Tree<T>.
We would like to make this Tree<T> class to be able to hold
Tree<T> (of course),SubTree<T> where SubTree extends Tree,Tree<SubT> where SubT extends T, andSubTree<SubT> where SubTree extends Tree and SubT extends T."Hold" means it accept the certain sub-class, and it returns the object of certain sub-class respectively, upon request.
For example, the original ArrayList has this property:
private static class Leaf {
}
private static class RedLeaf extends Leaf {
}
@Test
public final void test() {
ArrayList<Leaf> al = new ArrayList<Leaf>();
al.add(new Leaf());
System.out.println(al.get(al.size()-1).getClass()); // class Leaf
al.add(new RedLeaf());
System.out.println(al.get(al.size()-1).getClass()); // class RedLeaf
}
It is because the original ArrayList just keep a reference of the input object, but not re-creating it. This is not a desired behaviour while building my class, especially a tree. Consider the following example:
public final void test() {
ArrayList<Leaf> al = new ArrayList<Leaf>();
Leaf leaf = new Leaf();
RedLeaf redLeaf = new RedLeaf();
al.add(leaf);
al.add(redLeaf);
al.add(leaf);
System.out.println(al.indexOf(al.get( 0 ))); // 0
System.out.println(al.indexOf(al.get( 1 ))); // 1
System.out.println(al.indexOf(al.get( 2 ))); // 0 <-- disaster
}
Why this is a disaster? Consider for a certain node in a tree, we want to find the next sibling.
In fact, we can do a quick fix while inserting the elements:
private static class Leaf {
Leaf() { super(); }
Leaf(Leaf leaf) { super(); }
}
private static class RedLeaf extends Leaf {
RedLeaf() { super(); }
RedLeaf(RedLeaf redLeaf) { super(redLeaf); }
}
@Test
public final void test() {
ArrayList<Leaf> al = new ArrayList<Leaf>();
Leaf leaf = new Leaf();
RedLeaf redLeaf = new RedLeaf();
al.add(new Leaf(leaf));
al.add(new RedLeaf(redLeaf));
al.add(new Leaf(leaf));
System.out.println(al.indexOf(al.get( 0 ))); // 0
System.out.println(al.indexOf(al.get( 1 ))); // 1
System.out.println(al.indexOf(al.get( 2 ))); // 2 <-- nice :-)
}
But when it comes to building our own class (of the Tree), this becomes a big problem.
(solution below)
We have a Tree class, which uses ArrayList to hold the nodes:
public class Tree<T> {
// some constructors & methods skipped
private final ArrayList<Tree<T>> mChildren = new ArrayList<Tree<T>>();
}
We have this addChild method, with no problems:
public void addChild(final Tree<T> subTree) {
getChildren().add(new Tree<T>(this, subTree)); // copy the tree & set parent attach to this
}
Then, we want to make the addChild method more general, which allows adding a tree of sub-type.
private class RedTree<T> extends Tree<T> {}
private void showArrayListIsOkForSubType() {
RedTree<T> redTree = new RedTree();
getChildren().add(redTree);
getChildren().add(new RedTree());
}
In concept, we want to modify the addChild method to this:
(But the following code is having compile errors, shown in comments.)
public <Leaf extends T, SubTree extends Tree<T>> void add(final SubTree<Leaf> subTree) {
// The type SubTree is not generic; it cannot be parameterized with arguments <Leaf>
SubTree<Leaf> tr = new SubTree<Leaf>();
getChildren().add(new SubTree<Leaf>());
// SubTree cannot be resolved to a type
// Leaf cannot be resolved to a type
}
We have searched through stackoverflow, but still with no helps. Could you please help us with the correct syntax?
With the guide and explanation from @Jason C, here is my codes. Hope it helps others :)
Also, please feel free to correct me :)
Note: the codes are not 100% complete. But all the major pieces are included.
First, in the default zero-argument constructor, ensure all the sub-classes define the copy-constructor.
/** Default constructor. **/
public Tree() { // All sub-classes instantiation must invoke this default constructor
super(); // here is a good place to ensure every sub-class has a copy constructor
if (Reflection.hasCopyConstructor(this) == false)
throw new CopyConstructorRequiredException(this.getClass());
}
class Reflection {
public static boolean hasCopyConstructor(final Object object) {
return hasCopyConstructor(object.getClass());
}
public static boolean hasCopyConstructor(final Class<?> clazz) {
try {
clazz.getDeclaredConstructor(clazz);
return true;
} catch (SecurityException e) {
e.printStackTrace();
return false;
} catch (NoSuchMethodException e) {
e.printStackTrace();
return false;
}
}
}
Then this is the copy constructor of the base Tree<T>:
private Tree(final Tree<? extends T> copyFrom) {
super();
if (copyFrom != null) {
this.setData(copyFrom.getData());
for (final Tree<? extends T> child : copyFrom.getChildren()) {
this.addChildren(child); // addChildren() handles null well
}
}
}
Only the Generic Parameter <T> needs a wildcard of sub-class <? extends T>.
The parameter Tree inherently accepts all the sub-classes of Tree, by auto casting.
So, this copy constructor already able to accept Tree<T>, SubTree<T>, Tree<SubT>, and SubTree<SubT>.
For the copy constructor of the extended classes, it can be just simply:
private static class BlueTree<T> extends Tree<T> {
private BlueTree(final BlueTree<T> blueTree) { super(blueTree); }
}
Back to the base class, Tree. Here is how addChild stores the objects.
public Tree<T> addChildren(final Tree<? extends T>... subTrees) {
if (subTrees == null) // called addChildren((Tree<T>) null)
addChild((Tree<T>) null); // add null to children
else
for (final Tree<? extends T> subTree : subTrees) // empty parameter goes here != null array
addChild(subTree);
return this;
}
public Tree<T> addChild(final Tree<? extends T> subTree) {
if (subTree == null) // for addChild((Tree<T>) null)
getChildren().add(null); // add null to children
else { // else
getChildren().add( // copy (constructor) the tree & set parent attach to this
Reflection.<Tree<T>>invokeConstructor(subTree, new ParameterTypeAndArg(subTree.getClass(), subTree))
.setParent(this));
}
return this;
}
Because we have checked every sub-class must contain the default constructor, we can safely invoke it here by reflection, to get a new instance of the sub-class, and store it into the children ArrayList.
P.S. we need to use reflection invoke because the ordinary new doesn't work for generic parameters.
Well, first of all, you're overcomplicating this. All you really need to do is:
public void add(final Tree<? extends T> subTree) {
Theres no need to parameterize add().
But anyways, I'll address your original attempt: You want SubTree extends Tree<Leaf>, because even if Leaf extends T you can't guarantee that SubTree extends Tree<T> with SubTree<Leaf> matches. E.g. if your class hierarchy is:
public class Base { }
public class A extends Base { }
public class B extends Base { }
If Leaf is A and SubTree is Tree<B> then add (final SubTree<Leaf>) does not match Tree<B>.
So conceptually you actually want this:
public <Leaf extends T, SubTree extends Tree<Leaf>> void add(final SubTree<Leaf> subTree) {
Of course that is not valid syntax. Really all you need to do is this:
public <Leaf extends T, SubTree extends Tree<Leaf>> void add(final SubTree subTree) {
That will be sufficient to match all necessary types. Try it:
{
Tree<Object> x = new Tree<Object>();
MyTree<Integer> y = new MyTree<Integer>();
Tree<Integer> z = new Tree<Integer>();
x.add(y);
y.add(x); // not valid, as Tree<Object> does not extend Tree<Integer>
y.add(z); // fine, as Tree<Integer> matches
}
public static class MyTree<T> extends Tree<T> {
}
Within add() you also do not parameterize SubTree, since its type is already specified elsewhere:
SubTree tr = ...;
However, now you have a bigger problem, which is a classic one and is answered in many other places here:
tr = new SubTree();
You cannot instantiate an object of a generic type because of type erasure. You will have to specify the SubTree's Class somewhere and instantiate it with .newInstance().