A bare-bones implementation of a singly linked list Collection type in Swift with manual memory management

TripleRefLinkedList.swift

//
//  TripleRefLinkedList.swift
//
//  Created by aaplmath on 8/24/18.
//  Copyright © 2018 aaplmath. All rights reserved.
//

import Darwin

/// A native Swift implementation of a singly linked list that uses triple-reference pointers
final class TripleRefLinkedList<T: Equatable>: Collection {
    private class Node {
        var item: T
        var next: UnsafeMutablePointer<Node>?
        init(item: T, next: UnsafeMutablePointer<Node>?) {
            self.item = item
            self.next = next
        }
    }
    
    private var _count: Int
    
    var count: Int {
        get {
            return _count
        }
    }
    
    func index(after i: Int) -> Int {
        return i + 1
    }
    
    var startIndex: Int {
        get {
            return 0
        }
    }
    
    var endIndex: Int {
        get {
            if _count > 0 {
                return _count - 1
            }
            return 0
        }
    }
    
    private var start: UnsafeMutablePointer<Node>?
    
    /// Returns the list as an array
    var array: [T] {
        get {
            var arr: [T] = []
            var tracer: UnsafeMutablePointer<Node>? = start
            while let element = tracer?.pointee {
                arr.append(element.item)
                tracer = element.next
            }
            return arr
        }
    }
    
    /// Returns the first item in the list, or `nil` if it is empty
    var first: T? {
        get {
            return start?.pointee.item
        }
    }
    
    init() {
        start = nil
        _count = 0
    }
    
    /// Initializes a linked list from another Sequence-conformant value
    convenience init<S: Sequence>(from sequence: S) where S.Element: Equatable {
        self.init()
        var tracer: UnsafeMutablePointer<UnsafeMutablePointer<TripleRefLinkedList<T>.Node>?>? = UnsafeMutablePointer(&start)
        for element in sequence {
            let rawPointer = malloc(MemoryLayout<Node>.size)
            guard let ptr = rawPointer?.bindMemory(to: Node.self, capacity: 1) else {
                fatalError("Could not allocate memory for new element")
            }
            ptr.initialize(to: TripleRefLinkedList<S.Element>.Node(item: element, next: nil) as! TripleRefLinkedList<T>.Node)
            let elementPointer = UnsafeMutablePointer(ptr)
            tracer?.pointee = elementPointer
            tracer = UnsafeMutablePointer(&ptr.pointee.next)
            _count += 1
        }
    }
    
    /// Appends an item to the end of the array
    func append(_ item: T) {
        append(item, withCond: { _, _ in false })
    }
    
    /// Inserts at the specified index, or at the end of the array if the index is out of bounds
    func insert(_ item: T, at index: Int) {
        append(item, withCond: { $1 == index - 1 })
    }
    
    /// Inserts after the specified element, or at the end of the array if the element doesn't exist
    func insert(_ item: T, after element: T) {
        append(item, withCond: { (cur: T?, _) in cur == element })
    }
    
    /// Removes the element at the specified index
    func remove(at index: Int) {
        var tracer: UnsafeMutablePointer<UnsafeMutablePointer<Node>?>? = UnsafeMutablePointer(&start)
        var curIdx = 0
        while let pointer = tracer?.pointee {
            if curIdx == index {
                let old = pointer
                tracer?.pointee = UnsafeMutablePointer(pointer.pointee.next)
                old.deallocate()
                old.deinitialize(count: 1)
                _count -= 1
                return
            }
            tracer = UnsafeMutablePointer(&pointer.pointee.next)
            curIdx += 1
        }
        fatalError("Index out of range")
    }
    
    /// Returns a Boolean value indicating whether the specified value is contained in the list
    func contains(_ item: T) -> Bool {
        var tracer: UnsafeMutablePointer<Node>? = start
        while let element = tracer?.pointee {
            if element.item == item {
                return true
            }
            tracer = element.next
        }
        return false
    }
    
    /// Returns the index of the first occurrence of the specified item in the list, or `nil` if it is not found
    func index(of item: T) -> Int? {
        var tracer: UnsafeMutablePointer<Node>? = start
        var idx = 0
        while let element = tracer?.pointee {
            if element.item == item {
                return idx
            }
            tracer = element.next
            idx += 1
        }
        return nil
    }
    
    subscript(index: Int) -> T {
        return getIndex(index)
    }
    
    private func append(_ item: T, withCond cond: (T?, Int) -> Bool) {
        let rawPointer = malloc(MemoryLayout<Node>.size)
        guard let ptr = rawPointer?.bindMemory(to: Node.self, capacity: 1) else {
            fatalError("Could not allocate memory for new element")
        }
        ptr.initialize(to: Node(item: item, next: nil))
        let elementPointer = UnsafeMutablePointer(ptr)
        var tracer: UnsafeMutablePointer<UnsafeMutablePointer<Node>?>? = UnsafeMutablePointer(&start)
        var idx = 0
        while let pointer = tracer?.pointee {
            tracer = UnsafeMutablePointer(&pointer.pointee.next)
            if cond(pointer.pointee.item, idx) {
                break
            }
            idx += 1
        }
        elementPointer.pointee.next = tracer?.pointee
        tracer?.pointee = elementPointer
        _count += 1
    }
    
    private func getIndex(_ n: Int) -> T {
        var tracer: UnsafeMutablePointer<Node>? = start
        var idx = 0
        while let element = tracer?.pointee {
            if idx == n {
                return element.item
            }
            tracer = element.next
            idx += 1
        }
        fatalError("Index out of range")
    }
    
    deinit {
        var tracer: UnsafeMutablePointer<UnsafeMutablePointer<Node>?>? = UnsafeMutablePointer(&start)
        while let element = tracer?.pointee {
            tracer = UnsafeMutablePointer(&element.pointee.next)
            element.deallocate()
            element.deinitialize(count: 1)
        }
    }
}