Swift Value Semantic Linked List

Value Semantic Linked List.swift

// DEPRECATED!!!
// NEW VERSION HERE: https://github.com/JadenGeller/Linky/

class NodeBacking<T> {
    var backing: T
    
    init(backing: T) {
        self.backing = backing
    }
}

struct Node<T> : SequenceType, Printable {
    private var valueBacking: NodeBacking<T>
    private var nextBacking: NodeBacking<Node<T>?>
    
    mutating private func setAncestorValue(#distance: Int, value: T){
        if distance > 0 {
            if next != nil { next!.setAncestorValue(distance: distance - 1, value: value) }
            else { fatalError("fatal error: Linked list index out of range") }
        }
        else { setValueWithCopy(value) }
    }
    
    mutating private func setValueWithCopy(value: T){
        if !isUniquelyReferencedNonObjC(&valueBacking) {
            valueBacking = NodeBacking(backing: value)
        }
        else {
            valueBacking.backing = value
        }
    }
    
    init(_ value: T) {
        valueBacking = NodeBacking(backing: value)
        nextBacking = NodeBacking(backing: nil)
    }
    
    var value: T {
        get {
            return valueBacking.backing
        }
        set {
            setValueWithCopy(newValue)
        }
    }
    
    var next: Node<T>? {
        get {
            return nextBacking.backing
        }
        set {
            nextBacking = NodeBacking(backing: newValue)
        }
    }
    
    func generate() -> NodeGenerator<T> {
        return NodeGenerator(node: self)
    }
    
    var description: String {
        get {
            return "\(value)"
        }
    }
}

struct NodeGenerator<T> : GeneratorType {
    var node: Node<T>?
    
    mutating func next() -> Node<T>? {
        let previous = node
        node = node?.next
        return previous
    }

}

struct LinkedList<T> : MutableCollectionType, ArrayLiteralConvertible, Printable {
    private var head: Node<T>?
    
    init(arrayLiteral elements: T...) {
        if let first = elements.first {
            var node = Node(first)
            head = node
            for x in elements[1..<elements.endIndex] {
                let next = Node(x)
                node.nextBacking.backing = next
                node = next
            }
        }
        else {
            head = nil
        }
    }
    
    var count: Int {
        get {
            var c = 0
            for var i = head; i != nil; i = i?.next { c++ }
            return c
        }
    }
    
    var startIndex: Int {
        get {
            return 0
        }
    }
    
    var endIndex: Int {
        get {
            return count - 1
        }
    }
    
    func generate() -> LinkedListGenerator<T> {
        return LinkedListGenerator(node: head)
    }
    
    subscript(index: Int) -> T {
        get {
            for (i,v) in enumerate(self) {
                if i == index { return v }
            }
            fatalError("fatal error: Linked list index out of range")
        }
        set {
            if head != nil {
                head?.setAncestorValue(distance: index, value: newValue)
            }
            else {
                fatalError("fatal error: Linked list index out of range")
            }
        }
    }
    
    var description: String {
        get {
            var str = "["
            for (i,x) in enumerate(self) {
                str += "\(x)"
                if i != self.endIndex { str += ", " }
            }
            str += "]"
            return str
        }
    }
}

struct LinkedListGenerator<T> : GeneratorType {
    var node: Node<T>?

    mutating func next() -> T? {
        let value = node?.value
        node = node?.next
        return value
    }
}

// Apple implements Swift Array, Dictionary, and Set with value semantics
// so why not linked lists too!?

var x: LinkedList = [1,2,3,4]
var z = x

z[2] = 100
x[0] = 5

println(x) // -> [5, 2, 3, 4]
println(z) // -> [1, 2, 100, 4]

// Node that the values 2 and 4 are shared among both linked lists!
// These are actually the same reference!