//     Copyright (c) 2012 Vadym Kliuchnikov sqct(dot)software(at)gmail(dot)com, Dmitri Maslov, Michele Mosca
//
//     This file is part of SQCT.
// 
//     SQCT is free software: you can redistribute it and/or modify
//     it under the terms of the GNU Lesser General Public License as published by
//     the Free Software Foundation, either version 3 of the License, or
//     (at your option) any later version.
// 
//     SQCT is distributed in the hope that it will be useful,
//     but WITHOUT ANY WARRANTY; without even the implied warranty of
//     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//     GNU Lesser General Public License for more details.
// 
//     You should have received a copy of the GNU Lesser General Public License
//     along with SQCT.  If not, see <http://www.gnu.org/licenses/>.
// 

#include "exactdecomposer.h"
#include "matrix2x2.h"
#include "output.h"

#include <vector>
#include <iostream>
#include <deque>

using namespace std;

exactDecomposer::exactDecomposer()
{
    for( int i = 0; i < gen_count ; ++i)
    {
        generators[i] = M::T(8-i) * M::H() ;
        generators_ctr[i] = M::H() * M::T(i);
    }
}

void exactDecomposer::decompose( const matrix2x2<mpz_class>& matr, circuit& c)
{
    typedef ring_int< resring<8> > rr8;
    typedef matrix2x2< resring<8> > mrr8;

    c.clear();
    M current(matr);
    current.reduce();
    M t;

    int curr_sde = current.max_sde_abs2();
    while( curr_sde > 3 )
    {
        bool found = false;
        mrr8 mr( current ), tr; //the only last 8 bits matter
        int curr_gde = mr.d[0][0].abs2().gde();

        for( int i = 0; i < gen_count; ++i )
        {

            mr.mul_TkH(8-i,tr);
            int gde_got = tr.d[0][0].abs2().gde();
            if( gde_got == curr_gde + 3 )
            {
                curr_sde--;
                c.push_back( i );
                c.push_back( gateLibrary::H );

                current.mul_TkH(8-i,t);

                if( gde_got == 3 )
                    t.reduce(1);
                else
                    t.reduce(2);

                current = t;
                found = true;
                break;
            }
        }
        if( !found ) return;
    }

    circuit r;
    slC.find(current,r);
    c.push_back(r);
}