Write a program that takes any input text and produces both

Write a program that takes any input text and produces both a frequency table and the corresponding Huffman code. Take approximately 360 words from any English document as your input text. Ignore all blanks, all punctuation marks, al special symbols. Create an input file with this input text. Construct the frequency table according to the input text read from the file, in the form: The Frequency\'s MUST be listed, in order, from largest (at the top) to smallest (at the bottom). Only the BELOW Tablet Format will be accepted: Letter Comma Space Percentage Example: A, 2.5% Then, using the Huffman algorithm, construct the optimal prefix binary code for the table. Design your program to read the input from the input file \"infile.dat\" Your program must produce the output, in the file \"outfile.dat\". consisting of the frequency table for the source text. the Huffman code for each letter and digit in the source code, and the length of the coded message in terms of number of bits. MUST use exact file names provided

Solution

#include \"FileLoader.h\"
#include \"CharFreqInVector.h\"
#include \"LeafNode.h\"
#include \"TreeFromListConstruction.h\"
#include \"GenerateHuffFile.h\"
#include \"Decompressor.h\"
#include <crtdbg.h>
#include <list>
#include <fstream>

int main()
{
   {
   vector<char> vFile;
   vector<char> cvFile;
   vector<char> charByte;
   vector<int> frequency;

   FileLoader File(\"shakespeare.txt\");
  
   vFile = File.loadFileIntoVector();
  
   CharFreqInVector Frequency(vFile);
  
   Frequency.calculateFrequency();

   charByte = Frequency.getEachChar();//Frequency.getEachChar(); // need copies of the char and its frequency to put to a LeafNode
   frequency = Frequency.getEachFrequency();//Frequency.getEachFrequency();

   TreeFromListConstruction tree(charByte, frequency);
  
  
//passing into a class that can modify the list into a binary tree

   tree.formTree(); //modify the list into a binary tree

   GenerateHuffFile Huff(tree.getTree(), vFile, \"compressed.txt\",charByte, frequency);

   Huff.writeHuffFile();
///////////////////////////////////////////////////////////////////////////////////////decompression time
  

   FileLoader cFile(\"compressed.txt\");

   cvFile = cFile.loadFileIntoVector();

   CharFreqInVector Formated(cvFile);

   Formated.calcFreqInCompressed();

   charByte = Formated.getEachChar();//Frequency.getEachChar(); // need copies of the char and its frequency to put to a LeafNode
   frequency = Formated.getEachFrequency();//Frequency.getEachFrequency();

   TreeFromListConstruction recontructedTree(charByte, frequency);  

   recontructedTree.formTree();

   Decompressor uncompress(recontructedTree.getTree(), cvFile, \"compressed.txt\", \"decompressed.txt\", vFile.size());

   uncompress.remakeFile();
   }
   cout << _CrtDumpMemoryLeaks(); //no memory leaks yay!
   system(\"pause\");
  
   return 0;
}

CharFreqInVector.h

#ifndef CHARFREQINVECTOR_H
#define CHARFREQINVECTOR_H

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

class CharFreqInVector
{
public:  
   CharFreqInVector(vector<char>& charVec);
   ~CharFreqInVector();
   void clearVectors();
   void calculateFrequency();
   void calcFreqInCompressed();
   void displayFrequency();
   int convertStringToInt(string aString);
   vector<char> getEachChar(){return eachChar;}
   vector<int> getEachFrequency(){return eachFrequency;}
private:
   vector<char> charVector;
   vector<char> eachChar;
   vector<int>   eachFrequency;
   static const int streamSize = 255;
};

#endif

/CharFreqInVector.cpp

#include \"CharFreqInVector.h\"

CharFreqInVector::CharFreqInVector(vector<char>& charVec)
{
   charVector = charVec;
  
  
}

void CharFreqInVector::displayFrequency()
{
   for(unsigned int i = 0; i < eachChar.size(); i++)
   {
       cout <<\"char:\" << eachChar[i] << \" freq:\" << eachFrequency[i] << endl;
   }
}

void CharFreqInVector::calcFreqInCompressed()
{
   string intString;
   int j = 0;
   int i = 0;

   while(1)
   {
       eachChar.push_back(\' \');
       eachFrequency.push_back(0);
       eachChar[j] = charVector[i];
       i++;
      
       while(charVector[i] != \',\')
       {
           intString.push_back(charVector[i]);
           i++;
       }
       i++;
       eachFrequency[j] = convertStringToInt(intString);

       intString.clear();

       if(eachChar[j] == \'0\' || eachFrequency[j] == 0)
       {
           eachChar.pop_back();
           eachFrequency.pop_back();
           break;
       }
          
       j++;

   }
}

int CharFreqInVector::convertStringToInt(string aString)
{
   int anInt;
   stringstream myStream;
   myStream.str(aString);
   myStream >> anInt;

   return anInt;
}

void CharFreqInVector::calculateFrequency()
{
   bool isAlreadyIn = false;
   unsigned int i = 0;
   unsigned int j = 0;

   for(i = 0; i < charVector.size(); i++)
   {
       for(j = 0; j < eachChar.size(); j++)
       {
           if(charVector[i] == eachChar[j])
           {
               eachFrequency[j]++;
               isAlreadyIn = true;
               break;
           }
      
       }
       if(!isAlreadyIn)
       {
           eachChar.push_back(charVector[i]);
           eachFrequency.push_back(1);
       }
       else
           isAlreadyIn = false;
   }
}

void CharFreqInVector::clearVectors()
{
   charVector.clear();
   eachChar.clear();
   eachFrequency.clear();

}

CharFreqInVector::~CharFreqInVector()
{
   clearVectors();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//Decompressor.h

#ifndef DECOMPRESSOR_H
#define DECOMPRESSOR_H
#include \"LeafNode.h\"
class Decompressor
{
public:
   Decompressor(vector<Node*> *aList, vector<char> vFile, string inFile, string outFile, unsigned int origFile);
   void remakeFile();
   void uncompressChars(unsigned int i);

private:
   vector<char> vectorFile;
   unsigned int originalFileSize;
   string outputFileName;
   string inputFileName;
   vector<Node*> *myList;
   ofstream fout;
   ifstream infile;

};

#endif

//FileLoader.h

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

#ifndef FileLoader_H
#define FileLoader_H

class FileLoader
{
public:
   FileLoader(string fName);
   ~FileLoader(){;}
   vector<char> loadFileIntoVector();
   vector<char> fileVector;
  
private:
  
   string fileName;

};
#endif

#include \"FileLoader.h\"

FileLoader::FileLoader(string fName)
{
   fileName = fName;
}

vector<char> FileLoader::loadFileIntoVector()
{
  
   ifstream fin;
   fin.open(fileName.c_str(), ios::binary);
  
   if(!fin)
   {
       cout << \"unable to open file\ \";
       exit(1);
   }

   char ch;
   while(fin.get(ch))
       fileVector.push_back(ch);
  
  

   fin.close();
  
  
   return fileVector;
}

//GenerateHuffFile.h

#ifndef GENERATEHUFFFILE_H
#define GENERATEHUFFFILE_H

#include \"LeafNode.h\"
#include \"string\"
class GenerateHuffFile
{
public:
   GenerateHuffFile(vector<Node*> *aList, vector<char> vFile, string outPutFile,vector<char> charBytes, vector<int> frequencies);
   void writeHuffFile();//writes the true and bits to file
   void writeTreePortionToFile();//writes the tree into a file
   void writeBitPortionToFile();//writes the bits to a file
   void writeBits(vector<bool> bitVector,int i);
   void convertBoolVecToBits();//turns the boolean vector representing bits to real bits to write to file
  
   string getBitsInChar(char dummyByte);
private:
   vector<Node*> *myList;
   vector<char> vectorFile;
   vector<char> charBytes ;
   vector<int> frequencies ;
   string outputFile;
   ofstream fout;
   char dummyByte;
   int bitCounter;
   int bitPosition;
   int totalBitsInFile;
   static const int bitsInAByte = 8;
  
};

#endif

//GenerateHuffFile.cpp

#include \"GenerateHuffFile.h\"

GenerateHuffFile::GenerateHuffFile(vector<Node*> *aList, vector<char> vFile, string outFile, vector<char> cBytes, vector<int> freqs)
{
   vectorFile = vFile;
   outputFile = outFile;
   myList = aList;
   bitCounter = 0;
   bitPosition = 128;
   totalBitsInFile = 0;
   charBytes = cBytes;
   frequencies = freqs;
}

void GenerateHuffFile::writeHuffFile()
{
  
   fout.open(outputFile.c_str(), ios::binary);
  
   //diplay tree in file
   for(unsigned int i = 0; i < charBytes.size(); i++)
   {
       fout << charBytes[i];
       fout << frequencies[i];
       fout << \',\';  

   }
   fout << \"00\" << \',\'; //marker to mark the end of the tree in the file

  
   writeBitPortionToFile();
  

   fout.close();

}

void GenerateHuffFile::writeBits(vector<bool> bitVector,int index)
{
      
   //   for(unsigned int i = 1; i < bitVector.size();i++)
       //{
       //cout << bitVector[i];
   //   }
       //cout << endl;
          
       for(unsigned int i = 1; i < bitVector.size(); i++)
       {
       if(bitVector[i])
       {
           for(int j = 0; j < bitCounter; j++)
           {
               bitPosition = bitPosition/2;
           }
           dummyByte = dummyByte | bitPosition;
           bitPosition = 128;
           bitCounter++;
           totalBitsInFile++;
  
       }
       else
       {
           bitCounter++;
           totalBitsInFile++;
  

       }
       if(bitCounter == 8 || (index == vectorFile.size() - 1) && (i == bitVector.size() - 1))
       {
          
           fout << dummyByte;//cout dummy byte to a file
           ///cout << getBitsInChar(dummyByte);
           bitCounter = 0;
           dummyByte = dummyByte & 0;
       }
   }
  

}

string GenerateHuffFile::getBitsInChar(char dummyByte)
{
   int bitPosition = 128;
   string bits;
           for(int i = 0; i < 8; i++)
           {
               for(int j = 0; j < i; j++)
               {
                   bitPosition = bitPosition/2;
               }
               if((dummyByte & bitPosition) == bitPosition)
               {
                   bits.push_back(\'1\');
               }
               else
                   bits.push_back(\'0\');
               bitPosition = 128;
          
          
           }
               bits.push_back(\'\ \');
           return bits;
}

void GenerateHuffFile::writeBitPortionToFile()
{
  
   bool inChild = false;
   Node *aNode;
   dummyByte = dummyByte & 0; //clear bit inside to zero

   for(unsigned int i = 0; i < vectorFile.size(); i++)
   {
       for(unsigned int j = 0; j < myList->size(); j++)
       {
           if(myList[0][j]->getMyChildrenSize() > 0)
           {
               aNode = myList[0][j]->searchCharByte(vectorFile[i]) ;
               writeBits(aNode->getBitVector(),i);
              
           }
       }
   }

   //cout << endl << totalBitsInFile << endl;
  
  
}