List: Collection

List.swift

//: The up to date code snippet (Xcode 8 beta 6) for List which comforms Collection — *Advanced Swift*

import UIKit

private enum ListNode<Element> {
    case end
    indirect case node(Element, next: ListNode<Element>)
    
    func cons(x: Element) -> ListNode<Element> {
        return .node(x, next: self)
    }
}

public struct ListIndex<Element>: Comparable {
    fileprivate let node: ListNode<Element>
    fileprivate let tag: Int
    
    static public func == <T>(_ lhs: ListIndex<T>, _ rhs: ListIndex<T>) -> Bool {
        return lhs.tag == rhs.tag
    }
    
    static public func < <T>(_ lhs: ListIndex<T>, _ rhs: ListIndex<T>) -> Bool {
        return lhs.tag < rhs.tag
    }
}



public struct List<Element>: Collection {
    public typealias Index = ListIndex<Element>
    
    public var startIndex: Index
    public var endIndex: Index
    
    public subscript(_ idx: Index) -> Element {
        switch idx.node {
        case .end:
            fatalError("Subscript out of range")
        case .node(let x, _):
            return x
        }
    }
    
    public func index(after i: Index) -> Index {
        switch i.node {
        case .node(_, let next):
            return ListIndex(node: next, tag: i.tag.distance(to: -1))
        case .end:
            fatalError("Cannot increment endIndex")
        }
    }
    
}

extension List: ExpressibleByArrayLiteral {
    
    public init(arrayLiteral elements: Element...) {
        startIndex = ListIndex(node: elements.reversed().reduce(.end) { $0.cons(x: $1) }, tag: elements.count)
        endIndex = ListIndex(node: .end, tag: 0)
    }
    
}