#include "pupik.h"

// -----------------------------------------------------------------------
int Top_term::operator<(const Top_term &tt) const
{
    if (dc_count < tt.dc_count) return 1;
    
    return 0;
}

// -----------------------------------------------------------------------
Pupik::Pupik(int inputs, int outputs)
{
    min_tree = new I_buffer();
    count = 0;
//     pocet_sloucenych = 0;
    inputs_num = inputs;
    outputs_num = outputs;
}

// -----------------------------------------------------------------------
int Pupik::mt_count(I_buffer *akt)
{
    int i = 0;
    if (akt->zero) i++;
    if (akt->one) i++;
    if (akt->dc) i++;

    return i;
}

// -----------------------------------------------------------------------
void Pupik::mt_merge_leaves_recursive(I_buffer *akt, I_buffer *parent)
{
    if (akt->is_leaf()){
        if (mt_count(parent) >= 2){
//             cout << "slucuji listy" << endl;
//             pocet_sloucenych++;
//             parent->dc = parent->zero;
            if (parent->zero){
                if (parent->dc){
                    delete parent->zero;
//                     count--;
                }
                else {
                    parent->dc = parent->zero;
                }
                if (parent->one){
                    delete parent->one;
//                     count--;
                }
            }
            else {
                if (parent->dc){
                    delete parent->one;
//                     count--;
                }
                else {
                    parent->dc = parent->one;
                }
                if (parent->zero){
                    delete parent->zero;
//                     count--;
                }
            }
            parent->zero = parent->one = NULL;
        }
    }
    else {
        /*        term[index] = '0';*/
        if (akt->zero){
//             cout << "0";
            mt_merge_leaves_recursive(akt->zero, akt);
        }
//         term[index] = '1';
        if (akt->one){
//             cout << "1";
            mt_merge_leaves_recursive(akt->one, akt);
        }
//         term[index] = '2';
        if (akt->dc){
//             cout << "-";
            mt_merge_leaves_recursive(akt->dc, akt);
        }
    }
}

// -----------------------------------------------------------------------
void Pupik::mt_merge_leaves(void)
{
    mt_merge_leaves_recursive(min_tree, min_tree);
}

// -----------------------------------------------------------------------
void Pupik::mt_insert_leaf_recursive(I_buffer *akt, int val)
{
    if (akt->is_leaf()){
        switch(val){
            case 0:
                akt->zero = new I_buffer();
//                 cout << "vkladam 0" << endl;
//                 count++;
                break;
            case 1:
                akt->one = new I_buffer();
//                 cout << "vkladam 1" << endl;
//                 count++;
                break;
            case 2:
                akt->dc = new I_buffer();
//                 cout << "vkladam -" << endl;
//                 count++;
                break;
            default:
                cout << "chyba pri rozdelovani stromu" << endl;
                break;
        }
    }
    else {
        /*        term[index] = '0';*/
        if (akt->zero){
//             cout << "0";
            mt_insert_leaf_recursive(akt->zero, val);
        }
//         term[index] = '1';
        if (akt->one){
//             cout << "1";
            mt_insert_leaf_recursive(akt->one, val);
        }
//         term[index] = '2';
        if (akt->dc){
//             cout << "-";
            mt_insert_leaf_recursive(akt->dc, val);
        }
    }
}

// -----------------------------------------------------------------------
void Pupik::mt_divide_tree(void)
{
    I_buffer *tree1, *tree2, *tree3;
    clock_t t1, t2;

    tree1 = tree2 = tree3 = NULL;

    if (min_tree->zero)
        tree1 = min_tree->zero;
    if (min_tree->one)
        tree2 = min_tree->one;
    if (min_tree->dc)
        tree3 = min_tree->dc;

//     min_tree->zero = min_tree->one = min_tree->dc = NULL;
//     delete min_tree;
//     min_tree = NULL;
//     min_tree = tree1;

    t1 = clock();
//     cout << "prvni" << endl;
    if (tree1)
        mt_insert_leaf_recursive(tree1, 0);
//     cout << "druhy" << endl;
    if (tree2)
        mt_insert_leaf_recursive(tree2, 1);
//     cout << "treti" << endl;
    if (tree3)
        mt_insert_leaf_recursive(tree3, 2);
    t2 = clock();

//     cout << "nove listy vlozeny: "<< difftime(t2, t1)/CLOCKS_PER_SEC << " secs" << endl;

    if (min_tree->zero)
        min_tree->zero = NULL;
    if (min_tree->one)
        min_tree->one = NULL;
    if (min_tree->dc)
        min_tree->dc = NULL;

    delete min_tree;

    t1 = clock();
    if (tree1){
        min_tree = tree1;

//         cout << "ctvrty" << endl;
        if (tree2 && tree3)
            mt_merge_trees(tree3, tree2, tree1);
        else
            if (tree2)
                mt_merge_trees(tree2, tree1);
        else
            if (tree3)
                mt_merge_trees(tree3, tree1);
    }
    else {
        if (tree2){
            min_tree = tree2;

            if (tree1 && tree3)
                mt_merge_trees(tree3, tree1, tree2);
            else
                if (tree1)
                    mt_merge_trees(tree1, tree2);
            else
                if (tree3)
                    mt_merge_trees(tree3, tree2);
        }
        else {
            if (tree3){
                min_tree = tree3;

                if (tree1 && tree2)
                    mt_merge_trees(tree1, tree2, tree3);
                else
                    if (tree2)
                        mt_merge_trees(tree2, tree3);
                else
                    if (tree1)
                        mt_merge_trees(tree1, tree3);
            }
        }
    }
    t2 = clock();
//     cout << "stromy slouceny: "<< difftime(t2, t1)/CLOCKS_PER_SEC << " secs" << endl;
}

// -----------------------------------------------------------------------
void Pupik::mt_divide_and_merge(void)
{
    I_buffer *tree1, *tree2, *tree3;
//     clock_t t1, t2;

    tree1 = tree2 = tree3 = NULL;

    if (min_tree->zero)
        tree1 = min_tree->zero;
    if (min_tree->one)
        tree2 = min_tree->one;
    if (min_tree->dc)
        tree3 = min_tree->dc;

//     t1 = clock();
//     cout << "prvni" << endl;
    if (tree1)
        mt_insert_leaf_recursive(tree1, 0);
//     cout << "druhy" << endl;
    if (tree2)
        mt_insert_leaf_recursive(tree2, 1);
//     cout << "treti" << endl;
    if (tree3)
        mt_insert_leaf_recursive(tree3, 2);
//     t2 = clock();
//     cout << "nove listy vlozeny: "<< difftime(t2, t1)/CLOCKS_PER_SEC << " secs" << endl;

    if (min_tree->zero)
        min_tree->zero = NULL;
    if (min_tree->one)
        min_tree->one = NULL;
    if (min_tree->dc)
        min_tree->dc = NULL;

    delete min_tree;
    min_tree = NULL;

//     t1 = clock();
    if (tree1){
        min_tree = tree1;

        if (tree2)
            mt_merge_trees(tree2, tree1);
        if (tree3)
            mt_merge_trees(tree3, tree1);
    }
    else {
        if (tree2){
            min_tree = tree2;

            if (tree1)
                mt_merge_trees(tree1, tree2);
            if (tree3)
                mt_merge_trees(tree3, tree2);
        }
        else {
            if (tree3){
                min_tree = tree3;

                if (tree1)
                    mt_merge_trees(tree1, tree3);
                if (tree2)
                    mt_merge_trees(tree2, tree3);
            }
        }
    }
//     t2 = clock();
//     cout << "stromy slouceny: "<< difftime(t2, t1)/CLOCKS_PER_SEC << " secs" << endl;
}

// -----------------------------------------------------------------------
void Pupik::mt_merge_trees(I_buffer *src1, I_buffer *src2, I_buffer *dest)
{
    // nejdriv sloucime podstrom pro hodnotu NULA
    if (src1->zero && src2->zero){
        if (dest->zero)
            mt_merge_trees(src1->zero, src2->zero, dest->zero);
        else {
            mt_merge_trees(src1->zero, src2->zero);
            dest->zero = src2->zero;
        }
    }
    else {
        if (src1->zero){
            if (dest->zero)
                mt_merge_trees(src1->zero, dest->zero);
            else
                dest->zero = src1->zero;
        }
        else
            if (src2->zero){
            if (dest->zero)
                mt_merge_trees(src2->zero, dest->zero);
            else
                dest->zero = src2->zero;
            }
    }

    // potom sloucime podstrom pro hodnotu JEDNA
    if (src1->one && src2->one){
        if (dest->one)
            mt_merge_trees(src1->one, src2->one, dest->one);
        else {
            mt_merge_trees(src1->one, src2->one);
            dest->one = src2->one;
        }
    }
    else {
        if (src1->one){
            if (dest->one)
                mt_merge_trees(src1->one, dest->one);
            else
                dest->one = src1->one;
        }
        else
            if (src2->one){
            if (dest->one)
                mt_merge_trees(src2->one, dest->one);
            else
                dest->one = src2->one;
            }
    }

    // a nakonec sloucime podstrom pro hodnotu DON'T CARE
    if (src1->dc && src2->dc){
        if (dest->dc)
            mt_merge_trees(src1->dc, src2->dc, dest->dc);
        else {
            mt_merge_trees(src1->dc, src2->dc);
            dest->dc = src2->dc;
        }
    }
    else {
        if (src1->dc){
            if (dest->dc)
                mt_merge_trees(src1->dc, dest->dc);
            else
                dest->dc = src1->dc;
        }
        else
            if (src2->dc){
            if (dest->dc)
                mt_merge_trees(src2->dc, dest->dc);
            else
                dest->dc = src2->dc;
            }
    }

    if (src1->zero) src1->zero = NULL;
    if (src1->one) src1->one = NULL;
    if (src1->dc) src1->dc = NULL;
    if (src2->zero) src2->zero = NULL;
    if (src2->one) src2->one = NULL;
    if (src2->dc) src2->dc = NULL;

    delete src1;
    delete src2;
}

// -----------------------------------------------------------------------
void Pupik::mt_merge_trees(I_buffer *src, I_buffer *dest)
{
    if (src->zero){
        if (dest->zero)
            mt_merge_trees(src->zero, dest->zero);
        else
            dest->zero = src->zero;
    }
    if (src->one){
        if (dest->one)
            mt_merge_trees(src->one, dest->one);
        else
            dest->one = src->one;
    }
    if (src->dc){
        if (dest->dc)
            mt_merge_trees(src->dc, dest->dc);
        else
            dest->dc = src->dc;
    }
    if (src->zero) src->zero = NULL;
    if (src->one) src->one = NULL;
    if (src->dc) src->dc = NULL;
    delete src;
    src = NULL;
}

// -----------------------------------------------------------------------
void Pupik::mt_top_term(char *term, int dc_count)
{
    Top_term *tt;
    vector<Top_term>::iterator min;
    
//     cout << top_terms.size() << endl;
    
//     for(unsigned int i = 0;i < top_terms.size();i++)
//         cout << top_terms[i].dc_count << " ";
//     cout << endl;
    
    if (top_terms.size() <= 100){
        tt = new Top_term(inputs_num);
        memcpy((char *)tt->term, (char *)term, inputs_num*sizeof(char));
        tt->dc_count = dc_count;
        top_terms.push_back(*tt);
//         for(unsigned int i = 0;i < top_terms.size();i++)
//             cout << top_terms[i].dc_count << " ";
//         cout << endl;
//         sort(top_terms.begin(), top_terms.end());
    }
/*    else {
        min = min_element(top_terms.begin(), top_terms.end());
        
        if (dc_count > top_terms.end()->dc_count){
            sort(top_terms.begin(), top_terms.end());
            top_terms.erase(min);
            
            tt = new Top_term(inputs_num);
            
            memcpy(tt->term, term, inputs_num*sizeof(char));
            tt->dc_count = dc_count;
            top_terms.push_back(*tt);
        }
    }*/
}

//-----------------------------------------------------------------------
bool Pupik::mt_minimize_subset_recursive(I_buffer *akt, char *term_to_delete, char *term, int index)
{
    if (akt->is_leaf()){
/*        for(int i = 0;i < inputs_num;i++)
        cout << term_to_delete[i];
        cout << endl;
        for(int i = 0;i < inputs_num;i++)
        cout << term[i];
        cout << endl << "------------------------------------------------------------ " << endl;*/
        
//         cout << same_term << " " << inputs_num << endl;
        if (same_term != inputs_num){
            delete akt;
            akt = NULL;
//             cout << "mazu" << endl;
            return true;
        }
//         else {
//             cout << "stejny term => nesmim smazat" << endl;
//             cout << same_term << " " << inputs_num << endl;
//         }
    }
    else {
        if (term[index] == '0'){
            if (akt->zero){
                term_to_delete[index] = '0';
                same_term++;
                if (mt_minimize_subset_recursive(akt->zero, term_to_delete, term, index+1)){
                    akt->zero = NULL;
                    if (!akt->one && !akt->dc){
                        delete akt;
                        akt = NULL;
                        same_term--;
                        return true;
                    }
                }
                same_term--;
            }
        }
        if (term[index] == '1'){
            if (akt->one){
                term_to_delete[index] = '1';
                same_term++;
                if (mt_minimize_subset_recursive(akt->one, term_to_delete, term, index+1)){
                    akt->one = NULL;
                    if (!akt->zero && !akt->dc){
                        delete akt;
                        akt = NULL;
                        same_term--;
                        return true;
                    }
                }
                same_term--;
            }
        }
        if (term[index] == '2'){
            if (akt->zero){
                term_to_delete[index] = '0';
                if (mt_minimize_subset_recursive(akt->zero, term_to_delete, term, index+1)){
                    akt->zero = NULL;
                    if (!akt->one && !akt->dc){
                        delete akt;
                        akt = NULL;
                        return true;
                    }
                }
            }
            if (akt->one){
                term_to_delete[index] = '1';
                if (mt_minimize_subset_recursive(akt->one, term_to_delete, term, index+1)){
                    akt->one = NULL;
                    if (!akt->zero && !akt->dc){
                        delete akt;
                        akt = NULL;
                        return true;
                    }
                }
            }
            if (akt->dc){
                term_to_delete[index] = '2';
                same_term++;
                if (mt_minimize_subset_recursive(akt->dc, term_to_delete, term, index+1)){
                    akt->dc = NULL;
                    if (!akt->one && !akt->zero){
                        delete akt;
                        same_term--;
                        akt = NULL;
                        return true;
                    }
                }
                same_term--;
            }
        }
    }
    return false;
}

// -----------------------------------------------------------------------
void Pupik::mt_minimize_subset(void)
{
    char *term = new char[inputs_num], *term_to_delete = new char[inputs_num];
    
    count = 0;
    
//     cout << "generuji nejlepsi termy" << endl;
    mt_generate_top_terms(min_tree, term, 0);
//     cout << "mam nejlepsi termy" << endl;
    
    delete[] term;
    
    for(int i = 0;i < inputs_num;i++)
        term_to_delete[i] = '2';
    
//     cout << top_terms.size() << endl;
    
    for(unsigned int i = 0;i < top_terms.size();i++){
        term = top_terms[i].term;
        same_term = 0;

//         cout << "minimalizuji" << endl;
        mt_minimize_subset_recursive(min_tree, term_to_delete, term, 0);
//         cout << "minimalizovano" << endl;
    }
    
    top_terms.clear();
    delete[] term_to_delete;
//     cout << "podmnoziny..." << endl;
}

// -----------------------------------------------------------------------
void Pupik::mt_generate_top_terms(I_buffer *akt, char *term, int index)
{
    if (akt->is_leaf()){
        mt_top_term(term, count);
//         pocet_sloucenych++;
//         cout << count << endl;
//         print_array(term, inputs_num);
//         cout << endl;
//         PLA_elem *pla = new PLA_elem(inputs_num, outputs_num);
//         memcpy((char *)pla->pla_inputs, (char *)term, inputs_num*sizeof(char));
//         memcpy((char *)pla->pla_outputs, (char *)out, outputs_num*sizeof(char));
//         pla_list.push_back(pla);
    }
    else {
        term[index] = '0';
        if (akt->zero){
//             cout << "0";
            mt_generate_top_terms(akt->zero, term, index+1);
        }
        term[index] = '1';
        if (akt->one){
//             cout << "1";
            mt_generate_top_terms(akt->one, term, index+1);
        }
        term[index] = '2';
        if (akt->dc){
//             cout << "-";
            count++;
            mt_generate_top_terms(akt->dc, term, index+1);
            count--;
        }
    }
}

// -----------------------------------------------------------------------
void Pupik::mt_insert(char *term)
{
    I_buffer *akt = min_tree;
    
    for(int i = 0;i < inputs_num;i++){
        switch(term[i]){
            case '0':
                if (akt->zero == NULL){
//                     cout << "vkladam novy uzel do nuly, i = " << i << endl;
//                     cout << "new" << endl;
                    if (i == (inputs_num-1)){
                        if (akt->one || akt->dc){
                            if (akt->one){
                                delete akt->one;
                                akt->one = NULL;
                            }
                            if (!akt->dc){
                                akt->dc = new I_buffer();
                                break;
                            }
                            else
                                break;
                        }
                        else
                            akt->zero = new I_buffer();
                    }
                    else
                        akt->zero = new I_buffer();
                }
                akt = akt->zero;
                break;
            case '1':
                if (akt->one == NULL){
//                     cout << "vkladam novy uzel do jednicky" << endl;
//                     cout << "new" << endl;
                    if (i == (inputs_num-1)){
                        if (akt->zero || akt->dc){
                            if (akt->zero){
                                delete akt->zero;
                                akt->zero = NULL;
                            }
                            if (!akt->dc){
                                akt->dc = new I_buffer();
                                break;
                            }
                            else
                                break;
                        }
                        else
                            akt->one = new I_buffer();
                    }
                    else
                        akt->one = new I_buffer();
                }
                akt = akt->one;
                break;
            case '2':
                if (akt->dc == NULL){
//                     cout << "vkladam novy uzel do don't care" << endl;
//                     cout << "new" << endl;
                    if (i == (inputs_num-1)){
                        if (akt->one || akt->zero){
                            if (akt->one){
                                akt->dc = akt->one;
                                akt->one = NULL;
                                if (akt->zero){
                                    delete akt->zero;
                                    akt->zero = NULL;
                                }
                                break;
                            }
                            if (akt->zero){
                                akt->dc = akt->zero;
                                akt->zero = NULL;
                                if (akt->one){
                                    delete akt->one;
                                    akt->one = NULL;
                                }
                                break;
                            }
                        }
                        else {
                            akt->dc = new I_buffer();
                        }
                    }
                    else {
                        akt->dc = new I_buffer();
                    }
                }
                akt = akt->dc;
                break;
            default:
//                 cout << "chyba v termu" << endl;
                throw std::runtime_error("chyba v termu");
                break;
        }
    }
}

// -----------------------------------------------------------------------
void Pupik::mt_print_recursive(I_buffer *akt, char *term, int index, char *out)
{
    if (akt->is_leaf()){
        pocet_sloucenych++;
//         print_array(term, inputs_num);
//         cout << endl;
//         PLA_elem *pla = new PLA_elem(inputs_num, outputs_num);
//         memcpy((char *)pla->pla_inputs, (char *)term, inputs_num*sizeof(char));
//         memcpy((char *)pla->pla_outputs, (char *)out, outputs_num*sizeof(char));
//         pla_list.push_back(pla);
    }
    else {
        term[index] = '0';
        if (akt->zero){
//             cout << "0";
            mt_print_recursive(akt->zero, term, index+1, out);
        }
        term[index] = '1';
        if (akt->one){
//             cout << "1";
            mt_print_recursive(akt->one, term, index+1, out);
        }
        term[index] = '2';
        if (akt->dc){
//             cout << "-";
            mt_print_recursive(akt->dc, term, index+1, out);
        }
    }
}

// -----------------------------------------------------------------------
void Pupik::mt_print(char *out)
{
    char *term;

    term = new char[inputs_num];
    for(int i = 0;i < inputs_num;i++)
        term[i] = '3';

    mt_print_recursive(min_tree, term, 0, out);

    delete[] term;
}

// -----------------------------------------------------------------------
void Pupik::mt_export(Export *o_file, I_buffer *akt, char *term, char *out, int index)
{
    if (akt->is_leaf()){
        o_file->export_to_pla(o_file->get_file(), term, out, inputs_num, outputs_num);
/*        print_array(term, inputs_num);
        cout << " ";
        print_array(out, outputs_num);
        cout << endl;*/
    }
    else {
        term[index] = '0';
        if (akt->zero){
//             cout << "0";
            mt_export(o_file, akt->zero, term, out, index+1);
        }
        term[index] = '1';
        if (akt->one){
//             cout << "1";
            mt_export(o_file, akt->one, term, out, index+1);
        }
        term[index] = '2';
        if (akt->dc){
//             cout << "-";
            mt_export(o_file, akt->dc, term, out, index+1);
        }
    }
}

// -----------------------------------------------------------------------
void Pupik::print_array(char *arr, int size)
{
    for(int i = 0;i < size;i++)
        if (arr[i] == '2')
            cout << '-';
    else
        cout << arr[i];

//     cout << endl;
}
