Skip to content

Instantly share code, notes, and snippets.

@dph01
Created October 24, 2012 14:51
Show Gist options
  • Save dph01/3946517 to your computer and use it in GitHub Desktop.
Save dph01/3946517 to your computer and use it in GitHub Desktop.
// 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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment