//| This file is a part of the sferes2 framework.
//| Copyright 2009, ISIR / Universite Pierre et Marie Curie (UPMC)
//| Main contributor(s): Jean-Baptiste Mouret, mouret@isir.fr
//|
//| This software is a computer program whose purpose is to facilitate
//| experiments in evolutionary computation and evolutionary robotics.
//|
//| This software is governed by the CeCILL license under French law
//| and abiding by the rules of distribution of free software.  You
//| can use, modify and/ or redistribute the software under the terms
//| of the CeCILL license as circulated by CEA, CNRS and INRIA at the
//| following URL "http://www.cecill.info".
//|
//| As a counterpart to the access to the source code and rights to
//| copy, modify and redistribute granted by the license, users are
//| provided only with a limited warranty and the software's author,
//| the holder of the economic rights, and the successive licensors
//| have only limited liability.
//|
//| In this respect, the user's attention is drawn to the risks
//| associated with loading, using, modifying and/or developing or
//| reproducing the software by the user in light of its specific
//| status of free software, that may mean that it is complicated to
//| manipulate, and that also therefore means that it is reserved for
//| developers and experienced professionals having in-depth computer
//| knowledge. Users are therefore encouraged to load and test the
//| software's suitability as regards their requirements in conditions
//| enabling the security of their systems and/or data to be ensured
//| and, more generally, to use and operate it in the same conditions
//| as regards security.
//|
//| The fact that you are presently reading this means that you have
//| had knowledge of the CeCILL license and that you accept its terms.


#ifndef _NN_HPP_
#define _NN_HPP_

#include <iostream>
#include <fstream>
#include <utility>
#include <algorithm>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>

//#pragma GCC diagnostic push
#ifdef __GNUC__
#if __GNUC__ >= 4 && __GNUC_MINOR__ >= 6
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
#endif

#include <boost/graph/adjacency_list.hpp>

#ifdef __GNUC__
#if __GNUC__ >= 4 && __GNUC_MINOR__ >= 6
#pragma GCC diagnostic pop
#endif
#endif
//#pragma GCC diagnostic pop

#include <boost/graph/graphviz.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/foreach.hpp>

#include <boost/tuple/tuple.hpp>
#include <boost/lexical_cast.hpp>

#include <boost/mpl/assert.hpp>
#include <sferes/dbg/dbg.hpp>

#include <cmath>
#include <valarray>

#include "pf.hpp"
#include "af.hpp"
#include "neuron.hpp"
#include "connection.hpp"

namespace nn
{
// a useful boost functor
template<typename V>
class bfs_pred_visitor : public boost::default_bfs_visitor
{
public:
	bfs_pred_visitor(std::set<V>& pred) : _pred(pred) {}

	template <typename Vertex, typename Graph >
	void discover_vertex(Vertex u, const Graph & g)
	{
		_pred.insert(u);
	}
protected:
	std::set<V>& _pred;
};


// main class
// N : neuron type, C : connection type
template<typename N, typename C>
class NN
{
public:
	// types
	typedef boost::adjacency_list<boost::listS, boost::listS,
			boost::bidirectionalS,
			N, C> graph_t;
	typedef typename boost::graph_traits<graph_t>::vertex_iterator vertex_it_t;
	typedef typename boost::graph_traits<graph_t>::edge_iterator edge_it_t;
	typedef typename boost::graph_traits<graph_t>::out_edge_iterator out_edge_it_t;
	typedef typename boost::graph_traits<graph_t>::in_edge_iterator in_edge_it_t;
	typedef typename boost::graph_traits<graph_t>::edge_descriptor edge_desc_t;
	typedef typename boost::graph_traits<graph_t>::vertex_descriptor vertex_desc_t;
	typedef typename boost::graph_traits<graph_t>::adjacency_iterator adj_it_t;
	typedef typename std::vector<vertex_desc_t> vertex_list_t;
	typedef N neuron_t;
	typedef C conn_t;
	typedef typename N::af_t af_t;
	typedef typename N::pf_t pf_t;
	typedef typename C::weight_t weight_t;
	typedef typename C::io_t io_t;


	// constructor
	NN() : _neuron_counter(0), _init_done(false)
	{}
	NN(const NN& o) { *this = o; }

	NN& operator=(const NN& o)
	{
		if (&o == this)
			return *this;
		_g = o._g;
		_neuron_counter = o._neuron_counter;
		_inputs.clear();
		_outputs.clear();
		_inputs.resize(o.get_nb_inputs());
		_outputs.resize(o.get_nb_outputs());
		_init_io();
		_init_done = false;
		return *this;
	}
	// init
	void init() { _init(); }

	// set id for inputs and outputs
	void name_io() { _name_io(); }
	// load/write
	//void load(const std::string& fname) { _load_graph(fname); }
	//    void write(const std::string& fname) { _write_graph(fname); }
	void write(std::ostream& ofs) { _write_dot(ofs); }
	void dump(std::ostream& ofs) const
	{
		std::pair<vertex_it_t, vertex_it_t> vp;
		for (vp = boost::vertices(_g); vp.first != vp.second; ++vp.first)
			ofs<<_g[*vp.first]._id<<" "<<_g[*vp.first].get_next_output()<<" ";
		ofs<<std::endl;
	}

	// get the graph for graph algorithms
	const graph_t& get_graph() const { return _g; }
	graph_t& get_graph() { return _g; }

	// construction
	vertex_desc_t add_neuron(const std::string& label)
	{
		vertex_desc_t v = add_vertex(_g);
		_g[v]._id = boost::lexical_cast<std::string>(_neuron_counter++);
		_g[v]._label = label;
		return v;
	}

	vertex_desc_t add_neuron(const std::string& label,
			const typename pf_t::params_t& pf_params,
			const typename af_t::params_t& af_params)
	{
		vertex_desc_t v = add_neuron(label);
		_g[v].set_pfparams(pf_params);
		_g[v].set_afparams(af_params);
		return v;
	}

	bool add_connection(const vertex_desc_t& u,
			const vertex_desc_t& v,
			weight_t weight)
	{
		std::pair<edge_desc_t, bool> e = add_edge(u, v, _g);
		if (e.second)
			_g[e.first].set_weight(weight);
		return e.second;
	}

	// special version when you need to increase weight
	bool add_connection_w(const vertex_desc_t& u,
			const vertex_desc_t& v,
			weight_t weight)
	{
		std::pair<edge_desc_t, bool> e = add_edge(u, v, _g);
		if (e.second)
			_g[e.first].set_weight(weight);
		else
			_g[e.first].set_weight(_g[e.first].get_weight() + weight);
		return e.second;
	}

	bool vertex_is_member(const vertex_desc_t& u){
		BGL_FORALL_VERTICES_T(v, _g, graph_t){
			if(v == u) return true;
		}
		return false;
	}

	void set_all_pfparams(const std::vector<typename pf_t::params_t>& pfs)
	{
		assert(num_vertices(_g) == pfs.size());
		size_t k = 0;
		BGL_FORALL_VERTICES_T(v, _g, graph_t)
		_g[v].set_pfparamst(pfs[k++]);
	}

	void set_all_afparams(const std::vector<typename af_t::params_t>& afs)
	{
		assert(num_vertices(_g) == afs.size());
		size_t k = 0;
		BGL_FORALL_VERTICES_T(v, _g, graph_t)
		_g[v].set_afparamst(afs[k++]);
	}

	void set_all_weights(const std::vector<weight_t>& ws)
	{
#ifndef NDEBUG
		if (num_edges(_g) != ws.size())
			std::cout << "param errors: "
			<< num_edges(_g)
			<< " whereas "
			<< ws.size()
			<< " provided" <<std::endl;
#endif
		assert(num_edges(_g) == ws.size());
		size_t k = 0;
		BGL_FORALL_EDGES_T(e, _g, graph_t)
		_g[e].set_weight(ws[k++]);
	}

	void set_nb_inputs(unsigned i)
	{
		_inputs.resize(i);
		unsigned int k = 0;
		BOOST_FOREACH(vertex_desc_t& v, _inputs)
		{
			v = add_vertex(_g);
			this->_g[v].set_in(k);
			this->_g[v]._id = "i" + boost::lexical_cast<std::string>(k);
			k++;
		}
	}

    void set_nb_hidden(unsigned i){
        for(unsigned k=0; k<i; ++k){
            add_neuron(boost::lexical_cast<std::string>(k));
        }
    }

	void set_nb_outputs(unsigned i)
	{
		_outputs.resize(i);
		unsigned int k = 0;
		BOOST_FOREACH(vertex_desc_t& v, _outputs)
		{
			v = add_vertex(_g);
			this->_g[v].set_out(k);
			this->_g[v]._id = "o" + boost::lexical_cast<std::string>(k);
			k++;
		}
	}
	vertex_desc_t get_input(int i) const
	{
		assert((size_t)i < _inputs.size());
		assert(this->_g[_inputs[i]].get_in() != -1);
		return _inputs[i];
	}
	const std::vector<vertex_desc_t>& get_inputs() const { return _inputs; }
	const std::vector<vertex_desc_t>& get_outputs() const { return _outputs; }

	// warning : O(n)
	vertex_desc_t get_neuron(size_t i) const
	{
		i = std::min(num_vertices(_g) - 1, i);
		size_t k = 0;
		BGL_FORALL_VERTICES_T(v, _g, graph_t)
		if (k++ == i)
			return v;
		assert(0);
		return (vertex_desc_t)(0x0);;
	}

	vertex_list_t get_neuron_list()
	{
		vertex_list_t neuron_list;
		std::pair<vertex_it_t, vertex_it_t> vp;
		for (vp = boost::vertices(_g); vp.first != vp.second; ++vp.first)
		{
			neuron_list.push_back(vertex_desc_t(*vp.first));
		}
		return neuron_list;
	}

	neuron_t& get_neuron_by_vertex(vertex_desc_t v)
	{
		return this->_g[v];
	}
	io_t get_neuron_output(size_t i) const
	{
		return _g[get_neuron(i)].get_current_output();
	}

	std::string get_neuron_id(size_t i) const
	{
		return _g[get_neuron(i)]._id;
	}
	vertex_desc_t get_output(int i) const
	{
	    dbg::assertion(DBG_ASSERTION((size_t) i < _outputs.size()));
	    dbg::assertion(DBG_ASSERTION(this->_g[_outputs[i]].get_out() != -1));
//		assert((size_t) i < _outputs.size());
//		assert(this->_g[_outputs[i]].get_out() != -1);
		return _outputs[i];
	}
	const N& get_output_neuron(int i) const
	{
		return _g[_outputs[i]];
	}
	bool is_output(const vertex_desc_t& v) const
	{
		return std::find(_outputs.begin(), _outputs.end(), v) != _outputs.end();
	}
	bool is_input(const vertex_desc_t& v) const
	{
		return std::find(_inputs.begin(), _inputs.end(), v) != _inputs.end();
	}

	// step
	void step(const std::vector<io_t>& inputs) { _step(inputs); }

	// accessors
	const std::vector<io_t>& get_outf() const { return _outf; }
	io_t get_outf(unsigned i) const {
		//		            if(_outf[i] < -1.0 || _outf[i] > 1.0){
			//		              std::cout << __FILE__ << " at line " << __LINE__ << std::endl;
		//		          	  std::cout << "out: " << _outf[i] << std::endl;
		//		          	  std::cout << " i: " << i << std::endl;
		//		            }
		return _outf[i];
	}
	const std::vector<io_t>& outf() const { return get_outf(); }
	io_t outf(unsigned i) const { return get_outf(i); }
	unsigned get_nb_inputs() const { return _inputs.size(); }
	unsigned get_nb_outputs() const { return _outputs.size(); }
	unsigned get_nb_connections() const { return num_edges(_g); }
	unsigned get_nb_neurons() const { return num_vertices(_g); }

	// subnns
	void remove_subnn(const std::set<vertex_desc_t>& subnn)
	{
		BOOST_FOREACH(vertex_desc_t v, subnn)
        				  if (!is_input(v) && !is_output(v))
        				  {
        					  clear_vertex(v, _g);
        					  remove_vertex(v, _g);
        				  }
		_init_io();
	}

	template<typename NN>
	void add_subnn(const NN& nn,
			const std::vector<size_t>& inputs,
			const std::vector<size_t>& outputs)
	{
		assert(inputs.size() == nn.get_nb_inputs());
		assert(outputs.size() == nn.get_nb_outputs());
		std::map<typename NN::vertex_desc_t, vertex_desc_t> rmap;
		const typename NN::graph_t& g_src = nn.get_graph();
		BGL_FORALL_VERTICES_T(v, g_src, typename NN::graph_t)
		if (g_src[v].get_in() == -1 && g_src[v].get_out() == -1)
		{
			vertex_desc_t nv = add_vertex(_g);
			_g[nv] = g_src[v];
			_g[nv]._id = boost::lexical_cast<std::string>(_neuron_counter++);
			rmap[v] = nv;
		}

		std::vector<vertex_desc_t> vnodes;
		// hoping that the order did not change too much
		BGL_FORALL_VERTICES_T(v, _g, graph_t)
		vnodes.push_back(v);

		BGL_FORALL_EDGES_T(e, g_src, typename NN::graph_t)
		{
			std::pair<edge_desc_t, bool> ne;
			int in  = g_src[source(e, g_src)].get_in();
			int out = g_src[target(e, g_src)].get_out();
			assert(in == -1 || in < inputs.size());
			assert(out == -1 || out < outputs.size());
			if (in != -1 && out != -1)
			{
				int n_in = std::min(vnodes.size() - 1, inputs[in]);
				int n_out = std::min(vnodes.size() - 1, outputs[out]);
				ne = add_edge(vnodes[n_in], vnodes[n_out], _g);
			}
			else if (in != -1)
			{
				int n_in = std::min(vnodes.size() - 1, inputs[in]);
				ne = add_edge(vnodes[n_in], rmap[target(e, g_src)], _g);
			}
			else if (out != -1)
			{
				int n_out = std::min(vnodes.size() - 1, outputs[out]);
				ne = add_edge(rmap[source(e, g_src)], vnodes[n_out], _g);
			}
			else
			{
				assert(rmap.find(source(e, g_src)) != rmap.end());
				assert(rmap.find(target(e, g_src)) != rmap.end());
				ne = add_edge(rmap[source(e, g_src)], rmap[target(e, g_src)], _g);
			}
			_g[ne.first] = g_src[e];
		}

		_init_io();
	}

	// remove neurons that are not connected to both one input and
	// one output (this is NOT callled automatically in NN
	//
	// WARNING: if simplify_in is true, this can change the behavior
	// of neurons since neurons not connected to inputs but connected
	// to outputs can output a constant value
	//
	// principle : keep the neurons that are successors of inputs
	// and predecessors of outputs
	void simplify(bool simplify_in = false)
	{
		// we need sets and not lists without io
		std::set<vertex_desc_t> all_neurons;
		BGL_FORALL_VERTICES_T(v, this->_g, graph_t)
		if (!is_input(v) && !is_output(v))
			all_neurons.insert(v);
		std::set<vertex_desc_t> out_preds, in_succs;

		// out
		BOOST_FOREACH(vertex_desc_t v, this->_outputs)
		{
			std::set<vertex_desc_t> preds;
			nn::bfs_pred_visitor<vertex_desc_t> vis(preds);
			breadth_first_search(boost::make_reverse_graph(_g),
					v, color_map(get(&N::_color, _g)).visitor(vis));
			out_preds.insert(preds.begin(), preds.end());
		}
		// in
		if (simplify_in)
			BOOST_FOREACH(vertex_desc_t v, this->_inputs)
			{
			std::set<vertex_desc_t> succs;
			nn::bfs_pred_visitor<vertex_desc_t> vis(succs);
			breadth_first_search(_g,
					v, color_map(get(&N::_color, _g)).visitor(vis));
			in_succs.insert(succs.begin(), succs.end());
			}
		else
			in_succs = all_neurons;
		// make the intersection of in_succ and out_preds
		std::set<vertex_desc_t> valid_neurons;
		std::set_intersection(in_succs.begin(), in_succs.end(),
				out_preds.begin(), out_preds.end(),
				std::insert_iterator<std::set<vertex_desc_t> >(valid_neurons,
						valid_neurons.begin()));

		// get the list of neurons that are NOT in valid_neurons
		std::set<vertex_desc_t> to_remove;
		std::set_difference(all_neurons.begin(), all_neurons.end(),
				valid_neurons.begin(), valid_neurons.end(),
				std::insert_iterator<std::set<vertex_desc_t> >(to_remove,
						to_remove.begin()));
		// remove these neurons
		BOOST_FOREACH(vertex_desc_t v, to_remove)
		{
			clear_vertex(v, _g);
			remove_vertex(v, _g);
		}
	}

	// fully connect two vectors of neurons
	void full_connect(const std::vector<vertex_desc_t> v1,
			const std::vector<vertex_desc_t> v2,
			const weight_t& w)
	{
		BOOST_FOREACH(vertex_desc_t x, v1)
        				  BOOST_FOREACH(vertex_desc_t y, v2)
        				  this->add_connection(x, y, w);
	}

	// 1 to 1 connection
	void connect(const std::vector<vertex_desc_t> v1,
			const std::vector<vertex_desc_t> v2,
			const weight_t& w)
	{
		assert(v1.size() == v2.size());
		for (size_t i = 0; i < v1.size(); ++i)
			this->add_connection(v1[i], v2[i], w);
	}
protected:
	// attributes
	graph_t _g;
	vertex_list_t _inputs;
	vertex_list_t _outputs;
	std::vector<io_t> _outf;
	int _neuron_counter;
	bool _init_done;

	// methods
	void _write_dot(std::ostream& ofs)
	{
		ofs << "digraph G {" << std::endl;
		BGL_FORALL_VERTICES_T(v, this->_g, graph_t)
		{
			ofs << this->_g[v].get_id();
			ofs << " [label=\""<<this->_g[v].get_id()<<"\"";
			// ofs << " af"<< this->_g[v].get_afparams();
			// ofs << "| pf"<< this->_g[v].get_pfparams() <<"\"";
			if (is_input(v) || is_output(v))
				ofs<<" shape=doublecircle";

			ofs <<"]"<< std::endl;
		}
		BGL_FORALL_EDGES_T(e, this->_g, graph_t)
		{
			ofs << this->_g[source(e, this->_g)].get_id()
            				<< " -> " << this->_g[target(e, this->_g)].get_id()
            				<< "[label=\"" << _g[e].get_weight() << "\"]" << std::endl;
		}
		ofs << "}" << std::endl;
	}

	void _activate(vertex_desc_t n)
	{
		using namespace boost;
		if (_g[n].get_fixed()) return;

		in_edge_it_t in, in_end;
		unsigned i = 0;
		for (tie(in, in_end) = in_edges(n, _g); in != in_end; ++in, ++i)
			_g[n].set_input(i, _g[source(*in, _g)].get_current_output());

		_g[n].activate();
	}

	void _set_in(const std::vector<io_t>& inf)
	{
		assert(inf.size() == _inputs.size());
		if (inf.size()>0) {
			unsigned i = 0;
			for (typename vertex_list_t::const_iterator it = _inputs.begin();
					it != _inputs.end(); ++it, ++i)
			{
				//        	 std::cout << "Input " << i << " : " << inf[i] << std::endl;
				_g[*it].set_current_output(inf[i]);
				_g[*it].set_next_output(inf[i]);
			}
		}
	}

	void _set_out()
	{
		unsigned i = 0;
		for (typename vertex_list_t::const_iterator it = _outputs.begin();
				it != _outputs.end(); ++it, ++i){
			//        	 std::cout << "Output " << i << " : " << _g[*it].get_current_output() << std::endl;
			//        	 std::cout << "Vector size " << _outf.size() << std::endl;
			_outf[i] = _g[*it].get_current_output();
			float out = nn::trait<io_t>::single_value(_outf[i]);

#ifdef JHDEBUG
			if (std::isnan(_outf[i])){
			    std::cerr << "********* Warning: out in nn is nan *********" <<std::endl;
			    std::cerr << "********* Result: " << _outf[i] << "*********" << std::endl;
			}
#endif

			//    		            if(out < -1.0 || out > 1.0){
			//    		          	  std::cout << "out: " << _outf[i] << " i: " << i << std::endl;
			//    		          	  std::cout << "it: " << it << " i: " << i << " out begin: " << _outputs.begin() << " out end: " << _outputs.end() << std::endl;
			//    		          	  std::cout << " vert begin: " << boost::vertices(_g).first << " vert end: " << boost::vertices(_g).second << std::endl;
			//    		            }
		}
	}

	void _step(const std::vector<io_t>& inf)
	{
		assert(_init_done);
		// in
		_set_in(inf);

		// activate
		std::pair<vertex_it_t, vertex_it_t> vp;
		for (vp = boost::vertices(_g); vp.first != vp.second; ++vp.first)
			_activate(*vp.first);

		// step
		for (vp = boost::vertices(_g); vp.first != vp.second; ++vp.first)
			_g[*vp.first].step();

		// out
		_set_out();
	}

	void _name_io()
	{
		int i=0;
		BOOST_FOREACH(vertex_desc_t v, _inputs)
		{
			_g[v]._id = std::string("i") + boost::lexical_cast<std::string>(i);
			++i;
		}
		i = 0;
		BOOST_FOREACH(vertex_desc_t v, _outputs) {
			_g[v]._id = std::string("o") + boost::lexical_cast<std::string>(i);
			++i;
		}
	}
	void _init()
	{
		//      BOOST_MPL_ASSERT((boost::mpl::is_same<N::weight_t, C::weight_t>));
		// BOOST_MPL_ASSERT((boost::mpl::is_same<Pot::weight_t, C::weight_t>));
		_outf.clear();
		in_edge_it_t in, in_end;
		std::pair<vertex_it_t, vertex_it_t> vp;
		for (vp = boost::vertices(_g); vp.first != vp.second; ++vp.first)
		{
			vertex_desc_t n = *vp.first;
			_g[n].set_in_degree(in_degree(n, _g));
			unsigned i = 0;
			for (tie(in, in_end) = in_edges(n, _g); in != in_end; ++in, ++i)
				_g[n].set_weight(i, _g[*in].get_weight());
		}
		_outf.resize(_outputs.size());
		BOOST_FOREACH(vertex_desc_t v, _inputs)
		{
			_g[v].set_fixed();
			_g[v].set_current_output(N::zero());
		}
		// init to 0
		for (vp = boost::vertices(_g); vp.first != vp.second; ++vp.first)
			_g[*vp.first].init();
		_init_io();
		_name_io();
		_init_done = true;
	}
	void _init_io()
	{
		BGL_FORALL_VERTICES_T(v, _g, graph_t)
					{
			if (_g[v].get_in() != -1)
			{
				assert(_g[v].get_in() < (int)_inputs.size());
				_inputs[_g[v].get_in()] = v;
			}
			if (_g[v].get_out() != -1)
			{
				assert(_g[v].get_out() < (int)_outputs.size());
				_outputs[_g[v].get_out()] = v;
			}
					}
	}
};
}

#endif



