///////////////////////////////////////////////////////////////////////////////
// k_nearest_neighbor.hpp
//
//  Copyright 2005 Hirotaka Niitsuma. Distributed under the Boost
//  Software License, Version 1.0. (See accompanying file
//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_ACCUMULATORS_STATISTICS_K_NEAREST_NEIGHBOR_HPP_DE_01_01_2007
#define BOOST_ACCUMULATORS_STATISTICS_K_NEAREST_NEIGHBOR_HPP_DE_01_01_2007

#include <vector>

#include <queue>

#include <limits>
#include <numeric>
#include <functional>
#include <complex>
#include <boost/tuple/tuple.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/range.hpp>
#include <boost/parameter/keyword.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/lambda/lambda.hpp>

#include <boost/type_traits/is_scalar.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/accumulators/framework/accumulator_base.hpp>
#include <boost/accumulators/framework/extractor.hpp>
#include <boost/numeric/functional.hpp>
#include <boost/accumulators/framework/parameters/sample.hpp>
#include <boost/accumulators/statistics_fwd.hpp>
#include <boost/accumulators/statistics/count.hpp>


namespace boost { namespace accumulators
{
///////////////////////////////////////////////////////////////////////////////
// num_cells named parameter
//
BOOST_PARAMETER_NESTED_KEYWORD(tag, k_nearest_neighbor_distance, distance_obj)
BOOST_PARAMETER_NESTED_KEYWORD(tag, k_nearest_neighbor_target, target)
BOOST_PARAMETER_NESTED_KEYWORD(tag, k_nearest_neighbor_k, k_nearest)

namespace impl
{
    ///////////////////////////////////////////////////////////////////////////////
    // k_nearest_neighbor_impl
    //  

    template<typename Sample>
    struct k_nearest_neighbor_impl
      : accumulator_base
    {
		
        typedef typename numeric::functional::average<Sample, std::size_t>::result_type float_type;
		typedef double distance_type;

		typedef std::vector<float_type> array_type;		
		typedef iterator_range<typename array_type::iterator>  array_range_type;

		typedef std::pair<distance_type, typename array_type::iterator> dist_it_type;

		struct data_comparison{
			bool operator () ( dist_it_type  &left, dist_it_type &right){				
				return left.first < right.first; 
			}
		};

		
		typedef std::priority_queue< dist_it_type , mutable std::vector<dist_it_type > , data_comparison > dist_it_queue_type;
			//can not access iterator of priority_queue. Thus we can not use priority_queue as result like 
			//typedef iterator_range<typename dist_it_array_type::container_type::iterator> dist_it_array_range_type;

		typedef std::vector< dist_it_type > dist_it_array_type;
		typedef iterator_range<typename dist_it_array_type::iterator> dist_it_array_range_type;



		typedef std::pair< dist_it_array_range_type , array_range_type > result_type;
		

        template<typename Args>
        k_nearest_neighbor_impl(Args const &args)
          : 
			training_data_list(),dist_it_array()
			, distance_obj(args[k_nearest_neighbor_distance])
        {}
        
        template<typename Args>
        void operator ()(Args const &args)
        {
			training_data_list.push_back(args[sample]);
			
			
        }

        template<typename Args>
        result_type result(Args const &args) const
        {
			
			this->k_nearest=args[k_nearest_neighbor_k];
			this->dist_it_array.resize(this->k_nearest);			
			target=args[k_nearest_neighbor_target];


			dist_it_queue_type data_priority_queue;

			array_type::iterator it = training_data_list.begin();

			for(it	; it!= training_data_list.end() ; it++  )
			{
				distance_type dist =distance_obj(*it, target );
				dist_it_type a_datapair(dist,it);
				data_priority_queue.push(a_datapair );	
				if(data_priority_queue.size() > this->k_nearest  )
				{
					data_priority_queue.pop();
				}
			}	

			//copy priority_queue to vector
			for(int j=this->k_nearest-1 ; j>=0 ; j-- ){
				this->dist_it_array[j]=data_priority_queue.top();
				data_priority_queue.pop();		
			}
	
			return std::make_pair(make_iterator_range(this->dist_it_array) , make_iterator_range(this->training_data_list)) ;
			
        }

    private:
		mutable int k_nearest;
		mutable float_type target;

		mutable  array_type training_data_list;
		mutable  dist_it_array_type dist_it_array;
		
		boost::function2<distance_type, float_type, float_type> distance_obj;
    };

} // namespace detail

///////////////////////////////////////////////////////////////////////////////
// tag::k_nearest_neighbor
//
namespace tag
{
	
    struct k_nearest_neighbor
      : depends_on<count>
    {
        /// INTERNAL ONLY
        typedef accumulators::impl::k_nearest_neighbor_impl<mpl::_1> impl;
    };

}

///////////////////////////////////////////////////////////////////////////////
// extract::k_nearest_neighbor
//
namespace extract
{
    extractor<tag::k_nearest_neighbor> const k_nearest_neighbor = {};

}

using extract::k_nearest_neighbor;


}} // namespace boost::accumulators

#endif