#include <cstdlib>
#include <iostream>
#include <vector>
#include <iostream>
#include <fstream>
 
using namespace std;
 
class huffman_tree
{
      public:
              char _char;
              double count;
              huffman_tree *next;
 
/*
 
             huffman_tree( int stats[256] );
             string encde_to_string( unsigned char c);
             vector<unsigned char> decode_string (string s);
*/
};
 
 
int main(int argc, char *argv[])
{
    unsigned char a;
    vector <char> input;
 
    vector <char> letterstat;
    vector <int> numberstat;
 
    ifstream IFile;
 
    char letter, tempchar;
    int x, y, i, j, tempint;
    int counter = 0;
 
    IFile.open("file.txt");
 
    for( ; ; )
    {
          a = IFile.get();
          if ( !IFile.eof() )
          {
               input.push_back(a);
          }
          else
          {
              break;
          }
    }
 
    // check the input against itself for the stats
    // arrange the input via the integer equivalent of the characters
    // then get the stats
    for ( i = 0 ; i < input.size() - 2 ; i++ )
    {
        for ( j = i + 1 ; j < input.size() - 1 ; j++ )
        {
            if( input[i] > input[j] )
            {
                         tempchar = input[i];
                         input[i] = input[j];
                         input[j] = tempchar;                                                   
            }
 
        }
    }
 
    // stat checking
    cout << "Before numerical sorting." << endl;
    for ( i = 0 ; i < input.size() - 1 ; i++ )
    {
        counter = 0;
        for ( j = i ; j < input.size() ; j++ )
        {
            if( input[i] == input[j] )
            {
                counter++;
            }
            else
            {
                break;
            }
        }
        numberstat.push_back(counter);
        letterstat.push_back(input[i]);
        i = j - 1;
    }   
 
    for( x = 0 ; x < numberstat.size() ; x++ )
    {
         cout << letterstat[x] << " ---> " 
              << numberstat[x] << endl;
    }
 
 
    // sort lang according to their frequency
    cout << endl << "After numerical sorting." << endl;
    for ( i = 0 ; i < numberstat.size() - 1 ; i++ )
    {
        for ( j = i + 1 ; j < numberstat.size() ; j++ )
        {
            if( numberstat[i] > numberstat[j] )
            {
                         tempchar = letterstat[i];
                         letterstat[i] = letterstat[j];
                         letterstat[j] = tempchar;
 
                         tempint = numberstat[i];
                         numberstat[i] = numberstat[j];
                         numberstat[j] = tempint;
            }
 
        }
    }
 
    for( x = 0 ; x < numberstat.size() ; x++ )
    {
         cout << letterstat[x] << " ---> " 
              << numberstat[x] << endl;
    }
 
    /*
    constructing list
    */
 
    /*
      initialize the starting/head node
                 THIS IS IMPORTANT!
                      - can be used for reference
    */
 
 
    huffman_tree start;
    start._char = letterstat[0];
    start.count = numberstat[0];
 
    huffman_tree current = start;
    huffman_tree temp = start;
 
    //safety precaution, deleting stuff
 
    *current.next = start;
    *temp.next = start;
 
 
    cout << "Deletion of any prelim tree constructed." << endl;    
    for( ; current.next != NULL ; current = temp )
    {
           cout << "testline" << endl;
           temp = current.next;
           //current = *current.next;
           delete [] current.next;
 
    }
    cout << "Deletion complete." << endl;
 
    current = start;
    temp = start;
 
    //start the list
    for( i = 0 ; i < letterstat.size() ; i ++ )
    {
         current.count = numberstat[i];
         current._char = letterstat[i];
 
         if( i == letterstat.size() - 1 )
         {
                current.next = NULL;
                break;
         }
         else
         {
             current.next = new huffman_tree;
 
             current.count = numberstat[i];
             current._char = letterstat[i];
             current = *current.next;
 
         }
 
 
    }
 
 
    cout << endl << "The List is as follows:" << endl;
    *current.next = start;
    *temp.next = start;
 
    while( current.next != NULL )
    {
           cout << current.count << " " << current._char << endl;
           current = *current.next;
    }
 
    *current.next = start;
    *temp.next = start;
 
    //delete again
    while( current.next != NULL )
    {
           current = *current.next;
           delete [] temp.next;
           temp = current;
    }
 
 
    cout << "Memory freeing." << endl;    
 
    system("PAUSE");
    return EXIT_SUCCESS;
}