Implementing recursive generator for simple tree structure in Swift

Question

I have a simple tree structure in memory based on an XML document and I am trying to write a recursive generator to support SequenceType, but I am stuck on how to actually do this.

Here was my first attempt:

@objc public class XMLNode: NSObject, SequenceType {
    public weak var parentNode: XMLNode?
    public var nodeName: String
    public var attributes: [String: String]
    public var childNodes = [XMLNode]()

    public func generate() -> AnyGenerator<XMLNode> {
        var childGenerator = childNodes.generate()
        var returnedSelf = false

        return anyGenerator {
            let child = childGenerator.next()

            if child != nil {
                // I need to somehow recurse on child here

                return child
            } else if !returnedSelf {
                returnedSelf = true
                return self
            } else {
                return nil
            }
        }
    }
}

Since childNodes is an array, I'm calling its own built-in generate() function to create a generator on the child nodes and iterating it, and then returning self at the end. The problem is it's not recursing on each child, so it only ever goes one level deep. I can't figure out how to combine two generators in that way.

I'm having a hard time wrapping my head around how to do this! What do I need to do to make a recursive generator?

How is `childNodes` defined? And what is `self` (in `return self`)? – Perhaps you can provide a (stripped-down) *self-contained* example of the tree structure, that would make it easier to find (and test) a possible solution. — Martin R, Feb 08 '16 at 20:33
Basically a depth-first pre- or post-order traversal, but that's not terribly important. — devios1, Feb 08 '16 at 20:40

score 2 · Accepted Answer · edited May 23 '17 at 12:00

2

~~I don't know if a generator itself can be recursive.~~ Will M proved me wrong!

Here is a possible implementation for a pre-order traversal, using a stack for the child nodes which still have to be enumerated:

extension XMLNode : SequenceType {
    public func generate() -> AnyGenerator<XMLNode> {
        var stack : [XMLNode] = [self]
        return anyGenerator {
            if let next = stack.first {
                stack.removeAtIndex(0)
                stack.insertContentsOf(next.childNodes, at: 0)
                return next
            }
            return nil
        }
    }
}

For a level-order traversal, replace

stack.insertContentsOf(next.childNodes, at: 0)

by

stack.appendContentsOf(next.childNodes)

edited May 23 '17 at 12:00

Community

1
1

answered Feb 08 '16 at 21:10

Martin R

529,903
94
1,240
1,382

This is working great for pre-order, and is way simpler than my attempt! Cheers! – devios1 Feb 08 '16 at 21:28
1

Addressing your first line, I think my answer is a recursive generator, but I'm not 100% confident that I didn't cheat somewhere to make it not truly recursive – Will M. Feb 08 '16 at 21:33
@WillM.: I think you are right. It took me a while to wrap my head around it :) – Martin R Feb 08 '16 at 21:54

score 2 · Answer 2 · answered Feb 08 '16 at 21:25

Here is a recursive post-order generator. Can't say I'd recommend actually using it though. @MartinR's answer seems a bit more practical

 public func generate() -> AnyGenerator<XMLNode> {
    var childGenerator:AnyGenerator<XMLNode>?
    var childArrayGenerator:IndexingGenerator<[XMLNode]>? = self.childNodes.generate()
    var returnedSelf = false

    return anyGenerator {
        if let next = childGenerator?.next() {
            return next
        }
        if let child = childArrayGenerator?.next() {
            childGenerator = child.generate()
            return childGenerator?.next()

        } else if !returnedSelf {

            returnedSelf = true
            return self

        } else {

            return nil
        }
    }
}

I actually just managed to get a similar implementation working! But I think you are right, @MartinR's stack solution seems much simpler. — devios1, Feb 08 '16 at 21:30

score 1 · Answer 3 · answered Feb 08 '16 at 22:41

While Martin's answer is certainly more concise, it has the downside of making a lot of using a lot of array/insert operations and is not particularly usable in lazy sequence operations. This alternative should work in those environments, I've used something similar for UIView hierarchies.

public typealias Generator = AnyGenerator<XMLNode>

public func generate() -> AnyGenerator<XMLNode> {
    var childGenerator = childNodes.generate()
    var subGenerator : AnyGenerator<XMLNode>?
    var returnedSelf = false

    return anyGenerator {
        if !returnedSelf {
            returnedSelf = true
            return self
        }

        if let subGenerator = subGenerator,
            let next = subGenerator.next() {
                return next
        }

        if let child = childGenerator.next() {
            subGenerator = child.generate()
            return subGenerator!.next()
        }

        return nil
    }
}

Note that this is preorder iteration, you can move the if !returnedSelf block around for post order.

Good point re: the array inserts, and this has the benefit of being easily convertible between pre- and post-order, as does @WillM.'s answer. — devios1, Feb 08 '16 at 23:09

Implementing recursive generator for simple tree structure in Swift

3 Answers3

Linked