Объявление связанного списка в 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, то получу одновременно эту ошибку и одно из избыточного соответствия одному и тому же протоколу.

Чего здесь не хватает?

Версия Xcode 10.2 (10E125), Swift 5

Answer 1

Во-первых, я бы начал с простого типа узла связанного списка:

final class Node<Value> {
    let value: Value
    var next: Node<Value>?

    init(_ value: Value) {
        self.value = value
    }

    func insert(_ node: Node<Value>) {
        node.next = next
        next = node
    }

    func removeNext() -> Node<Value>? {
        guard let removedNode = next else { return nil }
        next = removedNode.next
        removedNode.next = nil
        return removedNode
    }
}

Затем вы можете добавить описываемое вами понятие: указатель на «либо узел ..., либо насам связанный список. "Когда вы видите «или» в описании, это подразумевает тип суммы, который в Swift представляет собой enum, либо указатель на начало списка (возможно, пустой), либо указатель на узел.Каждый из них имеет немного отличающееся поведение, которым вы управляете с помощью switch.

enum NodePointer<Value> {
    case head(Node<Value>?)
    case node(Node<Value>)

    mutating func insert(_ node: Node<Value>) {
        switch self {
        case .head(let n):
            self = .head(node)
            node.next = n
        case .node(let n):
            n.insert(node)
        }
    }

    mutating func removeNext() -> Node<Value>? {
        switch self {
        case .head(let n):
            self = .head(n?.next)
            return n
        case .node(let n):
            return n.removeNext()
        }
    }

    var pointee: Node<Value>? {
        switch self {
        case .head(let n): return n
        case .node(let n): return n
        }
    }
}

С этим у вас будет такой интерфейс:

var list = Node(1)
list.insert(Node(2))

var ptr = NodePointer.head(list)

ptr.insert(Node(1))
ptr.pointee?.next?.next?.value // 2

Обратите внимание, что вы столкнулись с конкретной проблемой (что компилятор не может определить соответствие) Я считаю, что это ошибка компилятора, хотя я также считаю, что она исправлена ​​на master в настоящее время.Я не проверял это все же.Но я не верю, что основанный на протоколе подход является правильным для этой проблемы.

Answer 2

Я решил это, разделив 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 как универсальный параметр протоколу, прежде чем он сможет определить, является ли объявление действительным, и считает объявленный тип, то есть Node, соответствующим к протоколу, но все же мне немного глупо делать это, казалось бы, бессмысленное объявление о расширении.

По крайней мере, компилятор может быть немного более полезным ...