I have more fluently in writting Java but for this program my advisor need me to convert my program from java to c++. I've already done with c++ code and the result is correct and got the same result as java program but the big problem is that the program is very very slow than java. I think the the problem is due to the way of my programming(i'm familiar with java coding style). I've tried to change the code for few days but it has nothing better. Can anyone please help me to look these program and it would be very grateful if you can tell me what i've done wrong and how i can correct it.
My program is for creating suffix tree by reading the one line of text from the file.
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <sys/time.h>
#include <unistd.h>
#define microsec 1000000.0
using namespace std;
vector <int> startPos;
vector <int> endPos;
class TimeTracker {
private:
struct timeval start_time;
struct timeval stop_time;
bool running;
public:
TimeTracker() {
running=false;
}
void Start() {
gettimeofday(&start_time, (struct timezone *)0);
running=true;
}
double Stop() {
double st, en;
if (!running) return(-1.0);
else {
gettimeofday(&stop_time, (struct timezone *)0);
st = start_time.tv_sec + (start_time.tv_usec/microsec);
en = stop_time.tv_sec + (stop_time.tv_usec/microsec);
running=false;
return (double)((en - st));
}
}
};
struct SuffNode // declare a new struct
{
string pre;
vector <SuffNode> suff;
vector <int> pos;
};
string toString(string level, SuffNode* suffix) //return the output string
{
string tree = level + suffix->pre;
tree += "\n";
if(suffix->suff.size() != 0)
{
int c = suffix->suff.size();
level += "-";
for(int i = 0; i < c; i++)
{
SuffNode aSuff = suffix->suff.at(i);
tree += toString(level, &aSuff);
}
}
return tree;
}
vector<SuffNode> put(string key, vector <SuffNode>& tree, int poss) //method for creating suffix tree by put each suffix one by one
{
if(tree.size() == 0) //put first suffix
{
SuffNode node;
node.pre = key;
node.pos.push_back(poss);
tree.push_back( node);
}
else //put subsequent suffix
{
int tsize = tree.size(); //size of arraylist
int i = 0;
bool check = true;
while( i < tsize && check) //if it already has list keep checking the suffix with the string in each node
{
string test = tree[i].pre; //get string in that node
vector <int> poslist;
poslist.assign(tree[i].pos.begin(), tree[i].pos.end());
int keysize = key.length(); //get size of input suffix
int testsize = test.length(); //get size of string in the node
int j = 1;
bool c = true;
if(test[0] == key[0]) //if first character of suffix match with the first character of string in the node
{
while( j < keysize && j < testsize && c) //keep checking the matching
{
if(test[j] == key[j]) //if next character match
{
j++; //go to next character
}
else //out of while loop
{
c = false;
}
}//end inner while
string newPre = test.substr(0, j); //get new string to put in current node
tree[i].pre = newPre; //add new string
if(!c) //if match only some part of the string
{
string newS1 = test.substr(j);
string newS2 = key.substr(j);
if(tree[i].suff.size() == 0) //if there are no list in the node
{
SuffNode node1; //create new object(node)
node1.pre = newS1; //add string into new node
node1.pos.assign(poslist.begin(), poslist.end());
tree[i].suff.push_back(node1); //add new node into the arraylist
SuffNode node2; //create new object(node)
node2.pre = newS2; //add string into new node
node2.pos.push_back(poss); //add new position into position list in this node
tree[i].suff.push_back(node2); //add new node into the arraylist
}
else //if it already has list
{
SuffNode node11; //create new object(node)
node11.pre = newS1; //add string (new string of current node) into new node
node11.suff.assign(tree[i].suff.begin(), tree[i].suff.end());
node11.pos.assign(poslist.begin(), poslist.end());
tree[i].suff.clear(); //clear list of current node
tree[i].suff.push_back(node11); //add new list to current node
SuffNode node12; //create new object(node)
node12.pre = newS2; //add string (new string of input suffix) into new node
node12.pos.push_back(poss); //add new position into the position list int this node
tree[i].suff.push_back(node12); //add new node into the current list
}
} //end if !c
else //if every character in the test stirng match
{
string newString = key.substr(j); //get new string of input suffix
if(tree[i].suff.size() == 0) //if no list in current node
{
SuffNode nnode; //create new node
nnode.pre = newString; //add string into new node
nnode.pos.push_back(poss); //add new position into the position list
tree[i].suff.push_back(nnode); //input new node into current list
}
else //if it already has the list
{
vector <SuffNode> newL = put(newString, tree[i].suff, poss); //put new input suffix into the current tree(current list)
tree[i].suff.assign(newL.begin(), newL.end());
}
}//end else !c
tree[i].pos.push_back(poss); //add new position
check = false;
}//end if first character match
else // if first character not match go to next index of arraylist
{
i++;
}
}//end outer while
if(i >= tsize) //no match in arraylist
{
SuffNode nNode; //create new node
nNode.pre = key; //add input suffix into new node
nNode.pos.push_back(poss); //add position into new node
tree.push_back(nNode); //add new node into current list
}
}//end else
return tree;
}
bool matching(vector<SuffNode> tree, string s, int count) //method for find the match substring in arraylist
{
bool match = false;
int sSize = s.length();
int listSize = tree.size();
int i = 0;
bool check = true;
while( i < listSize && check) //keep checking each string in each node until know whether match or not match
{
string test = tree[i].pre; //get string in that node
int testsize = test.length();
int j = 1;
bool c = true;
if(test[0] == s[0]) //if first character of string match with the first character of string in the node
{
if(count == 0)
{
startPos = tree[i].pos; //get position from the node that the first character matched
}
while( j < sSize && j < testsize && c) //keep checking the matching
{
if(test[j] == s[j]) //if next character match
{
j++; //go to next character
}
else //out of while loop
{
c = false;
}
}//end inner while
if(!c && j == sSize) //if all characters match
{
match = true;
endPos = tree[i].pos;
}
else if(!c) //if either one characters not match
{
match = false;
}
else if (j == sSize) //if all character match
{
match = true;
endPos = tree[i].pos; //get position from the node that the last character matched
}
else if (j < sSize) //if match the string in the node but still have character left in the input string
{
string newString = s.substr(j); //get the string have left
count++;
match = matching(tree[i].suff, newString, count); //continue finding the match
}
check = false;
} //end if match
else
{
i++;
} //end if first character not match
} //end while
if(i >= listSize) //no match in arraylist
{
match = false;
}
return match;
}
main()
{
string line, filename;
putname:
cout << "Please input file name: ";
getline (cin, filename);
char *name = new char[filename.length()+1];
strcpy ( name, filename.c_str() ); // that is correct
ifstream myfile (name);
if (myfile.is_open())
{
getline (myfile,line);
myfile.close();
}
else
{
cout << "Unable to open file\n";
goto putname;
}
line += "$";
cout << line << endl;
Tree t;
TimeTracker tt;
tt.Start();
vector <SuffNode> suftree;
for (int i = line.length(); i > 0; i--) //put each suffix of input string into class tree to create suffix tree
{
suftree = put(line.substr(i-1),suftree,(i-1));
}
cout << "Build Done! Time taken = " << tt.Stop() << " seconds.\n" << endl;
string tree = "";
for (int j = 0; j < suftree.size(); j++ ) //get created suffix tree and keep in form of string for presentation
{
tree += toString("-", &suftree[j]);
}
cout << tree;
string ans;
cout << "\nNeed to search (y/n) : ";
getline(cin, ans);
if ( ans == "y")
{
string search, files;
putname2:
cout << "Please input file name: ";
getline (cin, files);
char *names = new char[files.length()+1];
strcpy ( names, files.c_str() ); // that is correct
ifstream myfiles (names);
if (myfiles.is_open())
{
getline (myfiles,search);
myfiles.close();
TimeTracker ts;
ts.Start();
bool match = matching(suftree,search,0);
cout << "Searching Done! Time taken = " << ts.Stop() << " seconds." << endl;
if(match) //if searched string match
{
cout << "\nMATCH!!!" << endl;
vector<int> posi;
int sSize = startPos.size();
int eSize = endPos.size();
for(int k = 0; k < eSize; k++)
{
int epoint = endPos[k];
for(int m = 0; m < sSize; m++)
{
int spoint = startPos[m];
if(epoint == spoint)
{
posi.push_back(spoint);
}
}//end inner for loop
}//end outer for loop
int length = search.length() - 1;
int numMatch = posi.size();
cout << "Number of Matching : " << numMatch << "\n\n";
for(int p = numMatch-1; p >= 0; p--)
{
int stat = posi[p];
int en = stat + length;
cout << "position : ( " << stat << "," << en << " )\n";
}
}//end if match
else
{
cout << "\nNOT MATCH!!!" << endl;
}//end else (not match)
}
else
{
cout << "Unable to open file\n";
goto putname2;
}
}
getchar();
}