Podgotovka za kontrolno-8 gr

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <stack>

using namespace std;

struct TNode
{
    string name;
    vector<TNode*> children;
    int level;
    TNode(string name, int level = 0) :name(name), level(level) {}
};

struct State
{
    TNode* node;
    string currentFamily;
    State(TNode* node, string name) :node(node), currentFamily(name) {};
};

//клас Таксономия описва таксономията на животните. Всяко ниво на таксономията съответства на ниво в дърво.
//Върховете на разст 3 представляват разред, а на 6 - видове.

class Taxonomy
{
private:
    TNode* root;
    void printRec(TNode* node, vector<string>& path) const;
    int countNodes(bool(*p)(TNode* node), TNode* node);
    int countSpeciesRec(string familyName, TNode* node);
public:
    Taxonomy()
    {
        root = new TNode("Animalia");
    }
    void addEntity(vector<string> taxonomy);
    TNode* current = root;
    /*for (vector<string>::iterator it = Taxonomy.begin(); it != Taxonomy.end();++it)
    {
        TNode* existing = findChild(current, *it);
        if (!existing)
        {
            existing = addChild(current, *it);
        }
        current = existing;
    }*/
    TNode* findChild(TNode* node, string name);
    TNode* addChild(TNode* node, string name);
    void print() const;
    int countSpeciesInFamily(string familyName);
    bool isLeafComplexName(TNode* node);
    bool isSpeciesLeaf(TNode* node)
    {return node->children.empty() && node->level >= 6;}
    map<string, int> speciesPerFamily()
    {
        map<string, int> result;
        speciesPerFamilyRec(result, root," ");
        return result;
    }
    void speciesPerFamilyRec(map<string, int>& results, TNode* node,string);
    map<string, int> speciesPerFamilyStack();
    vector<string> listSpecies();
    void listSpeciesRec(TNode* node, vector<string>& res);
    vector<string> listSpeciesStack();
        //int countComplexNamedSpecies();
};

TNode* findChild(TNode * node, string name)
{
    for (int i = 0; i < node->children.size(); i++)
    {
        if (node->children[i]->name == name) {
            return node->children[i];
        }
    }
    return NULL;
}

TNode * addChild(TNode * node, string name)
{
    TNode* child = new TNode(name, node->level + 1);
    node->children.push_back(child);
    return child;
}

int Taxonomy::countNodes(bool(*p)(TNode *node), TNode * node)
{
    int count = 0;
    if(p(node))
        count++;
    for (int i = 0; node->children.size() > i; i++)
        count += countNodes(p, node->children[i]);
    return count;
}

int Taxonomy::countSpeciesRec(string familyName, TNode * node)
{
    if (node->level == 4)
    {
        if (node->name != familyName)
            return 0;
        else
            return countNodes(isSpeciesLeaf(), node);
    }
    else if(node->level<4)
    {
        int count = 0;
        for (int i = 0; i < node->children.size(); i++)
            count += countSpeciesRec(familyName, node->children[i]);
        return count;
    }
    else
    {
        return 0;
    }


}

int Taxonomy::countSpeciesInFamily(string familyName)
{
    return countSpeciesRec(familyName, root);
}

bool isLeafComplexName(TNode * node)
{
    return node->children.empty() && find(node->name, " ") != string::npos;
}

void Taxonomy::speciesPerFamilyRec(map<string, int>& results, TNode * node,string currFamily)
{
    if (node->level == 4)
        currFamily = node->name;
    if (isSpeciesLeaf(node))
    {
        results[currFamily] = results[currFamily] + 1;
    }
    for (int i = 0; i < node->children.size(); i++)
    {
        speciesPerFamilyRec(results, child,currFamily);
    }
}

map<string, int> Taxonomy::speciesPerFamilyStack()
{
    map<string, int> results;
    stack<State> operations;
    operations.push(State(root, " "));
    while (!operations.empty()) //Едно извикване на рекурсивната функция
    {
        State state = operations.top();
        operations.pop();
        if (isSpeciesLeaf(state.node))
            results[state.currentFamily] += 1;
        string nextFamily = state.currentFamily;
        if (state.node->level == 4)
            nextFamily = state.node->name;
        for (int i = 0; i < state.node->children.size(); i++)
        {
            operations.push(State(state.node->children[i], nextFamily));
        }
    }

    return results;
}

void Taxonomy::listSpeciesRec(TNode * node, vector<string>& res)
{
    if (isSpeciesLeaf(node))
        res.push_back(node->name);
    else
        for (int i = 0; i < node->children.size(); i++)
            listSpeciesRec(node->children[i], res);
}

vector<string> Taxonomy::listSpeciesStack()
{
    vector<string> result;
    stack<TNode*> operations;
    operations.push(root);
    while(!operations.empty())
    {
        TNode* top = operations.top();
        operations.pop();
        if (isSpeciesLeaf(top))
        {
            result.push_back(top->name);
        }
        else
            for (int i = 0; i < top->children.size(); i++)
                operations.push(top->children[i]);
    }
}

vector<string> Taxonomy::listSpecies()
{
    vector<string> results;
    listSpeciesRec(root, results);
    return results;
}

void Taxonomy::print() const
{
    vector<string> path;
    printRec(root, path);
}



void Taxonomy::printRec(TNode * node, vector<string>& path) const
{
    if (node->children.empty())
    {
        for (vector<string>::iterator it = path.begin(); it != path.end(); ++it)
            cout << *it << "->";
        cout << node->name << endl;
    }
    else
    {
        path.push_back(node->name);
        for (vector<TNode*>::iterator it = node->children.begin(); it != node->children.end(); ++it)
            printRec(*it, path);
    }
    path.pop_back();
}



#include <iostream>
#include <vector>
#include<stack>

using namespace std;

void generatePerms(char characters[],int size,vector<char*>& results,char* perm, bool* used,int index) {
    if (index == size) {
        char* ready = new char[size + 1];
        perm[size] = 0;
        strcpy(ready, perm);
        results.push_back(ready);
    }
    for (int i = 0; i < size; i++) {
        if (!used[i]) {
            used[i] = true;
            perm[index] = characters[i];
            generatePerms(characters, size, results, perm, used, index + 1);
            used[i] = false;
        }
    }
}

vector<char*> permute(char characters[]) {
    vector<char*> results;
    int numChars = strlen(characters);
    bool* used = new bool[numChars];
    char* permutation = new char[numChars + 1];
    for (int i = 0; i < numChars; i++) {
        used[i] = false;
        permutation[i] = 0;
    }
    generatePerms(characters, numChars, results, permutation, used, 0);
    return results;
}

struct PermStep {
    char* perm;
    bool* used;
    int index;
    PermStep(char* perm, bool* used,int size,int idx) {
        this->perm = new char[size + 1];
        this->used = new bool[size];
        for (int i = 0; i < size; i++) {
            this->used[i] = used[i];
            this->perm[i] = perm[i];
        }
        index = idx;
    }
    ~PermStep() {
        delete[]used;
        delete[]perm;
    }
};
vector<char*> permuteStack(char characters[]) {
    vector<char*> results;
    int numChars = strlen(characters);
    bool* used = new bool[numChars];
    char* permutation = new char[numChars + 1];
    for (int i = 0; i < numChars; i++) {
        used[i] = false;
        permutation[i] = 0;
    }
    stack<PermStep> operations;
    operations.push(PermStep(permutation, used, numChars, 0));
    while (!operations.empty()) {
        PermStep top = operations.top();
        operations.pop();
        if (top.index == numChars) {
            char* ready = new char[numChars + 1];
            top.perm[numChars] = 0;
            strcpy(ready, top.perm);
            results.push_back(ready);
        }
        else {
            for (int i = 0; i < numChars; i++) {
                if (!top.used[i]) {
                    top.used[i] = true;
                    top.perm[top.index] = characters[i];
                    operations.push(PermStep(top.perm,top.used,numChars,top.index+1));
                    top.used[i] = false;
                }
            }
        }

    }
    return results;
}

int main()
{
    return 0;
}

//PO MOI NAHCIN 1VA
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <iostream>
//#include <bits/stdc++.h>

using namespace std;

void swap(char &x, char &y)
{
    char temp;
    temp = x;
    x = y;
    y = temp;
}
void permute(string a, int l, int r, vector<string> &v)
{
    if (l == r)//there aren't any letters left to be permuted
    {
        //cout << a;
        v.push_back(a);
    }
    else
    {
        for (int i = l; i <= r; i++)
        {
            swap(a[l], a[i]);
            permute(a, l + 1, r, v);
            swap(a[l], a[i]); //backtrack
        }
    }
}

#define OPER_PRINT 0
#define OPER_TRAV 1
struct Operation {
    int operType;
    string a;
    int l, r;
    Operation(string s,int t,  int ll, int rr) :operType(t), a(s), l(ll), r(rr){}
};

bool isUsed(string a)
{
    return true;
}
void permStack(string a, int l, int r)
{
    stack <Operation> s;
    s.push(Operation(a, OPER_TRAV, l, r));
    while (!s.empty())
    {
        Operation topOperation = s.top();
        string a = topOperation.a;
        int l = topOperation.l;
        int r = topOperation.r;
        s.pop();
        if (l == r)
        {
            cout << a;
        //  swap(a[l], a[i]);
        }
        else
        {
            for (size_t i = l; i <=l; i++)
            {
                if(!used(a))
                swap(a[l], a[i]);
                s.push(Operation(a, OPER_TRAV, l+1, r));
            }
        }
    }
}

void printV(vector <string> v)
{
    for (size_t i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;
}



int main()
{
    //char str[] = "ABC";
    //int n = strlen(str);
    string str1 = "ABC";
    vector<string> v;
    int n = str1.size();
    permute(str1, 0, n - 1, v);
    printV(v);
    cout << endl;
    permStack(str1,0,n-1);

    /*string str = "ABCD";

    // Rotating arround second element
    // string becomes "BCDA"
    rotate(str.begin(), str.begin() + 1, str.end());
    cout << str << endl;

    // Again rotating around second element
    // string becomes "CDAB"
    rotate(str.begin(), str.begin() + 1, str.end());
    cout << str;
    */
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <iostream>
//#include <bits/stdc++.h>

using namespace std;

void swap(char &x, char &y)
{
    char temp;
    temp = x;
    x = y;
    y = temp;
}
/*void generatePerms(char characters[], int size, vector<char*>& results, char* perm, bool* used, int index) {
    if (index == size) {
        char* ready = new char[size + 1];
        perm[size] = 0;
        strcpy(ready, perm);
        results.push_back(ready);
    }
    for (int i = 0; i < size; i++) {
        if (!used[i]) {
            used[i] = true;
            perm[index] = characters[i];
            generatePerms(characters, size, results, perm, used, index + 1);
            used[i] = false;
        }
    }
}*/
struct PermStep {
    string perm;
    bool* used;
    int index;
    PermStep(string perm, bool* used, int size, int idx) {
        this->perm = perm;
        this->used = new bool[size];
        for (int i = 0; i < size; i++) {
            this->used[i] = used[i];
            this->perm[i] = perm[i];
        }