Implement BFS

[yosshi4486]

Playground refer https://qiita.com/drken/items/996d80bcae64649a6580

import Foundation

public func bfs<Data>(_ data: Data.Element, children keypath: KeyPath<Data.Element, Data?>, forEach: (Data.Element) -> Void) where Data: RandomAccessCollection, Data.Element : Identifiable {

    var discovered: [Data.Element.ID:Bool] = [data.id:true]
    var queue: [Data.Element] = [data]

    while !queue.isEmpty {
        if let vertex: Data.Element = queue.dropFirst().first, let children = vertex[keypath:keypath] {
            forEach(vertex)

            for child in children {
                if (discovered[child.id] ?? false) {
                    continue
                } 

                discovered[child] = true
                queue.append(child)
            }
        }
    }
}

final class TestStub {
    var title: String
    var children: [TestStub]

    init(_ title: String, children: [TestStub]) {
        self.title = title
        self.children = children
    }
}

final class TestStubOptional : Identifiable {
    var title: String
    var children: [TestStubOptional]?

    init(_ title: String, children: [TestStubOptional]) {
        self.title = title
        self.children = children
    }

    var id: String {
        return title
    }
}

let testData = TestStubOptional("Root", children: [
    TestStubOptional("Parent1", children: [
        TestStubOptional("Child1", children: []),
        TestStubOptional("Child2", children: [
            TestStubOptional("Grandchild", children: [])
        ])
    ]),
    TestStubOptional("Parent2", children: [])
])

var sequence: [String] = []
bfs(testData, children: \TestStubOptional.children) { (node) in
    sequence.append(node.title)
}

assert(sequence == ["Root", "Parent1", "Parent2", "Child1", "Child2", "Grandchild"])

[yosshi4486]

The code doesn’t work