-
Notifications
You must be signed in to change notification settings - Fork 0
/
HCTree.h
executable file
·102 lines (84 loc) · 3.04 KB
/
HCTree.h
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
/*************************************************************************
*
* Kening Zhang, Gang Yang
* CSE 100, fall 17
* 11/9/2017
* cs100fje cs100fiy
*
* Assignment 3
* Filename: HCTree.h
* Description: set the private public field and the method in tree
* **********************************************************************/
#ifndef HCTREE_H
#define HCTREE_H
#include <queue>
#include <vector>
#include <fstream>
#include "HCNode.h"
#include "BitInputStream.h"
#include "BitOutputStream.h"
using namespace std;
/** A 'function class' for use as the Compare class in a
* priority_queue<HCNode*>.
* For this to work, operator< must be defined to
* do the right thing on HCNodes.
*/
class HCNodePtrComp {
public:
bool operator()(HCNode*& lhs, HCNode*& rhs) const {
return *lhs < *rhs;
}
};
/** A Huffman Code Tree class.
* Not very generic: Use only if alphabet consists
* of unsigned chars.
*/
class HCTree {
private:
HCNode* root;
vector<HCNode*> leaves;
int freqSum; //sum of frequency of nodes
public:
// explicit keyword is used to avoid accidental implicit conversions
explicit HCTree() : root(0),freqSum(0){
leaves = vector<HCNode*>(256, (HCNode*) 0);
}
~HCTree();
/** Use the Huffman algorithm to build a Huffman coding trie.
* PRECONDITION: freqs is a vector of ints, such that freqs[i] is
* the frequency of occurrence of byte i in the message.
* POSTCONDITION: root points to the root of the trie,
* and leaves[i] points to the leaf node containing byte i.
*/
void build(const vector<int>& freqs);
/** Write to the given BitOutputStream
* the sequence of bits coding the given symbol.
* PRECONDITION: build() has been called, to create the coding
* tree, and initialize root pointer and leaves vector.
*/
void encode(byte symbol, BitOutputStream& out) const;
/** Write to the given ofstream
* the sequence of bits (as ASCII) coding the given symbol.
* PRECONDITION: build() has been called, to create the coding
* tree, and initialize root pointer and leaves vector.
* THIS METHOD IS USEFUL FOR STEP 1-3 BUT SHOULD NOT
* BE USED IN THE FINAL SUBMISSION.
*/
void encode(byte symbol, ofstream& out) const;
/** Return symbol coded in the next sequence of bits from the stream.
* PRECONDITION: build() has been called, to create the coding
* tree, and initialize root pointer and leaves vector.
*/
int decode(BitInputStream& in) const;
/** Return the symbol coded in the next sequence of bits (represented as
* ASCII text) from the ifstream.
* PRECONDITION: build() has been called, to create the coding
* tree, and initialize root pointer and leaves vector.
* THIS METHOD IS USEFUL FOR STEP 1-3 BUT SHOULD NOT BE USED
* IN THE FINAL SUBMISSION.
*/
int decode(ifstream& in) const;
int getSum() const;
void deleteNode( HCNode* node);
};
#endif // HCTREE_H