swift - Swift中的链表声明，手指类型可以透明地插入中间或开始

Question

我正在尝试在 Swift 中声明一个链表，其手指类型是对节点的引用，允许在该节点之外插入或删除，或者链接列表本身，在这种情况下插入或删除链表的顶部。

我想看看这是否可以统一到实现，而不是必须对所有事情进行特殊处理:毕竟 Swift 是面向对象的。

我以前有一个需要强制转换的版本，但我再次想看看是否可以在没有它们的情况下工作(例如，即使它们永远不会出错，它们仍然意味着每次都进行运行时检查)。

我目前有这段代码:

protocol ContainerNodeInterface: class {
    associatedtype ContainedItem;

    var contents: ContainedItem { get };
}

protocol ParentNodeInterface: class {
    associatedtype LinkedItem: ContainerNodeInterface;

    var next: LinkedItem? {get set};
}


class ProtoNode<Contents, NodeType: ParentNodeInterface>: ParentNodeInterface where NodeType.ContainedItem==Contents, NodeType.LinkedItem==NodeType { // not meant to be instantiated or directly referenced
    typealias LinkedItem = NodeType;
    var next: NodeType?;

    init() {
        next = nil;
    }

    final func insertThisAfterMe(_ node: NodeType) {
        node.next = next;
        next = .some(node);
    }

    final func removeNodeAfterMe() -> NodeType? {
        guard let nextNode = next else {
            return nil;
        }

        let result = nextNode;

        next = result.next;
        result.next = nil;
        return nextNode;
    }
}

class Node<Contents>: ProtoNode<Contents, Node<Contents>>, ContainerNodeInterface {
    typealias ContainedItem = Contents;
    typealias NextItem = Node<Contents>;
    var contents: Contents;

    init(withContents: Contents) {
        contents = withContents;
        super.init();
    }
}

typealias ParentNode<Contents> = ProtoNode<Contents, Node<Contents>>;

但是 Swift 编译器通过 Xcode 提示 Type 'Node<Contents>' does not conform to protocol 'ParentNodeInterface' .这没有意义!如果我添加明确符合 ParentNodeInterface至 Node ，然后我同时得到该错误和对同一协议(protocol)的冗余一致性之一。

这里缺少什么？

Xcode 版本 10.2 (10E125)，Swift 5

Answer 1

我通过将 ProtoNode 拆分为初始声明和扩展来解决它:

protocol ContainerNodeInterface: class {
    associatedtype ContainedItem;

    var contents: ContainedItem { get };
}

protocol ParentNodeInterface: class {
    associatedtype LinkedItem: ContainerNodeInterface;

    var next: LinkedItem? {get set};
}


class ProtoNode<Contents, NodeType: ContainerNodeInterface>: ParentNodeInterface where NodeType.ContainedItem==Contents { // not meant to be instantiated or directly referenced
    typealias LinkedItem = NodeType;
    var next: NodeType?;

    init() {
        next = nil;
    }
}

extension ProtoNode where NodeType: ParentNodeInterface, NodeType.LinkedItem==NodeType
{
    final func insertThisAfterMe(_ node: NodeType) {
        node.next = next;
        next = .some(node);
    }

    final func removeNodeAfterMe() -> NodeType? {
        guard let nextNode = next else {
            return nil;
        }

        let result = nextNode;

        next = result.next;
        result.next = nil;
        return nextNode;
    }
}

class Node<Contents>: ProtoNode<Contents, Node<Contents>>, ContainerNodeInterface {
    typealias ContainedItem = Contents;
    typealias NextItem = Node<Contents>;
    var contents: Contents;

    init(withContents: Contents) {
        contents = withContents;
        super.init();
    }
}

typealias ParentNode<Contents> = ProtoNode<Contents, Node<Contents>>;

我认为它可以帮助编译器打破依赖循环，在循环中它必须确定 Node 作为泛型参数是否符合协议(protocol)，然后才能确定声明是否有效并将声明的类型(即 Node)视为符合协议(protocol)到协议(protocol)，但我仍然觉得不得不做出这个看似毫无意义的扩展声明有点傻。

至少，编译器可以稍微有点帮助......