Layout according to offset without having elements overlap. Helper for SwiftUI implementation

DynamicSpacerHeightLayoutManager.swift

class DynamicSpacerHeightLayoutManager<ID: Equatable & Hashable>: ObservableObject {
    struct Element {
        let offset: CGFloat
        let height: CGFloat
    }
    @Published private var orderedByOffset = OrderedDictionary<ID, Element>()
    
    // insert: O(n) <- can be optimized further
    // append: O(1)
    // update offset: O(n) <- can be optimized furhter
    // update height: O(1)
    func set(id: ID, offset: CGFloat, height: CGFloat) {
        var newMap = orderedByOffset
        if let existing = orderedByOffset[id] {
            // offset didn't change so no need to recalculate indexes
            if existing.height != height && existing.offset == offset {
                orderedByOffset[id] = Element(offset: offset, height: height)
                return
            } else if existing.height == height && existing.offset == offset {
                // no-op
                return
            } else {
                // lets remove it so that we can insert at the correct position below
                newMap[id] = nil
            }
        }
        
        if let lastKey = newMap.keys.last {
            // optimization for appending to the end of the list
            if let payload = newMap[lastKey], payload.offset <= offset {
                orderedByOffset[id] = Element(offset: offset, height: height)
                return
            }
        } else {
            // there is no last key, the map is empty
            orderedByOffset[id] = Element(offset: offset, height: height)
            return
        }

        // okay this needs to be inserted somewhere in the middle of the list
        // NOTE: could probably switch to a binary search here if we switch our data structure
        // but this should be using less <20 elements so any perf gains would be negligible
        for (i, payload) in newMap.enumerated() {
            guard payload.value.offset > offset else { continue }
            newMap.updateValue(Element(offset: offset, height: height), forKey: id, insertingAt: i)
            break
        }
        orderedByOffset = newMap
    }
    
    func offset(for id: ID) -> CGFloat? {
        guard let value = orderedByOffset[id] else { return nil }
        var rollingY: CGFloat = 0
        for kv in orderedByOffset {
            guard kv.key != id else { break }
            // the offset is greater then our current height
            if rollingY <= kv.value.offset {
                rollingY = kv.value.offset + kv.value.height
            } else {
                // the offset is within the height of the previous node
                rollingY += kv.value.height
            }
        }
        return max(rollingY, value.offset)
    }
    
    func orderedKeys() -> [ID] {
        return orderedByOffset.keys.map({ $0 })
    }
    
    func offsetHeight(for id: ID) -> Element {
        guard let value = orderedByOffset[id] else { return Element(offset: 0, height: 0) }
        return value
    }
    
    var maxHeight: CGFloat {
        guard let last = orderedByOffset.keys.last, let lastElement = orderedByOffset[last] else { return 0 }
        return (offset(for: last) ?? 0) + lastElement.height
    }
}

class HeightAwareOffsetLayoutManager<ID: Hashable> {
    var scaleFactor: Float
    init(scaleFactor: Float) {
        self.scaleFactor = scaleFactor
    }
    
    private var orderedByOffset = OrderedDictionary<ID, Float>()
    private var nodeHeights = [ID: Float]()
    
    func set(offset: Float, for id: ID) {
        var newMap = orderedByOffset
        if let existing = orderedByOffset[id] {
            if existing == offset {
                // no-op: offset didn't change so no need to recalculate indexes
                return
            } else {
                // lets remove it so that we can insert at the correct position below
                newMap[id] = nil
            }
        }
        
        if let lastKey = newMap.keys.last {
            // optimization for appending to the end of the list
            if let payload = newMap[lastKey], payload <= offset {
                orderedByOffset[id] = offset
                return
            }
        } else {
            // there is no last key, the map is empty
            orderedByOffset[id] = offset
            return
        }

        // okay this needs to be inserted somewhere in the middle of the list
        // NOTE: could probably switch to a binary search here if we switch our data structure
        // but this should be using less <20 elements so any perf gains would be negligible
        for (i, payload) in newMap.enumerated() {
            guard payload.value > offset else { continue }
            newMap.updateValue(offset, forKey: id, insertingAt: i)
            break
        }
        orderedByOffset = newMap
    }
    
    func remove(id: ID) {
        nodeHeights[id] = nil
        orderedByOffset[id] = nil
    }
    
    func set(height: Float, for id: ID) {
        nodeHeights[id] = height
    }
    
    func orderedKeys() -> [ID] {
        return orderedByOffset.keys.map({ $0 })
    }
    
    func offset(for id: ID) -> Float? {
        guard let value = orderedByOffset[id] else { return nil }
        var rollingY: Float = 0
        print(#function, orderedByOffset.keys)
        for kv in orderedByOffset {
            guard kv.key != id else { break }
            let height = nodeHeights[id] ?? 0
            print("\(id)".dropFirst(57), height)
            let offset = kv.value * scaleFactor
            // the offset is greater then our current height
            if rollingY <= offset {
                rollingY = offset + height
            } else {
                // the offset is within the height of the previous node
                rollingY += height
            }
        }
        return max(rollingY, value * scaleFactor)
    }
}

DynamicSpacerHeightLayoutManagerTests.swift

class DynamicSpacerHeightLayoutManagerTests: XCTestCase {
    // MARK: - set
    func testOrdersByOffset() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "d", offset: 300, height: 100)
        manager.set(id: "c", offset: 200, height: 100)
        manager.set(id: "a", offset: 50, height: 100)
        manager.set(id: "e", offset: 400, height: 100)
        manager.set(id: "b", offset: 75, height: 100)
        
        XCTAssertEqual(["a", "b", "c", "d", "e"], manager.orderedKeys())
    }
    
    func testReOrdersOnOffsetChange() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "c", offset: 300, height: 100)
        manager.set(id: "b", offset: 200, height: 100)
        manager.set(id: "a", offset: 50, height: 100)
        
        XCTAssertEqual(["a", "b", "c"], manager.orderedKeys())
        
        manager.set(id: "c", offset: 100, height: 100)
        XCTAssertEqual(["a", "c", "b"], manager.orderedKeys())
    }
    
    func testUpdatesHeight() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "c", offset: 300, height: 100)
        manager.set(id: "b", offset: 200, height: 100)
        manager.set(id: "a", offset: 50, height: 100)
        
        XCTAssertEqual(["a", "b", "c"], manager.orderedKeys())
        XCTAssertEqual(200, manager.offset(for: "b"))
        XCTAssertEqual(300, manager.offset(for: "c"))
        
        manager.set(id: "b", offset: 200, height: 300)
        XCTAssertEqual(200, manager.offset(for: "b"))
        XCTAssertEqual(500, manager.offset(for: "c"))
    }
    
    // MARK: - offset
    func testCalculatesFirstOffset() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "a", offset: 50, height: 150)
        
        XCTAssertEqual(manager.offset(for: "a"), 50)
    }
    
    func testCalculatesSecondWithSpacing() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "a", offset: 50, height: 150)
        manager.set(id: "b", offset: 300, height: 75)
        
        XCTAssertEqual(manager.offset(for: "b"), 300)
    }
    
    func testCalculatesSecondWithoutSpacing() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "a", offset: 50, height: 150)
        manager.set(id: "b", offset: 100, height: 75)
        
        XCTAssertEqual(manager.offset(for: "b"), 200)
    }
    
    func testCalculatesThirdWithSpacing() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "a", offset: 50, height: 150)
        manager.set(id: "b", offset: 300, height: 75)
        manager.set(id: "c", offset: 400, height: 75)
        
        XCTAssertEqual(manager.offset(for: "c"), 400)
    }
    
    func testCalculatesThirdWithoutSpacing() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "a", offset: 50, height: 150)
        manager.set(id: "b", offset: 100, height: 75)
        manager.set(id: "c", offset: 250, height: 75)
        
        XCTAssertEqual(manager.offset(for: "c"), 275)
    }
    
    func testUpdatingPreceedingNodeDoesNotInfluenceNodeWithSpace() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "a", offset: 50, height: 150)
        manager.set(id: "b", offset: 400, height: 75)
        
        XCTAssertEqual(manager.offset(for: "b"), 400)
        
        manager.set(id: "a", offset: 50, height: 300)
        XCTAssertEqual(manager.offset(for: "b"), 400)
    }
    
    // MARK: - max height
    func testCalculatesEmptyMaxHeight() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        XCTAssertEqual(manager.maxHeight, 0)
    }
    
    func testCalculatesMaxHeight() {
        let manager = DynamicSpacerHeightLayoutManager<String>()
        manager.set(id: "a", offset: 50, height: 150)
        manager.set(id: "b", offset: 100, height: 75)
        manager.set(id: "c", offset: 250, height: 75)
        
        XCTAssertEqual(manager.maxHeight, 350)
    }
}