読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Iteratorパターン

Swift デザインパターン

https://ja.wikipedia.org/wiki/Iterator_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3 f:id:kanetai:20150905143839p:plain

↓みたいに要素を反復列挙できるようにするパターン

var iterator = aggregate.iterator()
while iterator.hasNext() {
    var element = iterator.next()
}

swiftIteratorを実装するには?

swiftだとSequenceType, GeneratorTypeプロトコルがそれぞれAggregate, Iteratorに相当する。

protocol SequenceType { //Aggregate
    func generate() -> GeneratorType //iterator()
}
protocol GeneratorType { //Iterator
    mutating func next() -> Element? //next()
}

プロトコルにはhasNext()は無いけど実装すればこう書ける。

var iterator = aggregate.generate()
while iterator.hasNext() {
    var element = iterator.next()
    //do something
}

しかし、hasNext() == falseのときnext()nilを返すので、hasNext()を実装する必要はあまり無い

var iterator = aggregate.generate()
while let element = iterator.next() {
    //do something
}

SequenceTypeプロトコルを実装していれば高速列挙可能

for element in aggregate {
    //do something
}

ループさせるだけなら、プロトコルを継承していなくても、closureをとるようなforeachを定義しとけばいいし、要素以外にも、いろいろな情報(indexとか)を付加してループさせることもできる。

func foreach(closure: (element: Element) -> Void) { /* ... */ }
aggregate.foreach {
    //do something ($0 is element)
}

FoundationのプロトコルだとNSFastEnumeration, NSEnumeratorで高速列挙できるが、 swiftで実装しようとすると、ポインタや、AnyObject?をいじらないといけないので面倒くさい。

protocol NSFastEnumeration {   
    func countByEnumeratingWithState(state: UnsafeMutablePointer<NSFastEnumerationState>, objects buffer: AutoreleasingUnsafeMutablePointer<AnyObject?>, count len: Int) -> Int
}
class NSEnumerator : NSObject, NSFastEnumeration {
    func nextObject() -> AnyObject?
}

参考

swiftでのIterator実装例

swiftでbinaryTreeの左の深さ優先探索(行きがけ順:pre-order)を実装してみた。 ほかにも、逆順(reverse-order)や、優先(breadth-first)のイテレータを作っておけば、状況に合わせて好きな順で列挙できる。

動作確認はあまりしてない...

didSetってイニシャライザの中では動作しないのん?

Apple Swift version 1.2 (swiftlang-602.0.53.1 clang-602.0.53)
Target: x86_64-apple-darwin14.5.0
public class Tree : SequenceType {
    let root: Node
    public init(rootNode: Node) {
        self.root = rootNode
    }
    public func generate() -> Iterator {
        return Iterator(node: self.root)
    }
    public class func node(#val: Int, left: Node?, right: Node?) -> Node {
        let node: Node = Node(val: val)
        node.left = left
        node.right = right
        return node
    }
    //    let rootNode: Node
    public class Node {
        let val: Int
        var parent: Node?
        var left: Node? {
            didSet { if left != nil { left?.parent = self } }
        }
        var right: Node? {
            didSet { if right != nil { right?.parent = self } }
        }
        public init(val: Int) { self.val = val }
    }
    public class Iterator : GeneratorType {
        private var node: Node?
        public init(node: Node) {
            self.node = node
        }
        public func next() -> Node? {
            var ret = self.node
            self.node = self.dynamicType.nextNodeOf(ret)
            return ret
        }
        public func hasNext() -> Bool {
            return self.node != nil
        }
        //pre-order search
        public class func nextNodeOf(targetNode: Node?) -> Node? {
            if let node: Node = targetNode {
                if node.left != nil {
                    return node.left
                }
                //return node.right
                //if node.right is nil, access node.parent.right recursively
                return nextRightNodeOf(node: node, preNode: node)
            } else {
                return nil
            }
        }
        private class func nextRightNodeOf(#node: Node, preNode: Node) -> Node? {
            if node.right != nil && preNode !== node.right {
                return node.right
            }
            if node.parent != nil {
                return nextRightNodeOf(node: node.parent!, preNode: node)
            }
            return nil
        }
    }
}

var tree: Tree = Tree(rootNode: Tree.node(val: 0,
    left: Tree.node(val: 1,
        left: Tree.node(val: 11,
            left: Tree.node(val: 111,
                left: Tree.node(val: 1111,
                    left: nil,
                    right: nil),
                right: Tree.node(val: 1112,
                    left: nil,
                    right: nil)),
            right: nil),
        right: nil),
    right: Tree.node(val: 2,
        left: nil,
        right: nil)
    ))

for node in tree {
    println("\(node.val)")
}