//     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/>.
// 

#ifndef OPTSEQUENCEGENERATOR_H
#define OPTSEQUENCEGENERATOR_H

#include "matrix2x2.h"
#include <vector>
#include <queue>
#include <set>
#include <memory>

/// \brief Node of a Breadth First Search tree
struct optNode
{
    int gen_id; ///< id of unitary used to get this node
    const optNode* parent; ///< parent of the node
    matrix2x2<int> unitary; ///< value of the node
    int cost; ///< total cost of the circuit required to get the node
};

/// \brief Node of priority queue used in Breadth First Search
struct pqoptNode
{
    const optNode* node;
    int cost;
};

/// \brief Order on priority queue nodes base on cost
struct pqoptNodeCompare
{
    bool operator() ( const optNode* a , const optNode* b ) const
    {
        return a->cost > b->cost;
    }
};

/// \brief Order on BFS nodes base on order of unitaries that they contain
struct optNodeCompare
{
    typedef std::shared_ptr<optNode> ptr;
    bool operator() ( const ptr& a, const ptr& b) const
    {
        return a->unitary < b->unitary;
    }
};

/// \brief Uses Breadth First Search (BFS) to find optimal sequences generated by a set of
/// gates, starting from sode initial unitaries with given cost
class optSequenceGenerator
{
public:
    /// \brief Matrix type used to store found unitaries
    typedef matrix2x2<int> m;

    std::vector<m> m_generators;///< Unitaries from gate library that is used
    std::vector<int> m_cost; ///< Cost assosisated with each generator
    std::vector<m> m_initial; ///< Initial unitaries ( root(s) of BFS tree(forest) )
    std::vector<int> m_initial_cost;///< Cost of each initial element

    typedef std::priority_queue< const optNode* ,std::vector< const optNode*>,pqoptNodeCompare> pq;
    typedef std::shared_ptr<optNode> nodeptr ;
    /// \brief Type of set of all found elements
    typedef std::set< nodeptr ,optNodeCompare> nset;

    optSequenceGenerator();
    /// \brief Function that is called for all unique unitaries found.
    /// If function returns true BFS will stop
    virtual bool processMatrix( const optNode& val, int counter );
    /// \brief Runs BFS until priority queue is empty or processMatrix returns true
    void generate();
    virtual ~optSequenceGenerator();
    /// \brief Returns set of all unique elements found
    const nset& unique_elements() const;

private:
    nset m_set;///< set of all unique elements
    pq m_pq; ///< priority queue used during BFS
};

/// \brief Breadth First Search (BFS) that gathers statistics of
/// \f$ sde(|\cdot|^2) \f$ of found elements and terminates
/// when requested quantity of unitaries with given values of
/// \f$ sde(|\cdot|^2) \f$ was found.
class optSequenceGeneratorSdeLim : public optSequenceGenerator
{
public:
    /// \brief Upper bound of \f$ sde(|\cdot|^2) \f$
    static const int max_sde = 100;
    /// \brief Number of found unitaries per \f$ sde(|\cdot|^2) \f$
    std::vector<int> m_sde_found;
    /// \brief Number of requested unitaries per \f$ sde(|\cdot|^2) \f$
    std::vector<int> m_sde_required;
    /// \brief Minimal cost of found unitaries per \f$ sde(|\cdot|^2) \f$
    std::vector<int> m_min_cost;
    /// \brief Maximal cost of found unitaries per \f$ sde(|\cdot|^2) \f$
    std::vector<int> m_max_cost;

    optSequenceGeneratorSdeLim() :
        m_sde_found( max_sde ),
        m_sde_required( max_sde ),
        m_min_cost( max_sde, max_sde * 4000 ),
        m_max_cost( max_sde, -1 )
    {}

    /// \brief Updates statistics per \f$ sde(|\cdot|^2) \f$ and terminates
    /// search when all requested unitaries were found
    virtual bool processMatrix( const optNode& val, int counter );
};

#endif // OPTSEQUENCEGENERATOR_H