#include <iostream>
#include <string>
#include <fstream>
#include <math.h>
#define PSEUDO_EOF 3
using namespace std;
struct HuffmanTree{
unsigned char letter; // the unsigned character of each code
int count; // frequency of each unsigned character
int left; // the left child of each node
int right; // the right child of each node
int parent; // the parent of each node
public:
bool operator==(const HuffmanTree& node) const;
bool operator!=(const HuffmanTree& node) const;
};
bool HuffmanTree::operator==(const HuffmanTree& node) const
{
return node.count == count && node.letter == letter && node.left == left && node.right == right && node.parent == parent;
}
bool HuffmanTree::operator!=(const HuffmanTree& node) const
{
return node.count != count || node.letter != letter || node.left != left || node.right != right || node.parent != parent;
}
class AdaptiveTree {
public:
AdaptiveTree(int rootNum);
AdaptiveTree(int rootNum, string str);
void swap(int first, int second); // swap two nodes of the tree
void initalCode(); // initializing the data
string char2code(unsigned char letter); // locate the character in the tree with its corresponding binary string and return the string
string char2binary(unsigned char letter); // translating the character to the 8-bit binary string
unsigned char binary2char(string bin); // translating the binary string: bin to the corresponding character
int spawn(unsigned char letter); // add a new character to the original tree
void updateTree(unsigned char newchar); // update the tree
int highestInBlock(int count); // return the highest node to be exchanged
void setString(string str); //
string decodingStr() const;
void encoding();
string decoding();
unsigned char code2char(string bincode);
static int size();
string binStr() const; // return the binary string of string: tempString
private:
void run();
int findchar(unsigned char letter ); // locate the letter in the tree
string tempString; //temp string to be encoded needed to be stored here
string deStr;// used for storing the decoding string
string bin; // used for storing the result of encoding process
/* Adaptive Tree data members */
HuffmanTree *tree;
int root;
/* Adaptive Tree constants */
static int ALPH_SIZE; // size of the alphabet
static unsigned char none; // not a unsigned character
static unsigned char NYT; // Not Yet transmitted code
};
int AdaptiveTree::ALPH_SIZE = 1024;
unsigned char AdaptiveTree::NYT = 255;
unsigned char AdaptiveTree::none = 254;
string AdaptiveTree::decodingStr() const
{
return deStr;
}
unsigned char AdaptiveTree::binary2char(string bin)
{
int n = bin.length();
int tempchar=0,i;
for (i=0; i<n; i++)
{
tempchar += (bin[i] - '0') * (int)pow(2,i);
}
return (unsigned char)(tempchar);
}
int AdaptiveTree::size()
{
return ALPH_SIZE;
}
AdaptiveTree::AdaptiveTree(int rootNum)
{
root = rootNum;
initalCode();
run();
}
AdaptiveTree::AdaptiveTree(int rootNum, string str)
{
root = rootNum;
setString(str);
initalCode();
run();
}
void AdaptiveTree::initalCode()
{
int i;
//
tree = new HuffmanTree[ALPH_SIZE];
if (!tree) {
return;
}
for (i = 0; i < ALPH_SIZE; i++)
{
tree[i].letter = none;
tree[i].count = 0;
tree[i].left = 0;
tree[i].right = 0;
tree[i].parent = 0;
}
tree[root].letter = NYT;
}
int AdaptiveTree::findchar( unsigned char letter )
{
int i;
for (i = 0; i < ALPH_SIZE; i++ )
{
if (letter == tree[i].letter)
return i;
}
return -1; //not found in the tree
}
string AdaptiveTree::char2code(unsigned char letter)
{
string buffer = "";
HuffmanTree current;
int n = findchar(letter);
if (n>=0)
{
bool flag = false;
current = tree[n];
while (current != tree[root])
{
flag = true;
if( current == tree[tree[current.parent].left]) {
buffer.insert(0,"0");
}
else if( current == tree[tree[current.parent].right]){
buffer.insert(0,"1");
}
current = tree[current.parent];
}
if (flag==false)
{
buffer = char2binary(letter);
}
}
else
{
buffer = char2binary(letter);
}
return buffer;
}
string AdaptiveTree::char2binary(unsigned char letter)
{
int n = static_cast<int>(letter);
string buffer;
char ch[1];
int frequency=0;
while (n > 0)
{
sprintf(ch,"%d",n%2);
buffer.append(ch);
n = n/2;
frequency++;
}
int t = 8-frequency; //不足8位,字符串前补零
while (t!=0)
{
ch[0] = '0';
buffer.append(ch);
t--;
}
return buffer;
}
void AdaptiveTree::run()
{// simulating the encoding and decoding process
//encoding
encoding();
initalCode(); // reset to prepare for decoding
// decoding
deStr = decoding();
}
void AdaptiveTree::encoding()
{
string code;
unsigned char hold;
int i ;
// encoding
for (i=0; i < tempString.length(); i++)
{
hold = tempString[i];
int n = findchar(hold);
if (n>=0) {// found in the tree
code = char2code( hold ); // translated into the corresponding binary code
updateTree(hold);
bin+=code;
}
else { //not found in the tree
code = char2code(NYT); // translated into the corresponding binary code
updateTree(hold);
bin+=code;
code = char2binary(hold);
bin+=code;
}
}
}
string AdaptiveTree::decoding()
{//decoding function
int i = 0;
bool stateSwitch = true;
unsigned char ch;
string bstr, str;
//start
while (true)
{
HuffmanTree current = tree[root]; // Go to the root of the tree
while( current.left != 0 || current.right != 0 )
{ // it is not a leaf node
if (bin[i] == '1')
{// move right down the tree
current = tree[current.right];
}
else if (bin[i] == '0')
{// move left down the tree
current = tree[current.left];
}
i++;
}
//it is a leaf node
if (current.letter==NYT)
{
if (stateSwitch==true)
{
i+=8; stateSwitch = false;
}
bstr = bin.substr(i,8);
ch = binary2char(bstr);
i+=8;
}
else {
ch = current.letter;
}
str += ch;
updateTree(ch);
if(i>=bin.size()) break;
}
return str;
}
unsigned char AdaptiveTree::code2char(string bincode)
{
HuffmanTree current = tree[root];
for (int i=0; i < bincode.length(); i++) {
// check if current binary digit is valid
// go left
if (bincode[i] == '0') {
if (current.left==0) return 0; // leaf node is encounted
else
current = tree[current.left];
//go right
} else if (bincode[i] == '1') {
if (current.right==0) return 0; // leaf node is encounted
else
current = tree[current.right];
}
}
return current.letter;
}
void AdaptiveTree::swap(int first, int second)
{
int temp;
unsigned char tempchar;
// swap return pointers
tree[tree[first].left].parent = second;
tree[tree[first].right].parent = second;
tree[tree[second].left].parent = first;
tree[tree[second].right].parent = first;
// swap left pointers
temp = tree[second].left;
tree[second].left = tree[first].left;
tree[first].left = temp;
// swap right pointers
temp = tree[second].right;
tree[second].right = tree[first].right;
tree[first].right = temp;
// swap data
tempchar = tree[second].letter;
tree[second].letter = tree[first].letter;
tree[first].letter = tempchar;
temp = tree[second].count;
tree[second].count = tree[first].count;
tree[first].count = temp;
}
int AdaptiveTree::spawn(unsigned char letter)
{//insert the character : letter into the tree
int oldNYTindex;
HuffmanTree *oldNYT;
oldNYTindex = findchar(NYT);
oldNYT = &tree[oldNYTindex];
oldNYT->letter = none;
评论19