-
-
Save EmmanuelMess/aa1f273c819762512c40ffd1d4786f89 to your computer and use it in GitHub Desktop.
#include <iostream> | |
#include <algorithm> | |
#include <stdio.h> | |
#include <string.h> | |
#include <map> | |
#include <queue> | |
using namespace std; | |
struct TRIE { | |
map<char, TRIE> arcs; | |
void add(char w[]) { | |
if(w[0] != '\0') { | |
arcs[w[0]].add(w+1); | |
} | |
} | |
int check(char* w, int i = 0) { | |
if(w[0] != '\0' && arcs.size() <= 2) { | |
map<char, TRIE>::iterator it = arcs.find(w[0]); | |
if (it != arcs.end()) | |
return arcs[w[0]].check(w+1, i+1); | |
else return i; | |
} else return i; | |
} | |
}; | |
int main() { | |
const int MARGIN_OF_SIMILARITY = 3; | |
int amount, maxC; | |
cout << "Enter number of files: "; | |
cin >> amount; | |
cout << "Enter max characters: "; | |
cin >> maxC; | |
int fileStartC = maxC/3, fileChangeC = maxC/3, fileEndC = maxC/3; | |
TRIE start; | |
priority_queue<string> names; | |
for(int i = 0; i < amount; i++) { | |
cout << "Enter " << i << ": "; | |
string s; | |
cin >> s; | |
string r = s; | |
reverse(r.begin(), r.end());//O(s.end() - s.begin()) | |
int similarStart = start.check((char *) s.data());//O(n) | |
int similarEnd = start.check((char *) r.data());//O(n) | |
string print; | |
start.add((char *) s.data());//O(n) | |
start.add((char *) r.data());//O(n) | |
names.push(s); | |
} | |
while(!names.empty()) { | |
string n = names.top(); | |
cout << endl << "for " << n << endl; | |
int similarStart = start.check((char *) n.data());//O(n) | |
string t = n; | |
reverse(t.begin(), t.end()); | |
int similarEnd = start.check((char *) t.data());//O(n) | |
string print; | |
if(similarStart < MARGIN_OF_SIMILARITY && similarEnd < MARGIN_OF_SIMILARITY) { | |
if(n.length() > maxC) { | |
cout << "length " << n.length() << endl; | |
print = n.substr(0, maxC/2) + ".." + n.substr(n.length()-maxC/2, n.length()); | |
} else { | |
print = n; | |
} | |
} else { | |
int shouldStart = similarStart > fileStartC? fileStartC:similarStart; | |
int shouldEnd = similarEnd > fileEndC? fileEndC:similarEnd; | |
print = n.substr(0, shouldStart) + ".." | |
+ n.substr(similarStart, (n.length()-similarEnd)-similarStart) + ".." | |
+ n.substr(n.length()-shouldEnd, n.length()); | |
} | |
cout << print << endl; | |
names.pop(); | |
} | |
} |
It's a great example of your idea, nice work.
I've tried it with many inputs (there's a bug when there is empty middle part, like if you change holaqhace.5.mp4 to holaqhace.mp4). Actually, I see two issues with this method and I beg your opinion.
I think we don't care for the extension in the case of not everything is displayable since the icon will reflect the extension type. In that case, a prefix only search is required, thus not requiring any trie at all (you only need to check if previousName.substring(0, whatIsDisplayed) == actualName.substring(0, whatIsDisplayed)
). If it's the case, then perform a suffix search for these items only and split from difference only, like in:
suffixLength = findCommonPrefix(previousName.reversed(). actualName.reversed(),0);
prefixLength = findCommonPrefix(previousName, actualName, whatIsDisplayed);
diffStr = actualName.substring(prefixLength, actualName.length() - prefixLength - suffixLength);
int prefixToShow = whatIsDisplayed - diffStr.length() - 1;
String finalName = actualName.substring(0, prefixToShow) + "< ellipsisChar here >" + diffStr;
Second issue, IMHO, is that the number of character to display depends on the text itself (unless a monospace font is used), thus hard to get right in practice before rendering (and based on how Android is structured, you don't have access to the rendered size for the current item of the list view).
Guaranteed to be buggy, created it in a few hours, also needs a lot of optimization.
Tried with "5 10 holaqhace.2.mp4 holaqhace.3.mp4 holaqhace.4.mp4 holaqhace.5.mp4 holaqhace.6.mp4".