Data Structures in Swift

// Fixed-size array via tuple or unsafe buffer
let fixed: [Int] = [10, 20, 30, 40, 50]

var copy = fixed
copy[0] = 99                  // O(1) - direct index access
let val = copy[2]             // O(1) - read by index

// Iterate
for item in copy {
    print(item, terminator: " ")
}

// Search and sort
let sorted = copy.sorted()             // O(n log n)
let idx = copy.firstIndex(of: 30)      // O(n)

var names = ["Alice", "Bob", "Charlie"]

names.append("Diana")                // O(1) amortized
names.insert("Eve", at: 1)           // O(n) - shifts elements
names.removeLast()                    // O(1)
names.remove(at: 0)                   // O(n) - shifts elements

let has = names.contains("Bob")       // O(n)
let idx = names.firstIndex(of: "Bob") // O(n)

names.sort()                          // O(n log n) - in-place
let squares = (0..<10).map { $0 * $0 }  // O(n) - functional transform

// Swift has no built-in Stack - use Array
var stack: [Int] = []

stack.append(10)          // O(1) - push
stack.append(20)
stack.append(30)

let top = stack.last!     // O(1) - peek -> 30
let val = stack.removeLast()  // O(1) - pop -> 30

// Interview pattern: valid parentheses
func isValid(_ s: String) -> Bool {
    var st: [Character] = []
    let pairs: [Character: Character] = ["(": ")", "[": "]", "{": "}"]
    for c in s {
        if let close = pairs[c] { st.append(close) }
        else if st.isEmpty || st.removeLast() != c { return false }
    }
    return st.isEmpty
}

// Simple queue using Array (or use Deque from Swift Collections)
var queue: [String] = []

queue.append("Task A")        // O(1) - enqueue
queue.append("Task B")
queue.append("Task C")

let first = queue.first!      // O(1) - peek
let val = queue.removeFirst()  // O(n) - dequeue (use Deque for O(1))

// Interview pattern: BFS
func bfs(_ root: TreeNode?) {
    guard let root else { return }
    var q = [root]
    while !q.isEmpty {
        let node = q.removeFirst()
        print(node.val, terminator: " ")
        if let l = node.left  { q.append(l) }
        if let r = node.right { q.append(r) }
    }
}

var prices: [String: Int] = ["apple": 3, "banana": 5]

prices["cherry"] = 2                // O(1) - add
prices["apple"] = 10                // O(1) - update
let has = prices.keys.contains("banana")  // O(1)
prices.removeValue(forKey: "cherry")      // O(1)

let count = prices["mango", default: 0]  // O(1) - safe lookup

// Interview pattern: Two Sum
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var seen: [Int: Int] = [:]
    for (i, num) in nums.enumerated() {
        if let j = seen[target - num] { return [j, i] }  // O(1)
        seen[num] = i                                      // O(1)
    }
    return []
}

var s: Set<Int> = [1, 2, 3, 4, 5]

s.insert(6)               // O(1)
s.remove(1)               // O(1)
let has = s.contains(4)   // O(1) -> true

// Set operations
let other: Set<Int> = [4, 5, 6, 7]
let inter = s.intersection(other)     // {4, 5, 6}
let union = s.union(other)            // {2, 3, 4, 5, 6, 7}
let diff  = s.subtracting(other)      // {2, 3}

// Interview pattern: contains duplicate
func containsDuplicate(_ nums: [Int]) -> Bool {
    return Set(nums).count != nums.count
}

// Swift has no built-in linked list - manual implementation
class ListNode<T> {
    var val: T
    var next: ListNode?
    init(_ val: T, _ next: ListNode? = nil) {
        self.val = val; self.next = next
    }
}

let head = ListNode(1, ListNode(2, ListNode(3)))

// Interview pattern: reverse a linked list
func reverse(_ head: ListNode<Int>?) -> ListNode<Int>? {
    var prev: ListNode<Int>? = nil
    var curr = head
    while let node = curr {
        let next = node.next    // save
        node.next = prev        // reverse link
        prev = node; curr = next
    }
    return prev  // O(n) time, O(1) space
}

// No built-in SortedSet - use a sorted Array wrapper
struct SortedSet<T: Comparable> {
    private var items: [T] = []

    mutating func insert(_ val: T) {         // O(log n) search + O(n) shift
        let idx = insertionIndex(for: val)
        if idx < items.count, items[idx] == val { return }
        items.insert(val, at: idx)
    }

    func contains(_ val: T) -> Bool {        // O(log n) - binary search
        let idx = insertionIndex(for: val)
        return idx < items.count && items[idx] == val
    }

    private func insertionIndex(for val: T) -> Int {
        items.firstIndex { $0 >= val } ?? items.count
    }

    var min: T? { items.first }              // O(1)
    var max: T? { items.last }               // O(1)
}

// No built-in SortedDictionary - use sorted keys pattern
var sd: [String: Int] = ["banana": 2, "apple": 5, "cherry": 1]

sd["date"] = 3                               // O(1) insert
let val = sd["apple"]                        // O(1) -> 5
sd.removeValue(forKey: "cherry")             // O(1)

// Iterate in sorted key order - O(n log n) for sort
for key in sd.keys.sorted() {
    print("\(key): \(sd[key]!)")
}
// apple: 5, banana: 2, date: 3

let firstKey = sd.keys.sorted().first        // "apple"
let lastKey  = sd.keys.sorted().last         // "date"

// Swift Collections provides Heap; or manual implementation
struct MinHeap<T: Comparable> {
    var items: [T] = []

    var peek: T? { items.first }              // O(1)
    mutating func insert(_ val: T) {          // O(log n)
        items.append(val); siftUp(items.count - 1)
    }
    mutating func extractMin() -> T? {        // O(log n)
        guard !items.isEmpty else { return nil }
        items.swapAt(0, items.count - 1)
        let min = items.removeLast(); siftDown(0)
        return min
    }
    private mutating func siftUp(_ i: Int) {
        var i = i
        while i > 0, items[i] < items[(i - 1) / 2] {
            items.swapAt(i, (i - 1) / 2); i = (i - 1) / 2
        }
    }
    private mutating func siftDown(_ i: Int) { /* heapify down */ }
}

// Actor-based thread-safe dictionary (Swift 5.9+)
actor ConcurrentCache<K: Hashable, V> {
    private var store: [K: V] = [:]

    func get(_ key: K) -> V? {
        store[key]                              // O(1) - isolated access
    }

    func set(_ key: K, _ value: V) {
        store[key] = value                      // O(1) - isolated access
    }

    func getOrSet(_ key: K, factory: () -> V) -> V {
        if let existing = store[key] { return existing }
        let val = factory()
        store[key] = val
        return val
    }
}

let cache = ConcurrentCache<String, Int>()
await cache.set("counter", 0)
let val = await cache.get("counter")           // O(1)

// ArraySlice - zero-copy view over an Array
let data = [10, 20, 30, 40, 50]
let slice = data[1..<4]           // O(1) - ArraySlice -> [20, 30, 40]
// slice shares storage with data (copy-on-write)

// UnsafeBufferPointer - raw memory view
data.withUnsafeBufferPointer { buffer in
    let first = buffer[0]         // O(1) - direct memory access
    let count = buffer.count      // 5
    for val in buffer { print(val, terminator: " ") }
}

// UnsafeMutableBufferPointer for mutation
var mutable = [1, 2, 3]
mutable.withUnsafeMutableBufferPointer { buf in
    buf[0] = 99                   // O(1) - direct write
}