Пользовательский тип индекса для связанного списка

Свифт 5.0, Xcode 10.3

Недавно я реализовал тип двусвязного списка в Swift. Когда я собирался сделать это, моей целью было предоставить пользователям ту же простоту использования, что и при использовании Array, но с алгоритмическими сложностями, связанными с двусвязными списками. Имея в виду эту цель, я решил, что одним из основных способов достижения этого будет превращение типа Node в деталь реализации; вне поля зрения и вне поля зрения пользователя. Я также решил, что LinkedList должен быть реализован как struct, чтобы обеспечить правильную неизменность/изменчивость.

Однако определить семантику для типа LinkedList и его закрытого типа Node было довольно сложно. В основном это произошло из-за того, что LinkedList был struct, а Node был class. Из-за этого всякий раз, когда делалась копия значения LinkedList, изменение скопированного связанного списка также приводило к изменению исходной переменной. Например, при описанных обстоятельствах это произойдет:

let list1 = LinkedList([1, 2, 3])
var list2 = list1
list2.append(4) // Mutates both list1 and list2
print(list1)
// Prints "[1, 2, 3, 4]"

По понятным причинам это было непреднамеренно и требовало от меня осмысления поведения и семантики, связанных с созданием копии LinkedList и ее мутацией. Чтобы бороться с этим, в единственных двух мутациях, определенных для LinkedList, которые были доступны для пользователя, я проверил, известно ли, что головной узел списка имеет уникальную ссылку или нет. Если бы это было так, мутация шла бы как обычно. Но если бы это было не так, функция создала бы копию всех узлов в списке перед их изменением. Это предотвратит влияние операций изменения экземпляра LinkedList на любой другой экземпляр. Эта проверка перед мутацией эффективно реализует семантику копирования при записи для узлов LinkedList. При этом предыдущий пример работает так, как ожидалось:

let list1 = LinkedList([1, 2, 3])
var list2 = list1
list2.append(4) // Nodes are copied 
print(list1)
// Prints "[1, 2, 3]"
print(list2)
// Prints "[1, 2, 3, 4]"

Это, казалось, довольно хорошо решило проблему общих ссылок на узлы и их мутацию в них. К сожалению, к моему огорчению, я тогда понял, что я не связал все свои концы с концами. Вот где я сейчас застрял. На данный момент мой пользовательский тип индекса LinkedList.Index определяется следующим образом:

extension LinkedList: Collection {

    //... 

    public struct Index: Comparable {
        fileprivate weak var node: Node?
        fileprivate var offset: Int

        fileprivate init(node: Node?, offset: Int) {
            self.node = node
            self.offset = offset
        }

        public static func ==(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset == rhs.offset
        }

        public static func <(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset < rhs.offset
        }
    }
}

Позвольте мне разобрать некоторые решения, которые я принял при построении этого... Во-первых, свойство offset было добавлено для сравнения с другими индексами и для обеспечения возможности проверки того, находится ли индекс в пределах списка. Во-вторых, свойство node было необходимо для придания каждому Index реального значения и полезности. Это означало, что и index(after:), и index(before:) могли полагаться на свойства next и previous свойства node, чтобы предоставить соответствующие желаемые индексы за время O(1). Для меня это само по себе кажется требованием для типа индекса реализации связанного списка. В настоящее время я не думаю, что есть какой-либо способ обойти это требование связывания каждого индекса с соответствующим узлом. При тестировании я также столкнулся с ошибкой, из-за которой узел списка копировался слишком часто, а также не освобождался ARC. Я понял, что это произошло из-за того, что Index содержит сильную ссылку на узлы. Чтобы бороться с этим, я сделал node слабой ссылкой.

Прежде чем я объясню проблему, с которой я столкнулся, вот мой текущий код для LinkedList:

public struct LinkedList<Element> {

    private var headNode: Node?
    private var tailNode: Node?
    public private(set) var count: Int = 0

    public init() { }

}

//MARK: - LinkedList Node
extension LinkedList {

    fileprivate class Node {
        public var value: Element
        public var next: Node?
        public weak var previous: Node?

        public init(value: Element) {
            self.value = value
        }
    }

}

//MARK: - Initializers
public extension LinkedList {

    private init(_ nodeChain: NodeChain?) {
        guard let chain = nodeChain else {
            return
        }
        headNode = chain.head
        tailNode = chain.tail
        count = chain.count
    }

    init<S>(_ sequence: S) where S: Sequence, S.Element == Element {
        if let linkedList = sequence as? LinkedList<Element> {
            self = linkedList
        } else {
            self = LinkedList(NodeChain(of: sequence))
        }
    }

}

//MARK: NodeChain
extension LinkedList {
    private struct NodeChain {
        let head: Node!
        let tail: Node!
        private(set) var count: Int

        // Creates a chain of nodes from a sequence. Returns `nil` if the sequence is empty.
        init?<S>(of sequence: S) where S: Sequence, S.Element == Element {
            var iterator = sequence.makeIterator()

            guard let firstValue = iterator.next() else {
                return nil
            }

            var currentNode = Node(value: firstValue)
            head = currentNode
            count = 1

            while let nextElement = iterator.next() {
                let nextNode = Node(value: nextElement)
                currentNode.next = nextNode
                nextNode.previous = currentNode
                currentNode = nextNode
                count += 1
            }
            tail = currentNode
        }

    }
}

//MARK: - Copy Nodes
extension LinkedList {

    private mutating func copyNodes(settingNodeAt index: Index, to value: Element) {

        var currentIndex = startIndex
        var currentNode = Node(value: currentIndex == index ? value : currentIndex.node!.value)
        let newHeadNode = currentNode
        currentIndex = self.index(after: currentIndex)

        while currentIndex < endIndex {
            let nextNode = Node(value: currentIndex == index ? value : currentIndex.node!.value)
            currentNode.next = nextNode
            nextNode.previous = currentNode
            currentNode = nextNode
            currentIndex = self.index(after: currentIndex)
        }
        headNode = newHeadNode
        tailNode = currentNode
    }

    @discardableResult
    private mutating func copyNodes(removing range: Range<Index>) -> Range<Index> {

        var currentIndex = startIndex

        while range.contains(currentIndex) {
            currentIndex = index(after: currentIndex)
        }

        guard let headValue = currentIndex.node?.value else {
            self = LinkedList()
            return endIndex..<endIndex
        }

        var currentNode = Node(value: headValue)
        let newHeadNode = currentNode
        var newCount = 1

        var removedRange: Range<Index> = Index(node: currentNode, offset: 0)..<Index(node: currentNode, offset: 0)
        currentIndex = index(after: currentIndex)

        while currentIndex < endIndex {
            guard !range.contains(currentIndex) else {
                currentIndex = index(after: currentIndex)
                continue
            }

            let nextNode = Node(value: currentIndex.node!.value)
            if currentIndex == range.upperBound {
                removedRange = Index(node: nextNode, offset: newCount)..<Index(node: nextNode, offset: newCount)
            }
            currentNode.next = nextNode
            nextNode.previous = currentNode
            currentNode = nextNode
            newCount += 1
            currentIndex = index(after: currentIndex)

        }
        if currentIndex == range.upperBound {
            removedRange = Index(node: nil, offset: newCount)..<Index(node: nil, offset: newCount)
        }
        headNode = newHeadNode
        tailNode = currentNode
        count = newCount
        return removedRange
    }

}


//MARK: - Computed Properties
public extension LinkedList {
    var head: Element? {
        return headNode?.value
    }

    var tail: Element? {
        return tailNode?.value
    }
}

//MARK: - Sequence Conformance
extension LinkedList: Sequence {

    public typealias Element = Element

    public __consuming func makeIterator() -> Iterator {
        return Iterator(node: headNode)
    }

    public struct Iterator: IteratorProtocol {

        private var currentNode: Node?

        fileprivate init(node: Node?) {
            currentNode = node
        }

        public mutating func next() -> Element? {
            guard let node = currentNode else {
                return nil
            }
            currentNode = node.next
            return node.value
        }

    }
}

//MARK: - Collection Conformance
extension LinkedList: Collection {

    public var startIndex: Index {
        return Index(node: headNode, offset: 0)
    }

    public var endIndex: Index {
        return Index(node: nil, offset: count)
    }

    public var first: Element? {
        return head
    }

    public var isEmpty: Bool {
        return count == 0
    }

    public func index(after i: Index) -> Index {
        precondition(i.offset != endIndex.offset, "LinkedList index is out of bounds")
        return Index(node: i.node?.next, offset: i.offset + 1)
    }

    public struct Index: Comparable {
        fileprivate weak var node: Node?
        fileprivate var offset: Int

        fileprivate init(node: Node?, offset: Int) {
            self.node = node
            self.offset = offset
        }

        public static func ==(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset == rhs.offset
        }

        public static func <(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset < rhs.offset
        }
    }

}


//MARK: - MutableCollection Conformance
extension LinkedList: MutableCollection {

    public subscript(position: Index) -> Element {
        get {
            precondition(position.offset != endIndex.offset, "Index out of range")
            guard let node = position.node else {
                preconditionFailure("LinkedList index is invalid")
            }
            return node.value
        }
        set {
            precondition(position.offset != endIndex.offset, "Index out of range")

            // Copy-on-write semantics for nodes
            if !isKnownUniquelyReferenced(&headNode) {
                copyNodes(settingNodeAt: position, to: newValue)
            } else {
                position.node?.value = newValue
            }
        }
    }
}



//MARK: LinkedList Specific Operations
public extension LinkedList {

    mutating func prepend(_ newElement: Element) {
        replaceSubrange(startIndex..<startIndex, with: CollectionOfOne(newElement))
    }

    mutating func prepend<S>(contentsOf newElements: __owned S) where S: Sequence, S.Element == Element {
        replaceSubrange(startIndex..<startIndex, with: newElements)
    }

    @discardableResult
    mutating func popFirst() -> Element? {
        if isEmpty {
            return nil
        }
        return removeFirst()
    }

    @discardableResult
    mutating func popLast() -> Element? {
        guard isEmpty else {
            return nil
        }
        return removeLast()
    }
}

//MARK: - BidirectionalCollection Conformance
extension LinkedList: BidirectionalCollection {
    public var last: Element? {
        return tail
    }

    public func index(before i: Index) -> Index {
        precondition(i.offset != startIndex.offset, "LinkedList index is out of bounds")
        if i.offset == count {
            return Index(node: tailNode, offset: i.offset - 1)
        }
        return Index(node: i.node?.previous, offset: i.offset - 1)
    }

}

//MARK: - RangeReplaceableCollection Conformance
extension LinkedList: RangeReplaceableCollection {

    public mutating func append<S>(contentsOf newElements: __owned S) where S: Sequence, Element == S.Element {
        replaceSubrange(endIndex..<endIndex, with: newElements)
    }

    public mutating func replaceSubrange<S, R>(_ subrange: R, with newElements: __owned S) where S: Sequence, R: RangeExpression, Element == S.Element, Index == R.Bound {

        var range = subrange.relative(to: indices)

        precondition(range.lowerBound >= startIndex && range.upperBound <= endIndex, "Subrange bounds are out of range")

        // If range covers all elements and the new elements are a LinkedList then set references to it
        if range.lowerBound == startIndex, range.upperBound == endIndex, let linkedList = newElements as? LinkedList {
            self = linkedList
            return
        }

        var newElementsCount = 0

        // There are no new elements, so range indicates deletion
        guard let nodeChain = NodeChain(of: newElements) else {

            // If there is nothing in the removal range
            // This also covers the case that the linked list is empty because this is the only possible range
            guard range.lowerBound != range.upperBound else {
                return
            }

            // Deletion range spans all elements
            if range.lowerBound == startIndex && range.upperBound == endIndex {
                headNode = nil
                tailNode = nil
                count = 0
                return
            }

            // Copy-on-write semantics for nodes and remove elements in range
            guard isKnownUniquelyReferenced(&headNode) else {
                copyNodes(removing: range)
                return
            }

            // Update count after mutation to preserve startIndex and endIndex validity
            defer {
                count = count - (range.upperBound.offset - range.lowerBound.offset)
            }

            // Move head up if deletion starts at start index
            if range.lowerBound == startIndex {
                // Can force unwrap node since the upperBound is not the end index
                headNode = range.upperBound.node!
                headNode!.previous = nil

                // Move tail back if deletion ends at end index
            } else if range.upperBound == endIndex {
                // Can force unwrap since lowerBound index must have an associated element
                tailNode = range.lowerBound.node!.previous
                tailNode!.next = nil

                // Deletion range is in the middle of the linked list
            } else {
                // Can force unwrap all bound nodes since they both must have elements
                range.upperBound.node!.previous = range.lowerBound.node!.previous
                range.lowerBound.node!.previous!.next = range.upperBound.node!
            }

            return
        }

        // Obtain the count of the new elements from the node chain composed from them
        newElementsCount = nodeChain.count

        // Replace entire content of list with new elements
        if range.lowerBound == startIndex && range.upperBound == endIndex {
            headNode = nodeChain.head
            tailNode = nodeChain.tail
            count = nodeChain.count
            return
        }

        // Copy-on-write semantics for nodes before mutation
        if !isKnownUniquelyReferenced(&headNode) {
            range = copyNodes(removing: range)
        }

        // Update count after mutation to preserve startIndex and endIndex validity
        defer {
            count += nodeChain.count - (range.upperBound.offset - range.lowerBound.offset)
        }

        // Prepending new elements
        guard range.upperBound != startIndex else {
            headNode?.previous = nodeChain.tail
            nodeChain.tail.next = headNode
            headNode = nodeChain.head
            return
        }

        // Appending new elements
        guard range.lowerBound != endIndex else {
            tailNode?.next = nodeChain.head
            nodeChain.head.previous = tailNode
            tailNode = nodeChain.tail
            return
        }

        if range.lowerBound == startIndex {
            headNode = nodeChain.head
        }
        if range.upperBound == endIndex {
            tailNode = nodeChain.tail
        }

        range.lowerBound.node!.previous!.next = nodeChain.head
        range.upperBound.node!.previous = nodeChain.tail
    }

}

//MARK: - ExpressibleByArrayLiteral Conformance
extension LinkedList: ExpressibleByArrayLiteral {
    public typealias ArrayLiteralElement = Element

    public init(arrayLiteral elements: ArrayLiteralElement...) {
        self.init(elements)
    }
}

//MARK: - CustomStringConvertible Conformance
extension LinkedList: CustomStringConvertible {
    public var description: String {
        return "[" + lazy.map { "\($0)" }.joined(separator: ", ") + "]"
    }
}

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

Моя проблема

Текущая проблема, с которой я сталкиваюсь, связана с Index экземплярами. Когда индекс предоставляется методу, как это имеет место в настоящее время, у метода нет возможности узнать и проверить, принадлежит ли этот индекс/узел этому конкретному экземпляру LinkedList. Это допускает такие ошибки:

let immutableList: LinkedList = [1, 2, 3, 4]
var mutableList: LinkedList = [5, 6, 7, 8]

let immutableIndex = immutableList.index(after: immutableList.startIndex)

mutableList[immutableIndex] = 0

print("Immutable List:", immutableList)
print("Mutable List:", mutableList)

// Prints:
//   Immutable List: [1, 0, 3, 4]
//   Mutable List: [5, 6, 7, 8]

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

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

var list: LinkedList = [1, 2, 3, 4]
let idx1 = list.index(list.startIndex, offsetBy: 2) // Index to node with value of 3 and offset of 2

list.remove(at: list.index(before: idx1))
print(list)
// Prints: "[1, 3, 4]"

let idx2 = list.index(before: list.endIndex) // Index to node with value of 4 and offset of 2
print(idx1 == idx2) 
// Prints: "true"

print(Array(list[idx1...idx2]))
// Prints: "[3]"

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

При первоначальном создании типа Index мне было трудно найти примеры, похожие на мои, в Интернете, и в результате я не совсем уверен, являются ли такие вещи, как startIndex и endIndex, и то, как index(before:) и index(after:) обрабатывают их, оптимальным/правильным способом. Я ищу информацию о том, как я могу исправить все эти проблемы, вызванные LinkedList.Index, и правильно реализовать его. Любой вклад приветствуется!