Как реализовать абстрактный класс универсального типа?

Question

Я работаю над проектом Java, касающимся бинарных деревьев поиска.Нас попросили имплантировать и AVL-дерево, но также посоветовали сохранить хорошую абстракцию для реализации других типов деревьев (таких как красно-чёрное дерево).Я решил использовать класс abstract BsNode (Bs = двоичный поиск) и класс abstract BsTree и реализовать их с AvlTree и AvlNode следующим образом:

public abstract class BsNode<T extends BsNode> {
    T parent
    T left
    T right
    ...
}

public abstract class BsTree<T extends BsNode> {
    T root
    ...
}

public class AvlNode extends BsNode<AvlNode> {
    int balance;
    ...
}

public class AvlTree<AvlNode> {
    private void rotate(int direction);
    ...
}

Это приводит к двумпроблемы: во-первых, мне не кажется, что BsNode должен получить тип наследника.Во-вторых, это открывает возможность для такой вещи:

public class RedBlackNode extends BsNode<AvlNode> {
    ...
}

или

RedBlackNode myRoot = new RedBlackNode<AvlNode>();

, и это не должно быть разрешено.Как можно принудительно использовать наследующий класс в BsNode (то есть сохранить указатели parent и дочерние элементы для типа, реализующего класс) вместо передачи универсальной переменной T?

Answer 1

Как уже упоминалось в комментариях, это невозможно реализовать во время компиляции.Есть хитрость, чтобы заставить его терпеть неудачу во время выполнения.

Что вы делаете, это запрашиваете реализующие классы передать свой собственный класс параметра типа абстрактному конструктору с аргументом, типизированным классом параметра типа.

Конструктор родительского класса проверяет, чтодействительно, этот класс является тем же классом, что и класс, который соответствует параметру типа.

abstract class BsNode<T extends BsNode<T>> {

   protected BsNode(final Class<T> clazz) {
       if (!this.getClass().equals(clazz)) 
          throw new IllegalArgumentException("invalid mixture of node types");
   } 
}

class AvlNode extends BsNode<AvlNode> {

   public AvlNode() {
        super(AvlNode.class); // works!!!
   }

}

class RBNode extends BsNode<AvlNode> {

   public RBNode() {
       // two possible super calls:
       super(AvlNode.class); // fails at run-time.
       // or
       super(RBNode.class); // fail at compilation-time.
   }
}

Если у вас есть формальный процесс сборки как часть вашего программного обеспечения, которое содержит тестирование, возможно, имеет смысл оставитьограниченная проверка производственного кода (экономия времени вычислений) и включение его в ваши юнит-тесты.