need to decode and encode the following text===
{Newton’s Law of Software Engineering
Law 1: Every Software Engineer continues her/his state of chatting or forwarding mails unless s/he is assigned work by external unbalanced manager.
Law 2: The rate of change in the software is directly proportional to the payment received from client and takes place at the quick rate as when deadline force is applied.
Law 3: For every Use Case Manifestation there is an equal but opposite Software Implementation. }
huffman.h
#ifndef HUFFMAN_H_INC
#define HUFFMAN_H_INC
#include <vector>
#include <map>
#include <queue>
template<typename DataType, typename Frequency> class Hufftree
{
public:
template<typename InputIterator>
Hufftree(InputIterator begin, InputIterator end);
~Hufftree() { delete tree; }
template<typename InputIterator>
std::vector<bool> encode(InputIterator begin, InputIterator end);
std::vector<bool> encode(DataType const& value)
{
return encoding[value];
}
template<typename OutputIterator>
void decode(std::vector<bool> const& v, OutputIterator iter);
private:
class Node;
Node* tree;
typedef std::map<DataType, std::vector<bool> > encodemap;
encodemap encoding;
class NodeOrder;
};
template<typename DataType, typename Frequency>
struct Hufftree<DataType, Frequency>::Node
{
Frequency frequency;
Node* leftChild;
union
{
Node* rightChild; // if leftChild != 0
DataType* data; // if leftChild == 0
};
Node(Frequency f, DataType d):
frequency(f),
leftChild(0),
data(new DataType(d))
{
}
Node(Node* left, Node* right):
frequency(left->frequency + right->frequency),
leftChild(left),
rightChild(right)
{
}
~Node()
{
if (leftChild)
{
delete leftChild;
delete rightChild;
}
else
{
delete data;
}
}
void fill(std::map<DataType, std::vector<bool> >& encoding,
std::vector<bool>& prefix)
{
if (leftChild)
{
prefix.push_back(0);
leftChild->fill(encoding, prefix);
prefix.back() = 1;
rightChild->fill(encoding, prefix);
prefix.pop_back();
}
else
encoding[*data] = prefix;
}
};
template<typename DataType, typename Frequency>
template<typename InputIterator>
Hufftree<DataType, Frequency>::Hufftree(InputIterator begin,
InputIterator end):
tree(0)
{
std::priority_queue<Node*, std::vector<Node*>, NodeOrder> pqueue;
while (begin != end)
{
Node* dataNode = new Node(begin->second, begin->first);
pqueue.push(dataNode);
++begin;
}
while (!pqueue.empty())
{
Node* top = pqueue.top();
pqueue.pop();
if (pqueue.empty())
{
tree = top;
}
else
{
Node* top2 = pqueue.top();
pqueue.pop();
pqueue.push(new Node(top, top2));
}
}
std::vector<bool> bitvec;
tree->fill(encoding, bitvec);
}
template<typename DataType, typename Frequency>
struct Hufftree<DataType, Frequency>::NodeOrder
{
bool operator()(Node* a, Node* b)
{
if (b->frequency < a->frequency)
return true;
if (a->frequency < b->frequency)
return false;
if (!a->leftChild && b->leftChild)
return true;
if (a->leftChild && !b->leftChild)
return false;
if (a->leftChild && b->leftChild)
{
if ((*this)(a->leftChild, b->leftChild))
return true;
if ((*this)(b->leftChild, a->leftChild))
return false;
return (*this)(a->rightChild, b->rightChild);
}
return *(a->data) < *(b->data);
}
};
template<typename DataType, typename Frequency>
template<typename InputIterator>
std::vector<bool> Hufftree<DataType, Frequency>::encode(InputIterator begin,
InputIterator end)
{
std::vector<bool> result;
while (begin != end)
{
typename encodemap::iterator i = encoding.find(*begin);
result.insert(result.end(), i->second.begin(), i->second.end());
++begin;
}
return result;
}
template<typename DataType, typename Frequency>
template<typename OutputIterator>
void Hufftree<DataType, Frequency>::decode(std::vector<bool> const& v,
OutputIterator iter)
{
Node* node = tree;
for (std::vector<bool>::const_iterator i = v.begin(); i != v.end(); ++i)
{
node = *i? node->rightChild : node->leftChild;
if (!node -> leftChild)
{
*iter++ = *(node->data);
node = tree;
}
}
}
#endifhuff.cpp
#include "huffman.h"
#include <map>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;
ostream& operator<<(ostream& os, vector<bool> vec)
{
copy(vec.begin(), vec.end(), ostream_iterator<bool>(os, ""));
return os;
}
int main()
{
std::map<char, double> frequencies;
frequencies['e'] = 0.114864;
frequencies['a'] = 0.078828;
frequencies['t'] = 0.067567;
frequencies['i'] = 0.056306;
frequencies['n'] = 0.065315;
frequencies['o'] = 0.049549;
frequencies['s'] = 0.047297;
frequencies['r'] = 0.054054;
frequencies['l'] = 0.027027;
frequencies['d'] = 0.020270;
frequencies['h'] = 0.024774;
frequencies['c'] = 0.024774;
frequencies['u'] = 0.013513;
frequencies['m'] = 0.013513;
frequencies['f'] = 0.022522;
frequencies['p'] = 0.020270;
frequencies['y'] = 0.011261;
frequencies['g'] = 0.018018;
frequencies['w'] = 0.024774;
frequencies['v'] = 0.006756;
frequencies['b'] = 0.006756;
frequencies['k'] = 0.006756;
frequencies['x'] = 0.002252;
frequencies['L'] = 0.006756;
frequencies['q'] = 0.004504;
frequencies['N'] = 0.002252;
frequencies['S'] = 0.006756;
frequencies['E'] = 0.006756;
frequencies['T'] = 0.002252;
frequencies['F'] = 0.002252;
frequencies['U'] = 0.002252;
frequencies['I'] = 0.002252;
frequencies['M'] = 0.002252;
frequencies['1'] = 0.002252;
frequencies['.'] = 0.006756;
frequencies['_'] = 0.162162;
frequencies['2'] = 0.002252;
frequencies[':'] = 0.004504;
frequencies['`'] = 0.002252;
Hufftree<char, double> hufftree(frequencies.begin(), frequencies.end());
for (char ch = '1'; ch <= '2'; ++ch)
{
cout << ch << ": " << hufftree.encode(ch) << "\n";
}
if (char ch = '.')
{
cout << ch << ": " << hufftree.encode(ch) << "\n";
}
if (char ch = '_')
{
cout << ch << ": " << hufftree.encode(ch) << "\n";
}
if (char ch = ':')
{
cout << ch << ": " << hufftree.encode(ch) << "\n";
}
if (char ch = '`')
{
cout << ch << ": " << hufftree.encode(ch) << "\n";
}
for (char ch = 'a'; ch <= 'z'; ++ch)
{
cout << ch << ": " << hufftree.encode(ch) << "\n";
}
for (char ch = 'A'; ch <= 'Z'; ++ch)
{
cout << ch << ": " << hufftree.encode(ch) << "\n";
}
string source="Newton`s_Law_of_Software_Engineering_continues";
vector<bool> encoded = hufftree.encode(source.begin(), source.end());
cout << encoded << "\n";
string destination;
hufftree.decode(encoded, std::back_inserter(destination));
cout << destination << "\n";
cin.get();cin.get();
}okay actually my program runs perfectly without any errors if i input a small part of the paragraph as a string but the problem arises when i input the whole paragraph as a source string .......it breaks and doesnt run....so can someone help me to encode and decode the whole paragraph.....