sommanatt 0 Newbie Poster

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(); 

}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.