huffman-encoding/test_huffman.cc at master · rcannon/huffman-encoding · GitHub

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
/*
 * test_huffman: test the Huffman class
 */

#include "huffman.hh"
#include <iostream>
#include <cassert>
#include <climits>

//////////////////////////////////////////////////////////////////////////////
// Ensure the encoder actually modifies the coding' length as expected
void test_encode()
{
  Huffman huff;

  auto bits = huff.encode('a');
  assert(bits.size() > CHAR_BIT);

  bits = huff.encode('b');
  assert(bits.size() > CHAR_BIT);

  bits = huff.encode('a');
  assert(bits.size() < CHAR_BIT);

  bits = huff.encode('b');
  assert(bits.size() < CHAR_BIT);

  bits = huff.encode('b');
  assert(bits.size() == huff.encode('a').size());

  bits = huff.encode('b');
  bits = huff.encode('b');
  bits = huff.encode('b');
  assert(bits.size() < huff.encode('a').size());
}

//////////////////////////////////////////////////////////////////////////////
// A utility function that takes a collection of bits and a Huffman tree, and
// figures out which symbol these bits encode.
int decode_symbol(Huffman& huff, const Huffman::bits_t& bits)
{
  int symbol = -1;

  for (auto b : bits) {
    symbol = huff.decode(b);
  }
  assert(symbol >= 0);
  return symbol;
}

//////////////////////////////////////////////////////////////////////////////
// Ensure decoding returns the same symbol that was encoded, in different
// scenarios.
void test_decode()
{
  Huffman encoder, decoder;

  auto bits = encoder.encode('a');
  assert(decode_symbol(decoder, bits) == 'a');
  bits = encoder.encode('a');
  assert(decode_symbol(decoder, bits) == 'a');
  bits = encoder.encode('b');
  assert(decode_symbol(decoder, bits) == 'b');
  bits = encoder.encode('a');
  assert(decode_symbol(decoder, bits) == 'a');
  bits = encoder.encode(Huffman::HEOF);
  assert(decode_symbol(decoder, bits) == Huffman::HEOF);
}

void more1() // encoding end_of_file and 0 -- multiple times
{
  Huffman encoder, decoder;

  auto bits = encoder.encode(256);
  assert(decode_symbol(decoder, bits) == 256);

  bits = encoder.encode(0);
  assert(decode_symbol(decoder, bits) == 0);

  bits = encoder.encode(256);
  assert(decode_symbol(decoder, bits) == 256);

  bits = encoder.encode(0);
  assert(decode_symbol(decoder, bits) == 0);

  bits = encoder.encode(256);
  assert(decode_symbol(decoder, bits) == 256);

  bits = encoder.encode(0);
  assert(decode_symbol(decoder, bits) == 0);

  bits = encoder.encode(0);
  assert(decode_symbol(decoder, bits) == 0);
}

void more2() // test all ascii chars
{
  Huffman::bits_t bits;
  Huffman encoder, decoder;
  for (int i = 0; i < 257; i++)
  {
    bits = encoder.encode(i);
    assert(decode_symbol(decoder, bits) == i);
  }
}

void more3() // this came in handy for encoder part
{
  Huffman huff;
  huff.encode('h');
  huff.encode(Huffman::HEOF);
}


//////////////////////////////////////////////////////////////////////////////
int main()
{
  test_encode();
  test_decode();
  more1();
  more2();
  more3();
  std::cout << "yay!" << "\n";
  return 0;
}