#include "adaptiveHuffman.h"
int AdaptiveHuffman::sum = 1;
BinaryTree::BinaryTree(int num,int weight){
p_root = new Node(nullptr,nullptr,nullptr);
p_root->num = num;
p_root->weight = weight;
}
BinaryTree::~BinaryTree()
{
deleteNode(p_root);
}
bool BinaryTree::swap(Node * p_nodeA, Node * p_nodeB)
{
if(p_nodeA==nullptr||p_nodeB==nullptr||p_nodeA==p_nodeB)
return false;
Node *pTemp;
if (getBrotherState(p_nodeA)==LeftChild) {
if (getBrotherState(p_nodeB)==LeftChild) {
pTemp = p_nodeA->parent->leftChild;
p_nodeA->parent->leftChild = p_nodeB->parent->leftChild;
p_nodeB->parent->leftChild = pTemp;
}
else {
pTemp = p_nodeA->parent->leftChild;
p_nodeA->parent->leftChild = p_nodeB->parent->rightChild;
p_nodeB->parent->rightChild = pTemp;
}
}
else {
if (getBrotherState(p_nodeB)==LeftChild) {
pTemp = p_nodeA->parent->rightChild;
p_nodeA->parent->rightChild = p_nodeB->parent->leftChild;
p_nodeB->parent->leftChild = pTemp;
}
else {
pTemp = p_nodeA->parent->rightChild;
p_nodeA->parent->rightChild = p_nodeB->parent->rightChild;
p_nodeB->parent->rightChild = pTemp;
}
}
pTemp = p_nodeA->parent;
p_nodeA->parent = p_nodeB->parent;
p_nodeB->parent = pTemp;
return true;
}
bool BinaryTree::addNode(Node * parent, Node * p_child, Brother brotherState)
{
if(parent==nullptr||p_child==nullptr)
return false;
if (brotherState == LeftChild) {
if (parent->leftChild != nullptr) {
std::cout << "error:left child exist!" << std::endl;
return false;
}
parent->leftChild = p_child;
}
else if (brotherState == RightChild) {
if (parent->rightChild != nullptr) {
std::cout << "error:right child exist!" << std::endl;
return false;
}
parent->rightChild = p_child;
}
else {
std::cout << "error:brotherState is wrong!" << std::endl;
return false;
}
p_child->parent = parent;
return true;
}
Node * BinaryTree::findNode(Node *p)
{
Node *p_node = p_root;
std::queue<Node *> queue;
queue.push(p_node);
while (!queue.empty()) {
p_node = queue.front();
if (p_node == p) {
return p_node;
}
queue.pop();
if (p_node->leftChild != nullptr) {
queue.push(p_node->leftChild);
}
if (p_node->rightChild != nullptr) {
queue.push(p_node->rightChild);
}
}
return nullptr;
}
bool BinaryTree::setNodeNum(Node* p_node, int num)
{
if(p_node==nullptr)
return false;
else {
p_node->num = num;
return true;
}
}
bool BinaryTree::isAncestor(Node * p_nodeChild, Node * p_nodeAncestor)
{
while (p_nodeChild != p_root) {
if (p_nodeChild == p_nodeAncestor) {
return true;
}
else {
p_nodeChild = p_nodeChild->parent;
}
}
return false;
}
void BinaryTree::deleteNode(Node *p_node)
{
if (p_node->leftChild!=nullptr) {
deleteNode(p_node->leftChild);
}
if (p_node->rightChild != nullptr) {
deleteNode(p_node->rightChild);
}
delete p_node;
}
BinaryTree::Brother BinaryTree::getBrotherState(Node *p_node)
{
if (p_node->parent->leftChild == p_node) {
return LeftChild;
}
else {
return RightChild;
}
}
AdaptiveHuffman::AdaptiveHuffman():tree(0,0)
{
}
AdaptiveHuffman::~AdaptiveHuffman()
{
os.close();
is.close();
}
bool AdaptiveHuffman::ReadFile(char * filename)
{
is.open(filename, std::ios_base::in);
if (!is.is_open()) {
cout << "error: " << filename << " is not exist!" << endl;
return false;
}
return true;
}
std::string AdaptiveHuffman::getHuffmanCode(Node *p_n)
{
std::string huffmanCode = "";
std::stack<Node *> stack;
std::deque<char> code;
while (p_n != tree.getRoot()) {
if (tree.getBrotherState(p_n) == tree.LeftChild) {
code.push_back('0');
}
else {
code.push_back('1');
}
p_n = p_n->parent;
}
while (!code.empty()) {
huffmanCode += code.back();
code.pop_back();
}
return huffmanCode;
}
Node * AdaptiveHuffman::findLarge(Node *p_node)
{
std::stack<Node *> stack;
Node *p = tree.getRoot();
Node *large = p;
while (p || !stack.empty()) {
if (p != nullptr) {
stack.push(p);
if (p->weight == p_node->weight) {
if (large->weight != p->weight) {
large = p;
}
else if(large->num > p->num){
large = p;
}
}
p = p->leftChild;
}
else {
p = stack.top();
stack.pop();
p = p->rightChild;
}
}
if (large == tree.getRoot()) {
return p_node;
}
return large;
}
bool AdaptiveHuffman::encode(char * out_filename)
{
if (!is.is_open()) {
cout << "error: no file read!" << endl;
return false;
}
os.open(out_filename, std::ios_base::out);
if (!os.is_open()) {
cout << "error: can not open file to write!" << endl;
}
char cbuffer;
Node *nyt = tree.getRoot();
while (!is.eof()) {
cbuffer = is.get();
bool exist = false;
std::string code;
auto existNode = buffers.begin();
for (existNode; existNode != buffers.end(); existNode++) {
if (existNode->key == cbuffer) {
code = existNode->value;
for (int i = 0; '\0' != code[i]; i++) {
os << code[i];
}
exist = true;
break;
}
}
if (exist) {
Node *root = existNode->p;
weightAdd(root);
}
else {
Node *c = new Node(nullptr, nullptr, nyt);
c->num = sum++;
c->weight = 1;
Node *NYT = new Node(nullptr, nullptr, nyt);
NYT->num = sum++;
NYT->weight = 0;
tree.addNode(nyt, NYT, BinaryTree::LeftChild);
tree.addNode(nyt, c, BinaryTree::RightChild);
nyt->weight = 1;
code = getHuffmanCode(nyt);
for (int i = 0; '\0' != code[i]; i++) {
os << code[i];
}
os << cbuffer;
charMap* new_cm = new charMap();
new_cm->key = cbuffer;
new_cm->p = nyt->rightChild;
new_cm->value = getHuffmanCode(nyt->rightChild);
buffers.push_back(*new_cm);
Node *root = nyt->parent;
weightAdd(root);
nyt = nyt->leftChild;
}
}
return false;
}
void AdaptiveHuffman::weightAdd(Node * p_node)
{
while (p_node != nullptr) {
Node* large = findLarge(p_node);
if (large != p_node && !tree.isAncestor(p_node, large)) {
tree.swap(large, p_node);
int temp;
temp = large->num;
large->num = p_node->num;
p_node->num = temp;
for (auto iterator = buffers.begin(); iterator != buffers.end(); iterator++) {
iterator->value = getHuffmanCode(iterator->p);
}
}
p_node->weight++;
p_node = p_node->parent;
}
}
