-
Notifications
You must be signed in to change notification settings - Fork 0
/
decodable.hpp
129 lines (113 loc) · 4.5 KB
/
decodable.hpp
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <iostream>
using namespace std;
// func prototypes
void doMapInsertion(map<string, vector<string>>*, string, vector<string>);
vector<string> findSuffixes(map<string, vector<string>>, string list1, string list2);
bool isDecodable(map<string, vector<string>>*);
bool isUndecodable(map<string, vector<string>>*);
// func implementations
void doMapInsertion(map<string, vector<string>>* _map, string key, vector<string> entries)
{
if (_map->find(key) == _map->end())
{
// the map do not contain the given key, so I have to add it even if the entries are empty
_map->insert({key, entries}); // or _map->insert(pair<string, vector<string>> (key, entries))
return;
}
// reaching here means the map already contains the key, so
auto* it = &_map->find(key)->second;
for (size_t i = 0; i < entries.size(); i++)
{
it->push_back(entries[i]);
}
}
vector<string> findSuffixes (map<string, vector<string>> _map, string list1, string list2)
{
vector<string> foundSuffixes;
// check if _map contains the key for list1
auto iterator_list1 = _map.find(list1);
if (iterator_list1 == _map.end())
{
cerr << list1 << " is not a valid key or has not been added to the map" << endl;
return foundSuffixes;
}
// check if map containt the key for list2
auto iterator_list2 = _map.find(list2);
if (iterator_list2 == _map.end())
{
cerr << list2 << " is not a valid key or has not been added to the map" << endl;
return foundSuffixes;
}
for (vector<string>::iterator it_i = iterator_list1->second.begin(); it_i != iterator_list1->second.end(); ++it_i)
{
for (vector<string>::iterator it_j = iterator_list2->second.begin(); it_j != iterator_list2->second.end(); ++it_j)
{
// the suffix of ai such that ai = aj + suffix, can only be found if length of aj is smaller than ai
if (it_j->length() >= it_i->length())
continue; // no suffix could be found, continuing with the next item on the vector
// check if aj can be found inside ai
string prefix = it_i->substr(0, it_j->length());
if (prefix.compare(*it_j))
continue; // no suffix will be found since ai is not equal to some aj + suffix
string suff = it_i->substr(it_j->length(), it_i->length() - it_j->length());
if (!suff.empty())
foundSuffixes.push_back(suff);
}
}
return foundSuffixes;
}
bool isDecodable(map<string, vector<string>>* _map)
{
// if the last comumn in the table is empty, the code is decodable
map<string, vector<string>>::iterator lastCol = --_map->end();
if (lastCol->second.size() <= 0)
return true; // NOTE the code is detactable
// // if the last column is a copy of the previous to the last column, the code is decodable
std::sort(lastCol->second.begin(), lastCol->second.end());
map<string, vector<string>>::iterator prevToLast = ----_map->end();
do
{
// FIXME check for iterator validity
std::sort(prevToLast->second.begin(), prevToLast->second.end());
if (prevToLast->second == lastCol->second)
{
return true; // NOTE the code is decodable
}
--prevToLast;
} while (prevToLast != _map->end() && prevToLast != _map->begin());
return false; // NOTE the code is not decodable
}
bool isUndecodable(map<string, vector<string>>* _map)
{
map<string, vector<string>>::iterator firstColIterator = _map->begin();
map<string, vector<string>>::iterator lastColIterator = --_map->end();
// iterating through items of the last column
for (auto sn = lastColIterator->second.begin(); sn != lastColIterator->second.end(); sn++)
{
// iterating through items of the very first column
for (auto s0 = firstColIterator->second.begin(); s0 != firstColIterator->second.end(); s0++)
{
if (*sn == *s0)
{
// found a match between the first and the last column. NOTE the code is undecodable
return true;
}
}
}
// I did not find a match, NOTE the code is decodable
return false;
}
// test functions
void testInput(vector<string>);
// test func implementations
void testInput(vector<string> chars)
{
for (vector<string>::iterator it = chars.begin(); it != chars.end(); ++it)
{
cout << *it << endl;
}
}