I'm looking at the Linked List implementation from here, and it shows how the class conforms to the Collection protocol:
extension LinkedList: Collection {
public typealias Index = LinkedListIndex<T>
public var startIndex: Index {
get {
return LinkedListIndex<T>(node: head, tag: 0)
}
}
public var endIndex: Index {
get {
if let h = self.head {
return LinkedListIndex<T>(node: h, tag: count)
} else {
return LinkedListIndex<T>(node: nil, tag: startIndex.tag)
}
}
}
public subscript(position: Index) -> T {
get {
return position.node!.value
}
}
public func index(after idx: Index) -> Index {
return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag 1)
}
}
In order to conform to the Collection
protocol, the code provided three things: startIndex
/endIndex
, read-only subscript to get an element, and index(after:)
.
And order to make this possible, the code also provided LinkedListIndex which is a wrapper object of the linked list in question to make it conform to Comparable
:
public struct LinkedListIndex<T>: Comparable {
fileprivate let node: LinkedList<T>.LinkedListNode<T>?
fileprivate let tag: Int
public static func==<T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
return (lhs.tag == rhs.tag)
}
public static func< <T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
return (lhs.tag < rhs.tag)
}
}
I have two questions:
- Why do the elements have to conform to
Comparable
? Unlike firstIndex(of:), which requires the elements to beEquatable
, I can't seem to find anything on Apple documentation about needing to conform toComparable
, or evenEquatable
, for things likestartIndex
. - How do these tags refer to a specific node? I'm not quite understanding the association between this arbitrary property
tag
and index.
Testing
final class LinkListTest: XCTestCase {
func test_linkedList() {
let linkedList = LinkedList<Int>()
for i in stride(from: 0, to: 100, by: 10) {
linkedList.append(i)
}
let startIndex = linkedList.startIndex // startIndex has a tag of 0 because that's how it was instantiated
let expectedStartIndex = LinkedListIndex<Int>(node: linkedList.head, tag: 0)
XCTAssertEqual(startIndex, expectedStartIndex)
let endIndex = linkedList.endIndex // endIndex also has a tag of the count because that's how it was instantiated
let expectedEndIndex = LinkedListIndex<Int>(node: linkedList.last, tag: 10)
XCTAssertEqual(endIndex, expectedEndIndex)
let node = LinkedList.Node(value: 50)
let testIndex = linkedList.index(after: LinkedListIndex<Int>(node: node, tag: 50))
print("testIndex", testIndex) // LinkedListIndex<Int>(node: nil, tag: 51)
}
}
There is no iteration going through every node and associating it with LinkedListIndex
to say node C has a tag of 3, D has a tag of 4. How does index(after:)
know which node comes after LinkedListIndex<Int>(node: node, tag: 50)
?
CodePudding user response:
Based on the code you show:
It's not the linked list elements which are
Comparable
, but the indices.Collection
has noComparable
requirement on its elements, but does require that its indexes be comparable so that they can be reasonably ordered:public protocol Collection: Sequence { // FIXME: ideally this would be in MigrationSupport.swift, but it needs // to be on the protocol instead of as an extension @available(*, deprecated/*, obsoleted: 5.0*/, message: "all index distances are now of type Int") typealias IndexDistance = Int // FIXME: Associated type inference requires this. override associatedtype Element /// A type that represents a position in the collection. /// /// Valid indices consist of the position of every element and a /// "past the end" position that's not valid for use as a subscript /// argument. associatedtype Index: Comparable // ... }
This requirement on the indices makes it possible to iterate over the
Collection
one index at a time, and know where you are relative tostartIndex
andendIndex
.Note too that the syntax
public struct LinkedListIndex<T>: Comparable
does not make
LinkedList
Comparable
itself, and only declares thatLinkedListIndex
isComparable
. Note that it does not reference the original list itself, but holds on to a node for constant-time access back withinLinkedList
itself: but this implementation detail does not have to do withComparable
conformance, nor does it affect it.It appears that
LinkedListIndex.tag
represents the index of the element in the list, like an array index: the first element (startIndex
) has a tag of0
, the second element has a tag of1
, etc.;endIndex
(the index once past the last element in the list) has an index ofcount
You can use an index to iterate
tag
times through the list to access a specific element. This iteration isn't strictly necessary, though, because aLinkedListIndex
also contains a pointer to the node it's supposed to refer to in the list, as a shortcut.
Update with additional question:
How does index(after:) know which node comes after LinkedListIndex(node: node, tag: 50)?
This is achieved using two things:
Alongside the
tag
,LinkedListIndex
values contain a pointer to the node that they reference in the original list:public struct LinkedListIndex: Comparable { fileprivate let node: LinkedList.LinkedListNode? fileprivate let tag: Int }
This is set at the time that the index is created in:
LinkedList.startIndex
LinkedList.endIndex
LinkedList.index(after:)
The implementation of
LinkedList.index(after:)
uses this node reference in its implementation:public func index(after idx: Index) -> Index { return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag 1) }
The index which comes after
idx
is an index which:- Points to the node after
idx.node
, and - Has a tag which is one past
idx.tag
- Points to the node after
There is no further association between a node and a tag:
- The
tag
appears to be used exclusively forComparable
conformance for indices, as a way to avoid having to compare nodes (e.g.,LinkedListIndex
trusts that ifidx1.tag < idx2.tag
then presumablyidx1.node
comes beforeidx2.node
in the list, even if this is not the case!), while - The
node
is the only thing really consulted when subscripting, and when producing new indices
Because the nodes and tags are only very loosely related in this way, this code isn't terribly robust against mismatches (e.g. if I edit the list while you hold on to an index
, the index's tag
may be out of date depending on the operation I perform!).