Scala99 P46, P47, P49, P50

gistfile1.scala

package s99

object P46 {
  def and(a: Boolean, b: Boolean): Boolean = a && b
  def or(a: Boolean, b: Boolean): Boolean = a || b
  def nand(a: Boolean, b: Boolean): Boolean = ! and(a, b)
  def xor(a: Boolean, b: Boolean): Boolean = or(a, b) && !and(a, b)
  def nor(a: Boolean, b: Boolean): Boolean = ! or(a, b)
  def impl(a: Boolean, b: Boolean): Boolean = a
  def equ(a: Boolean, b: Boolean): Boolean = a == b
  def not(a: Boolean): Boolean = !a

  def table2(f: (Boolean, Boolean) => Boolean) {
    val FORMAT = "%-5s %-5s %-5s"
    println(FORMAT.format("A", "B", "result"))
    for ((a, b) <- List((true, true), (true, false), (false, true), (false, false))) {
      println(FORMAT.format(a, b, f(a, b)))
    }
  }

}

object P47 {
  class RichBoolean(underlying: Boolean) {
    def and(x: Boolean): Boolean = P46.and(underlying, x)
    def or(x: Boolean): Boolean = P46.or(underlying, x)
    def nand(x: Boolean): Boolean = P46.nand(underlying, x)
    def xor(x: Boolean): Boolean = P46.xor(underlying, x)
    def nor(x: Boolean): Boolean = P46.nor(underlying, x)
    def impl(x: Boolean): Boolean = P46.impl(underlying, x)
    def equ(x: Boolean): Boolean = P46.equ(underlying, x)
    def not: Boolean = P46.not(underlying)
  }

  implicit def toRichBoolean(b: Boolean): RichBoolean = new RichBoolean(b)
}

object P49 {
  def gray(n: Int): List[String] = {
    (0 until scala.math.pow(2, n).toInt).toList.map(x => padZero(x.toBinaryString, n))
  }
  private def padZero(s: String, n: Int): String = "0" * (n - s.size) + s
}

object P50 {
  import scala.annotation.tailrec

  trait Tree {
    def count: Int
  }
  case class Node[A](left: Leaf[A], right: Tree) extends Tree {
    override def count: Int = left.count + right.count
  }
  case class Leaf[A](data: A, count: Int) extends Tree

  def huffman[A](list: List[Pair[A, Int]]): List[Pair[A, String]] = {
    val sorted = list.sortWith(_._2 < _._2)
    println(sorted)
    val tree = buildTree(sorted.tail, Leaf(sorted.head._1, sorted.head._2))
    println(tree)
    
    list.map(p => (p._1, code(tree, p._1, "")))
  }
  
  @tailrec private def buildTree[A](list: List[Pair[A, Int]], tree: Tree): Tree = {
    list match {
      case x :: xs => buildTree(xs, appendTree(tree, x))
      case Nil => tree
    }
  }
  private def appendTree[A](tree: Tree, p: Pair[A, Int]): Tree = {
    Node(Leaf(p._1, p._2), tree)
  }
  @tailrec private def code[A](tree: Tree, x: A, cur: String): String = {
    tree match {
      case leaf: Leaf[A] => cur
      case node: Node[A] =>
        if (node.left.data == x) code(node.left, x, cur + "0")
        else code(node.right, x, cur + "1")
    }
  }
}