Last active
April 6, 2017 15:59
-
-
Save saisumit/a664e70084fc1b7365a49ea7f91e3692 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** Code For Dynamic Huffman **/ | |
| #include <bits/stdc++.h> | |
| #define Int long long | |
| #define REP(i, a, b) for (int i = a; i <= b; i++) | |
| #define FOR(i, n) for (int i = 0; i < n; i++) | |
| #define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ ) | |
| #define PI 3.1415926535897932385 | |
| #define uint64 unsigned long long | |
| #define int64 long long | |
| #define all(ar) ar.begin(), ar.end() | |
| #define pb push_back | |
| #define ff first | |
| #define ss second | |
| #define bit(n) (1<<(n)) | |
| #define Last(i) ( (i) & (-i) ) | |
| #define sq(x) ((x) * (x)) | |
| #define mp make_pair | |
| #define author saisumit | |
| /* When Panda is Life ! | |
| _,add8ba, | |
| ,d888888888b, | |
| d8888888888888b _,ad8ba,_ | |
| d888888888888888) ,d888888888b, | |
| I8888888888888888 _________ ,8888888888888b | |
| __________`Y88888888888888P"""""""""""baaa,__ ,888888888888888, | |
| ,adP"""""""""""9888888888P""^ ^""Y8888888888888888I | |
| ,a8"^ ,d888P"888P^ ^"Y8888888888P' | |
| ,a8^ ,d8888' ^Y8888888P' | |
| a88' ,d8888P' I88P"^ | |
| ,d88' d88888P' "b, | |
| ,d88' d888888' `b, | |
| ,d88' d888888I `b, | |
| d88I ,8888888' ___ `b, | |
| ,888' d8888888 ,d88888b, ____ `b, | |
| d888 ,8888888I d88888888b, ,d8888b, `b | |
| ,8888 I8888888I d8888888888I ,88888888b 8, | |
| I8888 88888888b d88888888888' 8888888888b 8I | |
| d8886 888888888 Y888888888P' Y8888888888, ,8b | |
| 88888b I88888888b `Y8888888^ `Y888888888I d88, | |
| Y88888b `888888888b, `""""^ `Y8888888P' d888I | |
| `888888b 88888888888b, `Y8888P^ d88888 | |
| Y888888b ,8888888888888ba,_ _______ `""^ ,d888888 | |
| I8888888b, ,888888888888888888ba,_ d88888888b ,ad8888888I | |
| `888888888b, I8888888888888888888888b, ^"Y888P"^ ____.,ad88888888888I | |
| 88888888888b,`888888888888888888888888b, "" ad888888888888888888888' | |
| 8888888888888698888888888888888888888888b_,ad88ba,_,d88888888888888888888888 | |
| 88888888888888888888888888888888888888888b,`"""^ d8888888888888888888888888I | |
| 8888888888888888888888888888888888888888888baaad888888888888888888888888888' | |
| Y8888888888888888888888888888888888888888888888888888888888888888888888888P | |
| I888888888888888888888888888888888888888888888P^ ^Y8888888888888888888888' | |
| `Y88888888888888888P88888888888888888888888888' ^88888888888888888888I | |
| `Y8888888888888888 `8888888888888888888888888 8888888888888888888P' | |
| `Y888888888888888 `888888888888888888888888, ,888888888888888888P' | |
| `Y88888888888888b `88888888888888888888888I I888888888888888888' | |
| "Y8888888888888b `8888888888888888888888I I88888888888888888' | |
| "Y88888888888P `888888888888888888888b d8888888888888888' | |
| ^""""""""^ `Y88888888888888888888, 888888888888888P' | |
| "8888888888888888888b, Y888888888888P^ | |
| `Y888888888888888888b `Y8888888P"^ | |
| "Y8888888888888888P `""""^ | |
| `"YY88888888888P' | |
| ^""""""""' | |
| */ | |
| using namespace std ; | |
| int tp; | |
| struct node | |
| { | |
| node* Left ; // Storing the Left Child | |
| node* Right ; // Storing the Right Child | |
| node* parent ; // Storing the parent | |
| int freq ; // Storing the freq | |
| char ch ; // Storing the character | |
| node( node* L , node* R , char c , int freq , node* parent ) | |
| { | |
| this->Left = L ; | |
| this->Right = R ; | |
| this->ch = c ; | |
| this->freq = freq ; | |
| this->parent = parent ; | |
| } | |
| } ; | |
| vector<node*> Check_vector ; | |
| node* Insert ( node* nd , node* include ) | |
| { | |
| node* L = new node( NULL , NULL , '\0' , 0 , nd ) ; // Making a new Leaf | |
| nd->Left = L ; // this would be the Left child | |
| nd->Right = include ; // Right child would be the character | |
| return L ; // Returning our new Leaf | |
| } | |
| int dfs_update_freq( node* nd , node* root ) | |
| { | |
| int sum = 0 ; | |
| if( nd->ch != '\0' )sum = nd->freq ; | |
| if( nd->Left ) sum += dfs_update_freq(nd->Left, root ) ; | |
| if( nd->Right) sum += dfs_update_freq(nd->Right, root ) ; | |
| nd->freq = sum ; | |
| return sum ; | |
| } | |
| void Replace( node* A , node* B ) | |
| { | |
| node* p1 = A->parent ; // parent of first node | |
| node* p2 = B->parent ; // parent of second node | |
| A->parent = p2 ; // swapping the parents | |
| B->parent = p1 ; | |
| if( p1->Left == A and p2-> Left == B ) { swap( p1->Left , p2->Left ) ; } | |
| if( p1->Left == A and p2-> Right == B ) { swap( p1->Left , p2->Right ) ; } | |
| if( p1->Right == A and p2-> Left == B ) { swap( p1->Right , p2->Left ) ; } | |
| if( p1->Right == A and p2-> Right == B ) { swap( p1->Right , p2->Right ) ; } | |
| } | |
| bool check( node*root ) | |
| { | |
| Check_vector.resize( 0 ) ; | |
| queue<node*> q ; // Doing a Level Order Traversal . | |
| q.push( root ) ; | |
| /* | |
| Performing the Level order traversal in reverse order..when this vector will be reversed we would get our desired level order | |
| from bottom to top . | |
| */ | |
| while( !q.empty() ) | |
| { | |
| node* nd = q.front() ; | |
| q.pop() ; | |
| Check_vector.pb( nd ) ; | |
| if( nd->Right )q.push( nd->Right ) ; | |
| if( nd->Left )q.push( nd->Left ) ; | |
| } | |
| reverse( Check_vector.begin() , Check_vector.end() ) ; // Reversing the array | |
| node* Error = new node( NULL , NULL , '\0' , -5 , NULL ) ; // Error node | |
| for( int i = 0 ; i < Check_vector.size( ) - 1 ; i ++ ) | |
| { | |
| node* now = Check_vector[i] ; // Checking for error in adjacent nodes | |
| node* next = Check_vector[i+1] ; | |
| if( now->freq > next->freq ) // If error found then update the error node | |
| { Error = now ; | |
| break ; } | |
| } | |
| if( Error->freq == -5 )return false ; // if no error then return false | |
| for( int i = Check_vector.size() - 1 ; i >= 0 ; i -- ) // Finding the farthest node which has frequency error.freq - 1 | |
| { | |
| node* now = Check_vector[i] ; | |
| if( (now -> freq) == (Error->freq - 1) ) | |
| { Replace( now , Error ) ; // Replace this nodes | |
| break ; } | |
| } | |
| return true ; | |
| } | |
| void print_tree( node* root ) | |
| { | |
| cout<<root->ch<<" "<<root->freq<<" "<<endl ; | |
| if( root->Left ){ cout<<" Left Child "<< root->Left->ch<<" "<<root->Left-> freq<<" "<<endl ;} | |
| if( root->Right ){ cout<<" Right Child "<< root->Right->ch<<" "<<root->Right-> freq<<" "<<endl ;} | |
| cout<<endl; | |
| if( root->Left )print_tree( root->Left ) ; | |
| if( root->Right)print_tree( root->Right) ; | |
| } | |
| void print_code( node* root , string code ) | |
| { | |
| if( root->ch != '\0' )cout<<root->ch<<" "<<code<<endl; | |
| if( root->Left)print_code( root->Left , code + '0' ) ; | |
| if( root->Right)print_code( root->Right , code + '1' ) ; | |
| } | |
| bool dfs_find( node* root , char ch ) | |
| { | |
| if( root->ch == ch ) { root->freq += 1 ; return true ; } | |
| bool f = false ; | |
| if( root->Left )f = f or dfs_find( root->Left , ch ) ; | |
| if( root->Right)f = f or dfs_find( root->Right , ch ) ; | |
| return f ; | |
| } | |
| int main () | |
| { | |
| node* root = new node( NULL , NULL , '\0' , 0 , NULL ) ; // This would be the root of the huffman tree | |
| node* Leaf = root ; // initialisating the Leaf | |
| string s ; | |
| getline( cin , s ) ; | |
| cout<<s; | |
| string code = "" ; | |
| for( int i = 0 ; i < s.length() ; i ++ ) | |
| { | |
| if( !dfs_find( root , s[i] ) ) | |
| { node* include = new node( NULL , NULL , s[i] , 1 , Leaf ) ; // Constructing a node | |
| Leaf = Insert( Leaf , include ) ; // Inserting into the Leaf this new node | |
| } | |
| dfs_update_freq( root , root ) ; | |
| while( check(root) ) ; | |
| // print_tree( root ) ; | |
| print_code( root , code ) ; | |
| // cin >> tp ; | |
| cout<<" After "<< i + 1 <<" character "<<endl; | |
| cout<<endl<<endl; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment