Permuted Index

#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <vector>
#include <string>
#include <sstream>

struct Word
{
    int originalindex;
    std::string str;
};


/*
    Returns all the words of a given string
*/
std::vector<Word> getWords(const std::string &in);

/*
    Returns a vector of rotated strings given in vectors of words
    We rotate the strings by placing the first word at the end until it is fully rotated
*/
std::vector< std::vector<Word> > rotateString(const std::string &in);

/*
    Returns a generated string based on the words given.
*/
std::string makeStringFromWords(const std::vector<Word> &in);


int main()
{
    std::vector<std::string> input
    {
        "The quick brown fox",
        "jumped over the fence"
    };

    std::vector< std::vector<Word> > output;

    // Convert input to std::vector< std::vector<Word> > and put it in the output, all input sentences will be inside that vector
    for(const std::string &s : input)
    {
        std::vector< std::vector<Word> > sentences = rotateString(s);
        for(const std::vector<Word> &s2 : sentences)
        {
            output.push_back(s2);
        }
    }

    // Sort the output
    std::sort(output.begin(), output.end(), [](const std::vector<Word> &a, const std::vector<Word> &b){
        std::string str_a = makeStringFromWords(a);
        std::string str_b = makeStringFromWords(b);

        std::transform(str_a.begin(), str_a.end(), str_a.begin(), tolower);
        std::transform(str_b.begin(), str_b.end(), str_b.begin(), tolower);

        return str_a < str_b;
    });

    // Split output in left and right
    std::vector< std::vector<Word> > Left;
    std::vector< std::vector<Word> > Right;

    for(const std::vector<Word> &s : output)
    {
        std::vector<Word> l_sentence;
        std::vector<Word> r_sentence;

        for(size_t i=0; i<s.size(); ++i)
        {
            if(s[i].originalindex < (int)i)
            {
                l_sentence.push_back(s[i]);
            } else {
                r_sentence.push_back(s[i]);
            }
        }

        Left.push_back(l_sentence);
        Right.push_back(r_sentence);
    }


    // Display the output
    size_t left_max_len = 0;
    for(const std::vector<Word> &s : Left)
    {
        left_max_len = std::max(left_max_len, makeStringFromWords(s).length());
    }

    for(size_t i=0; i<Left.size(); ++i)
    {
        std::string leftstr = makeStringFromWords(Left[i]);
        std::cout << std::string(left_max_len-leftstr.length(), ' ') << leftstr << std::string(5, ' ') << makeStringFromWords(Right[i]) << std::endl;
    }

    return 0;
}


/*
    Returns all the words of a given string
*/
std::vector<Word> getWords(const std::string &in)
{
    // Make a vector of strings which have all the words of the given input string
    std::istringstream iss(in);
    std::vector<std::string> s_words // Construct a vector from 2 iterators
    {
        std::istream_iterator<std::string>{iss}, // iterator pointing to first element
        std::istream_iterator<std::string>{} // end-of-stream iterator
    };

    // Convert s_words
    std::vector<Word> words;
    for(std::string s : s_words)
    {
        Word w;
        w.str = s;
        words.push_back(w);
    }

    return words;
}

/*
    Returns a vector of rotated strings given in vectors of words
    We rotate the strings by placing the first word at the end until it is fully rotated
*/
std::vector< std::vector<Word> > rotateString(const std::string &in)
{
    std::vector< std::vector<Word> > out;
    std::vector<Word> words = getWords(in);

    // Loop through all the words so we have a vector of sentences with each sentence starting with i's word
    for(size_t i=0; i<words.size(); ++i)
    {
        std::vector<Word> rotatedString;

        // Loop through all the words so we can form a sentence with all the words in the correct order
        for(size_t r=0; r<words.size(); ++r)
        {
            int wordWeNeed = (i+r)%words.size(); // i makes sure each sentence starts with another word and r is meant to loop through the words
            Word w = words[wordWeNeed];
            w.originalindex = wordWeNeed;
            rotatedString.push_back(w);
        }

        out.push_back(rotatedString);
    }

    return out;
}

/*
    Returns a generated string based on the words given.
*/
std::string makeStringFromWords(const std::vector<Word> &in)
{
    std::string out;

    for(size_t i=0; i<in.size(); ++i)
    {
        out += in[i].str;

        if(i != in.size()-1)
        {
            out += ' ';
        }
    }

    return out;
}