Swift 中链接列表的自定义索引
Custom Index for Linked List in Swift
链接列表的自定义索引类型
Swift5.0，Xcode10.3
我最近在 Swift 中实现了一个双向链表类型。当我着手制作它时，我的目标是为用户提供与使用 Array 相同的大部分易用性，但具有与双向链表相关的算法复杂性。考虑到这个目标，我决定实现这一目标的主要方法之一是使 Node 类型成为实现细节；对用户来说是眼不见心不烦的。我还决定 LinkedList 必须作为 struct 实现，以便提供适当的支持 immutability/mutability。
确定 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:) 都可以依赖 node 属性 的 next 和 previous 属性来提供它们各自所需的索引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 { "\([=14=])" }.joined(separator: ", ") + "]"
}
}
注意： if/when我确实更新了我的代码，可以找到最新版本here。
我的问题
我目前遇到的问题是 Index 个实例。当向方法提供索引时，就像当前的情况一样，该方法无法知道和检查 index/node 是否属于那个特定的 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:) 如何处理它们是 optimal/proper 的方式。我正在寻找有关如何解决 LinkedList.Index 带来的所有这些问题并正确实施它的意见。感谢任何和所有输入！
先解决第二个问题：
Furthermore, indices' offset invalidate after mutation to their node's parent list, thus causing absurd situations ...
这是对所有系列的预期。来自 Collections:
Saved indices may become invalid as a result of mutating operations.
使用无效索引是未定义的行为，任何事情都可能发生：意外结果、致命错误……这是 Swift 个字符串的简单示例：
var s = "abcd"
let i = s.firstIndex(of: "")!
s.remove(at: s.startIndex) // invalidates `i`
s.remove(at: i)
print(s) // 0cd
现在第一个（主要？）问题：
... the method has no way of knowing and checking whether or not that index/node belongs to that specific LinkedList instance.
再次引用Collections：
You can pass only valid indices to collection operations. You can find a complete set of a collection’s valid indices by starting with the collection’s startIndex property and finding every successor up to, and including, the endIndex property. All other values of the Index type, such as the startIndex property of a different collection, are invalid indices for this collection.
你的情况
mutableList[immutableIndex] = 0
immutableIndex 不是 mutableList 的有效索引，因此这又是未定义的行为。您图书馆的用户不能指望这会做任何明智的事情。
防止这种滥用的一种可能方法是在 LinkedList.Index 中存储一个指向链表头节点的（弱）指针，并在访问器方法（下标）中验证所有者。
链接列表的自定义索引类型
Swift5.0，Xcode10.3
我最近在 Swift 中实现了一个双向链表类型。当我着手制作它时，我的目标是为用户提供与使用 Array 相同的大部分易用性，但具有与双向链表相关的算法复杂性。考虑到这个目标，我决定实现这一目标的主要方法之一是使 Node 类型成为实现细节；对用户来说是眼不见心不烦的。我还决定 LinkedList 必须作为 struct 实现，以便提供适当的支持 immutability/mutability。
确定 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:) 都可以依赖 node 属性 的 next 和 previous 属性来提供它们各自所需的索引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 { "\([=14=])" }.joined(separator: ", ") + "]"
}
}
注意： if/when我确实更新了我的代码，可以找到最新版本here。
我的问题
我目前遇到的问题是 Index 个实例。当向方法提供索引时，就像当前的情况一样，该方法无法知道和检查 index/node 是否属于那个特定的 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:) 如何处理它们是 optimal/proper 的方式。我正在寻找有关如何解决 LinkedList.Index 带来的所有这些问题并正确实施它的意见。感谢任何和所有输入！
先解决第二个问题：
Furthermore, indices' offset invalidate after mutation to their node's parent list, thus causing absurd situations ...
这是对所有系列的预期。来自 Collections:
Saved indices may become invalid as a result of mutating operations.
使用无效索引是未定义的行为，任何事情都可能发生：意外结果、致命错误……这是 Swift 个字符串的简单示例：
var s = "abcd"
let i = s.firstIndex(of: "")!
s.remove(at: s.startIndex) // invalidates `i`
s.remove(at: i)
print(s) // 0cd
现在第一个（主要？）问题：
... the method has no way of knowing and checking whether or not that index/node belongs to that specific LinkedList instance.
再次引用Collections：
You can pass only valid indices to collection operations. You can find a complete set of a collection’s valid indices by starting with the collection’s startIndex property and finding every successor up to, and including, the endIndex property. All other values of the Index type, such as the startIndex property of a different collection, are invalid indices for this collection.
你的情况
mutableList[immutableIndex] = 0
immutableIndex 不是 mutableList 的有效索引，因此这又是未定义的行为。您图书馆的用户不能指望这会做任何明智的事情。
防止这种滥用的一种可能方法是在 LinkedList.Index 中存储一个指向链表头节点的（弱）指针，并在访问器方法（下标）中验证所有者。