木構造Iterator試作

sceneのnodeとSkeletonのboneの木構造を共用にすべく型パラメータで書いてみた。
foreachが動けば十分なので、がんばってIterableを実装するほどでもなく、
Traversableを実装すればよかった気がする。

import scala.collection.Iterator
import scala.collection.Iterable
import scala.collection.mutable.Stack
import scala.collection.mutable.ArrayBuffer

class DoubleLinkedNode[T](val content: T) extends Iterable[T] {

    override def toString="<Node %s>".format(content.toString)

    var parent :Option[DoubleLinkedNode[T]]=None
    val children=ArrayBuffer[DoubleLinkedNode[T]]()

    def add(child :DoubleLinkedNode[T])={
        child.parent=Some(this)
        children.append(child)
        child
    }

    def iterator: Iterator[T]=new DepthFirstIterator(this)
    ////////////////////////////////////////////////////////////
    // DepthFirstIterator
    ////////////////////////////////////////////////////////////
    private class DepthFirstIterator[T](root :DoubleLinkedNode[T]) 
    extends Iterator[T]{

        class Position(val node :DoubleLinkedNode[T]){
            var index=0
            def hasNext=index<node.children.length
            def getNext :Position={
                val child=node.children(index)
                index+=1
                return new Position(child)
            }
        }
        
        val stack=Stack(new Position(root))
        var current :Option[T]=advance()
        private def advance() :Option[T]={
            while(!stack.isEmpty){
                if(stack.top.hasNext){
                    val position=stack.top.getNext
                    stack.push(position)
                    return Some(position.node.content)
                }
                else{
                    stack.pop()
                }
            }
            None
        }
        override def next :T=current match {
            case Some(content)=>
                current=advance()
                content
            case None=>throw new java.util.NoSuchElementException
        }
        override def hasNext=current match {
            case Some(content)=>true
            case None=>false
        }
    }
}

class Node(val name :String){
    override def toString=name
}

object App {
    def main(args :Array[String]){
        val root=new DoubleLinkedNode(new Node("root"))
        val ja=root.add(new DoubleLinkedNode(new Node("Japan")))
        ja.add(new DoubleLinkedNode(new Node("Tokyo")))
        ja.add(new DoubleLinkedNode(new Node("Kyoto")))
        val ussr=root.add(new DoubleLinkedNode(new Node("USSR")))
        ussr.add(new DoubleLinkedNode(new Node("Moscow")))
        root.foreach{println(_)}
    }
}

やっぱりTraversalを使ってみる

class DoubleLinkedNode[T](val content: T) extends Traversable[T] {

    override def toString="<Node %s>".format(content.toString)

    var parent :Option[DoubleLinkedNode[T]]=None
    val children=ArrayBuffer[DoubleLinkedNode[T]]()

    def add(child :DoubleLinkedNode[T])={
        child.parent=Some(this)
        children.append(child)
        child
    }

    def foreach[U](f: T => U){
        for(child <- children){
            f(child.content)
            child.foreach(f)
        }
    }
}

圧倒的にシンプルだ。
ちゃんとfor文でも使える。

  for(node <- root){
    println(node)
  }

Iteratorを実装するのは必要になってからでよさそうだ。