devios February 2016

Implementing recursive generator for simple tree structure in Swift

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?

Answers


Martin R February 2016

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)


Will M. February 2016

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
        }
    }
}


David Berry February 2016

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.

Post Status

Asked in February 2016
Viewed 2,783 times
Voted 5
Answered 3 times

Search




Leave an answer