Automatic cast to subclass in getter/setter

Question

I have a rather weird question. Consider the following two classes:

public class Node<T> {
    private Node<T> parent;
    private Node<T> left;
    private Node<T> right;
    private T data;

    public Node(Node<T> parent, T data) {
        this.parent = parent;
        this.data = data;
    }

    public Node<T> getParent() {
        return parent;
    }

    public void setParent(Node<T> parent) {
        this.parent = parent;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

}

and

public class RedBlackNode<T> extends Node<T> {

    private Color color;

    public RedBlackNode(Node<T> parent, T data) {
        super(parent, data);
        this.color = Color.Black;
    }

    public RedBlackNode(Node<T> parent, T data, Color color) {
        super(parent, data);
        this.color = color;
    }

    public Color getColor() {
        return color;
    }

    public void setColor(Color color) {
        this.color = color;
    }

}

My question is .. is there any way in which I could write:

RedBlackNode<Whatever> x = y.getLeft();

where y is a RedBlackNode without having to specifically cast using:

RedBlackNode<Whatever> x = (RedBlackNode<Whatever>) y.getLeft();

and also, without having to override the getters/setters in the RedBlackNode class?

I mean, I just want to somehow make the RedBlackNode be "aware" that it's a RedBlackNode and know that all its children/parent are actually RedBlackNodes as well. I am not sure but maybe somehow add a new abstraction layer on top of the Node class somehow maybe?

Ty!

Later edit:

Thank you for all your prompt answers, this is what I have so far:

public abstract class AbstractNode<T, U extends AbstractNode<T, U>> {
    private AbstractNode<T, U> parent;
    private AbstractNode<T, U> left;
    private AbstractNode<T, U> right;
    private T data;

    public AbstractNode(AbstractNode<T, U> parent, T data) {
        this.parent = parent;
        this.data = data;
    }

    public AbstractNode<T, U> getParent() {
        return parent;
    }

    public void setParent(AbstractNode<T, U> parent) {
        this.parent = parent;
    }

    public AbstractNode<T, U> getLeft() {
        return left;
    }

    public void setLeft(AbstractNode<T, U> left) {
        this.left = left;
    }

    public AbstractNode<T, U> getRight() {
        return right;
    }

    public void setRight(AbstractNode<T, U> right) {
        this.right = right;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

}

public class RedBlackNode<T extends Element> extends AbstractNode<Element, RedBlackNode<Element>> {

    private Color color;

    public RedBlackNode(RedBlackNode<Element> parent, T data) {
        super(parent, data);
        this.color = Color.Black;
    }

    public RedBlackNode(RedBlackNode<Element> parent, T data, Color color) {
        super(parent, data);
        this.color = color;
    }

    public Color getColor() {
        return color;
    }

    public void setColor(Color color) {
        this.color = color;
    }

}


public class Node<T> extends AbstractNode<T, Node<T>> {

    public Node(AbstractNode<T, Node<T>> parent, T data) {
        super(parent, data);
    }

}

However, I need to create 2 types of trees. A simple Binary Search Tree which has as nodes only instances of class Node and, as expected, a Red Black Tree which has only instances of RedBlackNode as nodes.

I made an abstract class for these trees (with many more methods, this is the trimmed version) but I fear that I am missing something as I seem to have this Node<Element> as the generic type in the class definition.

public abstract class Tree<T extends AbstractNode<Element, Node<Element>>> {

    protected T root;

    public T getRoot() {
        return this.root;
    }

    public abstract T search(T n, int key);

    public abstract T insert(Element e, T cRoot);
}

What am I missing here? How to best model this?

Later edit 2:

I currently have:

public abstract class AbstractNode<E extends Element, U extends AbstractNode<E, U>> {
    private U parent;
    private U left;
    private U right;
    private E data;

    public AbstractNode(U parent, E data) {
        this.parent = parent;
        this.data = data;
    }

    public U getParent() {
        return parent;
    }

    public void setParent(U parent) {
        this.parent = parent;
    }

    public U getLeft() {
        return left;
    }

    public void setLeft(U left) {
        this.left = left;
    }

    public U getRight() {
        return right;
    }

    public void setRight(U right) {
        this.right = right;
    }

    public E getData() {
        return data;
    }

    public void setData(E data) {
        this.data = data;
    }

}

public class Node<E extends Element> extends AbstractNode<E, Node<E>> {

    public Node(Node<E> parent, E data) {
        super(parent, data);
    }

}

public class RedBlackNode<E extends Element> extends AbstractNode<E, RedBlackNode<E>> {

    private Color color;

    public RedBlackNode(RedBlackNode<E> parent, E data) {
        super(parent, data);
        this.color = Color.Black;
    }

    public RedBlackNode(RedBlackNode<E> parent, E data, Color color) {
        super(parent, data);
        this.color = color;
    }

    public Color getColor() {
        return color;
    }

    public void setColor(Color color) {
        this.color = color;
    }

}

The Tree class:

public abstract class Tree<E extends Element, T extends AbstractNode<E, T>> {

    protected T root;

    public T getRoot() {
        return this.root;
    }

    public abstract T search(T n, int key);
}

AND The BinarySearchTreeClass

public class BinarySearchTree<Element> extends Tree<Element, Node<Element>> {

    @Override
    public Node<Element> search(Node<Element> n, int key) {
        if (n == null || n.getData().getIntegerData() == key) {
            return n;
        }
        return key < n.getData().getIntegerData() ? search(  n.getLeft(), key) : search( n.getRight(), key);
    }

}

Why in the world am I getting Bound mismatch: The type Element is not a valid substitute for the bounded parameter <E extends Element> of the type Node<E>. It's E extends Element. Doesn't that mean it can be of type Element as well? Nevertheless, I tried using something like a separate class which extended Element but to no avail..

Also, I am getting a The type parameter Element is hiding the type Element and I have no idea why..

I created a GIST for this.

The simplest solution (yet boilerplate) is to override super class methods and change return type to `RedBlackNode`. — user3707125, Jun 09 '15 at 17:18
Yes, I know that, but is there any way to avoid overriding those methods? — Alexandr, Jun 09 '15 at 17:19
Perhaps if you extract the boilerplate code and add it as an interface with generics? So you implement NodeGetters for the Node and NodeGetters or a parent class. — MiltoxBeyond, Jun 09 '15 at 17:20
Yes, but they suck :( http://stackoverflow.com/questions/10968557/java-returning-subclass-in-superclass-method-signature — user3707125, Jun 09 '15 at 17:21
Your abstract class does not have the right generics. See SamYonnou's example: `AbstractNode>`. The `T` is the type of the data in each node. The `U` - I'd have called it `N` personally - is the type of the associated nodes (parent, left and right) which are of type `U extends AbstractNode` (which is to say "some subtype of `AbstractNode` where `T` is the data in it, and its related nodes (parent, left, right) are also of type `U`"). If that all sounds a bit recursive, that's because it is. — Paul, Jun 09 '15 at 18:04

SamYonnou · Accepted Answer · 2015-06-09T18:26:46.027

4

If you don't mind pulling Node out into an abstract class you can specify the type as part of the generic signature like so:

public abstract class AbstractNode<T, U extends AbstractNode<T, U>> {
    ...
    public U getLeft() {
        ...
    }
    ...
}

// inherited getLeft() will return Node<T>
public class Node<T> extends AbstractNode<T, Node<T>> { ... }

// inherited getLeft() will return RedBlackNode<T>
public class RedBlackNode<T> extends AbstractNode<T, RedBlackNode<T>> { ... }

Edit: for your trees you would either create a separate tree for each node type, or if you want to reuse base functionality you could do something like:

// base functionality goes here, T is the element type, U is the node type
public abstract class Tree<T, U extends AbstractNode<T, U>> { ... }

public class BinarySearchTree<T> extends Tree<T, Node<T>> { ... }

public class RedBlackTree<T> extends Tree<T, RedBlackNode<T>> { ... }

or if you just want to share the method signatures then make Tree an interface instead of an abstract class. Or better yet, have a Tree interface and an AbstractTree abstract class that implements shared functionality.

edited Jun 09 '15 at 18:26

answered Jun 09 '15 at 17:29

SamYonnou

2,068
1
19
23

That should work. We use this approach in a fluent form component library, allowing each component to be aware of, and to return, its own type for method chaining. – Paul Jun 09 '15 at 17:38
+1, however, I'd recommend that we use `This` as the conventional name for such type parameters; and lose the bound. see http://stackoverflow.com/questions/30382847/avoiding-generic-types-of-form-fooactualtype-extends-fooactualtype/30656295#30656295 – ZhongYu Jun 09 '15 at 17:40
Is it really conventional? I've never seen that use before. I wouldn't personally as `This` will look suspiciously like a class name. And it *is* conventional to use a single uppercase letter for generic type arguments, in most cases. I'd use `N` (for node). – Paul Jun 09 '15 at 17:43
@Paul - not conventional yet, but that's what I'm proposing :) – ZhongYu Jun 09 '15 at 17:44
What bound are you suggesting losing? I can't see anything that can be dropped that leaves this still working. – Paul Jun 09 '15 at 17:45
@Paul I think he means do `AbstractNode` instead of `AbstractNode>` – SamYonnou Jun 09 '15 at 17:48
That won't work because when you assign to a `RedBlackNode` variable the result of calling `getLeft()` (for example) the compiler won't know about the `ConcreteThing` part in the assignment. It will result in a warning at least. I don't remember if it is an outright compiler error. – Paul Jun 09 '15 at 17:53
Guys, thank you for your wonderful responses. Check out my latest edit of the problem. – Alexandr Jun 09 '15 at 17:56
@Paul - I mean `AbstractNode`. The bound of `This` is often not needed; as in this case. – ZhongYu Jun 09 '15 at 18:02
Re edits. Shouldn't `BinarySearchTree extends Tree>` be `BinarySearchTree extends Tree>`? – Paul Jun 09 '15 at 18:12
@Paul I think OP was saying that he would use the `Node` type for the BST implementation, although I'm not 100% sure – SamYonnou Jun 09 '15 at 18:13
@bayou.io Still don't see how the recursive bounds can be left out. (See my comment above mentioning `ConcreteThing`.) However, I haven't seen a complete set of your definitions using `AbstractNode` so I have to infer the rest. – Paul Jun 09 '15 at 18:15
@Paul - the bound doesn't exactly work - e.g. you can declare `RedBlackNode extends AbstractNode>`. – ZhongYu Jun 09 '15 at 18:19
Again, I added some new info on the latest edit. This is driving me crazy – Alexandr Jun 10 '15 at 05:55
1

@Alexandr if `Element` is a concrete type not a generic then you don't write `BinarySearchTree extends Tree>` but instead `BinarySearchTree extends Tree>` or if you meant to use a generic type then `BinarySearchTree extends Tree>` – SamYonnou Jun 10 '15 at 13:07

Automatic cast to subclass in getter/setter

1 Answers1