gistfile1.scala

  // a utility class for building up the bits that encodes a char as we trawl down the CodeTree
  case class Coding(char: Char, bits: List[Bit]) {
    def addBit(b: Bit): Coding = this.copy(bits = b :: bits)
  }

  // this method builds up a list of codings for each character in the tree. E.g
  // for a input of Fork(Fork(Leaf('a', 2), Leaf('b', 3), List('a', 'b'), 5), Leaf('d', 4), List('a', 'b', 'd'), 9)
  // it returns List(Coding(a,List(0, 0)), Coding(b,List(0, 1)), Coding(d,List(1)))
  // 
  // recurse down the tree, at each fork, add '0' to each bit pattern from the codings formed from the
  // bit patterns formed from the left tree and add '1' to the bit patterns from the codings formed from
  // right tree, and return the concatination of these two lists
  def codings(tree: CodeTree): List[Coding] = {
    tree match {
      case Fork(left, right, chars, weight) => {
        val fromLeft = for (leftRes <- codings(left)) yield (leftRes.addBit(0))
        val fromRight = for (rightRes <- codings(right)) yield (rightRes.addBit(1))
        fromLeft ::: fromRight
      }
      // we've reached the leaf, so record the char and return to allow the recursion to start building up the 
      // list of bits
      case Leaf(char, weight) => {
        List(Coding(char, List()))
      }
    }
  }

  def encode(tree: CodeTree)(text: List[Char]): List[Bit] = {
      def bitsForChar(char: Char): List[Bit] = {
        codings(tree).find(coding => coding.char == char).map(coding => coding.bits).getOrElse(throw new Exception("character: " + char + " not found in tree"))
      }
    
    // loop over each char in the input text, getting the list of bits for that char
    // this produces a list of lists, so need to flatten to get one long list of bits
    (for (char <- text) yield bitsForChar(char)).flatten
  }