1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
package patmat

import common._

/**
  * Assignment 4: Huffman coding
  *
  */
object Huffman {

  /**
    * A huffman code is represented by a binary tree.
    *
    * Every `Leaf` node of the tree represents one character of the alphabet that the tree can encode.
    * The weight of a `Leaf` is the frequency of appearance of the character.
    *
    * The branches of the huffman tree, the `Fork` nodes, represent a set containing all the characters
    * present in the leaves below it. The weight of a `Fork` node is the sum of the weights of these
    * leaves.
    */
  abstract class CodeTree
  case class Fork(left: CodeTree,
                  right: CodeTree,
                  chars: List[Char],
                  weight: Int)
      extends CodeTree

  case class Leaf(char: Char, weight: Int) extends CodeTree

  // Part 1: Basics
  def weight(tree: CodeTree): Int = tree match {
    case f: Fork => weight(f.left) + weight(f.right)
    case l: Leaf => l.weight
  } // tree match ...

  def chars(tree: CodeTree): List[Char] = tree match {
    case f: Fork => chars(f.left) ::: chars(f.right)
    case l: Leaf => l.char :: List()
  } // tree match ...

  def makeCodeTree(left: CodeTree, right: CodeTree) =
    Fork(left,
         right,
         chars(left) ::: chars(right),
         weight(left) + weight(right))

  // Part 2: Generating Huffman trees

  /**
    * In this assignment, we are working with lists of characters. This function allows
    * you to easily create a character list from a given string.
    */
  def string2Chars(str: String): List[Char] = str.toList

  /**
    * This function computes for each unique character in the list `chars` the number of
    * times it occurs. For example, the invocation
    *
    *   times(List('a', 'b', 'a'))
    *
    * should return the following (the order of the resulting list is not important):
    *
    *   List(('a', 2), ('b', 1))
    *
    * The type `List[(Char, Int)]` denotes a list of pairs, where each pair consists of a
    * character and an integer. Pairs can be constructed easily using parentheses:
    *
    *   val pair: (Char, Int) = ('c', 1)
    *
    * In order to access the two elements of a pair, you can use the accessors `_1` and `_2`:
    *
    *   val theChar = pair._1
    *   val theInt  = pair._2
    *
    * Another way to deconstruct a pair is using pattern matching:
    *
    *   pair match {
    *     case (theChar, theInt) =>
    *       println("character is: "+ theChar)
    *       println("integer is  : "+ theInt)
    *   }
    */
  //pattern matching version, but is O(n^2)
//  def times(chars: List[Char]): List[(Char, Int)] = chars.distinct match {
//    case List()  => List()
//    case c :: cs => (c, chars.count((c1: Char) => c == c1)) :: times(cs)
//  }

  //imperative version, runs at O(n)
  def times(chars: List[Char]): List[(Char, Int)] = {
    var d = scala.collection.mutable.Map[Char, Int]()

    for (c <- chars) {
      if (d.contains(c)) d(c) += 1
      else d(c) = 1
    }

    d.toList
  }

  /**
    * Returns a list of `Leaf` nodes for a given frequency table `freqs`.
    *
    * The returned list should be ordered by ascending weights (i.e. the
    * 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] =
    freqs.sortWith((p1: Pair[Char, Int], p2: Pair[Char, Int]) => p1._2 < p2._2) match {
      case List()  => List()
      case p :: ps => new Leaf(p._1, p._2) :: makeOrderedLeafList(ps)
    }

  /**
    * Checks whether the list `trees` contains only one single code tree.
    */
  def singleton(trees: List[CodeTree]): Boolean = trees match {
    case t :: List() => true
    case _           => false
  }

  /**
    * The parameter `trees` of this function is a list of code trees ordered
    * by ascending weights.
    *
    * This function takes the first two elements of the list `trees` and combines
    * them into a single `Fork` node. This node is then added back into the
    * remaining elements of `trees` at a position such that the ordering by weights
    * is preserved.
    *
    * If `trees` is a list of less than two elements, that list should be returned
    * unchanged.
    */
  def combine(trees: List[CodeTree]): List[CodeTree] = trees match {
    case List()      => List()
    case t :: List() => trees
    case t1 :: t2 :: ts => {
      val combined: Fork = makeCodeTree(t1, t2)
      val treeSpan = ts.span((tx: CodeTree) => weight(tx) < combined.weight)
      treeSpan._1 ::: combined :: treeSpan._2
    }
  } //O(n)

  /**
    * This function will be called in the following way:
    *
    *   until(singleton, combine)(trees)
    *
    * where `trees` is of type `List[CodeTree]`, `singleton` and `combine` refer to
    * the two functions defined above.
    *
    * In such an invocation, `until` should call the two functions until the list of
    * code trees contains only one single tree, and then return that singleton list.
    *
    * Hint: before writing the implementation,
    *  - start by defining the parameter types such that the above example invocation
    *    is valid. The parameter types of `until` should match the argument types of
    *    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(s: List[CodeTree] => Boolean, c: List[CodeTree] => List[CodeTree])(
      trees: List[CodeTree]): List[CodeTree] =
    if (s(trees)) trees
    else until(s, c)(c(trees))

  /**
    * This function creates a code tree which is optimal to encode the text `chars`.
    *
    * 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 =
    until(singleton, combine)(makeOrderedLeafList(times(chars)))(0)

  // Part 3: Decoding

  type Bit = Int

  /**
    * 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] = {
    val root = tree

    def loop(tree: CodeTree, bits: List[Bit]): List[Char] = (tree, bits) match {
      case (l: Leaf, List()) => l.char :: List()
      case (f: Fork, List()) =>
        throw new IllegalStateException("Incomplete Bit Stream")

      case (f: Fork, 0 :: bs) => loop(f.left, bs)
      case (f: Fork, 1 :: bs) => loop(f.right, bs)

      case (l: Leaf, b :: bs) => l.char :: loop(root, b :: bs)

    }

    loop(root, bits)
  }

  /**
    * A Huffman coding tree for the French language.
    * Generated from the data given at
    *   http://fr.wikipedia.org/wiki/Fr%C3%A9quence_d%27apparition_des_lettres_en_fran%C3%A7ais
    */
  val frenchCode: CodeTree = Fork(
    Fork(
      Fork(
        Leaf('s', 121895),
        Fork(
          Leaf('d', 56269),
          Fork(
            Fork(Fork(Leaf('x', 5928), Leaf('j', 8351), List('x', 'j'), 14279),
                 Leaf('f', 16351),
                 List('x', 'j', 'f'),
                 30630),
            Fork(
              Fork(
                Fork(Fork(Leaf('z', 2093),
                          Fork(Leaf('k', 745),
                               Leaf('w', 1747),
                               List('k', 'w'),
                               2492),
                          List('z', 'k', 'w'),
                          4585),
                     Leaf('y', 4725),
                     List('z', 'k', 'w', 'y'),
                     9310),
                Leaf('h', 11298),
                List('z', 'k', 'w', 'y', 'h'),
                20608
              ),
              Leaf('q', 20889),
              List('z', 'k', 'w', 'y', 'h', 'q'),
              41497
            ),
            List('x', 'j', 'f', 'z', 'k', 'w', 'y', 'h', 'q'),
            72127
          ),
          List('d', 'x', 'j', 'f', 'z', 'k', 'w', 'y', 'h', 'q'),
          128396
        ),
        List('s', 'd', 'x', 'j', 'f', 'z', 'k', 'w', 'y', 'h', 'q'),
        250291
      ),
      Fork(
        Fork(Leaf('o', 82762), Leaf('l', 83668), List('o', 'l'), 166430),
        Fork(Fork(Leaf('m', 45521), Leaf('p', 46335), List('m', 'p'), 91856),
             Leaf('u', 96785),
             List('m', 'p', 'u'),
             188641),
        List('o', 'l', 'm', 'p', 'u'),
        355071
      ),
      List('s', 'd', 'x', 'j', 'f', 'z', 'k', 'w', 'y', 'h', 'q', 'o', 'l', 'm',
        'p', 'u'),
      605362
    ),
    Fork(
      Fork(
        Fork(
          Leaf('r', 100500),
          Fork(Leaf('c', 50003),
               Fork(Leaf('v', 24975),
                    Fork(Leaf('g', 13288),
                         Leaf('b', 13822),
                         List('g', 'b'),
                         27110),
                    List('v', 'g', 'b'),
                    52085),
               List('c', 'v', 'g', 'b'),
               102088),
          List('r', 'c', 'v', 'g', 'b'),
          202588
        ),
        Fork(Leaf('n', 108812), Leaf('t', 111103), List('n', 't'), 219915),
        List('r', 'c', 'v', 'g', 'b', 'n', 't'),
        422503
      ),
      Fork(Leaf('e', 225947),
           Fork(Leaf('i', 115465), Leaf('a', 117110), List('i', 'a'), 232575),
           List('e', 'i', 'a'),
           458522),
      List('r', 'c', 'v', 'g', 'b', 'n', 't', 'e', 'i', 'a'),
      881025
    ),
    List('s', 'd', 'x', 'j', 'f', 'z', 'k', 'w', 'y', 'h', 'q', 'o', 'l', 'm',
      'p', 'u', 'r', 'c', 'v', 'g', 'b', 'n', 't', 'e', 'i', 'a'),
    1486387
  )

  /**
    * What does the secret message say? Can you decode it?
    * For the decoding use the `frenchCode' Huffman tree defined above.
    */
  val secret: List[Bit] = List(0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0,
    1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0,
    0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1)

  /**
    * Write a function that returns the decoded secret
    */
  def decodedSecret: List[Char] = decode(frenchCode, secret)

  // Part 4a: Encoding using Huffman tree

  /**
    * This function encodes `text` using the code tree `tree`
    * into a sequence of bits.
    */
  def encode(tree: CodeTree)(text: List[Char]): List[Bit] = {
    val root = tree

    def inLeft(fork: Fork, c: Char) = chars(fork.left).contains(c)

    def loop(tree: CodeTree)(text: List[Char]): List[Bit] = (tree, text) match {
      case (_, List()) => List()
      case (f: Fork, c :: cs) =>
        if (inLeft(f, c)) 0 :: loop(f.left)(c :: cs)
        else 1 :: loop(f.right)(c :: cs)
      case (l: Leaf, c :: cs) => loop(root)(cs)
    }

    loop(root)(text)
  }

  // Part 4b: Encoding using code table

  type CodeTable = List[(Char, List[Bit])]

  /**
    * This function returns the bit sequence that represents the character `char` in
    * the code table `table`.
    */
  def codeBits(table: CodeTable)(char: Char): List[Bit] = {
    val map = table.toMap
    map(char)
  } //why????
  /**
    * Given a code tree, create a code table which contains, for every character in the
    * code tree, the sequence of bits representing that character.
    *
    * Hint: think of a recursive solution: every sub-tree of the code tree `tree` is itself
    * 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 = tree match {
    case f: Fork => mergeCodeTables(convert(f.left), convert(f.right))
    case l: Leaf => (l.char, List()) :: List()
  }

  /**
    * 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 = (a, b) match {
    case (Nil, Nil)       => Nil
    case (Nil, c2 :: cs2) => (c2._1, 1 :: c2._2) :: mergeCodeTables(a, cs2)
    case (c1 :: cs1, Nil) => (c1._1, 0 :: c1._2) :: mergeCodeTables(cs1, b)
    case (c1 :: cs1, c2 :: cs2) =>
      (c1._1, 0 :: c1._2) :: (c2._1, 1 :: c2._2) :: mergeCodeTables(cs1, cs2)
  }

  /**
    * This function encodes `text` according to the code tree `tree`.
    *
    * 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 mapper(c: Char) = codeBits(convert(tree))(c)

    def loop(text: List[Char]): List[Bit] = text match {
      case Nil     => Nil
      case c :: cs => mapper(c) ::: loop(cs)
    }

    loop(text)
  }
}