damus

NonCopyableLinkedList.swift (5893B)

---

 //
 //  NonCopyableLinkedList.swift
 //  damus
 //
 //  Created by Daniel D’Aquino on 2025-07-04.
 //
 
 /// A linked list to help with iteration of non-copyable elements
 ///
 /// This is needed to provide an array-like abstraction or iterators since swift arrays or iterator protocols require the element to be "copyable"
 struct NonCopyableLinkedList<T: ~Copyable>: ~Copyable {
     private var head: Node<T>? = nil
     private var tail: Node<T>? = nil
     private(set) var count: Int = 0
     
     /// Iterates over each item of the list, with enumeration support.
     func forEachItem<Y>(_ borrowingFunction: ((_ index: Int, _ item: borrowing T) throws -> LoopCommand<Y>)) rethrows -> Y?  {
         var indexCounter = 0
         
         var cursor: Node? = self.head
         
         outerLoop: while let nextItem = cursor {
             let loopIterationResult = try borrowingFunction(indexCounter, nextItem.value)
             indexCounter += 1
             cursor = nextItem.next
             switch loopIterationResult {
             case .loopBreak:
                 break outerLoop
             case .loopContinue:
                 continue outerLoop
             case .loopReturn(let result):
                 return result
             }
         }
         
         return nil
     }
     
     /// Iterates over each item of the list in reverse, with enumeration support.
     func forEachItemReversed<Y, E: Error>(_ borrowingFunction: ((_ index: Int, _ item: borrowing T) throws(E) -> LoopCommand<Y>)) throws(E) -> Y?  {
         var indexCounter = count - 1
         var cursor: Node? = self.tail
         
         outerLoop: while let nextItem = cursor {
             let loopIterationResult = try borrowingFunction(indexCounter, nextItem.value)
             indexCounter -= 1
             cursor = nextItem.previous
             switch loopIterationResult {
             case .loopBreak:
                 break outerLoop
             case .loopContinue:
                 continue outerLoop
             case .loopReturn(let result):
                 return result
             }
         }
         
         return nil
     }
     
     /// Iterates over each item of the list, with enumeration support, updating some value in each iteration and returning the final value at the end.
     func reduce<Y>(initialResult: Y, _ borrowingFunction: ((_ index: Int, _ partialResult: Y, _ item: borrowing T) throws -> LoopCommand<Y>)) throws -> Y {
         var indexCounter = 0
         var currentResult = initialResult
         
         var cursor: Node? = self.head
         
         outerLoop: while let nextItem = cursor {
             let loopIterationResult = try borrowingFunction(indexCounter, currentResult, nextItem.value)
             indexCounter += 1
             cursor = nextItem.next
             switch loopIterationResult {
             case .loopBreak:
                 break outerLoop
             case .loopContinue:
                 continue outerLoop
             case .loopReturn(let result):
                 currentResult = result
                 continue outerLoop
             }
         }
         
         return currentResult
     }
     
     /// Uses a specific item of the list based on a provided index.
     ///
     /// O(N/2) worst case scenario
     ///
     /// Returns `nil` if nothing was found
     func useItem<Y>(at index: Int, _ borrowingFunction: ((_ item: borrowing T) throws -> Y)) rethrows -> Y? {
         if index < 0 || index >= self.count {
             return nil
         }
         else if index < self.count / 2 {
             return try self.forEachItem({ i, item in
                 if i == index {
                     return .loopReturn(try borrowingFunction(item))
                 }
                 return .loopContinue
             })
         }
         else {
             return try self.forEachItemReversed({ i, item in
                 if i == index {
                     return .loopReturn(try borrowingFunction(item))
                 }
                 return .loopContinue
             })
         }
     }
     
     /// Adds an item to the tail end list
     mutating func add(item: consuming T) {
         guard self.head != nil, let currentTail = self.tail else {
             let firstNode = Node(value: item, next: nil, previous: nil)
             self.head = firstNode
             self.tail = firstNode
             self.count = 1
             return
         }
         let newTail = Node(value: item, next: nil, previous: currentTail)
         currentTail.next = newTail
         self.tail = newTail
         self.count += 1
     }
     
     /// A node of the linked list
     ///
     /// Should be `~Copyable` but that would require using a value type such as a struct or enum, and the Swift compiler does not support recursive enums with non-copyable objects for some reason. Example:
     /// ```swift
     /// enum List<Y: ~Copyable>: ~Copyable {
     ///     indirect case node(value: Y, next: NewList<Y>)  // <-- ERROR: Noncopyable enum 'List' cannot be marked indirect or have indirect cases yet
     ///     case empty
     /// }
     /// ```
     ///
     /// Therefore, we make it `private` to make sure we contain the exposure of this unsafe object to only this class. Outside users of the linked list can access objects via the iterator functions.
     private class Node<Item: ~Copyable> {
         let value: Item
         var next: Node?
         var previous: Node?
         
         init(value: consuming Item, next: consuming Node?, previous: consuming Node?) {
             self.value = value
             self.next = next
             self.previous = previous
         }
     }
 
     /// A loop command to allow closures to control the loop they are in.
     enum LoopCommand<Y> {
         /// Breaks out of the loop
         case loopBreak
         /// Continues to the next iteration of the loop
         case loopContinue
         /// Stops iterating and return a value
         case loopReturn(Y)
     }
 }