Share behaviors among multiple protocol-based trees

Using Swift
1

I am working on some N-ary tree similar to a DOM tree used in a browser. Nodes have different behaviors such as carrying different types of information but also share a same property children: BaseType. The typical solution is to use a class hierarchy. However, I want to make reasoning about mutation on the tree easier and decide to go with a protocol/struct based approach:

protocol Base {
    var children: [Base] { get }
}

struct Leaf: Base {
    var children: [Base] { [] }
}

struct Branch: Base {
    var children: [Base]
}

Then, I realize I need to make different trees that are nearly isomorphic to each other, again, like what happens in a browser. I need to render my tree, for instance, and my render tree would have a similar if not the same shape as the data tree.

I would like to define some common behaviors across these trees, such as different ways to traversal or compute distance between two tree indices. It feels natural to define some base protocol for all such trees:

protocol TreeNode {
    associatedtype Node
    var children: [Node] { get }
}

protocol Base {
    var children: [Base] { get }
}

struct Leaf: Base {
    var children: [Base] { [] }
}

extension Leaf: TreeNode {
    typealias Node = Base
}

struct Branch: Base {
    var children: [Base]
}

extension Branch: TreeNode {
    typealias Node = Base
}

Notice that I cannot make Base conform to Node, for otherwise Base would have an associated type. And a protocol with associated type(s) can only be used as generic constraint. However, this would not work since I cannot even write a function of accessing some node given a path of type [Int], precisely because I cannot have something of protocol TreeNode and hence unable to do recursion.

Any workaround?

2

I just figured one solution, introducing a wrapper around the middle protocol using struct. This way, the definition for the tree type can also easily accommodate homogeneous trees (all nodes sharing the same type).

1 Like