Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<string>
- #include<fstream>
- using namespace std;
- class cnode
- {
- public:
- int frequency;
- char name[256];
- string encryption;
- cnode *pnext;
- cnode *pleft = NULL;;
- cnode *pright = NULL;
- cnode *pdown = NULL;
- };
- class clist
- {
- public:
- cnode *phead;
- cnode *ptail;
- clist()
- {
- phead = NULL;
- ptail = NULL;
- }
- ~clist()
- {
- cnode *ptrav = phead;
- while (ptrav != NULL)
- {
- phead = phead->pnext;
- delete ptrav;
- ptrav = phead;
- }
- }
- void Attach(cnode *pnn)
- {
- if (phead == NULL)
- {
- phead = pnn;
- ptail = pnn;
- }
- else
- {
- ptail->pnext = pnn;
- ptail = pnn;
- }
- }
- void sortAttach(cnode *pnn)
- {
- cnode *pB = NULL;
- cnode *ptrav = phead;
- while (ptrav != NULL)
- {
- if (ptrav->frequency > pnn->frequency)
- {
- break;
- }
- pB = ptrav;
- ptrav = ptrav->pnext;
- }
- if (ptrav != NULL)
- {
- if (pB != NULL)
- {
- pB->pnext = pnn;
- pnn->pnext = ptrav;
- }
- else
- {
- pnn->pnext = ptrav;
- phead = pnn;
- }
- }
- else
- {
- pB->pnext = pnn;
- pnn->pnext = NULL;
- }
- }
- void combine(cnode *pnn, cnode *ptrav)
- {
- cnode *pnn2;
- pnn2 = new cnode;
- cnode *tnext;
- cnode *tdown;
- tdown = new cnode;
- tnext = pnn->pnext;
- pnn2->frequency = pnn->frequency + tnext->frequency;
- int k = 0;
- //copy name pnn
- for (int i = 0; i < 256; i++)
- {
- if (pnn->name[i] != '\0')
- {
- pnn2->name[k] = pnn->name[i];
- k++;
- }
- else
- {
- break;
- }
- }
- //copy name pnext
- for (int i = 0; i < 256; i++)
- {
- if (tnext->name[i] != '\0')
- {
- pnn2->name[k] = tnext->name[i];
- k++;
- }
- else
- {
- break;
- }
- }
- //make rest of array null
- pnn2->name[k] = '\0';
- //set tdown
- for (int i = 0; pnn2->name[i]!='\0'; i++)
- {
- tdown->name[i] = pnn2->name[i];
- }
- tdown->frequency = pnn2->frequency;
- //set tree
- //check pnn
- if (pnn->pdown != NULL)
- {
- tdown->pleft = pnn->pdown;
- }
- else
- {
- tdown->pleft = pnn;
- }
- //check tnext
- if (tnext->pdown != NULL)
- {
- tdown->pright = tnext->pdown;
- }
- else
- {
- tdown->pright = tnext;
- }
- pnn2->pdown = tdown;
- //sortAttach
- cnode *pB = NULL;
- while (ptrav != NULL)
- {
- if (ptrav->frequency > pnn2->frequency)
- {
- break;
- }
- pB = ptrav;
- ptrav = ptrav->pnext;
- }
- if (ptrav != NULL)
- {
- pB->pnext = pnn2;
- pnn2->pnext = ptrav;
- }
- else
- {
- pB->pnext = pnn2;
- pnn2->pnext = ptrav;
- }
- }
- void binsearch(cnode *pnn)
- {
- cnode *ptrav;
- string bin;
- int flag = 0;
- ptrav = pnn;
- cout << "input binary" << endl;
- cin >> bin;
- for (int i = 0; i < bin.length(); i++)
- {
- if (ptrav != NULL)
- {
- if (bin[i] == '0')
- {
- ptrav = ptrav->pleft;
- }
- else
- {
- if (bin[i] == '1')
- {
- ptrav = ptrav->pright;
- }
- else
- {
- flag = 1;
- break;
- }
- }
- }
- else
- {
- break;
- }
- }
- cout << endl << "-------------------------------" << endl;
- if (ptrav != NULL && flag==0)
- {
- for (int i = 0; i < 256; i++)
- {
- if (ptrav->name[i] != ' ')
- {
- cout << ptrav->name[i];
- }
- else
- {
- break;
- }
- }
- cout << " : " << ptrav->frequency << endl;
- }
- else
- {
- cout << "node not found" << endl;
- }
- }
- void searchBin(cnode *pnn)
- {
- cnode *ptrav;
- ptrav = pnn;
- char code[1];
- int flag = 0;
- cin >> code[0];
- while (ptrav->pleft != NULL && ptrav->pright != NULL)
- {
- for (int i = 0; i < 256; i++)
- {
- if (ptrav->pleft->name[i] == code[0])
- {
- ptrav = ptrav->pleft;
- break;
- }
- if (ptrav->pright->name[i] == code[0])
- {
- ptrav = ptrav->pright;
- break;
- }
- }
- }
- pnn = ptrav;
- for (int i = 0; i < 256; i++)
- {
- if (pnn->name[i] != ' ')
- {
- cout << pnn->name[i];
- }
- else
- {
- break;
- }
- }
- cout << " : " << pnn->frequency << endl;
- }
- void searchEnc(cnode *pnn, cnode *pnn2)
- {
- cnode *ptrav;
- ptrav = pnn;
- string encryption;
- char code[1];
- int flag = 0;
- code[0] = pnn2->name[0];
- while (ptrav->pleft != NULL && ptrav->pright != NULL)
- {
- for (int i = 0; i < 256; i++)
- {
- if (ptrav->pleft->name[i] == code[0])
- {
- ptrav = ptrav->pleft;
- encryption += '0';
- break;
- }
- if (ptrav->pright->name[i] == code[0])
- {
- ptrav = ptrav->pright;
- encryption += '1';
- break;
- }
- }
- }
- pnn = ptrav;
- for (int i = 0; pnn->name[i] != '\0'; i++)
- {
- if (pnn->name[i] != '\0')
- {
- cout << pnn->name[i];
- }
- }
- pnn2->encryption = encryption;
- cout << " : " << pnn2->frequency << " : " << pnn2->encryption << endl;
- }
- };
- int main()
- {
- cnode *pnn;
- cnode *t, *t2;
- clist l, lcopy;
- int c = 0, flag = 0, n;
- //string p;
- //getline(cin, p);
- ofstream fl2("decompressed.png", ofstream::binary);
- ifstream fl("2.png", ifstream::binary);
- fl.seekg(0, fl.end);
- int h = fl.tellg();
- cout << h << endl;
- fl.seekg(0, fl.beg);
- string p = "";
- char cpto = 0;
- char ch = 0;
- for (int i = 0; i < h; i++)
- {
- fl.read(&ch, 1);
- p += ch;
- //fl2.write(&ch, 1);
- }
- /*for (int i = 0; i < h; i++)
- {
- fl2.write(&word[i], 1);
- }*/
- pnn = new cnode;
- pnn->name[0] = p[0];
- pnn->name[1] = '\0';
- pnn->frequency = 1;
- for (int i = 1; i < p.length(); i++)
- {
- if (p[i] == pnn->name[0])
- {
- pnn->frequency++;
- }
- }
- l.Attach(pnn);
- c++;
- for (int i = c; i < p.length(); i++)
- {
- t = l.phead;
- while (t != NULL)
- {
- if (p[c] == t->name[0])
- {
- flag = 1;
- break;
- }
- t = t->pnext;
- }
- if (flag != 1)
- {
- pnn = new cnode;
- pnn->name[0] = p[c];
- pnn->name[1] = '\0';
- pnn->frequency = 0;
- for (int i = c; i < p.length(); i++)
- {
- if (p[i] == pnn->name[0])
- {
- pnn->frequency++;
- }
- }
- l.sortAttach(pnn);
- }
- flag = 0;
- c++;
- }
- t = l.phead;
- while (t != NULL)
- {
- cout << t->name[0] << " : " << t->frequency << endl;
- t = t->pnext;
- }
- //show nodes
- cout << endl << "-------------------------------" << endl;
- t = l.phead;
- while (t != NULL)
- {
- for (int i = 0; i < 256; i++)
- {
- if (t->name[i] != '\0')
- {
- cout << t->name[i];
- }
- else
- {
- break;
- }
- }
- cout << " : " << t->frequency << endl;
- t = t->pnext;
- }
- t = l.phead;
- while (t->pnext != NULL)
- {
- t2 = l.phead;
- l.combine(t, t2);
- t = t->pnext;
- t = t->pnext;
- l.phead = t;
- }
- //show first root
- t = l.phead;
- cout << endl << "-------------------------------" << endl << "First root : ";
- for (int i = 0; i < 256; i++)
- {
- if (t->name[i] != '\0')
- {
- cout << t->name[i];
- }
- else
- {
- break;
- }
- }
- cout << " : " << t->frequency << endl;
- //functions
- cout << endl << "-------------------------------" << endl;
- t = l.phead->pdown;
- c = 0;
- pnn = new cnode;
- pnn->name[0] = p[0];
- pnn->name[1] = '\0';
- pnn->frequency = 1;
- for (int i = 1; i < p.length(); i++)
- {
- if (p[i] == pnn->name[0])
- {
- pnn->frequency++;
- }
- }
- lcopy.Attach(pnn);
- c++;
- for (int i = c; i < p.length(); i++)
- {
- t = lcopy.phead;
- while (t != NULL)
- {
- if (p[c] == t->name[0])
- {
- flag = 1;
- break;
- }
- t = t->pnext;
- }
- if (flag != 1)
- {
- pnn = new cnode;
- pnn->name[0] = p[c];
- pnn->name[1] = '\0';
- pnn->frequency = 0;
- for (int i = c; i < p.length(); i++)
- {
- if (p[i] == pnn->name[0])
- {
- pnn->frequency++;
- }
- }
- lcopy.sortAttach(pnn);
- }
- flag = 0;
- c++;
- }
- t2 = lcopy.phead;
- while (t2 != NULL)
- {
- t = l.phead->pdown;
- l.searchEnc(t, t2);
- t2 = t2->pnext;
- }
- clist lencypt;
- char m, stemp = 0, comp[500000];
- int iBit = 7;
- c = 0;
- for (int i = 0; i < h; i++)
- {
- t = lcopy.phead;
- while (t->name[0] != p[i])
- {
- t = t->pnext;
- }
- for (int k = 0; k < t->encryption.length(); k++)
- {
- if (iBit == -1)
- {
- comp[c] = stemp;
- c++;
- iBit = 7;
- stemp = 0;
- }
- if (t->encryption[k] == '0')
- {
- m = 0;
- }
- else
- {
- m = 1;
- }
- stemp = stemp | (m << iBit);
- iBit--;
- }
- if ((i + 1) == h)
- {
- comp[c] = stemp;
- //comp[c + 1] = '\0';
- c++;
- }
- }
- cout << endl << "-------------------------------" << endl;
- for (int i = 0; i<(c+1); i++)
- {
- cout << comp[i];
- }
- cout << endl << endl;
- clist lcomp;
- char res, decomp[500000];
- string check, null;
- int cc = (c+1);
- c = 0;
- for (int i = 0; i<cc; i++)
- {
- cout << i << endl;
- stemp = comp[i];
- iBit = 7;
- while (iBit != -1)
- {
- char res = stemp & (1 << iBit);
- if (res != 0)
- {
- pnn = new cnode;
- pnn->name[0] = '1';
- pnn->pnext = NULL;
- lcomp.Attach(pnn);
- }
- else
- {
- pnn = new cnode;
- pnn->name[0] = '0';
- pnn->pnext = NULL;
- lcomp.Attach(pnn);
- }
- t = lcopy.phead;
- t2 = lcomp.phead;
- check = null;
- while (t2 != NULL)
- {
- check += t2->name[0];
- t2 = t2->pnext;
- }
- //check encry
- while (t != NULL)
- {
- if (check == t->encryption)
- {
- if (c != h)
- {
- decomp[c] = t->name[0];
- fl2.write(&t->name[0], 1);
- c++;
- lcomp.phead = NULL;
- }
- break;
- }
- t = t->pnext;
- }
- iBit--;
- }
- }
- cout << endl << endl;
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement