README.md

PFDSの演習問題5.8をScalaで考えたい

使い方

git clone [email protected]:7c3a853f01e3b19d3c3eba79516e978b.git PFDS_EX_5_8
cd PFDS_EX_5_8/

sbt run

PFDS_Ex_5_8.scala

/**
  * 準備。Elem型
  */
abstract trait Elem {
  def <=(other : Elem) : Boolean
}
case class IntElem(val i : Int) extends Elem {
  override def <=(other : Elem) = other match {
    case (o: IntElem) => i <= o.i
    case _ => false
    }
  override def toString = i.toString
}

object Wandbox {

  /**
    * 多分木の実装
    * merge, deleteMinは教科書通りのアルゴリズム
    */
  sealed abstract trait MultiTree {
    import MultiTree.{E, T}
    override def toString() = {
      def aux(t : MultiTree) : List[String] = {
        t match {
        case E => List(".")
        case T(x, ts) if ts == Nil || ts.forall(_ == E) => List(x.toString)
        case T(x, ts) =>
          val last = aux(ts.last).zipWithIndex.map{case (s, 0) => "└── " + s; case (s, _) => "    " + s}
          val nakas = for {
            t <- ts.take(ts.length - 1)
            naka <- aux(t).zipWithIndex.map{case (s, 0) => "├── " + s; case (s, _) => "│   " + s}
          } yield naka
          x.toString :: nakas ++ last
        }
      }
      aux(this).mkString("\n")
    }
    def merge(t : MultiTree) = (this, t) match {
      case (E, _) => t      
      case (_, E) => this
      case (T(x, ts1), T(y, ts2)) => {
        if (x <= y) { T(x, t :: ts1) } else { T(y, this :: ts2) }
      }
    }
    def deleteMin() ={
      def mergePairs(ts : List[MultiTree]) : MultiTree = ts match {
        case Nil => E
        case t :: Nil => t
        case t1 :: t2 :: ts => t1.merge(t2).merge(mergePairs(ts))
      }
      this match {
        case E => throw new RuntimeException("空の木だよ")
        case T(x, ts) => mergePairs(ts)
      }
    }
  }
  object MultiTree {
    case object E extends MultiTree
    case class T(x : Elem, ts : List[MultiTree]) extends MultiTree
  }

  /**
    * 2分木の実装
    * mergeの実装が演習の(b)
    */
  sealed abstract trait BinTree {
    import BinTree.{E, T}
    def toMultiTree() : MultiTree = this match {
      case E => MultiTree.E
      case T(x, a, b) => MultiTree.T(x, List(a.toMultiTree(), b.toMultiTree()))
    }
    override def toString() = this.toMultiTree().toString()

    def merge(t : BinTree) : BinTree = (this, t) match {
      case (E, _) => t
      case (_, E) => this
      case (T(x, l1, E), T(y, l2, E)) => {
        if (x <= y) { T(x, T(y, l2, l1), E) } else { T(y, T(x, l1, l2), E) }
      }
      case _ => throw new Exception("ありえないパターンじゃよ")
    }
    def deleteMin() = {
      def mergePairs(t : BinTree) : BinTree = t match {
        case E => E
        case T(_, _, E) => {
          // MultiTree における、子が1つの場合
          t
        }
        case T(x, l1, T(y, l2, r2)) => {
          // r は MultiTree のときの兄弟要素
          T(x, l1, E).merge(T(y, l2, E)).merge(mergePairs(r2))
        }
      }
      this match {
        case E => throw new RuntimeException("空の木だよ")
        case T(x, l, E) => mergePairs(l)
        case _ => throw new RuntimeException("ここはありえないパターンじゃよ")
      }
    }
  }
  object BinTree {
    case object E extends BinTree
    case class T(x : Elem, a : BinTree, b : BinTree) extends BinTree
  }


  /**
    * 教科書 p.57 での説明を基にした多分木 -> 2分木の変換
    */
  def toBinaryAux(ts : List[MultiTree]) : BinTree =
    ts match {
      case Nil => BinTree.E
      case MultiTree.T(x, ts1) :: ts => BinTree.T(x, toBinaryAux(ts1), toBinaryAux(ts))
      case MultiTree.E :: _ => throw new RuntimeException("ここはあり得ないパターンじゃよ")
    }
  def toBinary(t : MultiTree) = toBinaryAux(List(t))

  
  def main(args: Array[String]): Unit = {
    import MultiTree.{E, T}
    val t = T(new IntElem(0), List(
      T(IntElem(3), List(
        T(IntElem(5), Nil)
      )),
      T(IntElem(1), List(
        T(IntElem(6), Nil),
        T(IntElem(2), List(
          T(IntElem(4), List(
            T(IntElem(7), Nil)
          ))
        ))
      ))
    ))

    println(s"=== 多分木での操作")
    println(s"- 初期状態: \n$t")
    println(s"- deleteMinを一回行う: \n${t.deleteMin()}")
    println(s"- deleteMinをもう一回行う: \n${t.deleteMin().deleteMin()}")
    println(s"=== ２分木での操作")
    val bt = toBinary(t)
    println(s"- 初期状態: \n$bt")
    println(s"- deleteMinを一回行う: \n${bt.deleteMin()}")
    println(s"- deleteMinをもう一回行う: \n${bt.deleteMin().deleteMin()}")
    
    // test
    println(bt.deleteMin() == toBinary(t.deleteMin()))
    println(bt.deleteMin().deleteMin() == toBinary(t.deleteMin().deleteMin()))
  }    
}