How to Return subscript in Constant Time?

Question

As per the Swift Documentation when conforming to the Collection protocol:

Types that conform to Collection are expected to provide the startIndex and endIndex properties and subscript access to elements as O(1) operations.

How can subscript be returned in constant time? Wouldn't it need to iterate through the collection, up to the correct index, and then return that value?

This is the LinkedList that I'm using to conform to Collection:

indirect enum LinkedList<T> {
    case value(element: T, next: LinkedList<T>)
    case end
}

extension LinkedList: Sequence {
    func makeIterator() -> LinkedListIterator<T> {
        return LinkedListIterator(current: self)
    }
    var underestimatedCount: Int {
        var count = 0
        for _ in self {
            count += 1
        }
        return count
    }
}

struct LinkedListIterator<T>: IteratorProtocol {
    var current: LinkedList<T>
    mutating func next() -> T? {
        switch current {
        case let .value(element, next):
            current = next
            return element
        case .end:
            return nil
        }
    }
}

And here is this is where I actually conform to the protocol:

extension LinkedList: Collection {

    typealias Index = Int
    typealias Element = T

    var startIndex: Index {
        return 0
    }
    var endIndex: Index {
        return underestimatedCount
    }
    func index(after i: Index) -> Index {
        return (i < endIndex) ? i + 1 : endIndex
    }
    subscript (position: Index) -> Element {
        precondition(position < endIndex && position >= startIndex)
        var iterator = makeIterator()
        for i in 0 ..< position {
            iterator.next()
            if i + 1 == position {
                return iterator.next()!
            }
        }
        var zero = makeIterator()
        return zero.next()!
    }

}

let test = LinkedList<Int>.value(element: 2, next: LinkedList<Int>.value(element: 4, next: LinkedList<Int>.value(element: 7, next: LinkedList<Int>.value(element: 9, next: LinkedList<Int>.end))))

Answer 1

The collection's Index does not have to be an Int. One possible approach is to use a custom index type which has a reference to the corresponding element. However this requires the list nodes to be instances of a class.

Here is something that I came up with. It can probably be improved, but hopefully demonstrates the idea.

class ListNode stores the element and a pointer to the next node, and in addition, an increasing integer ordinal, which is used to make struct ListIndex adopt the Comparable protocol.

struct ListIndex contains a reference to the list node, or nil for endIndex.

struct LinkedListCollection<T>: Collection {

    class ListNode {
        let element: T
        let next: ListNode?
        let ordinal: Int

        init(element: T, next: ListNode?, ordinal: Int) {
            self.element = element
            self.next = next
            self.ordinal = ordinal
        }

        // Create ListNode as the head of a linked list with elements from an iterator.
        convenience init?<I: IteratorProtocol>(it: inout I, ordinal: Int = 0) where I.Element == T {
            if let el = it.next() {
                self.init(element: el, next: ListNode(it: &it, ordinal: ordinal + 1), ordinal: ordinal)
            } else {
                return nil
            }
        }
    }

    struct ListIndex: Comparable {
        let node: ListNode?

        static func <(lhs: ListIndex, rhs: ListIndex) -> Bool {
            // Compare indices according to the ordinal of the referenced
            // node. `nil` (corresponding to `endIndex`) is ordered last.

            switch (lhs.node?.ordinal, rhs.node?.ordinal) {
            case let (r?, l?):
                return r < l
            case (_?, nil):
                return true
            default:
                return false
            }
        }

        static func ==(lhs: ListIndex, rhs: ListIndex) -> Bool {
            return lhs.node?.ordinal == rhs.node?.ordinal
        }
    }

    let startIndex: ListIndex
    let endIndex: ListIndex

    // Create collection as a linked list from the given elements.
    init<S: Sequence>(elements: S) where S.Iterator.Element == T {
        var it = elements.makeIterator()
        startIndex = ListIndex(node: ListNode(it: &it))
        endIndex = ListIndex(node: nil)
    }

    func index(after i: ListIndex) -> ListIndex {
        guard let next = i.node?.next else {
            return endIndex
        }
        return ListIndex(node: next)
    }

    subscript (position: ListIndex) -> T {
        guard let node = position.node else {
            fatalError("index out of bounds")
        }
        return node.element
    }
}

Example usage:

let coll = LinkedListCollection(elements: [1, 1, 2, 3, 5, 8, 13])
for idx in coll.indices {
    print(coll[idx])
}