#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* constants */

#define NA -1

#define N 10
#define TRIAL 10

#define INIT_OPERATION 20
#define OPERATION_NUMBER 5

#define MAX_LENGTH 100
#define MAX_RUNTIME_FACTOR 100

#define RUNTIME_WEIGHT 0.0005
#define INVERSION_WEIGHT 0.9945
#define LENGTH_WEIGHT 0.005

#define POPULATION 500
#define SELECTED_PARENTS 120

/* instructions */

#define EXCH    0
#define INC        1
#define DEC        2
#define PUT        3
#define BR        4

/* operation types */

#define INSLINE        0
#define DELLINE        1
#define SWAPLINE    2
#define MUTATELINE    3

/* some tools globally used */

int myrand (int min, int max) {
    return min + (int) ((max - min + 1.0)*rand()/(RAND_MAX+1.0));
} // myrand ()

int myrand_except (int min, int max, int except) {
    int x;

    x = myrand (min, max - 1);
    if (x >= except) x++;

    return x;
}

int** make_new_array (int m, int n) {
    int** A;
    int i;

    A = new (int*) [m];
    for (i = 0; i < m; i++)
        A[i] = new int [n];
    return A;
} // make_new_array ()

void delete_array (int** A, int m, int n) {
    int i;

    for (i = 0; i < m; i++)
        delete [] A[i];
    delete [] A;
} // delete_array ()

void fill_array_randomly (int** A, int m, int n) {
    int i, j;

    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
            A[i][j] = rand();
} // random_array ()


struct line {
    unsigned char instr;
    unsigned char opr1;
    int opr2;
    line* next;
}; // struct line

class code {
private:
    int length;
    line* firstline;
    float runtime;
    float inversion;
    float fitness;

    line* gotoline (int linenum);
    line* gotoline_skipping_EXCH (int linenum);
    int count_inversion (int* A, int n);
    bool insline ();
    bool delline ();
    bool swapline ();
    bool mutateline ();

public:
    code ();
    code* copy ();
    void random_init ();
    float get_runtime ();
    float get_inversion ();
    float get_fitness ();
    int get_length ();
    float get_timecomplexity ();
    void operation ();
    void evaluate_fitness (int** given_A, int trial_no, int n);
    void print_code ();
    void save_code ();
    ~code ();
}; // class code

code::code () {
    length = 1;
    runtime = 0.0;
    inversion = 0.0;
    fitness = NA;

    firstline = new line;
    firstline->instr = EXCH;
    firstline->next = NULL;
} // code::code ()

code::~code () {
    line* p, * q;

    p = firstline;
    while (p != NULL) {
        q = p->next;
        delete p;
        p = q;
    }
} // code::~code ()

line* code::gotoline (int linenum) {
    int i;
    line* p;

    if (linenum < 0 || linenum >= length) return NULL;

    p = firstline;
    for (i = 1; i <= linenum && p != NULL/*for safety*/; i++)
        p = p->next;
    return p;
} // code::gotoline ()

line* code::gotoline_skipping_EXCH (int linenum) {
    int i;
    line* p;

    if (linenum < 0 || linenum >= length - 1) return NULL;

    p = firstline;
    if (p->instr == EXCH) p = p->next;
    for (i = 1; i <= linenum && p != NULL/*for safety*/; i++) {
        p = p->next;
        if (p->instr == EXCH) p = p->next;
    } // for i
    return p;
} // code::gotoline_skipping_EXCH ()

int code::count_inversion (int* A, int n) {
    int i, j;
    int inv = 0;

    for (i = 0; i < n-1; i++) {
        for (j = i+1; j < n; j++) {
            if (A[i] > A[j]) inv++;
        } // for j
    } // for i
    return inv;
} //code::count_inversion ()

bool code::insline () {
    line* new_line, * p;
    int wheretoput;
    int i;

    if (length > MAX_LENGTH) return false;

    length++;
    /* decide the location where we put the new line */
    wheretoput = myrand (0, length - 1);

    /* make new line */
    new_line = new line;
    new_line->instr = myrand_except (EXCH, BR, EXCH);
    switch (new_line->instr) {
        case INC :
        case DEC :
        case PUT :
            new_line->opr1 = myrand (0, 1);
            break;
        case BR :
            new_line->opr1 = myrand (0, 6);
            new_line->opr2 = myrand_except (0, length - 1, wheretoput);
            break;
    } // switch (new_line->instr)

    if (wheretoput == 0) {
        new_line->next = firstline;
        firstline = new_line;
    } else {
        p = gotoline (wheretoput - 1);
        if (p == NULL) {length--; return false;} /* for safety */
        new_line->next = p->next;
        p->next = new_line;
    } // if - else

    return true;
} // code::insline ()

bool code::delline () {
    line* p, * q;
    int wheretodelete;
    int i;

    if (length <= 1) return false;
    wheretodelete = myrand (0, length - 1 - 1);

    if (wheretodelete == 0) {
        if (firstline == NULL) return false; /* for safety */
        else if (firstline->instr == EXCH) wheretodelete++;
        else {
            q = firstline;
            firstline = firstline->next;
            delete q;
        }
    } // do not use else-if !!
    if (wheretodelete > 0) {
        p = firstline;
        for (i = 1; i < wheretodelete; i++) {
            p = p->next;
            if (p == NULL) return false; /* for safety */
            if (p->instr == EXCH) p = p->next;
            if (p == NULL) return false; /* for safety */
        }
        q = p->next;
        if (q == NULL) return false; /* for safety */
        p->next = q->next;
        delete q;
    }
    length--;
    return true;
} // code::delline ()

bool code::swapline () {
    int i1, i2;
    line* p1, * p2, tmp;

    if (length <= 1) return false;

    i1 = myrand (0, length - 1);
    i2 = myrand_except (0, length - 1, i1);

    p1 = gotoline (i1);
    p2 = gotoline (i2);

    tmp.instr = p1->instr;
    tmp.opr1 = p1->opr1;
    tmp.opr2 = p1->opr2;
    p1->instr = p2->instr;
    p1->opr1 = p2->opr1;
    p1->opr2 = p2->opr2;
    p2->instr = tmp.instr;
    p2->opr1 = tmp.opr1;
    p2->opr2 = tmp.opr2;

    return true;
} // code::swapline ()

bool code::mutateline () {
    line* p;
    int tmp;
    int wheretochange;

    if (length <= 1) return false;
    wheretochange = myrand (0, length - 1 - 1);
    p = gotoline_skipping_EXCH (wheretochange);
    if (p == NULL) return false; /* for safety */

    switch (p->instr) {
        case INC :
        case DEC :
        case PUT :
            p->opr1 = ! (p->opr1);
            break;
        case BR :
            if (myrand (0,1))
                p->opr1 = myrand_except (0, 6, p->opr1);
            else {
                /* i think it is not so good, but ... */
                p->opr2 = myrand_except (0, length - 1, p->opr2);
            } // if - else
            break;
    } // switch (p->instr)
    return true;
} // code::mutateline ()

code* code::copy () {
    code* p;
    line* src, * dst;

    p = new code;
    *p = *this;

    src = firstline;
    if (src == NULL) return p; /* for safety */
    
    dst = new line;
    p->firstline = dst;
    while (src != NULL) {
        *dst = *src;
        if (src->next != NULL) {
            dst->next = new line;
            dst = dst->next;
        }
        src = src->next;
    }

    return p;
} // code::copy ()

void code::random_init () {
    int i;

    for (i = 0; i < INIT_OPERATION; i++)
        operation ();
} // code::random_init ()

float code::get_runtime () {
    return runtime;
} // code::runtime ()

float code::get_inversion () {
    return inversion;
} // code::inversion ()

float code::get_fitness () {
    return fitness;
} // code::fitness ()

int code::get_length () {
    return length;
} // code::get_length ()

float code::get_timecomplexity () {
    return runtime / length;
} // code::get_timecomplexity ()

void code::operation () {
    int operation_type;
    bool succeded = false;

    do {
        operation_type = myrand (INSLINE, MUTATELINE);

        switch (operation_type) {
            case INSLINE :
                succeded = insline ();
                break;
            case DELLINE :
                succeded = delline ();
                break;
            case SWAPLINE :
                succeded = swapline ();
                break;
            case MUTATELINE :
                succeded = mutateline ();
                break;
        } // switch (operation_type)
    } while (! succeded);
} // code::operation ()

void code::evaluate_fitness (int** given_A, int trial_no, int n) {
    int** A;
    int i;
    int curr_trial;
    line* curr_line, * next_line;
    int curr_runtime, curr_inv, old_inv, inv_fixed_period;
    int i1, i2;
    int temp;

    A = make_new_array (trial_no, n);
    for (i = 0; i < trial_no; i++)
        memcpy (A[i], given_A[i], sizeof(int)*n);

    runtime = 0.0;
    inversion = 0.0;

    for (curr_trial = 0; curr_trial < trial_no; curr_trial++) {
        curr_runtime = 0;
        old_inv = NA;
        inv_fixed_period = 1;

        i1 = 0; i2 = 0;
        curr_line = firstline;
        while (curr_line != NULL) { // until the last line
            next_line = curr_line->next;
            switch (curr_line->instr) {
                case EXCH :
                    if (0 <= i1 && i1 < n && 0 <= i2 && i2 < n) { // index range check
                        if ( // inversion check
                                (i1 < i2 && A[curr_trial][i1] > A[curr_trial][i2])
                                || (i1 > i2 && A[curr_trial][i1] < A[curr_trial][i2])
                           ) {
                            temp = A[curr_trial][i1];
                            A[curr_trial][i1] = A[curr_trial][i2];
                            A[curr_trial][i2] = temp;
                        } // inversion check
                    } // index range check
                    break;
                case INC :
                    if (curr_line->opr1 == 0) i1++;
                    else if (curr_line->opr1 == 1) i2++;
                    break;
                case DEC :
                    if (curr_line->opr1 == 0) i1--;
                    else if (curr_line->opr1 == 1) i2--;
                    break;
                case PUT :
                    if (curr_line->opr1 == 0) i1 = i2;
                    else i2 = i1;
                    break;
                case BR :
                    if (0 <= curr_line->opr2 && curr_line->opr2 < length) { // branching addr check
                        if ( // branching type & condition check
                                (curr_line->opr1 == 0 && i1 <= 0)
                                || (curr_line->opr1 == 1 && i2 <= 0)
                                || (curr_line->opr1 == 2 && i1 >= n-1)
                                || (curr_line->opr1 == 3 && i2 >= n-1)
                                || (curr_line->opr1 == 4 && i1 < i2)
                                || (curr_line->opr1 == 5 && i1 > i2)
                                || (curr_line->opr1 == 6 && i1 == i2)
                           ) {
                            next_line = gotoline (curr_line->opr2);
                        } // branching type & condition check
                    } // branching addr check
                    break;
            } // switch (curr_line->instr)
            curr_runtime++;
            if (curr_runtime > n*n*MAX_RUNTIME_FACTOR) break;
            curr_line = next_line;
        } // while (curr_line != NULL) // until the last line

        curr_inv = count_inversion (A[curr_trial], n);
        runtime += ((float)curr_runtime);
        inversion += ((float)curr_inv);
    } // for curr_trial
    runtime /= ((float)trial_no);
    inversion /= ((float)trial_no); 
    fitness = RUNTIME_WEIGHT*runtime + INVERSION_WEIGHT*inversion + LENGTH_WEIGHT*((float)length);

    delete_array (A, trial_no, n);
} // code::evaluate_fitness ()

void code::print_code () {
    line* p;

    p = firstline;
    while (p!= NULL) {
        printf ("instr=%d, op1=%d, op2=%d\n", p->instr, p->opr1, p->opr2);
        p = p->next;
    }
}

void code::save_code () {
    FILE* f;
    line* p;

    f = fopen ("ea_sort.cod", "at");
    fprintf (f, "rt=%f inv=%f ln=%d (fitness=%lf)\n", runtime, inversion, length, fitness);

    p = firstline;
    while (p!= NULL) {
        fprintf (f, "instr=%d, op1=%d, op2=%d\n", p->instr, p->opr1, p->opr2);
        p = p->next;
    }

    fprintf (f, "\n");
    fclose (f);
}


int fitness_compare (const void* p1, const void* p2) {
/* for qsort */
    code* q1, * q2;

    q1 = *((code **)p1);
    q2 = *((code **)p2);

    if (q1->get_fitness () < q2->get_fitness ())
        return -1;
    return (q1->get_fitness () > q2->get_fitness ());
} // fitness_compare ()


main () {
    code** population;
    int i;
    int** A;
    unsigned int itr = 0;
    char tmp[100];
    FILE* file;
    float f_mean, f_var, f_min, f_max, f;

    population = new (code*) [POPULATION];

    srand (100);

    file = fopen ("ea_sort.log", "wt");


    /* initial population */
    for (i = 0; i < POPULATION; i++) {
        population[i] = new code;
        population[i]->random_init ();
    }

    A = make_new_array (TRIAL, N);
    tmp[0] = 0;

    /* main iteration - for itr-th generation */
    do {
        printf("itr=%u : ", itr);

        /* make test vector (sample array) */
        fill_array_randomly (A, TRIAL, N);

        /* evaluation */
        for (i = 0; i < POPULATION; i++) {
            population[i]->evaluate_fitness (A, TRIAL, N);
        }

        qsort (population, POPULATION, sizeof(code*), fitness_compare);

        /* display current state */
        for (i = 0; i < 1; i++)
            printf ("%dth: %f %f %d (%f)\n", i, population[i]->get_runtime(), population[i]->get_inversion(), population[i]->get_length(), population[i]->get_fitness());

        /* user-interaction mode */
        if (population[0]->get_inversion() < 1e-6 && population[0]->get_length() <= 13) { /* stop condition */
            do {
                fgets (tmp, 99, stdin);    // get a command from the user
                switch (tmp[0]) {
                    case 'c' :
                        for (i=0; i<10; i++) {
                            printf("%dth:", i);
                            population[i]->print_code();
                        }
                        break;
                    case 'r' :
                        for (i=0; i<10; i++) printf("%d th: %f \n", i, population[i]->get_runtime());
                        break;
                    case 'i' :
                        for (i=0; i<10; i++) printf("%d th: %f \n", i, population[i]->get_inversion());
                        break;
                    case 'f' :
                        for (i=0; i<10; i++) printf("%d th: %f \n", i, population[i]->get_fitness());
                        break;
                    case 't' :
                        for (i=0; i<10; i++) printf("%d th: %f \n", i, population[i]->get_timecomplexity());
                        break;
                    case 'l' :
                        for (i=0; i<10; i++) printf("%d th: %f \n", i, population[i]->get_length());
                        break;
                } // switch
            } while (tmp[0] != '\n' && tmp[0] != 'q');
        } // if

        /* save current state */
        f_mean = 0.0;
        f_min = 99999;
        f_max = -1;
        for (i = 0; i < POPULATION; i++) {
            f = population[i]->get_fitness();
            f_mean += f;
            if (f < f_min) f_min = f;
            if (f > f_max) f_max = f;
        }
        f_mean /= POPULATION;
        f_var = 0.0;
        for (i = 0; i < POPULATION; i++) {
            f = population[i]->get_fitness();
            f_var += (f - f_mean)*(f - f_mean);
        }
        f_var /= POPULATION;
        fprintf (file, "%20f %20f %20f %20f\n", f_mean, f_var, f_min, f_max);

        if (!(itr % 50)) population[0]->save_code(); // save the best code
        if (itr > 2500) break;    // end condition

        /* selection */
        // remove the worst group, and replace them with the copy of the best group
        for (i = 0; i < SELECTED_PARENTS; i++) {
            delete (population [POPULATION - i - 1]);    // remove the worst group
            population [POPULATION - i - 1] = population[i]->copy ();    // copy the best group
        }

        // mutate the best group and the ordinary group
        for (i = 0; i < POPULATION - SELECTED_PARENTS; i++) {
            population [i]->operation ();
        }

        itr++;
    } while (tmp[0] != 'q');

    delete_array (A, TRIAL, N);
    fclose (file);
} // main ()