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 Collections such as linked lists or search trees. If anyone has one that can satisfy Collection's guarantees, I’d love to see it!
Hmm,… for a linked list, each node (which would be a class) would have an Int (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’s Index would be those key IDs. It’s up to the list to make sure all IDs are strictly increasing whenever a RangeReplaceableCollection 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.
