lab2.cpp

#include "lab2.h"
void WordCount::parse(string &sWord)
{
    int i=0, iSize = 0;
    string sWord2;
    iSize = sWord.length();
    while(i <= iSize)
    {
        if(isalnum(sWord[i]))
            sWord2+= tolower(sWord[i]);
        i++;
    }
    sWord = sWord2;
}
void WordCount::ReadFile(ifstream &input, string sWord, vector<pair<string,int> > &vec)
{
    while(input >> sWord)
    {
        parse(sWord);
        if(MapOfWords.count(sWord))
        { MapIt=MapOfWords.find(sWord);
            MapIt->second++;
        }
        else
            MapOfWords.insert((pair<string,int>(sWord,1)));
    }
    for(MapIt=MapOfWords.begin(); MapIt!=MapOfWords.end(); MapIt++)
    {
        string tmp = MapIt->first;
        if(!isalnum(tmp[0]))
        {
        }
        else
            vec.push_back(*MapIt);
    }

}
void WordCount::print(vector<pair<string,int> > &vec)
{
    for(VecIt=vec.begin(); VecIt != vec.end(); VecIt++)
        cout << VecIt->first << " " << VecIt->second << endl;
}
void WordCount::quicksort(string KEY_VALUE, int left, int right, vector<pair<string, int> > &vec)
{
    int i = left, j = right;
    //  srand (time(NULL ));
    //  int pivot = rand() % ((right - left));
    int pivot = (left+right)/2;
    if(KEY_VALUE == "key") //sort by key string
    {
        //partition
        while(i < j )
        {
            //moving from the left to the right untill the pivot is no longer greater than the vec [i]
            while(vec[i].first < vec[pivot].first)
                i++;
            //moving from right to the left of the pivot so that the vec [j] is no longer greater than the pivot
            while(vec[j].first > vec[pivot].first)
                j--;
            if(i < j)
            {
                swap(vec[i], vec[j]);
                i++;
                j--;
            }
        }
        //recursion
        if (left < j)
            quicksort(KEY_VALUE, left, j-1, vec);
        if (i < right)
            quicksort(KEY_VALUE, i+1, right, vec);
    }
    else //sort by Values
    {
        while(i < j ) //partition
        {
            while((vec[i].second <= vec[pivot].second))
            {
                if(vec[i].second == vec[pivot].second)
                {
                    if(vec[i].first < vec[pivot].first)
                        {}
                    else
                        break;
                }
                i++;
            }
            while((vec[j].second > vec[pivot].second))
                j--;
            if(i < j)
            {
                swap(vec[i], vec[j]);
                i++;
                j--;
            }
        }
    }
    //recursion
    if (left < j)
        quicksort(KEY_VALUE, left, j-1, vec);
    if (i < right)
        quicksort(KEY_VALUE, i+1, right, vec);
}
void WordCount::insert_sort(string KEY_VALUE, vector<pair<string,int> > &vec)
{
    int size = vec.size();
    int j = 0;
    pair<string,int> temp;
    if(KEY_VALUE == "key")
    {
        for(int i = 1; i < size; i++)
        {
            temp = vec[i];
            j = i;
            while((j > 0) && (vec[j-1].first > temp.first))
            {
                vec[j] = vec[j-1];
                j--;
            }
            vec[j] = temp;
        }
    }
    else
    {
        for(int i = 1; i < size; i++)
        {
            temp = vec[i];
            j = i;
            while((j > 0) && (vec[j-1].second > temp.second))
            {
                vec[j] = vec[j-1];
                j--;
            }
            vec[j] = temp;
        }
    }
}

void WordCount::getmyvec(vector<pair<string, int> > &avector)
{
    avector = myVector;
}
void WordCount::setmyvec(vector<pair<string, int> > vec)
{
    myVector = vec;
}

/*void WordCount::merge_sort(string KEY_VALUE, int left, int right)
    {
    int middle;
    if( left < right){
    middle = (left + right)/2 ;
    merge_sort(KEY_VALUE,left,middle);
    merge_sort(KEY_VALUE,middle + 1, right);
    merge(KEY_VALUE, left, middle, right);
    }
    }*/

void WordCount::merge(string KEY_VALUE,vector<pair<string,int> > &sortvec)
{
    if(sortvec.size() < 2){}
    else
    {
        vector<pair<string,int> > leftVec;
        vector<pair<string,int> > rightVec;

        int size = sortvec.size();
        int middle = size /2;

        for(int i = 0; i < middle; i++) //set everything on the left side of middle to the left vector
            leftVec.push_back(sortvec[i]);

        for(int i = middle; i < size; i++) // everything on the right side of middle to the right vector
            rightVec.push_back(sortvec[i]);

        merge(KEY_VALUE, leftVec);
        merge(KEY_VALUE, rightVec);

        int leftSize = leftVec.size(), rightSize = rightVec.size();
        int rightIndex = 0, leftIndex = 0, myVectorIndex = 0; //indexes so i no where i am in the array err vector
        //--------------sort by keys-------------------//

        if(KEY_VALUE == "key")
        {
            while(leftIndex < leftSize && rightIndex < rightSize) //left and right index starts at 0
            {
                if(leftVec[leftIndex].first < rightVec[rightIndex].first)
                    sortvec[myVectorIndex++] = leftVec[leftIndex++];
                else
                    sortvec[myVectorIndex++] = rightVec[rightIndex++];
            }
            if(leftIndex == leftSize) //if left is completley sorted
            {
                while(rightIndex < rightSize)
                    sortvec[myVectorIndex++] = rightVec[rightIndex++];
            }
            else if(rightIndex == rightSize)
            {
                while(leftIndex < leftSize)
                    sortvec[myVectorIndex++] = leftVec[leftIndex++];
            }
        }

        //------------------ sort by values ------------- //

        else //sorting values
        {
            while(leftIndex < leftSize && rightIndex < rightSize)
            {
                if(leftVec[leftIndex].second < rightVec[rightIndex].second) //merge cause left side is less than right
                    sortvec[myVectorIndex++] = leftVec[leftIndex++];
                else if(leftVec[leftIndex].second == rightVec[rightIndex].second) //both values are the same so we have to check there key to detrmin which to sort
                {
                    if(leftVec[leftIndex].first < rightVec[rightIndex].first)
                        sortvec[myVectorIndex++] = leftVec[leftIndex++];
                    else
                        sortvec[myVectorIndex++] = rightVec[rightIndex++];
                }
                else //left has to be bigger because we checked all the other cases
                    sortvec[myVectorIndex++] = rightVec[rightIndex++];
            }
            if(leftIndex == leftSize) //now in the right side
            {
                while(rightIndex < rightSize)
                    sortvec[myVectorIndex++] = rightVec[rightIndex++];
            }
            else if(rightIndex == rightSize) //now in the left side
            {
                while(leftIndex < leftSize)
                    sortvec[myVectorIndex++] = leftVec[leftIndex++];
            }
        }
    }
}