Можно ли спроектировать безопасный для типов связанный список, предотвращающий getNext () в хвостовом узле? - PullRequest
Новая
       42

Можно ли спроектировать безопасный для типов связанный список, предотвращающий getNext () в хвостовом узле?

1 голос
/ 07 февраля 2012

Мне интересно, возможно ли спроектировать, например, типобезопасную односвязную структуру списка так, что невозможно запросить следующий узел у хвостового узла.

В то же время клиент должен был бы иметь возможность проходить (рекурсивно или иным образом) по списку через node.getChild(), но во время компиляции он должен быть предотвращен (по крайней мере, с помощью явной проверки типа, написанной человеком)проходя мимо хвоста

Мне интересно:

  1. Есть ли название для этого типа проблемы?
  2. Есть ли объектно-ориентированный или другой подход, который поможет избежать явногопроверка типа во время выполнения?

Язык реализации не важен, но вот пример того, о чем я думаю.

Редактировать после ответа Joop: 

public class TestHiddenInterfaces {
   interface Node { HasNoChildNode getTail(); }
   interface HasNoChildNode extends Node {};
   interface HasChildNode extends Node { Node getChild(); }
   class HasNoChild implements HasNoChildNode {
      @Override public HasNoChildNode getTail() { return this; }
   }
   class HasChild implements HasChildNode {
      final Node child;
      @Override
      public Node getChild() { return child; }
      HasChild(Node child) {
         this.child = child;
      }
      @Override public HasNoChildNode getTail() {
         if(child instanceof HasChild) return ((HasChild) child).getTail();
         else if(child instanceof HasNoChild) return (HasNoChildNode) child;
         else throw new RuntimeException("Unknown type");
      }
   }

   @Test
   public void test() {
      HasNoChild tail = new HasNoChild();
      assertEquals(tail, tail.getTail());
      HasChild level1 = new HasChild(tail);
      assertEquals(tail, level1.getTail());
      HasChild level2 = new HasChild(level1);
      assertEquals(tail, level2.getTail());
   }
}

Ответы [ 2 ]

1 голос
/ 07 февраля 2012

В Scala используются «типы падежей» для такой типизации.В диаграммах Java или UML часто можно увидеть различие между ветвью и листом.И это может уменьшить половину памяти неиспользуемых листовых потомков.

Типы сосуществуют как значения перечисления.

Так что можно использовать следующее: 

/**
 * Base of all nodes. For the remaining types I have dropped the type parameter T.
 */
public interface Node<T> {
    void setValue(T value);
    T getValue();
}

public interface HasParent extends Node {
    void setParent(HasChildren node);
    HasChildren getParent();
}

public interface HasChildren extends Node {
    void setChildren(HasParent... children);
    HasPOarent[] getChildren();
}

public final class RootBranch implements HasChildren {
    ...
}

public final class SubBranch implements HasChildren, HasParent {
    ...
}

public final class Leaf implements HasParent {
    ...
}

public final class RootLeaf implements Node {
    ...
}

Использование будетлибо использовать перегрузку, либо различать случаи: 

void f(Node node) {
    if (node instanceof HasParent) {
         HasParent nodeHavingParent = (HasParent) node;
         ...
    }
}

Лично я думаю, что это перестаралось в Java, но в Scala, например, где объявление типа является конструктором, это имело бы смысл: SubBranche(parent, child1, child2).

0 голосов
/ 07 февраля 2012

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

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

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

На следующем уровне реализация getParent должна возвращать тип, который реализует getParent, который возвращает корневой узел, который не имеет getParent.

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

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

...