Skip to content

Instantly share code, notes, and snippets.

@EmmanuelMess
Last active May 13, 2017 02:58
Show Gist options
  • Save EmmanuelMess/aa1f273c819762512c40ffd1d4786f89 to your computer and use it in GitHub Desktop.
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();
}
}
@EmmanuelMess
Copy link
Author

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".

@X-Ryl669
Copy link

X-Ryl669 commented May 2, 2017

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).

@EmmanuelMess
Copy link
Author

@X-Ryl669 Sorry for the late response, GitHub didn't notify me of your comment. If in Java you use a data structure that auto-orders you don't need the trie, but if not you have to try for each the equality, and it would be slower. About text size, check this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment