#include "lab1.h"
#include "lab2.h"
#include "lab3.h"

using namespace std;



void sort(lab1::Queue<int>& q){
    q.N_op+=3;
    for(int i = 0; i < q.size(); ++i){
        q.N_op+= 12;
        int mn = INT_MAX;
        int first = 0, temp = 0;
        bool swap = true;
        for(int j = 0; j < i; ++j){
            q.N_op++;
            temp = q.front();
            q.pop();
            q.push(temp);
        }
        first = q.front();
        for(int j = i; j < q.size(); ++j){
            temp = q.front();
            mn = min(q.front(), mn);
            q.pop();
            q.push(temp);
            q.N_op+=3;
        }
        for(int j = 0; j < i; ++j){
            q.N_op++;
            temp = q.front();
            q.pop();
            q.push(temp);
        }
        for(int j = i; j < q.size(); ++j){
            q.N_op+=5;
            temp = q.front();
            q.pop();
            if(temp == mn && swap) {
                q.push(first);
                swap = false;
            }
            else if(i == j) {
                q.push(mn);
            }
            else
                q.push(temp);
        }
    }
}

int main(){
    for (int a = 5000; a <= 10000; a += 500) {
        size_t n = 0;
        lab1::Queue<int> queue(a);
        srand(time(NULL));
        ::clock_t start = ::clock();
        for(int i = 0; i < a; ++i)
            queue.push(::rand() % (5 * a));
        cout << "init of " << a << " elements takes " <<
            (::clock() - start) * 1000 /CLOCKS_PER_SEC << " millisec\n";
        start = ::clock();
        sort(queue);
        cout << "sort of " << a << " elements takes " <<
            (::clock() - start) * 1000 /CLOCKS_PER_SEC << " millisec\n";
        cout << "takes " << queue.N_op << " N_op\n\n";
    }

}
/*int main(){
    lab2::Graph G(4);
    set<int> visited;
    int cCount;
    cin >> cCount;
    for(int i = 0; i < cCount; ++i){
        string first_v, second_v;
        int weight;
        cin >> first_v >> second_v >> weight;
        G.Add_E(first_v, second_v, weight);
    }
    G.print();


    return 0;
}*/
/*
4
a c 5
b c 1
c b 3
d a 7
 */