Continuing the discussion from [Draft] Adding Safe indexing to Array:
Isn’t
Collection.Index
:Comparable
?Huh, it is. I didn’t realize this, since it’s not that prominent in the documentation. This makes it a lot harder (if not impossible!) to write custom Swift
Collection
s such as linked lists or search trees. If anyone has one that can satisfyCollection
's guarantees, I’d love to see it!Hmm,… for a linked list, each node (which would be a
class
) would have anInt
(or similar) ID, and the main body of the list would have an internal[Int: Node]
property to index all of its nodes. The list’sIndex
would be those key IDs. It’s up to the list to make sure all IDs are strictly increasing whenever aRangeReplaceableCollection
or a custom equivalent event occurs, which may involve recalculating all indexes.
I tried out making a linked list that conforms to Collection
:
/// A singly-linked list.
public class SinglyLinkedList<T>: RangeReplaceableCollection, MutableCollection {
/// A node for a singly-linked list.
class Node {
/// The node's data. May be absent (like for sentinel nodes).
var value: T?
/// The link to the next node, or `nil` when none.
var next: Node?
/// A link to the owning list.
weak var list: SinglyLinkedList?
/// Creates a disconnected node, possibly with data.
init(possibleValue: T? = nil) {
value = possibleValue
next = nil
list = nil
print("Node created at:", UnsafeRawPointer(Unmanaged.passUnretained(self).toOpaque()))
}
/// Creates a disconnected node with the given data.
convenience init(value: T) {
self.init(possibleValue: value)
}
deinit {
print("Bye! From:", UnsafeRawPointer(Unmanaged.passUnretained(self).toOpaque()))
}
}
/// The one-past-the-end node, and points to the first node when the list is not empty.
var sentinel: Node
/// The end node. Points to `sentinel` when the list is empty.
var tail: Node
deinit {
print("Running SinglyLinkedList.deinit")
tail.next = nil
var node = sentinel
while let next = node.next {
node.next = nil
node = next
}
}
// MARK: Sequence
public var underestimatedCount: Int { return sentinel.next! === sentinel ? 0 : 1 }
// MARK: (Mutable)Collection
// The index type. Hashable to be usable in Key-Paths (I think).
public struct Index: Comparable, Hashable {
public static func <(lhs: Index, rhs: Index) -> Bool {
return lhs.id < rhs.id
}
public var hashValue: Int { return id.hashValue }
public static func ==(lhs: Index, rhs: Index) -> Bool {
return lhs.node === rhs.node
}
/// The targeted node.
let node: Node
/// A pusedo-ID. Should be the offset from `startIndex`, except it's always `max` for `endIndex`.
let id: UInt
}
public subscript(position: Index) -> T {
get { return position.node.value! }
set { position.node.value! = newValue } // The "!" forces a NIL check before write.
}
public var endIndex: Index { return Index(node: sentinel, id: UInt.max) }
public var startIndex: Index {
guard let head = sentinel.next, head !== sentinel else { return endIndex }
return Index(node: head, id: 0)
}
public func index(after i: Index) -> Index {
let nextNode = i.node.next!
guard nextNode !== sentinel else { return endIndex }
return Index(node: nextNode, id: i.id + 1)
}
// MARK: RangeReplaceableCollection
public required init() {
print("Running SinglyLinkedList.init()")
sentinel = Node()
sentinel.next = sentinel
tail = sentinel
sentinel.list = self
}
public func replaceSubrange<C: Collection>(_ subrange: Range<Index>, with newElements: C) where C.Element == Element {
// Sanity checks.
precondition(subrange.lowerBound.node.list! === self)
precondition(subrange.upperBound.node.list! === self)
precondition(subrange.lowerBound.id <= subrange.upperBound.id)
// Create nodes for the new elements.
let newNodes = newElements.map { Node(value: $0) }
zip(newNodes.dropLast(), newNodes.dropFirst()).forEach { arg in arg.0.next = arg.1 }
newNodes.forEach { $0.list = self }
// Point to the parts of the current list that are staying.
var lastPrefixNode = sentinel
if subrange.lowerBound < endIndex {
for _ in 0..<subrange.lowerBound.id {
lastPrefixNode = lastPrefixNode.next!
}
} else {
lastPrefixNode = tail
}
var firstNodeToKill = lastPrefixNode.next!
let firstSuffixNode = subrange.upperBound.node
assert(firstNodeToKill === subrange.lowerBound.node)
// Connect the nodes
switch (newNodes.isEmpty, subrange.lowerBound == endIndex, subrange.upperBound == endIndex) {
case (true, true, _):
// No change.
break
case (true, false, true):
// Truncation.
lastPrefixNode.next = sentinel
tail = lastPrefixNode
case (true, false, false):
// Interior removal.
lastPrefixNode.next = firstSuffixNode
case (false, true, _):
// Appending.
newNodes.last!.next = sentinel
tail.next = newNodes.first!
tail = newNodes.last!
case (false, false, true):
// Tail-end replacement.
newNodes.last!.next = sentinel
lastPrefixNode.next = newNodes.first!
tail = newNodes.last!
case (false, false, false):
// Interior replacement or insertion.
newNodes.last!.next = firstSuffixNode
lastPrefixNode.next = newNodes.first!
}
// Purge any removed nodes.
while firstNodeToKill !== firstSuffixNode {
let next = firstNodeToKill.next!
firstNodeToKill.next = nil
firstNodeToKill = next
}
}
// MARK: Custom Linked-List Stuff
var aDescription: String {
return String(describing: Array(self))
}
}
I did use custom numbers for indexes, but not in the same way as my original guess.
It seems to be working so far. I originally had a description
property for printing. But it hung the playground. You can see that I added a custom property; and sure enough, it works. Then I realized that official descriptions are what are called on the right sidebar for object states. Is there some sort of computation limit a type can have for description
before locking up the playground? I've been using Xcode 9.2 (with Swift 4.0) here.