Escribir tu propia colección: conformar a Collection con índices propios

Conformar a Collection es una de las mejores relaciones coste-beneficio de todo Swift: implementas cuatro miembros y recibes a cambio más de cien operaciones que funcionan sobre tu tipo como si las hubieras escrito tú. Pero el trato tiene letra pequeña. Junto a esos cuatro miembros firmas un puñado de promesas semánticas que el compilador no puede comprobar, y romperlas no produce un error de compilación: produce algoritmos genéricos que devuelven basura o no terminan nunca.

Los cuatro requisitos

Todo lo que Collection te exige es un principio, un final, una forma de avanzar y una forma de leer:

protocol Collection: Sequence {
    associatedtype Index: Comparable
    var startIndex: Index { get }
    var endIndex: Index { get }
    subscript(position: Index) -> Element { get }
    func index(after i: Index) -> Index
}

Los tipos asociados Element e Index se infieren de esas firmas, y el iterador te lo pone la biblioteca gratis mediante IndexingIterator, que simplemente avanza de startIndex a endIndex leyendo el subíndice. No tienes que escribir ni una línea de iteración.

flowchart LR
A[tu tipo] --> B[startIndex]
A --> C[endIndex]
A --> D[index after]
A --> E[subscript]
B --> F[Collection]
C --> F
D --> F
E --> F
F --> G[map filter reduce sorted contains prefix split y cien mas]
style F fill:#89b4fa,color:#11111b
style G fill:#a6e3a1,color:#11111b

El caso trivial ni siquiera necesita un tipo de índice propio: si tu almacenamiento interno es un array, delega y termina en cinco líneas.

struct Bolsa<T>: Collection {
    private var items: [T]
    var startIndex: Int { items.startIndex }
    var endIndex: Int { items.endIndex }
    func index(after i: Int) -> Int { items.index(after: i) }
    subscript(i: Int) -> T { items[i] }
}

Un índice que no es un entero

El caso interesante llega cuando la posición no se puede numerar. Una lista enlazada simple no sabe saltar al elemento k: solo sabe seguir punteros. Su índice, por tanto, tiene que envolver el nodo, y llevar además un desplazamiento para poder cumplir el requisito de Comparable:

final class Nodo<T> {
    let valor: T
    var siguiente: Nodo<T>?
    init(_ valor: T, siguiente: Nodo<T>? = nil) {
        self.valor = valor
        self.siguiente = siguiente
    }
}

struct Lista<T>: Collection {
    private let cabeza: Nodo<T>?
    private let longitud: Int

    struct Indice: Comparable {
        fileprivate let nodo: Nodo<T>?
        fileprivate let salto: Int
        static func == (a: Indice, b: Indice) -> Bool { a.salto == b.salto }
        static func < (a: Indice, b: Indice) -> Bool { a.salto < b.salto }
    }

    var startIndex: Indice { Indice(nodo: cabeza, salto: 0) }
    var endIndex: Indice { Indice(nodo: nil, salto: longitud) }

    func index(after i: Indice) -> Indice {
        Indice(nodo: i.nodo?.siguiente, salto: i.salto + 1)
    }

    subscript(position: Indice) -> T {
        guard let nodo = position.nodo else {
            preconditionFailure("indice fuera de rango")
        }
        return nodo.valor
    }
}

El desplazamiento no se usa para navegar —eso lo hace el puntero al nodo— sino solo para ordenar y comparar índices, que es lo que exige Comparable. Separar la información de navegación de la de orden es el patrón habitual al diseñar índices no triviales.

Lo que la stdlib te regala

En cuanto esos cuatro miembros existen, tu tipo hereda el catálogo entero de extensiones de protocolo:

let l = Lista([3, 1, 4, 1, 5])
print(l.count)                     // 5, calculado recorriendo
print(l.map { $0 * 2 })            // [6, 2, 8, 2, 10]
print(l.sorted())                  // [1, 1, 3, 4, 5]
print(l.contains(4))               // true
print(Array(l.prefix(2)))          // [3, 1]

Nada de eso está escrito en Lista. Todo viene de extensiones sobre Collection que solo saben usar los cuatro miembros que implementaste.

Afinar y subir de nivel

Las implementaciones por defecto son correctas pero genéricas: count recorre la colección entera. Si tu tipo sabe hacerlo mejor, redeclara el miembro y el despacho dinámico del protocolo usará tu versión:

extension Lista {
    var count: Int { longitud }        // constante en vez de lineal
    var isEmpty: Bool { cabeza == nil }
}

Subir por la torre funciona igual: si añades index(before:) en tiempo constante puedes declarar conformidad a BidirectionalCollection y ganar last, suffix y reversed; si además index(_:offsetBy:) y distance(from:to:) son constantes, RandomAccessCollection te da un count constante y habilita los algoritmos que lo exigen. Una lista enlazada simple no puede subir: no tiene enlace hacia atrás, y prometerlo mintiendo convertiría una operación lineal en una trampa dentro de código ajeno.