Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <queue>
- #include <map>
- using namespace std;
- typedef unsigned char byte;
- struct Node{
- byte symbol = '-';
- int freq;
- vector<bool> path;
- int size = 0;
- int lvl = 0;
- Node* lchild = nullptr;
- Node* rchild = nullptr;
- Node(Node* _lchild, Node* _rchild) : lchild(_lchild), rchild(_rchild), freq(_rchild->freq + _lchild->freq){}
- Node(byte _symbol, int _freq) : symbol(_symbol), freq(_freq){}
- Node() = default;
- ~Node(){
- delete lchild;
- delete rchild;
- }
- };
- void State(Node* _node){
- queue<Node*> q;
- q.push(_node);
- Node* it;
- _node->lvl = 1;
- while(q.size()){
- it = q.front();
- if(it->lchild != nullptr){
- q.push(it->lchild);
- it->lchild->lvl = it->lvl + 1;
- }
- if(it->rchild != nullptr){
- q.push(it->rchild);
- it->rchild->lvl = it->lvl + 1;
- }
- for(int i = 0; i < it->lvl; ++i){
- cout << '\t';
- }
- cout << it->symbol << '.';
- for(int i = 0; i < it->path.size(); ++i){
- cout << it->path[i]?1:0;
- }
- cout << '\n';
- q.pop();
- }
- it = nullptr;
- cout << '\n' << '\n';
- }
- void FixSize(Node* _node){
- if(_node->lchild == nullptr){
- _node->size = 1;
- return;
- }
- FixSize(_node->lchild);
- FixSize(_node->rchild);
- _node->size = _node->lchild->size + _node->rchild->size + 1;
- }
- void CalcPath(Node* _node){
- if(_node->lchild == nullptr){
- return;
- }
- _node->lchild->path = _node->path;
- _node->lchild->path.push_back(false);
- _node->rchild->path = _node->path;
- _node->rchild->path.push_back(true);
- }
- byte BFSCalc(Node* _node, map<byte, vector<bool> >& mp){
- byte treeSize = 0;
- queue<Node*> q;
- q.push(_node);
- Node* it = nullptr;
- while(!q.empty()){
- it = q.front();
- q.pop();
- if(it->lchild != nullptr){
- CalcPath(it);
- q.push(it->lchild);
- q.push(it->rchild);
- }
- else{
- treeSize++;
- mp[it->symbol] = it->path;
- }
- }
- return treeSize;
- }
- void WriteBit(bool bit, int& bitIt, vector<byte>& outputData){
- if(bit){
- outputData.back() |= 1 << (8 - bitIt);
- }
- bitIt++;
- if(bitIt == 9){
- outputData.push_back(0);
- bitIt = 1;
- }
- }
- void WriteByte(byte value, int& bitIt, vector<byte>& outputData){
- bool bit;
- for(int i = 1; i < 9; ++i){
- bit = ((value >> (8 - i)) & 1 == 1);
- WriteBit(bit, bitIt, outputData);
- }
- }
- int main(){
- vector<byte> data;
- byte cursor;
- // int n;
- // cin >> n;
- // for(int i = 0; i < n; ++i){
- // cin >> cursor;
- // data.push_back(cursor);
- // }
- while(cin >> cursor){
- data.push_back(cursor);
- }
- vector<byte> symbols(256);
- int size = data.size();
- for(int i = 0; i < size; ++i){
- symbols[(int)data[i]]++;
- }
- vector<Node*> usedSymbols;
- int it = 0;
- Node* newNode = nullptr;
- for(int i = 0; i < 256; ++i){
- if(symbols[i] > 0){
- newNode = new Node((byte)i, symbols[i]);
- usedSymbols.push_back(newNode);
- it = usedSymbols.size() - 1;
- while(it > 0 && usedSymbols[it]->freq > usedSymbols[it - 1]->freq){
- swap(usedSymbols[it], usedSymbols[it - 1]);
- it--;
- }
- }
- }
- Node* node1;
- Node* node2;
- while(usedSymbols.size() > 1){
- node1 = usedSymbols.back();
- usedSymbols.pop_back();
- node2 = usedSymbols.back();
- usedSymbols.pop_back();
- newNode = new Node(node1, node2);
- usedSymbols.push_back(newNode);
- it = usedSymbols.size() - 1;
- while(it > 0 && usedSymbols[it]->freq > usedSymbols[it - 1]->freq){
- swap(usedSymbols[it], usedSymbols[it - 1]);
- it--;
- }
- }
- FixSize(usedSymbols[0]);
- map<byte, vector<bool> > mp;
- byte treeSize = BFSCalc(usedSymbols[0], mp);
- State(usedSymbols[0]);
- cout << '\n';
- vector<byte> outputData;
- outputData.push_back(treeSize);
- outputData.push_back(0);
- int bitIt = 1;
- map<byte, vector<bool> >::iterator iter = mp.begin();
- for(; iter != mp.end(); ++iter){
- WriteByte(iter->first, bitIt, outputData);
- WriteByte((byte)iter->second.size(), bitIt, outputData);
- for(int i = 0; i < iter->second.size(); ++i){
- WriteBit(iter->second[i], bitIt, outputData);
- }
- }
- for(int i = 0; i < data.size(); ++i){
- for(int j = 0; j < mp[data[i]].size(); ++j){
- WriteBit(mp[data[i]][j], bitIt, outputData);
- }
- }
- for(int i = 0; i < outputData.size(); ++i){
- for(int j = 1; j < 9; ++j){
- cout << (((outputData[i] >> (8 - j)) & 1) == 1)?1:0;
- }
- }
- delete usedSymbols[0];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement