David Hadizadeh

#ifndef MAIN_HEADER
#define MAIN_HEADER
 
#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
#include "menu.h"
#include "huffman.h"
 
using namespace std;
 
string read_string();
 
string read_filename(bool exist);
 
vector<bool> compress_single(Huffman* huffman_compr);
 
void decompress_single(Huffman* huffman_compr, vector<bool> compr_bits);
 
bool* compress_file(Huffman* huffman_compr, bool* compr_bits, int* count, int algo_id);
 
void save_compression(bool* compr_bits, int length);
 
void save_decompression(Huffman* huffman_compr);
 
void build_tree(Huffman* huffman_compr, string filename);
 
#endif

/**	@file main.cpp	Datei zum Starten eines Menues und Ausfuehren des Huffman-Algorithmus
 
	@author		- David Hadizadeh
	@version	- 1.0
	@date		- 07.06.2012
*/
 
#include "main.h"
 
/**	Start-Funktion, die ein Objekt der Huffman-Klasse auf dem Heap erzeugt
	und auf dieses bei verschiedenen Menüauswahlen die jeweilige Methode
	des Huffman-Objekts aufruft.
	Abschliessend wird das Objekt ordnungsgemaess vom Speicher entfernt.
 
	@param argc Anzahl uebergebener Parameter
	@param argv Parameter-Feld, das beim Start des Programms uebergeben wird
	@returns Wert der angibt, ob das Programm korrekt beendet wurde (0 = korrekt).
*/
int main(int argc, char *argv[]) {
 
	Huffman* huffman_compr = new Huffman();
	vector<bool> cur_compression;
	build_tree(huffman_compr, "data/english");
	bool* compr_bits = 0;
	int count_bits = 0;
	const int COUNT_MENU = 8;
	const string MENU_NAMES[COUNT_MENU] = {
		"Aktuellen Huffman-Tree anzeigen",
		"Neuen Huffman-Tree anhand einer Textdatei generieren.",
		"Manuellen Text komprimieren und ausgeben",
		"Manuell eingegebenen komprimierten Text dekomprimiert ausgeben",
		"Datei komprimieren und abspeichern [intuitiver Algorithmus]",
		"Datei komprimieren und abspeichern [mit einfacher Tabelle]",
		"Datei komprimieren und abspeichern [mit Hash-Look-Up Tabelle]",
		"Komprimierte Datei dekomprimieren und als Datei speichern",
	};
 
	int selection = COUNT_MENU;
	do {
		cout << "Bitte waehlen Sie einen Menuepunkt aus:" << endl << endl;
		selection = get_menu(MENU_NAMES, COUNT_MENU);
 
		switch(selection) {
			case 1:
				system("data\\tree.png");
				break;
			case 2:
				build_tree(huffman_compr, read_filename(true));
				break;
			case 3:
				cur_compression = compress_single(huffman_compr);
				break;
			case 4:
				decompress_single(huffman_compr, cur_compression);
				break;
			case 5:
				compr_bits = compress_file(huffman_compr, compr_bits, &count_bits, 0);
				save_compression(compr_bits, count_bits);
				break;
			case 6:
				compr_bits = compress_file(huffman_compr, compr_bits, &count_bits, 1);
				save_compression(compr_bits, count_bits);
				break;
			case 7:
				compr_bits = compress_file(huffman_compr, compr_bits, &count_bits, 2);
				save_compression(compr_bits, count_bits);
				break;
			case 8:
				save_decompression(huffman_compr);
				break;
		}
 
		cout << endl << endl;
	} while(selection != (COUNT_MENU + 1));
 
	delete huffman_compr;
 
	return 0;
}
 
/**	Liest einen Text (mit Leerzeichen) ein und leert vor- und nachher den Puffer.
 
    @returns eingelesenen Text
*/
string read_string() {
	string text = "";
	cin.seekg(0, std::ios::end);
	cin.clear();
	getline(cin, text);
	cin.seekg(0, std::ios::end);
	cin.clear();
	return text;
}
 
/**	Fragt nach einem Dateinamen, liest ihn ein und prueft, ob die
	Datei existiert. Je nach Parameteruebergabe wird dies so lange wiederholt,
	wie erforderlich.
 
    @param exist 0, wenn die Datei nicht existieren muss, sonst muss sie existieren
    @returns eingelesener Dateiname
*/
string read_filename(bool exist) {
	string filename;
	do {
		cout << "Bitte geben Sie einen Dateinamen ein: ";
		filename = read_string();
 
		ifstream check_file("data/" + filename);
		if(exist && !check_file) {
			cout << "Diese Datei existiert nicht." << endl;
			filename = "";
		} else {
			filename = "data/" + filename;
		}
	} while (filename == "" && exist);
 
	return filename;
}
 
/**	Komprimiert einen einzelnen einzulesenden Text und gibt deren Kompressionsbits
	aus.
 
    @param huffman_compr Zeiger auf ein Huffman-Objekt, das zum Ausfuehren des Algorithmus verwendet wird
    @returns Kompressions-Bits
*/
vector<bool> compress_single(Huffman* huffman_compr) {
	string text;
	vector<bool> compr_bits_vec;
	cout << "Bitte geben Sie den Text ein, der komprimiert werden soll:" << endl;
	text = read_string();
 
	bool* compr_bits = 0;
	int count_compr_bits = 0;
	//compr_bits = huffman_compr->compress_lookup(compr_bits, &count_compr_bits, text, false);
	compr_bits = huffman_compr->compress_table(compr_bits, &count_compr_bits, text, false);
 
	cout << endl << "Komprimierter Text: " << endl;
	for (unsigned int i = 0; i < count_compr_bits; i++) {
		compr_bits_vec.push_back(compr_bits[i]);
		cout << compr_bits[i];
	}
	cout << endl << endl;
	if (compr_bits != 0) {
		delete [] compr_bits;
		compr_bits = 0;
	}
	return compr_bits_vec;
}
 
/**	Dekomprimiert uebergebene Bits mit dem Huffman-Algorithmus und gibt den dekomprimierten
	Text aus.
 
    @param huffman_compr Zeiger auf ein Huffman-Objekt, das zum Ausfuehren des Algorithmus verwendet wird
    @param compr_bits text
*/
void decompress_single(Huffman* huffman_compr, vector<bool> compr_bits) {
	string read_string;
	cout << "Der derzeit gespeicherte komprimierte Bitstream ist dekomprimiert:" << endl;
	cout << huffman_compr->decompress(compr_bits) << endl << endl;
}
 
/**	Komprimiert eine komplette Datei auf 3 verschiedene Arten und gibt deren Dauer aus.
 
    @param huffman_compr Zeiger auf ein Huffman-Objekt, das zum Ausfuehren des Algorithmus verwendet wird
	@param algo_id Algorithmus-ID, 0 fuer intuitiven, 1 fuer tabellearischen, sonst Loookup Algorithmus
    @returns Zeiger auf Komprimierte Bits
*/
bool* compress_file(Huffman* huffman_compr, bool* compr_bits, int* count, int algo_id) {
	cout << "Zu komprimierende Datei:" << endl;
	string compr_file = read_filename(true);
 
	clock_t time_start = clock();
	if (algo_id == 0) {
		compr_bits = huffman_compr->compress(compr_bits, count, compr_file, true);
	} else if (algo_id == 1) {
		compr_bits = huffman_compr->compress_table(compr_bits, count, compr_file, true);
	} else {
		compr_bits = huffman_compr->compress_lookup(compr_bits, count, compr_file, true);
	}
	cout << endl << "Dauer: " << ((double)(clock() - time_start)) / 1000.0 << " Sekunden" << endl << endl;
	return compr_bits;
}
 
/**	Speichert die uebergebenen Bits in einer Datei.
 
    @param compr_bits zu speichernde Bits
*/
void save_compression(bool* compr_bits, int length) {
	cout << "Ausgabe-Datei:" << endl;
	char value = 0;
	int j = 0;
	fstream f;
	f.open(read_filename(false), ios::out);
	for (int i = 0; i < length; i++) {
		value |= compr_bits[i] << (j % 8);
		j++;
		if (j % 8 == 0) {
			f << value;
			value = 0;
		}
	}
	if (j % 8 != 0) {
		f << value;
	}
	f.close();
	if (compr_bits != 0) {
		delete [] compr_bits;
		compr_bits = 0;
	}
}
 
/**	Liest eine komprimierte Datei ein, dekomprimiert sie und
	speichert sie in einer anderen Datei. Die Dateinamen werden
	jeweils eingelesen.
 
    @param huffman_compr Zeiger auf ein Huffman-Objekt, das zum Ausfuehren des Algorithmus verwendet wird
*/
void save_decompression(Huffman* huffman_compr) {
	cout << "Einlese-Datei:" << endl;
	string filename = read_filename(true);
	cout << "Ausgabe-Datei:" << endl;
	huffman_compr->decompress(filename, read_filename(false));
}
 
/**	Erzeugt einen Huffman-Binaer-Baum anhand einer Datei.
 
    @param huffman_compr Zeiger auf ein Huffman-Objekt, das zum Ausfuehren des Algorithmus verwendet wird
	@param filename Dateiname der Datei, die als Wortvorlage verwendet wird
*/
void build_tree(Huffman* huffman_compr, string filename) {
	huffman_compr->build_tree(filename, true);
	huffman_compr->save_tree("data/tree.txt");
	system("data\\dot.exe -Tpng data/tree.txt > data/tree.png");
}

#ifndef MENU_HEADER
#define MENU_HEADER
 
#include <iostream>
#include <sstream>
 
using namespace std;
 
void print_menu_names(const string names[], int count);
 
int get_menu(const string names[], int count);
 
#endif

/**	@file menu.cpp Liefert Funktionalitaet, um ein Menue auszugeben und aus
	diesem Menue die einzelnen Punkte mit
	Zahlen auszuwaehlen.
 
	@author		- David Hadizadeh
	@version	- 1.0
	@date		- 07.06.2012
*/
 
#include <iostream>
#include <iomanip>
#include <cstring>
#include <sstream>
 
#include "menu.h"
 
using namespace std;
 
/**	Gibt das Menue mit uebergebenen Punkten
	geordnet und nummeriert aus. Der Menue-Punkt
	Programm-Beenden wird automatisch erzeugt.
 
	@param names Feld mit Namen der Menue-Punkte
	@param count Anzahl der Menue-Punkte
*/
void print_menu_names(const string names[], int count) {
	int x = 0;
	for(x = 0; x < count; x++) {
        std::ostringstream stm;
        stm << "("  << (x+1) << ")";
 
		cout << left << setw(6) << stm.str();
 
		cout << names[x] << endl;
	}
 
	cout << setw(0) << "(" << (x+1) << ")  ";
 
	if (x+1 > 9) {
		cout << "Beenden";
	} else {
		cout << " Beenden";
	}
 
	 cout << endl << endl;
}
 
/**	Ruft das Ausgeben des Menues auf und erfasst
	die Benutzereingabe zum waehlen eines
	Menue-Punktes.
 
	@param names Feld mit Namen der Menue-Punkte
	@param count Anzahl der Menue-Punkte
	@returns ausgewaehlte Menue-Punkt-Nummer
*/
int get_menu(const string names[], int count) {
	cout << "Bitte waehlen:" << endl;
 
	print_menu_names(names, count);
 
    int result = 0;
	cout << "Bitte geben Sie einen Menuepunkt ein: ";
 
	cin.seekg(0, std::ios::end);
	cin.clear();
	cin >> result;
	cin.seekg(0, std::ios::end);
	cin.clear();
 
    cout << endl << endl;
 
	return result;
}

#ifndef LETTER_HEADER
#define LETTER_HEADER
 
/**
	Klasse zum Verwalten von Buchstaben und deren Anzahlen
*/
class Letter {
	private:
		/**
			Buchstabe
		*/
		int letter;
		/**
			Anzahl an Vorkommnissen des Buchstabens
		*/
		int count;
 
	public:
		Letter();
		Letter(int cur_letter);
		virtual bool operator< (const Letter& compare) const;
		virtual int get_letter() const;
		virtual int get_count() const;
		virtual void add_count();
 
	private:
 
};
 
#endif

/**	@file letter.cpp Verwalten von Buchstaben und deren Anzahlen
 
	@author		- David Hadizadeh
	@version	- 1.0
	@date		- 07.06.2012
*/
 
#include "letter.h"
 
/**	Erzeugt einen Buchstaben mit 0 als Wert und 0 als Vorkommens-Anzahl
*/
Letter::Letter() {
	letter = 0;
	count = 0;
}
 
/**	Erzeugt einen Buchstaben mit 0 als Vorkommens-Anzahl
 
    @param cur_letter Dezimalwert des Buchstaben
*/
Letter::Letter(int cur_letter) {
	letter = cur_letter;
	count = 0;
}
 
/**	Ueberladung des < Operator ermoeglicht den Vergleich von Buchstaben.
	Buchstaben mit geringerer Anzahl sind kleiner als Buchstaben mit
	groesserer Vorkommens-Anzahl.
 
    @param compare zu vergleichender Buchstabe
    @returns 0, wenn der aktuelle Buchstabe nicht kleiner ist, sonst ist er kleiner
*/
bool Letter::operator< (const Letter& compare) const {
	return (count < compare.get_count());
}
 
/**	Liefert den aktuellen Buchstaben.
 
    @returns aktueller Buchstabe
*/
int Letter::get_letter() const {
	return letter;
}
 
/**	Liefert die aktuelle Vorkommens-Anzahl.
 
    @returns Anzahl
*/
int Letter::get_count() const {
	return count;
}
 
/**	Erhoeht die Vorkommens-Anzahl um 1.
*/
void Letter::add_count() {
	count++;
}

#ifndef HUFFMAN_ELEMENT_HEADER
#define HUFFMAN_ELEMENT_HEADER
 
#include <list>
 
using namespace std;
 
/**
	Klasse zum Verwalten von Huffman-Knoten und -Blaettern
*/
class HuffmanElement {
	private:
		/**
			Anzahl der Gesamtknoten
		*/
		static int count_nodes;
		/**
			Groesse des laengsten Lookup-Codes
		*/
		static int longest_code;
		/**
			Name des Knotens
		*/
		int name;
		/**
			Buchstabe des Blatts
		*/
		char letter;
		/**
			Linker Ast
		*/
		HuffmanElement* left;
		/**
			Rechter Ast
		*/
		HuffmanElement* right;
		/**
			Wert des Asts
		*/
		int value;
		/**
			Uebergeordneter Knoten
		*/
		HuffmanElement* parent;
		/**
			Ist es ein rechter Ast, dann true, sonst ist es ein linker Ast
		*/
		bool is_right;
		/**
			Binaer-Code des Knotens/Blatts
		*/
		bool* lookup_code;
		/**
			Laenge des Binaer-Codes des Knotens/Blatts
		*/
		unsigned int lookup_code_length;
 
	public:
		HuffmanElement();
		HuffmanElement(char cur_letter, int cur_value);
		HuffmanElement(HuffmanElement* cur_left, HuffmanElement* cur_right, int cur_value);
		HuffmanElement(const HuffmanElement& original);
		virtual ~HuffmanElement();
		virtual HuffmanElement& operator=(const HuffmanElement& original);
		virtual bool operator> (const HuffmanElement& compare) const;
		virtual char get_letter() const;
		virtual int get_value() const;
		virtual int get_name() const;
		virtual bool get_is_right() const;
		virtual HuffmanElement* get_parent();
		virtual HuffmanElement* get_left();
		virtual HuffmanElement* get_right();
		virtual bool* get_lookup_code();
		virtual unsigned int get_lookup_code_length() const;
		virtual void set_parent(HuffmanElement* cur_parent, bool cur_is_right);
		virtual void add_lookup_code(bool code);
		virtual int get_longest_code();
 
	private:
		void copy_huffman_element(const HuffmanElement& original);
		void delete_huffman_element();
};
 
/**
	Comparator zum Vergleichen von Knoten/Blaettern
*/
struct compareCharacters {
  bool operator ()(HuffmanElement *left, HuffmanElement *right) {
	  return *left > *right;
  }
};
 
#endif

/**	@file huffmanElement.cpp Verwalten von Huffman-Knoten und -Blaettern
 
	@author		- David Hadizadeh
	@version	- 1.0
	@date		- 07.06.2012
*/
 
#include "huffmanElement.h"
 
int HuffmanElement::count_nodes = 1;
int HuffmanElement::longest_code = 0;
 
/**	Erzeugt einen leeren Knoten.
	Reserviert Speicher fuer 30 Lookup-Bits.
*/
HuffmanElement::HuffmanElement() {
	left = 0;
	right = 0;
	parent = 0;
	name = 0;
	letter = -1;
	value = 0;
	is_right = false;
	lookup_code = new bool[30];
	lookup_code_length = 0;
}
 
/**	Erzeugt ein Blatt mit Buchstaben und deren Anzahl.
	Reserviert Speicher fuer 30 Lookup-Bits.
 
    @param cur_letter Buchstabe
	@param cur_value Anzahl
*/
HuffmanElement::HuffmanElement(char cur_letter, int cur_value) : letter(cur_letter), value(cur_value) {
	left = 0;
	right = 0;
	name = 0;
	is_right = false;
	parent = 0;
	lookup_code = new bool[30];
	lookup_code_length = 0;
}
 
/**	Erzeugt einen Knoten mit linkem und rechtem Nachfolger, sowie einem Wert,
	der die Wertigkeit des aktuellen Asts angibt.
	Reserviert Speicher fuer 30 Lookup-Bits.
 
    @param cur_left linker Nachfolger
	@param cur_right rechter Nachfolger
	@param cur_value Wert des Asts
*/
HuffmanElement::HuffmanElement(HuffmanElement* cur_left, HuffmanElement* cur_right, int cur_value) : left(cur_left), right(cur_right), value(cur_value) {
	letter = -1;
	name = count_nodes;
	count_nodes++;
	is_right = false;
	parent = 0;
	lookup_code = new bool[30];
	lookup_code_length = 0;
}
 
/**	Kopiert einen Knoten/Blatt.
 
    @param original zu kopierender Knoten/Blatt
*/
HuffmanElement::HuffmanElement(const HuffmanElement& original) {
	copy_huffman_element(original);
}
 
/**	Gibt alle Speicherbereiche des Knotens/Blatt frei.
*/
HuffmanElement::~HuffmanElement() {
	delete_huffman_element();
}
 
/**	Zuweisungsoperator zum Kopieren/Zuweisen eines Kontens/Blatts.
 
    @param original zuzuweisender Knoten/Blatt
    @returns Referenz auf den neuen Knoten/Blatt
*/
HuffmanElement& HuffmanElement::operator=(const HuffmanElement& original) {
	copy_huffman_element(original);
	return *this;
}
 
/**	Ueberladung des > Operator ermoeglicht den Vergleich von Knoten/Blaettern.
	Knoten/Blaettern mit grossem Wert sind groesser als Knoten/Blaettern mit
	kleinem Wert.
 
    @param compare zu vergleichender Knoten
    @returns 0, wenn der aktuelle Knoten nicht groesser ist, sonst ist er groesser
*/
bool HuffmanElement::operator> (const HuffmanElement& compare) const {
	return (value > compare.get_value());
}
 
/**	Liefert den aktuellen Buchstaben.
 
    @returns Buchstabe
*/
char HuffmanElement::get_letter() const {
	return letter;
}
 
/**	Liefert den aktuellen Wert (Wertigkeit des aktuellen Asts)
 
    @returns Wertigkeit
*/
int HuffmanElement::get_value() const {
	return value;
}
 
/**	Liefert den Namen des Knotens (Nummer)
 
    @returns Namens-ID
*/
int HuffmanElement::get_name() const {
	return name;
}
 
/**	Gibt an, ob der aktuelle Knoten/Blatt ein
	rechter oder linker Nachfolger ist.
 
    @returns 0, wenn es ein liker Nachfolger ist, sonst ist es ein rechter Nachfolger
*/
bool HuffmanElement::get_is_right() const {
	return is_right;
}
 
/**	Liefert den uebergeordneten Knoten.
 
    @returns uebergeordneter Knoten
*/
HuffmanElement* HuffmanElement::get_parent() {
	return parent;
}
 
/**	Liefert den linken Nachfolger.
 
    @returns linker Nachfolger
*/
HuffmanElement* HuffmanElement::get_left() {
	return left;
}
 
/**	Liefert den rechten Nachfolger.
 
    @returns rechter Nachfolger
*/
HuffmanElement* HuffmanElement::get_right() {
	return right;
}
 
/**	Liefert den Lookup-Code des aktuellen Blatts.
 
    @returns Lookup-Bit-Code
*/
bool* HuffmanElement::get_lookup_code() {
	return lookup_code;
}
 
/**	Liefert die Laenge des Lookup-Codes des aktuellen Blatts.
 
    @returns Laenge des Lookup-Bit-Codes
*/
unsigned int HuffmanElement::get_lookup_code_length() const {
	return lookup_code_length;
}
 
/**	Legt den Uebergeordneten Knoten fest und bestimmt, ob der aktuelle Knoten/Blatt
	ein linker oder rechter ist.
 
    @param cur_parent uebergeordneter Knoten
    @param cur_is_right 0, wenn es ein liker Nachfolger ist, sonst ist es ein rechter Nachfolger
*/
void HuffmanElement::set_parent(HuffmanElement* cur_parent, bool cur_is_right) {
	parent = cur_parent;
	is_right = cur_is_right;
	add_lookup_code(cur_is_right);
}
 
/**	Fuegt ein uebergebenes Bit zum eigenen Lookup-Code hinzu und macht
	dies auch fuer alle Nachfolger des aktuellen Knotens.
 
    @param code hinzuzufuegendes Bit
*/
void HuffmanElement::add_lookup_code(bool code) {
	lookup_code[lookup_code_length] = code;
	++lookup_code_length;
	//lookup_code.push_front(code);
	if (longest_code < lookup_code_length) {
		longest_code = lookup_code_length;
	}
 
	if (left != 0) {
		left->add_lookup_code(code);
	}
	if (right != 0) {
		right->add_lookup_code(code);
	}
}
 
/**	Liefert die Laenge des laengsten Lookup-Codes.
 
    @returns Anzahl an Stellen des laengsten Lookup-Codes
*/
int HuffmanElement::get_longest_code() {
	return longest_code;
}
 
/**	Kopiert einen Knoten/Blatt.
 
    @param original zu kopierender Knoten/Blatt
*/
void HuffmanElement::copy_huffman_element(const HuffmanElement& original) {
	if (this != &original) {
		delete_huffman_element();
 
		left = original.left;
		right = original.right;
		parent = original.parent;
		name = original.name;
		letter = original.letter;
		value = original.value;
		is_right = original.is_right;
		lookup_code = original.lookup_code;
	}
}
 
/**	Gibt alle Speicherbereiche des aktuellen Knotens frei.
*/
void HuffmanElement::delete_huffman_element() {
	if (left != 0) {
		delete left;
	}
	if (right != 0) {
		delete right;
	}
	if (lookup_code != 0) {
		delete [] lookup_code;
	}
}

#ifndef HUFFMAN_HEADER
#define HUFFMAN_HEADER
 
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>
#include <ctime>
#include "huffmanElement.h"
#include "letter.h"
 
using namespace std;
 
/**
	Ermoeglicht das Erstellen eines Huffman-Binaer-Baums,
	deren Speicherung und Loeschung. Ausserdem die Kompression auf
	3 verschiedene Arten und die Dekompression. Jeweils von Strings
	oder von ganzen Dateien.
*/
class Huffman {
	private:
		/**
			Anzahl an maximalen Buchstaben des Binaer-Baums
		*/
		static const int ENCODING_MAX;
		/**
			Blaetter des Baums
		*/
		vector<HuffmanElement*> tree;
		/**
			Oberster Knoten des Binaerbaums
		*/
		HuffmanElement* root;
		/**
			Look-Up-Struktur zum Speichern und Lesen von Blatt-Positionen
		*/
		int* lookup_positions;
		/**
			Zaehlt Anzahnl der Statusmeldungen
		*/
		int print_status_counter;
 
	public:
		Huffman();
		Huffman(const Huffman& original);
		virtual ~Huffman();
		virtual Huffman& operator=(const Huffman& original);
		virtual void build_tree(string text, bool file);
		virtual bool* compress(bool* compr_bits_ar, int* count, string text, bool file);
		virtual bool* compress_table(bool* compr_bits_ar, int* count, string text, bool file);
		virtual bool* compress_lookup(bool* compr_bits_ar, int* count, string text, bool file);
		virtual void decompress(string filename, string out_filename);
		virtual string decompress(vector<bool> compr_bits);
		virtual void save_tree(string filename) const;
 
	private:
		void copy_huffman(const Huffman& original);
		void delete_huffman();
		string decompress(bool* compr_bits, int count, string filename);
		void save_element(fstream* f, HuffmanElement* element) const;
		bool depth_search(char search_node, HuffmanElement* node, vector<bool>* compr_buffer);
		void read_file(string filename, vector<Letter>* letters) const;
		void read_file(string filename, vector<char>* letters) const;
		string to_ascii(string text) const;
		void print_and_write(string file_name, string text) const;
		int insert_compr_bits(bool* compr_bits, unsigned int compr_bits_index, bool* compr_bits_rev, HuffmanElement* cur_element) const;
		void print_status(int overall, int current);
};
 
#endif

/**	Erzeugt einen Huffman-Verwalter.
*/
Huffman::Huffman() {
	print_status_counter = 0;
	lookup_positions = 0;
	root = 0;
}
 
/**	Kopiert einen Huffman-Verwalter.
 
    @param original zu kopierender Huffman-Verwalter
*/
Huffman::Huffman(const Huffman& original) {
	copy_huffman(original);
}
 
/**	Loescht einen Huffman-Verwalter.
*/
Huffman::~Huffman() {
	delete_huffman();
}
 
/**	Zuweisungsoperator fuer einen Huffman-Verwalter.
 
    @param original zuzuweisender Huffman-Verwalter
    @returns Referenz auf zugewiesenen Huffman-Verwalter
*/
Huffman& Huffman::operator=(const Huffman& original) {
	copy_huffman(original);
	return *this;
}

/**	Erzeugt einen Huffman-Binaer-Baum anhand einer Datei
	oder eines uebergebenen Textes. Der Baum ist fuer die
	Komprimierung optimal.
 
    @param text Dateiname/Text
	@param file 0, wenn der Baum aus einem Text erzeugt werden soll, sonst aus einer Datei
*/
void Huffman::build_tree(string text, bool file) {
	delete_huffman();
	tree.clear();
	vector tmp_tree;
	vector letters;
	for (unsigned int i = 0; i < ENCODING_MAX; i++) {
		letters.push_back(Letter(i));
	}
 
	if (file) {
		read_file(text, &letters);
	} else {
		for (unsigned int i = 0; i < text.length(); i++) { 			letters.at(text[i]).add_count(); 		} 	} 	sort(letters.begin(), letters.end()); 	lookup_positions = new int[ENCODING_MAX]; 	for (unsigned int i = ENCODING_MAX - 1; i >= 0 && letters[i].get_count() > 0; i--) {
		tmp_tree.push_back(new HuffmanElement(letters[i].get_letter(), letters[i].get_count()));
		tree.push_back(tmp_tree[tmp_tree.size()-1]);
		lookup_positions[letters[i].get_letter()] = tree.size()-1;
	}

	while (tmp_tree.size() > 1) {
		tmp_tree.push_back(new HuffmanElement(tmp_tree[tmp_tree.size()-1], tmp_tree[tmp_tree.size()-2], tmp_tree[tmp_tree.size()-1]->get_value() + tmp_tree[tmp_tree.size()-2]->get_value()));
		root = tmp_tree[tmp_tree.size()-1];
		tmp_tree[tmp_tree.size()-2]->set_parent(root, false);
		tmp_tree[tmp_tree.size()-3]->set_parent(root, true);
		tmp_tree.erase(remove(tmp_tree.begin(), tmp_tree.end(), tmp_tree[tmp_tree.size()-2]), tmp_tree.end());
		tmp_tree.erase(remove(tmp_tree.begin(), tmp_tree.end(), tmp_tree[tmp_tree.size()-2]), tmp_tree.end());
		sort(tmp_tree.begin(), tmp_tree.end(), compareCharacters());
	}
}

/**	Rekursive Tiefensuche. Durchsucht den Binaerbaum nach einem uebergebenen Blatt
	und speichert die Bits, die zum Erreichen notwendig waren.
 
    @param search_node zu suchendes Blatt
	@param node aktuelles Blatt
	@param compr_buffer derzeit gespeicherte Bitfolge
    @returns 0, wenn Blatt nicht gefunden wurde, sonst wurde es gefunden
*/
bool Huffman::depth_search(char search_node, HuffmanElement* node, vector* compr_buffer) {
	bool success = false;
	if (node->get_left() != 0 || node->get_right() != 0) {
		if (node->get_left() != 0) {
			compr_buffer->push_back(false);
			success = depth_search(search_node, node->get_left(), compr_buffer);
		}
		if (!success && node->get_right() != 0) {
			compr_buffer->push_back(true);
			success = depth_search(search_node, node->get_right(), compr_buffer);
		}
		if (!success) {
			if (compr_buffer->size() > 0) {
				compr_buffer->pop_back();
			}
		}
	} else {
		if (node->get_letter() == search_node) {
			success = true;
		} else {
			if (compr_buffer->size() > 0) {
				compr_buffer->pop_back();
			}
			success = false;
		}
	}
 
	return success;
}

bool* Huffman::compress(bool* compr_bits_ar, int* count, string text, bool file) {
	vector compr_bits;
	vector cur_compr_bits;
	vector letters;
 
	if (file) {
		read_file(text, &letters);
		for (unsigned int i = 0; i < letters.size(); i++) {
			cur_compr_bits.clear();
			depth_search(letters[i], root, &cur_compr_bits);
			compr_bits.insert(compr_bits.end(), cur_compr_bits.begin(), cur_compr_bits.end());
			print_status(letters.size(), i);
		}
	} else {
		//...
	}
 
        //...
        //Rausgenommen, da trivial: compr_bits umgekehrt an das Ende von compr_bits_ar anfügen
 
	*count = compr_bits.size();
	return compr_bits_ar;
}

/**	Komprimiert einen Text/Datei mit Hilfe einer Tabelle.
	Er geht den Text Zeichen fuer Zeichen durch, sucht das Zeichen in einer Tabelle (Laufzeit O(n))
	und geht von diesem gefundenen Element so lange zum Vorgaenger, bis er beim obersten Element (root)
	angekommen ist. Dabei wird jeweils das aktuelle Bit notiert. Gesamtlaufzeit O(n * log n).
 
	@param compr_bits_ar Zeiger auf Array, in das die Kompressions-Bits geschrieben werden sollen
	@param count Zeiger auf Zahl, in die die Anzahl der Kompressions-Bits geschrieben werden soll
    @param text zu komprimierender Text/Datei
	@param file 0, wenn Text, sonst Datei
    @returns Zeiger auf neuen Speicherbereich, in den die Kompressions-Bits geschrieben wurden
*/
bool* Huffman::compress_table(bool* compr_bits_ar, int* count, string text, bool file) {
	vectorletters;
	unsigned int index = 0;
	bool* compr_bits_rev = new bool[tree[0]->get_longest_code()];
	int lookup_position_index = 0;
 
	if (file) {
		read_file(text, &letters);
		compr_bits_ar = new bool[tree[0]->get_longest_code() * letters.size()];
		for (unsigned int i = 0; i < letters.size(); i++) { 			lookup_position_index = lookup_positions[(int)letters[i]]; 			if (lookup_position_index >= 0 && lookup_position_index

/**	Hilfsfunktion fuer die Tabellen-Kompression. Geht solange zum Vorgaenger, bis das root-Element
	erreicht ist und schreibt jeweils den Pfad (linkes oder rechtes Element) an das Ende des Bit-Arrays.
 
    @param compr_bits Bit-Array, in das geschrieben werden soll
	@param compr_bits_index aktueller Index, ab dem geschrieben werden kann
	@param compr_bits_rev Bit-Array zum Umdrehen des Codes
	@param cur_element Element, fuer das der Bitstream gesucht und geschrieben werden soll
	@returns naechste freie Position des Bit-Arrays
*/
int Huffman::insert_compr_bits(bool* compr_bits, unsigned int compr_bits_index, bool* compr_bits_rev, HuffmanElement* cur_element) const {
	int index = 0;
	while (cur_element != root) {
		compr_bits_rev[index] = cur_element->get_is_right();
		++index;
		cur_element = cur_element->get_parent();
	}
 
	for (int i = index - 1; i >= 0; i--) {
		compr_bits[compr_bits_index] = compr_bits_rev[i];
		++compr_bits_index;
	}
 
	return compr_bits_index;
}

/**	Komprimiert einen Text/Datei mit einer Tabelle und einer weiteren Lookup-Tabelle
	Er geht den Text Zeichen fuer Zeichen durch, sucht das Zeichen in einer Tabelle (Laufzeit O(n)).
	In diesem Zeichen ist der korrekte Bit-Stream gespeichert, der nur noch an den kompletten Bitstream angefuegt
	werden muss. Gesamtlaufzeit O(n) -> linear.
 
	@param compr_bits_ar Zeiger auf Array, in das die Kompressions-Bits geschrieben werden sollen
	@param count Zeiger auf Zahl, in die die Anzahl der Kompressions-Bits geschrieben werden soll
    @param text zu komprimierender Text/Datei
	@param file 0, wenn Text, sonst Datei
    @returns Zeiger auf neuen Speicherbereich, in den die Kompressions-Bits geschrieben wurden
*/
bool* Huffman::compress_lookup(bool* compr_bits_ar, int* count, string text, bool file) {
	bool* cur_compr_bits;
	HuffmanElement* current_element = 0;
	vector letters;
	unsigned int position = 0;
	int lookup_position_index = 0;
 
	if (file) {
		read_file(text, &letters);
		compr_bits_ar = new bool[tree[0]->get_longest_code() * letters.size()];
		for (unsigned int i = 0; i < letters.size(); i++) { 			lookup_position_index = lookup_positions[(int)letters[i]]; 			if (lookup_position_index >= 0 && lookup_position_index get_lookup_code();
				for(int j = (current_element->get_lookup_code_length()-1); j >= 0; j--) {
					compr_bits_ar[position] = cur_compr_bits[j];
					++position;
				}
			}
		}
	} else {
		//...
	}
	*count = position;
	return compr_bits_ar;
}

/**	Dekomprimiert ein uebergebenes Bit-Array und speichert
	den dekomprimierten Text bei Bedarf in einer Datei
 
    @param compr_bits Kompressions-Bit-Array
	@param count Laenge des Kompressions-Bit-Arrays
	@param filename wenn Dateiname leer, dann wird der Text zurueckgegeben und nicht gespeichert, sonst wird er gespeichert
    @returns dekomprimierter Text, wenn er nicht gespeichert werden sollte, sonst leer
*/
string Huffman::decompress(bool* compr_bits, int count, string filename) {
	clock_t time_start = clock();
	stringstream decompr_string;
	HuffmanElement* node;
	int i = 0;
	while (i < count) {
		node = root;
		while (i < count && (node->get_left() != 0 || node->get_right() != 0)) {
			if (!compr_bits[i]) {
				if (node->get_left() != 0) {
					node = node->get_left();
				}
			} else {
				if (node->get_right() != 0) {
					node = node->get_right();
				}
			}
			i++;
			//print_status(count, i);
		}
 
		decompr_string << node->get_letter();
	}
 
	if (filename != "") {
		ofstream file;
		file.open(filename);
		file << decompr_string.str();
		file.close();
		decompr_string.str("");
	}
	cout << endl << "Dauer: " << ((double)(clock() - time_start)) / 1000.0 << " Sekunden" << endl << endl;
	return decompr_string.str();
}