diff options
| -rw-r--r-- | Scala/patmat/src/main/scala/patmat/Huffman.scala | 98 |
1 files changed, 83 insertions, 15 deletions
diff --git a/Scala/patmat/src/main/scala/patmat/Huffman.scala b/Scala/patmat/src/main/scala/patmat/Huffman.scala index a40c212..9796fdd 100644 --- a/Scala/patmat/src/main/scala/patmat/Huffman.scala +++ b/Scala/patmat/src/main/scala/patmat/Huffman.scala @@ -26,9 +26,15 @@ object Huffman { // Part 1: Basics - def weight(tree: CodeTree): Int = ??? // tree match ... + def weight(tree: CodeTree): Int = tree match { + case Leaf(c, w) => w + case Fork(l, r, c, w) => w + } - def chars(tree: CodeTree): List[Char] = ??? // tree match ... + def chars(tree: CodeTree): List[Char] = tree match { + case Leaf(c, w) => c :: Nil + case Fork(l, r, c, w) => c + } def makeCodeTree(left: CodeTree, right: CodeTree) = Fork(left, right, chars(left) ::: chars(right), weight(left) + weight(right)) @@ -71,7 +77,10 @@ object Huffman { * println("integer is : "+ theInt) * } */ - def times(chars: List[Char]): List[(Char, Int)] = ??? + def times(chars: List[Char]): List[(Char, Int)] = { + def counts(chs: List[Char]): List[Int] = if (chs.isEmpty) Nil else chars.count(c => c == chs.head) :: counts(chs.tail) + chars.distinct.zip(counts(chars.distinct)) + } /** * Returns a list of `Leaf` nodes for a given frequency table `freqs`. @@ -80,12 +89,17 @@ object Huffman { * head of the list should have the smallest weight), where the weight * of a leaf is the frequency of the character. */ - def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] = ??? + def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] = { + freqs.sortWith((p1, p2) => p1._2 < p2._2).map(p => new Leaf(p._1, p._2)) + } /** * Checks whether the list `trees` contains only one single code tree. */ - def singleton(trees: List[CodeTree]): Boolean = ??? + def singleton(trees: List[CodeTree]): Boolean = trees match { + case x :: Nil => true + case _ => false + } /** * The parameter `trees` of this function is a list of code trees ordered @@ -99,7 +113,16 @@ object Huffman { * If `trees` is a list of less than two elements, that list should be returned * unchanged. */ - def combine(trees: List[CodeTree]): List[CodeTree] = ??? + def combine(trees: List[CodeTree]): List[CodeTree] = { + def insert(x: Fork, xs: List[CodeTree]): List[CodeTree] = xs match { + case List() => x :: Nil + case y :: ys => if ( weight(x) < weight(y) ) x :: xs else y :: insert(x, ys) + } + trees match { + case x :: y :: xs => insert(makeCodeTree(x, y), xs) + case _ => trees + } + } /** * This function will be called in the following way: @@ -118,7 +141,8 @@ object Huffman { * the example invocation. Also define the return type of the `until` function. * - try to find sensible parameter names for `xxx`, `yyy` and `zzz`. */ - def until(xxx: ???, yyy: ???)(zzz: ???): ??? = ??? + def until(done: List[CodeTree] => Boolean, reduce: List[CodeTree] => List[CodeTree])(trees: List[CodeTree]): List[CodeTree] = + if (done(trees)) trees else until(done, reduce)(reduce(trees)) /** * This function creates a code tree which is optimal to encode the text `chars`. @@ -126,7 +150,8 @@ object Huffman { * The parameter `chars` is an arbitrary text. This function extracts the character * frequencies from that text and creates a code tree based on them. */ - def createCodeTree(chars: List[Char]): CodeTree = ??? + def createCodeTree(chars: List[Char]): CodeTree = + until(singleton,combine)(makeOrderedLeafList(times(chars))).head @@ -138,7 +163,16 @@ object Huffman { * This function decodes the bit sequence `bits` using the code tree `tree` and returns * the resulting list of characters. */ - def decode(tree: CodeTree, bits: List[Bit]): List[Char] = ??? + def decode(tree: CodeTree, bits: List[Bit]): List[Char] = { + def decodeRec (subTree: CodeTree, bits: List[Bit], chars: List[Char]): List[Char] = subTree match { + case Leaf(c, w) => decodeRec(tree, bits, chars ::: c :: Nil) + case Fork(l, r, c, w) => bits match { + case b :: bs => if (b == 0) decodeRec(l, bs, chars) else decodeRec(r, bs, chars) + case _ => chars + } + } + decodeRec(tree, bits, Nil) + } /** * A Huffman coding tree for the French language. @@ -156,7 +190,7 @@ object Huffman { /** * Write a function that returns the decoded secret */ - def decodedSecret: List[Char] = ??? + def decodedSecret: List[Char] = decode(frenchCode, secret) @@ -166,7 +200,20 @@ object Huffman { * This function encodes `text` using the code tree `tree` * into a sequence of bits. */ - def encode(tree: CodeTree)(text: List[Char]): List[Bit] = ??? + def encode(tree: CodeTree)(text: List[Char]): List[Bit] = { + def checkSub(sub: CodeTree, char: Char): Boolean = sub match { + case Leaf(c, w) => c == char + case Fork(l, r, c, w) => c.contains(char) + } + def encodeRec(subTree: CodeTree, text: List[Char], bits: List[Bit]): List[Bit] = text match { + case Nil => bits + case _ => subTree match { + case Leaf(c, w) => encodeRec(tree, text.tail, bits) + case Fork(l, r, c, w) => if (checkSub(l,text.head)) encodeRec(l, text, bits ::: 0 :: Nil) else encodeRec(r, text, bits ::: 1 :: Nil) + } + } + encodeRec(tree, text, Nil) + } // Part 4b: Encoding using code table @@ -177,7 +224,10 @@ object Huffman { * This function returns the bit sequence that represents the character `char` in * the code table `table`. */ - def codeBits(table: CodeTable)(char: Char): List[Bit] = ??? + def codeBits(table: CodeTable)(char: Char): List[Bit] = table match { + case Nil => Nil + case (c, bits) :: xs => if (c == char) bits else codeBits(xs)(char) + } /** * Given a code tree, create a code table which contains, for every character in the @@ -187,14 +237,25 @@ object Huffman { * a valid code tree that can be represented as a code table. Using the code tables of the * sub-trees, think of how to build the code table for the entire tree. */ - def convert(tree: CodeTree): CodeTable = ??? + def convert(tree: CodeTree): CodeTable = { + def prependBit(bit: Bit, table: CodeTable) = { + table.map(x => (x._1, bit :: x._2)) + } + def convertRec(subTree: CodeTree, table: CodeTable, bits: Bit): CodeTable = subTree match { + case Leaf(c, w) => (c, Nil) :: Nil + case Fork(l, r, c, w) => { + mergeCodeTables(prependBit(0,convertRec(l, table, 0)), prependBit(1,convertRec(r, table, 1))) + } + } + convertRec(tree, Nil, 2) + } /** * This function takes two code tables and merges them into one. Depending on how you * use it in the `convert` method above, this merge method might also do some transformations * on the two parameter code tables. */ - def mergeCodeTables(a: CodeTable, b: CodeTable): CodeTable = ??? + def mergeCodeTables(a: CodeTable, b: CodeTable): CodeTable = a ::: b /** * This function encodes `text` according to the code tree `tree`. @@ -202,5 +263,12 @@ object Huffman { * To speed up the encoding process, it first converts the code tree to a code table * and then uses it to perform the actual encoding. */ - def quickEncode(tree: CodeTree)(text: List[Char]): List[Bit] = ??? + def quickEncode(tree: CodeTree)(text: List[Char]): List[Bit] = { + val codeTable = convert(tree) + def encodeRec(text: List[Char], bits: List[Bit]): List[Bit] = text match { + case Nil => bits + case x :: xs => encodeRec(xs, bits ::: codeBits(codeTable)(x)) + } + encodeRec(text, Nil) + } } |