diff options
Diffstat (limited to 'labb6/src')
| -rwxr-xr-x | labb6/src/HuffmanNode.cpp | 78 | ||||
| -rwxr-xr-x | labb6/src/HuffmanNode.h | 70 | ||||
| -rwxr-xr-x | labb6/src/bitstream.cpp | 372 | ||||
| -rwxr-xr-x | labb6/src/bitstream.h | 368 | ||||
| -rwxr-xr-x | labb6/src/encoding.cpp | 44 | ||||
| -rwxr-xr-x | labb6/src/encoding.h | 33 | ||||
| -rwxr-xr-x | labb6/src/huffmanmain.cpp | 472 | ||||
| -rwxr-xr-x | labb6/src/huffmanutil.cpp | 206 | ||||
| -rwxr-xr-x | labb6/src/huffmanutil.h | 105 | ||||
| -rwxr-xr-x | labb6/src/readme.txt | 3 |
10 files changed, 1751 insertions, 0 deletions
diff --git a/labb6/src/HuffmanNode.cpp b/labb6/src/HuffmanNode.cpp new file mode 100755 index 0000000..4f50054 --- /dev/null +++ b/labb6/src/HuffmanNode.cpp @@ -0,0 +1,78 @@ +/*
+ * TDDD86 Huffman Encoding
+ * This file implements the members of the HuffmanNode structure that you will
+ * use in your Huffman encoding tree. See HuffmanNode.h for documentation of
+ * each member.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ */
+
+#include <cctype>
+#include "HuffmanNode.h"
+#include "huffmanutil.h"
+
+static void printHuffmanNode(ostream& out, const HuffmanNode& node, bool showAddress = false);
+
+HuffmanNode::HuffmanNode(int character, int count, HuffmanNode* zero, HuffmanNode* one) {
+ this->character = character;
+ this->count = count;
+ this->zero = zero;
+ this->one = one;
+}
+
+bool HuffmanNode::isLeaf() const {
+ return zero == nullptr && one == nullptr;
+}
+
+string HuffmanNode::toString() const {
+ ostringstream out;
+ out << *this;
+ return out.str();
+}
+
+bool HuffmanNode::operator <(const HuffmanNode &rhs) const {
+ return this->count > rhs.count;
+}
+
+void printSideways(HuffmanNode* node, bool showAddresses, string indent) {
+ if (node != nullptr) {
+ printSideways(node->one, showAddresses, indent + " ");
+ cout << indent << *node << endl;
+ printSideways(node->zero, showAddresses, indent + " ");
+ }
+}
+
+ostream& operator <<(ostream& out, const HuffmanNode& node) {
+ printHuffmanNode(out, node, false);
+ return out;
+}
+
+static void printHuffmanNode(ostream& out, const HuffmanNode& node, bool showAddress) {
+ if (showAddress) {
+ out << "@" << &node;
+ }
+ out << "{";
+
+ if (node.character == NOT_A_CHAR) {
+ out << "NOT, ";
+ } else {
+ out << toPrintableChar(node.character)
+ << " (" << node.character << "), ";
+ }
+ out << "count=" << node.count;
+
+ if (showAddress) {
+ if (node.zero == nullptr) {
+ out << ", zero=nullptr";
+ } else {
+ out << ", zero=" << node.zero;
+ }
+ if (node.one == nullptr) {
+ out << ", one=nullptr";
+ } else {
+ out << ", one=" << node.one;
+ }
+ }
+ out << "}";
+}
diff --git a/labb6/src/HuffmanNode.h b/labb6/src/HuffmanNode.h new file mode 100755 index 0000000..b788c00 --- /dev/null +++ b/labb6/src/HuffmanNode.h @@ -0,0 +1,70 @@ +/*
+ * TDDD86 Huffman Encoding
+ *
+ * This file declares the HuffmanNode structure that you will use in your
+ * Huffman encoding tree.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ */
+
+#ifndef _huffmannode_h
+#define _huffmannode_h
+
+#include <cstddef>
+#include <iomanip>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include "bitstream.h"
+using namespace std;
+
+/* Type: HuffmanNode
+ * A node inside a Huffman encoding tree. Each node stores four
+ * values - the character stored here (or NOT_A_CHAR if the value
+ * is not a character), pointers to the 0 and 1 subtrees, and the
+ * character count (weight) of the tree.
+ */
+struct HuffmanNode {
+ int character; // character being represented by this node
+ int count; // number of occurrences of that character
+ HuffmanNode* zero; // 0 (left) subtree (nullptr if empty)
+ HuffmanNode* one; // 1 (right) subtree (nullptr if empty)
+
+ /*
+ * Constructs a new node to store the given character and its count,
+ * along with the given child pointers.
+ */
+ HuffmanNode(int character = NOT_A_CHAR, int count = 0,
+ HuffmanNode* zero = nullptr, HuffmanNode* one = nullptr);
+
+ /*
+ * Returns true if this node is a leaf (has NULL children).
+ */
+ bool isLeaf() const;
+
+ /*
+ * Returns a string representation of this node for debugging.
+ */
+ string toString() const;
+
+ /*
+ * Returns false if count of this node is strictly less than that of rhs,
+ * true otherwise.
+ */
+ bool operator <(const HuffmanNode &rhs) const;
+};
+
+/*
+ * Prints an indented horizontal view of the tree of HuffmanNodes with the given
+ * node as its root.
+ * Can optionally show the memory addresses of each node for debugging.
+ */
+void printSideways(HuffmanNode* node, bool showAddresses = false, string indent = "");
+
+/*
+ * Stream insertion operator so that a HuffmanNode can be printed for debugging.
+ */
+ostream& operator <<(ostream& out, const HuffmanNode& node);
+
+#endif
diff --git a/labb6/src/bitstream.cpp b/labb6/src/bitstream.cpp new file mode 100755 index 0000000..c96beaf --- /dev/null +++ b/labb6/src/bitstream.cpp @@ -0,0 +1,372 @@ +/*
+ * TDDD86 Huffman Encoding
+ * This file contains the implementation of ibitstream and obitstream classes.
+ * These classes are patterned after (and, in fact, inherit from) the standard
+ * ifstream and ofstream classes. Please see bitstream.h for information about
+ * how a client properly uses these classes.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ */
+
+#include <iostream>
+#include "bitstream.h"
+#include "error.h"
+#include "strlib.h"
+
+static const int NUM_BITS_IN_BYTE = 8;
+
+inline int GetNthBit(int n, int fromByte) {
+ return ((fromByte & (1 << n)) != 0);
+}
+
+inline void SetNthBit(int n, int & inByte) {
+ inByte |= (1 << n);
+}
+
+/*
+ * Returns a printable string for the given character.
+ */
+static string toPrintable(int ch) {
+ if (ch == '\n') {
+ return "'\\n'";
+ } else if (ch == '\t') {
+ return "'\\t'";
+ } else if (ch == '\r') {
+ return "'\\r'";
+ } else if (ch == '\f') {
+ return "'\\f'";
+ } else if (ch == '\b') {
+ return "'\\b'";
+ } else if (ch == '\0') {
+ return "'\\0'";
+ } else if (ch == ' ') {
+ return "' '";
+ } else if (ch == (int) PSEUDO_EOF) {
+ return "EOF";
+ } else if (ch == (int) NOT_A_CHAR) {
+ return "NONE";
+ } else if (!isgraph(ch)) {
+ return "???";
+ } else {
+ return string("'") + (char) ch + string("'");
+ }
+}
+
+/* Constructor ibitstream::ibitstream
+ * ------------------------------
+ * Each ibitstream tracks 3 integers as private data.
+ * "lastTell" is streampos of the last byte that was read (this is used
+ * to detect when other non-readBit activity has changed the tell)
+ * "curByte" contains contents of byte currently being read
+ * "pos" is the bit position within curByte that is next to read
+ * We set initial state for lastTell and curByte to 0, then pos is
+ * set at 8 so that next readBit will trigger a fresh read.
+ */
+ibitstream::ibitstream() : istream(nullptr), lastTell(0), curByte(0), pos(NUM_BITS_IN_BYTE) {}
+
+/* Member function ibitstream::readBit
+ * ---------------------------------
+ * If bits remain in curByte, retrieve next and increment pos
+ * Else if end of curByte (or some other read happened), then read next byte
+ * and start reading from bit position 0 of that byte.
+ * If read byte from file at EOF, return EOF.
+ */
+int ibitstream::readBit() {
+ if (!is_open()) {
+ error("Cannot read a bit from a stream that is not open.");
+ }
+
+ // if just finished bits from curByte or if data read from stream after last readBit()
+ if (lastTell != tellg() || pos == NUM_BITS_IN_BYTE) {
+ if ((curByte = get()) == EOF) {
+ // read next single byte from file
+ return EOF;
+ }
+ pos = 0; // start reading from first bit of new byte
+ lastTell = tellg();
+ }
+ int result = GetNthBit(pos, curByte);
+ pos++; // advance bit position for next call to readBit
+ return result;
+}
+
+/* Member function ibitstream::rewind
+ * ---------------------------------
+ * Simply seeks back to beginning of file, so reading begins again
+ * from start.
+ */
+void ibitstream::rewind() {
+ if (!is_open()) {
+ error("Cannot rewind stream that is not open.");
+ }
+ clear();
+ seekg(0, ios::beg);
+}
+
+/* Member function ibitstream::size
+ * ------------------------------
+ * Seek to file end and use tell to retrieve position.
+ * In order to not disrupt reading, we also record cur streampos and
+ * re-seek to there before returning.
+ */
+long ibitstream::size() {
+ if (!is_open()) {
+ error("Cannot get size of stream which is not open.");
+ }
+ clear(); // clear any error state
+ streampos cur = tellg(); // save current streampos
+ seekg(0, ios::end); // seek to end
+ streampos end = tellg(); // get offset
+ seekg(cur); // seek back to original pos
+ return long(end);
+}
+
+/* Member function ibitstream::is_open
+ * -------------------------------------------
+ * Default implementation of is_open has the stream always
+ * open. Subclasses can customize this if they'd like.
+ */
+bool ibitstream::is_open() {
+ return true;
+}
+
+/* Constructor obitstream::obitstream
+ * ----------------------------------
+ * Each obitstream tracks 3 integers as private data.
+ * "lastTell" is streampos of the last byte that was written (this is used
+ * to detect when other non-writeBit activity has changed the tell)
+ * "curByte" contains contents of byte currently being written
+ * "pos" is the bit position within curByte that is next to write
+ * We set initial state for lastTell and curByte to 0, then pos is
+ * set at 8 so that next writeBit will start a new byte.
+ */
+obitstream::obitstream() : ostream(nullptr), lastTell(0), curByte(0), pos(NUM_BITS_IN_BYTE) {}
+
+/* Member function obitstream::writeBit
+ * ----------------------------------
+ * If bits remain to be written in curByte, add bit into byte and increment pos
+ * Else if end of curByte (or some other write happened), then start a fresh
+ * byte at position 0.
+ * We write the byte out for each bit (backing up to overwrite as needed), rather
+ * than waiting for 8 bits. This is because the client might make
+ * 3 writeBit calls and then start using << so we can't wait til full-byte
+ * boundary to flush any partial-byte bits.
+ */
+void obitstream::writeBit(int bit) {
+ if (bit != 0 && bit != 1) {
+ error(string("writeBit must be passed an integer argument of 0 or 1. You passed the integer ")
+ + toPrintable(bit) + " (" + integerToString(bit) + ").");
+ }
+ if (!is_open()) {
+ error("Cannot writeBit to stream which is not open.");
+ }
+
+ // if just filled curByte or if data written to stream after last writeBit()
+ if (lastTell != tellp() || pos == NUM_BITS_IN_BYTE) {
+ curByte = 0; // zero out byte for next writes
+ pos = 0; // start writing to first bit of new byte
+ }
+
+ if (bit) {
+ // only need to change if bit needs to be 1 (byte starts already zeroed)
+ SetNthBit(pos, curByte);
+ }
+
+ if (pos == 0 || bit) { // only write if first bit in byte or changing 0 to 1
+ if (pos != 0) {
+ seekp(-1, ios::cur); // back up to overwite if pos > 0
+ }
+ put(curByte);
+ }
+
+ pos++; // advance to next bit position for next write
+ lastTell = tellp();
+}
+
+
+/* Member function obitstream::size
+ * ------------------------------
+ * Seek to file end and use tell to retrieve position.
+ * In order to not disrupt writing, we also record cur streampos and
+ * re-seek to there before returning.
+ */
+long obitstream::size() {
+ if (!is_open()) {
+ error("Cannot get size of stream which is not open.");
+ }
+ clear(); // clear any error state
+ streampos cur = tellp(); // save current streampos
+ seekp(0, ios::end); // seek to end
+ streampos end = tellp(); // get offset
+ seekp(cur); // seek back to original pos
+ return long(end);
+}
+
+/* Member function obitstream::is_open
+ * -------------------------------------------
+ * Default implementation of is_open has the stream always
+ * open. Subclasses can customize this if they'd like.
+ */
+bool obitstream::is_open() {
+ return true;
+}
+
+/* Constructor ifbitstream::ifbitstream
+ * -------------------------------------------
+ * Wires up the stream class so that it knows to read data
+ * from disk.
+ */
+ifbitstream::ifbitstream() {
+ init(&fb);
+}
+
+/* Constructor ifbitstream::ifbitstream
+ * -------------------------------------------
+ * Wires up the stream class so that it knows to read data
+ * from disk, then opens the given file.
+ */
+ifbitstream::ifbitstream(const char* filename) {
+ init(&fb);
+ open(filename);
+}
+ifbitstream::ifbitstream(string filename) {
+ init(&fb);
+ open(filename);
+}
+
+/* Member function ifbitstream::open
+ * -------------------------------------------
+ * Attempts to open the specified file, failing if unable
+ * to do so.
+ */
+void ifbitstream::open(const char* filename) {
+ if (!fb.open(filename, ios::in | ios::binary)) {
+ setstate(ios::failbit);
+ }
+}
+
+void ifbitstream::open(string filename) {
+ open(filename.c_str());
+}
+
+/* Member function ifbitstream::is_open
+ * -------------------------------------------
+ * Determines whether the file stream is open.
+ */
+bool ifbitstream::is_open() {
+ return fb.is_open();
+}
+
+/* Member function ifbitstream::close
+ * -------------------------------------------
+ * Closes the file stream, if one is open.
+ */
+void ifbitstream::close() {
+ if (!fb.close()) {
+ setstate(ios::failbit);
+ }
+}
+
+/* Constructor ofbitstream::ofbitstream
+ * -------------------------------------------
+ * Wires up the stream class so that it knows to write data
+ * to disk.
+ */
+ofbitstream::ofbitstream() {
+ init(&fb);
+}
+
+/* Constructor ofbitstream::ofbitstream
+ * -------------------------------------------
+ * Wires up the stream class so that it knows to write data
+ * to disk, then opens the given file.
+ */
+ofbitstream::ofbitstream(const char* filename) {
+ init(&fb);
+ open(filename);
+}
+
+ofbitstream::ofbitstream(string filename) {
+ init(&fb);
+ open(filename);
+}
+
+/* Member function ofbitstream::open
+ * -------------------------------------------
+ * Attempts to open the specified file, failing if unable
+ * to do so.
+ */
+void ofbitstream::open(const char* filename) {
+ /* Confirm we aren't about to do something that could potentially be a
+ * Very Bad Idea.
+ */
+ if (endsWith(filename, ".cpp") || endsWith(filename, ".h") ||
+ endsWith(filename, ".hh") || endsWith(filename, ".cc")) {
+ error(string("It is potentially dangerous to write to file ")
+ + filename + ", because that might be your own source code. "
+ + "We are explicitly disallowing this operation. Please choose a "
+ + "different filename.");
+ setstate(ios::failbit);
+ } else {
+ if (!fb.open(filename, ios::out | ios::binary)) {
+ setstate(ios::failbit);
+ }
+ }
+}
+void ofbitstream::open(string filename) {
+ open(filename.c_str());
+}
+
+/* Member function ofbitstream::is_open
+ * -------------------------------------------
+ * Determines whether the file stream is open.
+ */
+bool ofbitstream::is_open() {
+ return fb.is_open();
+}
+
+/* Member function ofbitstream::close
+ * -------------------------------------------
+ * Closes the given file.
+ */
+void ofbitstream::close() {
+ if (!fb.close()) {
+ setstate(ios::failbit);
+ }
+}
+
+/* Constructor istringbitstream::istringbitstream
+ * -------------------------------------------
+ * Sets the stream to use the string buffer, then sets
+ * the initial string to the specified value.
+ */
+istringbitstream::istringbitstream(string s) {
+ init(&sb);
+ sb.str(s);
+}
+
+/* Member function istringbitstream::str
+ * -------------------------------------------
+ * Sets the underlying string in the buffer to the
+ * specified string.
+ */
+void istringbitstream::str(string s) {
+ sb.str(s);
+}
+
+/* Member function ostringbitstream::ostringbitstream
+ * -------------------------------------------
+ * Sets the stream to use the string buffer.
+ */
+ostringbitstream::ostringbitstream() {
+ init(&sb);
+}
+
+/* Member function ostringbitstream::str
+ * -------------------------------------------
+ * Retrives the underlying string data.
+ */
+string ostringbitstream::str() {
+ return sb.str();
+}
diff --git a/labb6/src/bitstream.h b/labb6/src/bitstream.h new file mode 100755 index 0000000..3e6c4b1 --- /dev/null +++ b/labb6/src/bitstream.h @@ -0,0 +1,368 @@ +/*
+ * TDDD86 Huffman Encoding
+ * This file defines the ibitstream and obitstream classes which are basically
+ * same as the ordinary istream and ostream classes, but add the
+ * functionality to read and write one bit at a time.
+ *
+ * The idea is that you can substitute an ibitstream in place of an
+ * istream and use the same operations (get, fail, >>, etc.)
+ * along with added member functions of readBit, rewind, and size.
+ *
+ * Similarly, the obitstream can be used in place of ofstream, and has
+ * same operations (put, fail, <<, etc.) along with additional
+ * member functions writebit and size.
+ *
+ * There are two subclasses of ibitstream: ifbitstream and istringbitstream,
+ * which are similar to the ifstream and istringstream classes. The
+ * obitstream class similarly has ofbitstream and ostringbitstream as
+ * subclasses.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ */
+
+#ifndef _bitstream_h
+#define _bitstream_h
+
+#include <istream>
+#include <ostream>
+#include <fstream>
+#include <sstream>
+using namespace std;
+
+/* Constant: PSEUDO_EOF
+ * A constant representing the PSEUDO_EOF marker that you will
+ * write at the end of your Huffman-encoded file.
+ */
+const int PSEUDO_EOF = 256;
+
+/* Constant: NOT_A_CHAR
+ * A constant representing an extended character that does not
+ * actually hold a value. When you are constructing your Huffman
+ * encoding tree, you should set the characters in each internal
+ * node (non-leaf) to this value to explicitly mark that they are not
+ * being used.
+ */
+const int NOT_A_CHAR = 257;
+
+/*
+ * Class: ibitstream
+ * ---------------
+ * Defines a class for reading files with all the functionality of istream
+ * along with an added member function for reading a single bit and convenience
+ * functions for rewinding the stream back to the beginning and getting the stream
+ * size.
+ *
+ * You will probably not create instances of this class directly. Instead, you
+ * will create ifbitstreams or istringbitstreams to read from files or string buffers.
+ */
+class ibitstream: public istream {
+public:
+ /*
+ * Constructor: ibitstream
+ * Usage: ibitstream stream;
+ * -----------------------
+ * Initializes a new ibitstream that is not attached to any source. You are
+ * unlikely to use this function directly.
+ */
+ ibitstream();
+
+ /*
+ * Member function: readBit
+ * Usage: bit = in.readBit();
+ * --------------------------
+ * Reads a single bit from the ibitstream and returns 0 or 1 depending on
+ * the bit value. If the stream is exhausted, EOF (-1) is returned.
+ * Raises an error if this ibitstream has not been properly opened.
+ */
+ int readBit();
+
+ /*
+ * Member function: rewind
+ * Usage: in.rewind();
+ * -------------------
+ * Rewinds the ibitstream back to the beginning so that subsequent reads
+ * start again from the beginning. Raises an error if this ibitstream
+ * has not been properly opened.
+ */
+ void rewind();
+
+ /*
+ * Member function: size
+ * Usage: sz = in.size();
+ * ----------------------
+ * Returns the size in bytes of the data attached to this stream.
+ * Raises an error if this ibitstream has not been properly opened.
+ */
+ long size();
+
+ /*
+ * Member function: is_open()
+ * Usage: if (ibs.is_open()) { ... }
+ * ----------------------
+ * Returns whether or not this ibitstream is opened. This only has
+ * meaning if the ibitstream is a file stream; otherwise it always
+ * returns true.
+ */
+ virtual bool is_open();
+
+private:
+ std::streampos lastTell;
+ int curByte;
+ int pos;
+};
+
+
+/*
+ * Class: obitstream
+ * ---------------
+ * Defines a class for writing files with all the functionality of ostream
+ * along with an added member function for writing a single bit and a convenience
+ * function for getting the stream size.
+ *
+ * You are unlikely to instantiate this class directly; instead, instantiate one
+ * of the subclasses.
+ */
+
+class obitstream: public ostream {
+public:
+ /*
+ * Constructor: obitstream
+ * Usage: obitstream outfile;
+ * ------------------------
+ * Initializes a new obitstream that is not attached to any file. Use the
+ * open member function from ofstream to attach the stream to a file.
+ */
+ obitstream();
+
+ /*
+ * Member function: writeBit
+ * Usage: out.writeBit(1);
+ * -----------------------
+ * Writes a single bit to the obitstream.
+ * Raises an error if this ibitstream has not been properly opened.
+ */
+ void writeBit(int bit);
+
+ /*
+ * Member function: size
+ * Usage: sz = in.size();
+ * ----------------------
+ * Returns the size in bytes of the file attached to this stream.
+ * Raises an error if this obitstream has not been properly opened.
+ */
+ long size();
+
+ /*
+ * Member function: is_open()
+ * Usage: if (ibs.is_open()) { ... }
+ * ----------------------
+ * Returns whether or not this obitstream is opened. This only has
+ * meaning if the obitstream is a file stream; otherwise it always
+ * returns true.
+ */
+ virtual bool is_open();
+
+private:
+ std::streampos lastTell;
+ int curByte;
+ int pos;
+};
+
+/*
+ * Class: ifbitstream
+ * ---------------
+ * A class for reading files in all of the usual ways, plus bit-by-bit.
+ * You can treat this class like a normal ifstream, except that there is
+ * extra support for bit-level operations.
+ */
+
+class ifbitstream: public ibitstream {
+public:
+ /*
+ * Constructor: ifbitstream();
+ * Usage: ifbitstream ifb;
+ * -------------------------
+ * Constructs a new ifbitstream not attached to any file. You can
+ * open a file for reading using the .open() member functions.
+ */
+ ifbitstream();
+
+ /*
+ * Constructor: ifbitstream(const char* filename);
+ * Constructor: ifbitstream(string filename);
+ * Usage: ifbitstream ifb("filename");
+ * -------------------------
+ * Constructs a new ifbitstream that reads the specified file, if
+ * it exists. If not, the stream enters an error state.
+ */
+ ifbitstream(const char* filename);
+ ifbitstream(string filename);
+
+ /*
+ * Member function: open(const char* filename);
+ * Member function: open(string filename);
+ * Usage: ifb.open("my-file.txt");
+ * -------------------------
+ * Opens the specified file for reading. If an error occurs, the
+ * stream enters a failure state, which can be detected by calling
+ * ifb.fail().
+ */
+ void open(const char* filename);
+ void open(string filename);
+
+ /*
+ * Member function: is_open();
+ * Usage: if (ifb.is_open()) { ... }
+ * --------------------------
+ * Returns whether or not this ifbitstream is connected to a file for
+ * reading.
+ */
+ bool is_open();
+
+ /*
+ * Member function: close();
+ * Usage: ifb.close();
+ * --------------------------
+ * Closes the currently-opened file, if the stream is open. If the
+ * stream is not open, puts the stream into a fail state.
+ */
+ void close();
+
+private:
+ /* The actual file buffer which does reading and writing. */
+ filebuf fb;
+};
+
+/*
+ * Class: ofbitstream
+ * ---------------
+ * A class for writing files in all of the usual ways, plus bit-by-bit.
+ * You can treat this class like a normal ofstream, except that there is
+ * extra support for bit-level operations.
+ *
+ * As a safety feature, you cannot use ofbitstream to open files that end
+ * in .h, .hh, .cpp, or .cc for writing, as this could very easily cause
+ * you to destroy your source files.
+ */
+
+class ofbitstream: public obitstream {
+public:
+ /*
+ * Constructor: ofbitstream();
+ * Usage: ofbitstream ofb;
+ * -------------------------
+ * Constructs a new ofbitstream not attached to any file. You can
+ * open a file for writing using the .open() member functions.
+ */
+ ofbitstream();
+
+ /*
+ * Constructor: ofbitstream(const char* filename);
+ * Constructor: ofbitstream(string filename);
+ * Usage: ofbitstream ofb("filename");
+ * -------------------------
+ * Constructs a new ofbitstream that writes the specified file, if
+ * it exists. If not, the stream enters an error state. Read
+ * the documentation on "open" for more details.
+ */
+ ofbitstream(const char* filename);
+ ofbitstream(string filename);
+
+ /*
+ * Member function: open(const char* filename);
+ * Member function: open(string filename);
+ * Usage: ofb.open("my-file.txt");
+ * -------------------------
+ * Opens the specified file for writing. If an error occurs, the
+ * stream enters a failure state, which can be detected by calling
+ * ifb.fail(). If an invalid filename is specified (for example,
+ * a source file), reports an error.
+ */
+ void open(const char* filename);
+ void open(string filename);
+
+ /*
+ * Member function: is_open();
+ * Usage: if (ofb.is_open()) { ... }
+ * --------------------------
+ * Returns whether or not this ofbitstream is connected to a file for
+ * reading.
+ */
+ bool is_open();
+
+ /*
+ * Member function: close();
+ * Usage: ifb.close();
+ * --------------------------
+ * Closes the currently-opened file, if the stream is open. If the
+ * stream is not open, puts the stream into a fail state.
+ */
+ void close();
+
+private:
+ /* The actual file buffer which does reading and writing. */
+ filebuf fb;
+};
+
+/*
+ * Class: istringbitstream
+ * ---------------
+ * A variant on C++'s istringstream class, which acts as a stream that
+ * reads its data from a string. This is mostly used by the testing
+ * code to test your Huffman encoding without having to read or write
+ * files on disk, but you can use it in your own testing if you would
+ * like.
+ */
+class istringbitstream: public ibitstream {
+public:
+ /* Constructor: istringbitstream(string s = "");
+ * Usage: istringbitstream stream;
+ * --------------------------
+ * Constructs an istringbitstream reading the specified string.
+ */
+ istringbitstream(string s = "");
+
+ /* Member Function: str(string s);
+ * Usage: isb.str("This is some text!");
+ * ---------------------------
+ * Sets the underlying string of the istringbitstream.
+ */
+ void str(string s);
+private:
+ /* The actual string buffer that does character storage. */
+ stringbuf sb;
+};
+
+/*
+ * Class: ostringbitstream
+ * ---------------
+ * A variant on C++'s ostringstream class, which acts as a stream that
+ * writes its data to a string. This is mostly used by the testing
+ * code to test your Huffman encoding without having to read or write
+ * files on disk, but you can use it in your own testing if you would
+ * like.
+ */
+
+class ostringbitstream: public obitstream {
+public:
+ /* Constructor: ostringbitstream();
+ * Usage: ostringbitstream stream;
+ * --------------------------
+ * Constructs an ostringbitstream.
+ */
+ ostringbitstream();
+
+ /* Member function: string str();
+ * Usage: cout << osb.str() << endl;
+ * ----------------------------
+ * Retrieves the underlying string of the istringbitstream.
+ */
+ string str();
+
+private:
+ /* The actual string buffer that does character storage. */
+ stringbuf sb;
+};
+
+#endif
diff --git a/labb6/src/encoding.cpp b/labb6/src/encoding.cpp new file mode 100755 index 0000000..b6edb84 --- /dev/null +++ b/labb6/src/encoding.cpp @@ -0,0 +1,44 @@ +// This is the CPP file you will edit and turn in.
+// Also remove these comments here and add your own, along with
+// comments on every function and on complex code sections.
+// TODO: remove this comment header
+
+#include "encoding.h"
+// TODO: include any other headers you need
+
+map<int, int> buildFrequencyTable(istream& input) {
+ // TODO: implement this function
+ map<int, int> freqTable;
+ return freqTable;
+}
+
+HuffmanNode* buildEncodingTree(const map<int, int> &freqTable) {
+ // TODO: implement this function
+ return nullptr;
+}
+
+map<int, string> buildEncodingMap(HuffmanNode* encodingTree) {
+ // TODO: implement this function
+ map<int, string> encodingMap;
+ return encodingMap;
+}
+
+void encodeData(istream& input, const map<int, string> &encodingMap, obitstream& output) {
+ // TODO: implement this function
+}
+
+void decodeData(ibitstream& input, HuffmanNode* encodingTree, ostream& output) {
+ // TODO: implement this function
+}
+
+void compress(istream& input, obitstream& output) {
+ // TODO: implement this function
+}
+
+void decompress(ibitstream& input, ostream& output) {
+ // TODO: implement this function
+}
+
+void freeTree(HuffmanNode* node) {
+ // TODO: implement this function
+}
diff --git a/labb6/src/encoding.h b/labb6/src/encoding.h new file mode 100755 index 0000000..5a5fe48 --- /dev/null +++ b/labb6/src/encoding.h @@ -0,0 +1,33 @@ +/*
+ * TDDD86 Huffman Encoding
+ * This file declares the functions that you will need to write in this
+ * assignment for your Huffman Encoder in huffmanencoding.cpp.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ */
+
+#ifndef _encoding_h
+#define _encoding_h
+
+#include <iostream>
+#include <string>
+#include <map>
+#include "bitstream.h"
+#include "HuffmanNode.h"
+using namespace std;
+
+/*
+ * See huffmanencoding.cpp for documentation of these functions
+ * (which you are supposed to write, based on the spec).
+ */
+map<int, int> buildFrequencyTable(istream& input);
+HuffmanNode* buildEncodingTree(const map<int, int>& freqTable);
+map<int, string> buildEncodingMap(HuffmanNode* encodingTree);
+void encodeData(istream& input, const map<int, string>& encodingMap, obitstream& output);
+void decodeData(ibitstream& input, HuffmanNode* encodingTree, ostream& output);
+void compress(istream& input, obitstream& output);
+void decompress(ibitstream& input, ostream& output);
+void freeTree(HuffmanNode* node);
+
+#endif
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);
+}
diff --git a/labb6/src/huffmanutil.cpp b/labb6/src/huffmanutil.cpp new file mode 100755 index 0000000..918a7c3 --- /dev/null +++ b/labb6/src/huffmanutil.cpp @@ -0,0 +1,206 @@ +/*
+ * TDDD86 Huffman Encoding
+ * This file defines various utility functions used by the main client program.
+ * See huffmanutil.h for documentation of each function.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ */
+
+#include "huffmanutil.h"
+#include "bitstream.h"
+#include "strlib.h"
+#include "simpio.h"
+
+string bitsToBytes(string text) {
+ istringbitstream input(text);
+ ostringstream out;
+ while (true) {
+ int bit = input.readBit();
+ if (input.fail()) {
+ break;
+ }
+ out.put(bit == 1 ? '1' : '0');
+ }
+ return out.str();
+}
+
+string bytesToBits(string text) {
+ ostringbitstream out;
+ for (int i = 0; i < (int) text.length(); i++) {
+ out.writeBit(text[i] == '1' ? 1 : 0);
+ }
+ return out.str();
+}
+
+#if defined(_WIN32) || defined(_WIN64)
+ #include <windows.h>
+#else
+ // assume POSIX
+ #include <sys/stat.h>
+#endif
+
+bool confirmOverwrite(string filename) {
+#if defined(_WIN32) || defined(_WIN64)
+ bool fileExists = (GetFileAttributesA(filename.c_str()) != INVALID_FILE_ATTRIBUTES);
+#else
+ // assume POSIX
+ struct stat fileInfo;
+ bool fileExists = (stat(filename.c_str(), &fileInfo) == 0);
+#endif
+ if (!fileExists) {
+ return true;
+ } else {
+ return yesOrNo(filename + " already exists. Overwrite? (y/n) ");
+ }
+}
+
+int fileSize(string filename) {
+ ifstream input;
+ input.open(filename.c_str(), ifstream::binary);
+ input.seekg(0, ifstream::end);
+ return (int) input.tellg();
+}
+
+void printBits(string text) {
+ istringbitstream input(text);
+ int i = 0;
+ while (true) {
+ i++;
+ int bit = input.readBit();
+ if (input.fail()) break;
+ cout << bit;
+ if (i > 0 && i % 8 == 0) {
+ cout << " ";
+ }
+ if (i > 0 && i % 64 == 0) {
+ cout << endl;
+ }
+ }
+ cout << endl;
+}
+
+string promptForExistingFileName(string prompt) {
+ while (true) {
+ string filename = getLine(prompt);
+#if defined(_WIN32) || defined(_WIN64)
+ bool fileExists = (GetFileAttributesA(filename.c_str()) != INVALID_FILE_ATTRIBUTES);
+#else
+ // assume POSIX
+ struct stat fileInfo;
+ bool fileExists = (stat(filename.c_str(), &fileInfo) == 0);
+#endif
+ if (fileExists) {
+ return filename;
+ } else {
+ cout << "That file does not exist; please try again." << endl;
+ }
+ }
+ return "";
+}
+
+string readEntireFileText(string filename) {
+ ifstream input;
+ input.open(filename.c_str());
+ return readEntireFileText(input);
+}
+
+string readEntireFileText(istream& input) {
+ ostringstream out;
+ while (true) {
+ int ch = input.get();
+ if (input.fail()) {
+ break;
+ }
+ out << (char) ch;
+ }
+ return out.str();
+}
+
+string stringReplace(string s, char oldChar, char newChar) {
+ for (int i = (int) s.length() - 1; i >= 0; i--) {
+ if (s[i] == oldChar) {
+ s[i] = newChar;
+ }
+ }
+ return s;
+}
+
+string stringReplace(string s, char oldChar, string newStr) {
+ for (int i = (int) s.length() - 1; i >= 0; i--) {
+ if (s[i] == oldChar) {
+ s.erase(i, 1);
+ if (newStr.length() > 0) {
+ s.insert(i, newStr);
+ }
+ }
+ }
+ return s;
+}
+
+string stringReplace(string s, string oldStr, string newStr) {
+ int l2 = oldStr.length();
+ for (int i = (int) (s.length() - l2); i >= 0; i--) {
+ if (s.substr(i, l2) == oldStr) {
+ s.replace(i, l2, newStr);
+ }
+ }
+ return s;
+}
+
+/*
+ * Returns a printable string for the given character. See bitstream.h.
+ */
+string toPrintableChar(int ch) {
+ if (ch == '\n') {
+ return "'\\n'";
+ } else if (ch == '\t') {
+ return "'\\t'";
+ } else if (ch == '\r') {
+ return "'\\r'";
+ } else if (ch == '\f') {
+ return "'\\f'";
+ } else if (ch == '\b') {
+ return "'\\b'";
+ } else if (ch == '\0') {
+ return "'\\0'";
+ } else if (ch == ' ') {
+ return "' '";
+ } else if (ch == (int) PSEUDO_EOF) {
+ return "EOF";
+ } else if (ch == (int) NOT_A_CHAR) {
+ return "NONE";
+ } else if (!isgraph(ch)) {
+ return "???";
+ } else {
+ return string("'") + (char) ch + string("'");
+ }
+}
+
+bool yesOrNo(string prompt) {
+ while (true) {
+ string answer = trim(toLowerCase(getLine(prompt)));
+ if (startsWith(answer, 'y')) {
+ return true;
+ } else if (startsWith(answer, 'n')) {
+ return false;
+ } else {
+ cout << "Please type a word that begins with 'y' or 'n'." << endl;
+ }
+ }
+}
+
+string getRoot(string filename) {
+ int dot = -1;
+ int len = filename.length();
+ for (int i = 0; i < len; i++) {
+ char ch = filename[i];
+ if (ch == '.') dot = i;
+ if (ch == '/' || ch == '\\') dot = -1;
+ }
+ if (dot == -1) {
+ return filename;
+ } else {
+ return filename.substr(0, dot);
+ }
+}
diff --git a/labb6/src/huffmanutil.h b/labb6/src/huffmanutil.h new file mode 100755 index 0000000..b78023d --- /dev/null +++ b/labb6/src/huffmanutil.h @@ -0,0 +1,105 @@ +/*
+ * TDDD86 Huffman Encoding
+ * This file declares various utility functions used by the main client program.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ */
+
+#ifndef _huffmanutil_h
+#define _huffmanutil_h
+
+#include <iostream>
+#include <string>
+using namespace std;
+
+/*
+ * Takes a string of 0 and 1 binary bits and unpacks it so that it actually
+ * stores them with each "bit" being its own ASCII character of '0' or '1'.
+ */
+string bitsToBytes(string text);
+
+/*
+ * Takes a string of '0' and '1' characters and packs it so that it actually
+ * stores them as bits rather than each "bit" being its own ASCII character.
+ */
+string bytesToBits(string text);
+
+/*
+ * Checks whether the given file exists; if it does, prompts the user whether
+ * they want to overwrite the file. Returns true if the user does want to
+ * overwrite, and false if not.
+ */
+bool confirmOverwrite(string filename);
+
+/*
+ * Returns the size of the given file in bytes.
+ */
+int fileSize(string filename);
+
+/*
+ * Displays a detailed dump of every bit and byte of the given string.
+ * It prints every 8 bits (one byte) followed by a space, 8 bytes per line.
+ * e.g. 10010010 10110011 10100010 00011101 ...
+ */
+void printBits(string text);
+
+/*
+ * Repeatedly asks the user to type a file name using the given prompt message
+ * until the user types the name of a file that exists, then returns that file's name.
+ */
+string promptForExistingFileName(string prompt);
+
+/*
+ * Reads the entire contents of the given input source and returns them as a string.
+ */
+string readEntireFileText(istream& input);
+
+/*
+ * Reads the entire contents of the given input file and returns them as a string.
+ */
+string readEntireFileText(string filename);
+
+/*
+ * Replaces all occurrences in s of the given character with the given other character,
+ * returning the newly formed string.
+ */
+string stringReplace(string s, char oldChar, string newChar);
+
+/*
+ * Replaces all occurrences in s of the given character with the given string,
+ * returning the newly formed string.
+ */
+string stringReplace(string s, char oldChar, string newStr);
+
+/*
+ * Replaces all occurrences in s of the given string with the given other string,
+ * returning the newly formed string.
+ */
+string stringReplace(string s, string oldStr, string newStr);
+
+/*
+ * Returns a string that represents the given character.
+ * For most standard ASCII characters, this is just the character itself.
+ * But for whitespace, escape characters, and extended ASCII, it returns an
+ * expanded representation like "\\n" for '\n' or "???" for a non-printable char.
+ * It also returns "EOF" when passed PSEUDO_EOF and NOT when passed NOT_A_CHAR.
+ */
+string toPrintableChar(int ch);
+
+/*
+ * Prompts the user to answer a yes/no question and returns true if the user
+ * typed 'yes' (or anything that starts with a 'y', case-insensitively),
+ * false if the user types anything that starts with 'n', or re-prompts if
+ * the user doesn't type a 'y' or 'n' word.
+ */
+bool yesOrNo(string prompt);
+
+/*
+ * Returns the root of filename. The root consists
+ * of everything in filename up to the last dot and
+ * the subsequent extension. If no dot appears in the final component
+ * of the filename, getRoot returns the entire name.
+ */
+std::string getRoot(std::string filename);
+#endif
diff --git a/labb6/src/readme.txt b/labb6/src/readme.txt new file mode 100755 index 0000000..1d48e84 --- /dev/null +++ b/labb6/src/readme.txt @@ -0,0 +1,3 @@ +This directory contains the source code files (*.cpp, *.h)
+that you will write as you complete the assignment.
+We will also put any instructor-provided code here.
|