-
Notifications
You must be signed in to change notification settings - Fork 0
/
CTrieEnc.cpp
90 lines (78 loc) · 3.17 KB
/
CTrieEnc.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "CTrieEnc.hpp"
CTrieEnc::CTrieEnc(){
for(int index=0; index<256; index++){
m_symbolTable[index].setSymbol(intToString(index));
m_symbolTable[index].setParent(-1);
//-2 wird standardmaeßig fuer alle Elemente gesetzt (siehe CKnot)
}
}
bool getValuesEqual(CKnot table[], int pos, int parent, const string& val){
return (table[pos].getParent()==parent && table[pos].getSymbol()==val);
}
vector<unsigned int> CTrieEnc::encode(const string& inputstr){
//Wenn Eingabe leer, beenden
if (inputstr=="") return {};
//Elternposition: I, Numer. ASCII Wert fuer akt Zeichen: J
int I = 0;
//Hashing-Singleton
CDoubleHashing& hasher = CDoubleHashing::getInstance();
//Versuchs-Zaehler fuer Rehashing
CForwardCounter attemptCounter;
//Ausgabeverktor fuer encodete Zeichenkette
vector <unsigned int> encoded = {};
//Erstes Zeichen blind einlesen
std::string::const_iterator initialiter = inputstr.begin();
I=charToInt(*initialiter);
//encoded.push_back(charToInt(*initialiter));
++initialiter;
//durch alle Zeichen iterieren
for (std::string::const_iterator iter=initialiter; iter != inputstr.end(); ++iter){
//Neues Zeichen in J eingelesen
int J = charToInt(*iter);
//Rehashing soll bei Versuch 0 beginnen
attemptCounter.setValue(0);
//Position bestimmen mittels Hashing
int position = hasher.hash(I, J, LZW_DICT_SIZE, 0);
//wenn Position schon mit anderen Werten belegt (Kollision)
if (!getValuesEqual(m_symbolTable, position, I, intToString(J))){
//Wird auch ausgefuehrt, wenn unbelegt (parent=-2)
//dann wird aber nicht die Schleife durchlaufen
//neue Variable fuer Hashwert -> warum? Steht in der Aufgabenstellung
//(Gegen Endlossschleife), aber es werden doch nur I und J sowie der Zaehler benutzt
int newPosition = position;
//neu hashen, bis leeres Feld oder der Wert gefunden wurde
while ((m_symbolTable[newPosition].getParent()!=-2) || (getValuesEqual(m_symbolTable, newPosition, I, intToString(J)))) {
//wenn Werte uebereinstimmen; Schleife abbrechen
if (getValuesEqual(m_symbolTable, newPosition, I, intToString(J))) break;
//Versuchszaehler inkrementieren
attemptCounter.count();
//neu hashen (veraenderter Zaehlerstand)
newPosition = hasher.hash(I, J, LZW_DICT_SIZE, attemptCounter.getValue());
}
//Wenn leeres Feld oder das Feld mit dem Wert gefunden wurde,
//neue Position uebernehmen
position=newPosition;
}
//pruefen ob auf leeren Knoten gestoßen
if (m_symbolTable[position].getParent()==-2 || m_symbolTable[position].getSymbol()==""){
//Debug-Ausgabe
//dann soll hier das aktuelle Zeichen gespeichert werden
//und parent auf die erste Zeichenkette zeigen
m_symbolTable[position].setParent(I);
m_symbolTable[position].setSymbol(intToString(J));
//I an den Ausgabevektor anhaengen
encoded.push_back(I);
//I mit J ueberschreiben
I = J;
//neues Zeichen einlesen -> neuer Schleifendurchlauf?
}
//pruefen ob String schon vorhanden
else if (getValuesEqual(m_symbolTable,position,I,intToString(J))){
//gerade ermittelte Position wird in I gespeichert
I = position;
//und ein neues Zeichen J eingelesen -> Schleifendurchlauf?
}
}
encoded.push_back(I);
return encoded;
}