diff options
Diffstat (limited to 'labb6/src/huffmanmain.cpp')
| -rwxr-xr-x | labb6/src/huffmanmain.cpp | 472 |
1 files changed, 472 insertions, 0 deletions
diff --git a/labb6/src/huffmanmain.cpp b/labb6/src/huffmanmain.cpp new file mode 100755 index 0000000..71d8ee4 --- /dev/null +++ b/labb6/src/huffmanmain.cpp @@ -0,0 +1,472 @@ +/*
+ * TDDD86 Huffman Encoding
+ * This file contains the main program and user interface for running your
+ * Huffman Encoder. It contains a text menu to allow you to test all of the
+ * various functions of your program for encoding and decoding data.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ */
+
+#include <algorithm>
+#include <fstream>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include "simpio.h"
+#include "strlib.h"
+#include "HuffmanNode.h"
+#include "encoding.h"
+#include "huffmanutil.h"
+using namespace std;
+
+const bool SHOW_TREE_ADDRESSES = false; // set to true to debug tree pointer issues
+const string DEFAULT_COMPRESSED_FILE_EXTENSION = ".huf";
+const string DEFAULT_DECOMPRESSED_FILE_EXTENSION = ".txt";
+
+// function prototype declarations; see definitions below for documentation
+void intro();
+string menu();
+void test_buildFrequencyTable(map<int, int>& freqTable, string& data, bool& isFile);
+void test_buildEncodingTree(map<int, int>& freqTable, HuffmanNode*& encodingTree);
+void test_buildEncodingMap(HuffmanNode*& encodingTree, map<int, string>& encodingMap);
+void test_encodeData(map<int, string>& encodingMap, string& data, bool& isFile);
+void test_decodeData(HuffmanNode* encodingTree);
+void test_compress();
+void test_decompress();
+void test_freeTree(HuffmanNode* encodingTree);
+void test_binaryFileViewer();
+void test_textFileViewer();
+void test_sideBySideComparison();
+istream* openInputStream(string data, bool isFile, bool isBits = false);
+istream* openStringOrFileInputStream(string& data, bool& isFile, bool isBits = false);
+
+int main() {
+ intro();
+
+ // these variables maintain state between steps 1-4
+ string data;
+ bool isFile = false;
+ HuffmanNode* encodingTree = nullptr;
+ map<int, int> freqTable;
+ map<int, string> encodingMap;
+
+ // prompt user for options repeatedly
+ while (true) {
+ string choice = menu();
+ if (choice == "Q") {
+ break;
+ } else if (choice == "1") {
+ test_buildFrequencyTable(freqTable, data, isFile);
+ } else if (choice == "2") {
+ test_buildEncodingTree(freqTable, encodingTree);
+ } else if (choice == "3") {
+ test_buildEncodingMap(encodingTree, encodingMap);
+ } else if (choice == "4") {
+ test_encodeData(encodingMap, data, isFile);
+ } else if (choice == "5") {
+ test_decodeData(encodingTree);
+ } else if (choice == "C") {
+ test_compress();
+ } else if (choice == "D") {
+ test_decompress();
+ } else if (choice == "B") {
+ test_binaryFileViewer();
+ } else if (choice == "T") {
+ test_textFileViewer();
+ } else if (choice == "S") {
+ test_sideBySideComparison();
+ } else if (choice == "F") {
+ test_freeTree(encodingTree);
+ encodingTree = nullptr;
+ }
+ }
+
+ cout << "Exiting." << endl;
+ return 0;
+}
+
+/*
+ * Sets up the output console and explains the program to the user.
+ */
+void intro() {
+ cout << "Welcome to TDDD86 Shrink-It!" << endl;
+ cout << "This program uses the Huffman coding algorithm for compression." << endl;
+ cout << "Any file can be compressed by this method, often with substantial" << endl;
+ cout << "savings. Decompression will faithfully reproduce the original." << endl;
+}
+
+/*
+ * Prints a menu of choices for the user and reads/returns the user's response.
+ */
+string menu() {
+ cout << endl;
+ cout << "1) build character frequency table" << endl;
+ cout << "2) build encoding tree" << endl;
+ cout << "3) build encoding map" << endl;
+ cout << "4) encode data" << endl;
+ cout << "5) decode data" << endl;
+ cout << endl;
+ cout << "C) compress file" << endl;
+ cout << "D) decompress file" << endl;
+ cout << "F) free tree memory" << endl;
+ cout << endl;
+ cout << "B) binary file viewer" << endl;
+ cout << "T) text file viewer" << endl;
+ cout << "S) side-by-side file comparison" << endl;
+ cout << "Q) quit" << endl;
+
+ cout << endl;
+ string choice = toUpperCase(trim(getLine("Your choice? ")));
+ return choice;
+}
+
+/*
+ * Tests the buildFrequencyTable function.
+ * Prompts the user for a string of data or input file to read,
+ * then builds a frequency map of its characters and prints that map's contents.
+ * Stores the built map in the given output parameter freqTable.
+ * Also stores output parameters for the text input read, and whether the input
+ * came from a string of text or a file. This is reused later by main.
+ *
+ */
+void test_buildFrequencyTable(map<int, int> &freqTable, string& data, bool& isFile) {
+ istream* input = openStringOrFileInputStream(data, isFile);
+ cout << "Building frequency table ..." << endl;
+ freqTable = buildFrequencyTable(*input);
+ for (auto const & freq : freqTable) {
+ int ch = freq.first;
+ cout << " " << setw(3) << ch
+ << ": " << setw(4) << toPrintableChar(ch) << " => "
+ << setw(7) << freqTable[ch] << endl;
+ }
+ cout << freqTable.size() << " character frequencies found." << endl;
+ delete input;
+}
+
+/*
+ * Tests the buildEncodingTree function.
+ * Accepts a frequency table map as a parameter, presumably the one generated
+ * previously in step 1 by buildFrequencyTable.
+ * Then prints the encoding tree in an indented sideways format.
+ * Stores the built tree in the given output parameter encodingTree.
+ */
+void test_buildEncodingTree(map<int, int> &freqTable, HuffmanNode*& encodingTree) {
+ if (freqTable.empty()) {
+ cout << "Can't build tree; character frequency table is empty or uninitialized." << endl;
+ } else {
+ cout << "Building encoding tree ..." << endl;
+ encodingTree = buildEncodingTree(freqTable);
+ printSideways(encodingTree, SHOW_TREE_ADDRESSES);
+ }
+}
+
+/*
+ * Tests the buildEncodingMap function.
+ * Accepts an encoding tree as a parameter, presumably the one generated
+ * previously in step 2 by buildEncodingTree.
+ * Then prints the encoding map of characters to binary encodings.
+ * Stores the built map in the given output parameter encodingMap.
+ */
+void test_buildEncodingMap(HuffmanNode*& encodingTree, map<int, string> &encodingMap) {
+ if (encodingTree == nullptr) {
+ cout << "Can't build map; encoding tree is NULL." << endl;
+ } else {
+ cout << "Building encoding map ..." << endl;
+ encodingMap = buildEncodingMap(encodingTree);
+ for (auto const & enc : encodingMap) {
+ int ch = enc.first;
+ cout << " " << setw(3) << ch
+ << ": " << setw(4) << toPrintableChar(ch) << " => "
+ << encodingMap[ch] << endl;
+ }
+ cout << encodingMap.size() << " character encodings found." << endl;
+ }
+}
+
+/*
+ * Tests the encodeData function.
+ * Accepts as a parameter a map of encodings, presumably the one generated
+ * previously in step 3 by buildEncodingMap.
+ * Allows the user to encode the same data from the original file/string,
+ * or new data that is typed / data from a file.
+ * Once encoding is done, prints the bits of the encoded data.
+ */
+void test_encodeData(map<int, string> &encodingMap, string& data, bool& isFile) {
+ if (encodingMap.empty()) {
+ cout << "Can't encode data; encoding map is empty or uninitialized." << endl;
+ } else {
+ istream* input = nullptr;
+ bool reuse = yesOrNo("Reuse your previous string/file data for encoding? ");
+ if (reuse) {
+ input = openInputStream(data, isFile);
+ } else {
+ input = openStringOrFileInputStream(data, isFile);
+ }
+
+ ostringbitstream output;
+ cout << "Encoding data ..." << endl;
+ encodeData(*input, encodingMap, output);
+ output.flush();
+ string text = output.str();
+ cout << "Here is the binary encoded data (" << text.length() << " bytes):" << endl;
+ printBits(text);
+ delete input;
+ }
+}
+
+/*
+ * Tests the decodeData function.
+ * Uses the given encoding tree, presumably one encoded previously in step 2
+ * by buildEncodingTree.
+ * Prompts for a file or string of binary input data and decodes it into a
+ * string output stream, then prints the text on the console.
+ */
+void test_decodeData(HuffmanNode* encodingTree) {
+ if (encodingTree == nullptr) {
+ cout << "Can't decode; encoding tree is NULL." << endl;
+ } else {
+ string data;
+ bool isFile;
+ ibitstream* input = (ibitstream*) openStringOrFileInputStream(data, isFile, /* isBits */ true);
+ ostringstream output;
+
+ cout << "Decoding data ..." << endl;
+ decodeData(*input, encodingTree, output);
+ output.flush();
+
+ string decoded = output.str();
+ cout << "Here is the decoded data ("
+ << decoded.length() << " bytes):" << endl;
+ cout << decoded << endl;
+
+ delete input;
+ }
+}
+
+#if defined(_WIN32) || defined(_WIN64)
+ #include <windows.h>
+#else
+ // assume POSIX
+ #include <sys/stat.h>
+#endif
+
+/*
+ * Tests the compress function.
+ * Prompts for input/output file names and opens streams on those files.
+ * Then calls your compress function and displays information about how many
+ * bytes were written, if any.
+ */
+void test_compress() {
+ string inputFileName = promptForExistingFileName("Input file name: ");
+ ifstream input;
+ ofbitstream output;
+ string defaultOutputFileName = getRoot(inputFileName) + DEFAULT_COMPRESSED_FILE_EXTENSION;
+ string outputFileName = trim(getLine("Output file name (Enter for "
+ + defaultOutputFileName + "): "));
+ if (outputFileName == "") {
+ outputFileName = defaultOutputFileName;
+ }
+ if (!confirmOverwrite(outputFileName)) {
+ return;
+ }
+
+ int inputFileSize = fileSize(inputFileName);
+ cout << "Reading " << inputFileSize << " uncompressed bytes." << endl;
+ input.open(inputFileName.c_str(), ifstream::binary);
+ output.open(outputFileName.c_str());
+ cout << "Compressing ..." << endl;
+ compress(input, output);
+ input.close();
+ output.flush();
+ output.close();
+
+#if defined(_WIN32) || defined(_WIN64)
+ bool fileExists = (GetFileAttributesA(outputFileName.c_str()) != INVALID_FILE_ATTRIBUTES);
+#else
+ // assume POSIX
+ struct stat fileInfo;
+ bool fileExists = (stat(outputFileName.c_str(), &fileInfo) == 0);
+#endif
+ if (fileExists) {
+ cout << "Wrote " << fileSize(outputFileName) << " compressed bytes." << endl;
+ } else {
+ cout << "Compressed output file was not found; perhaps there was an error." << endl;
+ }
+}
+
+/*
+ * Tests the decompress function.
+ * Prompts for input/output file names and opens streams on those files.
+ * Then calls your decompress function and displays information about how many
+ * bytes were written, if any.
+ */
+void test_decompress() {
+ string inputFileName = promptForExistingFileName("Input file name: ");
+ ifbitstream input;
+ ofstream output;
+ string defaultOutputFileName = getRoot(inputFileName) + "-out" + DEFAULT_DECOMPRESSED_FILE_EXTENSION;
+ string outputFileName = trim(getLine("Output file name (Enter for "
+ + defaultOutputFileName + "): "));
+ if (outputFileName == "") {
+ outputFileName = defaultOutputFileName;
+ }
+ if (!confirmOverwrite(outputFileName)) {
+ return;
+ }
+
+ int inputFileSize = fileSize(inputFileName);
+ cout << "Reading " << inputFileSize << " compressed bytes." << endl;
+ input.open(inputFileName.c_str());
+ output.open(outputFileName.c_str(), ofstream::binary);
+ cout << "Decompressing ..." << endl;
+ decompress(input, output);
+ input.close();
+ output.flush();
+ output.close();
+
+#if defined(_WIN32) || defined(_WIN64)
+ bool fileExists = (GetFileAttributesA(outputFileName.c_str()) != INVALID_FILE_ATTRIBUTES);
+#else
+ // assume POSIX
+ struct stat fileInfo;
+ bool fileExists = (stat(outputFileName.c_str(), &fileInfo) == 0);
+#endif
+ if (fileExists) {
+ cout << "Wrote " << fileSize(outputFileName) << " decompressed bytes." << endl;
+ } else {
+ cout << "Decompressed output file was not found; perhaps there was an error." << endl;
+ }
+}
+
+/*
+ * Tests the freeTree function by freeing the given encoding tree.
+ * If the tree is NULL, your freeTree function is supposed to have no effect.
+ */
+void test_freeTree(HuffmanNode* encodingTree) {
+ cout << "Freeing memory for encoding tree ..." << endl;
+ freeTree(encodingTree);
+}
+
+/*
+ * Binary file viewer function.
+ * Prompts the user for a file name and then prints all bits/bytes of that file.
+ */
+void test_binaryFileViewer() {
+ string filename = promptForExistingFileName("File name to display: ");
+ ifbitstream input;
+ input.open(filename.c_str());
+ string fileText = readEntireFileText(input);
+ input.close();
+ cout << "Here is the binary encoded data (" << fileText.length() << " bytes):" << endl;
+ printBits(fileText);
+}
+
+/*
+ * Text file viewer function.
+ * Prompts the user for a file name and prints all text in that file.
+ */
+void test_textFileViewer() {
+ string filename = promptForExistingFileName("File name to display: ");
+ ifstream input;
+ ostringstream output;
+ input.open(filename.c_str(), ifstream::binary);
+ while (true) {
+ int ch = input.get();
+ if (input.fail()) {
+ break;
+ }
+ output.put(ch);
+ }
+ string fileText = output.str();
+ cout << "Here is the text data (" << fileText.length() << " bytes):" << endl;
+ cout << fileText << endl;
+ input.close();
+}
+
+/*
+ * Side-by-side file comparison function.
+ * Prompts for two file names and then checks their contents,
+ * printing information about differences between the two.
+ * Most of this code is written by Keith Schwarz.
+ */
+void test_sideBySideComparison() {
+ string filename1 = promptForExistingFileName("First file name: ");
+ string filename2 = promptForExistingFileName("Second file name: ");
+ string fileText1 = readEntireFileText(filename1);
+ string fileText2 = readEntireFileText(filename2);
+
+ // compare the two sequences to find a mismatch
+ pair<string::const_iterator, string::const_iterator> diff =
+ mismatch(fileText1.begin(), fileText1.end(), fileText2.begin());
+ if (diff.first != fileText1.end()) {
+ ptrdiff_t offset = diff.first - fileText1.begin();
+ cout << "File data differs at byte offset " << offset << ":" << endl;
+ cout << setw(16) << filename1 << " has value " << setw(3) << (int) (*diff.first) << " ("
+ << toPrintableChar(*diff.first) << ")" << endl;
+ cout << setw(16) << filename2 << " has value " << setw(3) << (int) (*diff.second) << " ("
+ << toPrintableChar(*diff.second) << ")" << endl;
+ int size1 = fileSize(filename1);
+ int size2 = fileSize(filename2);
+ if (size1 != size2) {
+ cout << "File sizes differ! " << size1 << " vs. " << size2 << " bytes." << endl;
+ }
+ } else {
+ cout << "Files match!" << endl;
+ }
+}
+
+/*
+ * Opens an input stream based on the given parameters and returns a pointer
+ * to the stream that was opened.
+ * If isFile is true, treats data as a file name and opens that file.
+ * If isFile is false, treats data as a string of data and opens a string stream
+ * over that data.
+ * If isBits is true, opens the equivalent bit input stream rather than byte based.
+ */
+istream* openInputStream(string data, bool isFile, bool isBits) {
+ if (isFile) {
+ if (isBits) {
+ return new ifbitstream(data);
+ } else {
+ ifstream* input = new ifstream;
+ input->open(data.c_str(), ifstream::binary);
+ return input;
+ }
+ } else {
+ if (isBits) {
+ return new istringbitstream(bytesToBits(data));
+ } else {
+ return new istringstream(data);
+ }
+ }
+}
+
+/*
+ * Prompts the user to choose between reading from a string or file.
+ * If the user wants to read from a string, asks the user to type said string.
+ * If the user wants to read from a file, asks the user for the file name.
+ * Then opens an input stream for the appropriate type of data and returns
+ * a pointer to the stream.
+ * The memory for the stream must be freed by the caller.
+ */
+istream* openStringOrFileInputStream(string& data, bool& isFile, bool isBits) {
+ while (true) {
+ string choice = toLowerCase(trim(getLine("Read from a s)tring or f)ile? ")));
+ if (startsWith(choice, 's')) {
+ isFile = false;
+ data = getLine("Type the string to process: ");
+ if (isBits) {
+ // strip spaces because user may have copy/pasted from printBits output
+ data = stringReplace(data, ' ', "");
+ data = stringReplace(data, '\t', "");
+ }
+ break;
+ } else if (startsWith(choice, 'f')) {
+ isFile = true;
+ data = promptForExistingFileName("File name to process: ");
+ break;
+ }
+ }
+ return openInputStream(data, isFile, isBits);
+}
|