//===========================================================================
/*!
 * 
 *
 * \brief       Fast lookup for elements in constant datasets
 * 
 * 
 * 
 * 
 *
 * \author      O. Krause
 * \date        2012
 *
 *
 * \par Copyright 1995-2017 Shark Development Team
 * 
 * <BR><HR>
 * This file is part of Shark.
 * <http://shark-ml.org/>
 * 
 * Shark 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.
 * 
 * Shark 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 Shark.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
//===========================================================================


#ifndef SHARK_DATA_DATAVIEW_H
#define SHARK_DATA_DATAVIEW_H

#include <shark/Data/Dataset.h>
#include <shark/Core/utility/functional.h>
#include <numeric>
namespace shark {
/// \brief Constant time Element-Lookup for Datasets
///
/// Datasets are fast for random lookup of batches. Since batch sizes can be arbitrary structured and
/// changed by the user, there is no way for the Data and LabeledData classes to provide fast random access
/// to single elements. Still, this property is needed quite often, for example for creating subsets,
/// randomize data or tree structures. 
/// A View stores the position of every element in a dataset. So it has constant time access to the elements but
/// it also requires linear memory in the number of elements in the set. This is typically small compared
/// to the size of the set itself, but construction imposes an considerable overhead.
///
/// In contrast to (Un)LabeledData, which is centered around batches, the View is centered around single elements,
/// so its iterators iterate over the elements.
/// For a better support for bagging an index method is added which returns the position of the element in the
/// underlying data container. Also the iterators are indexed and return this index.
template <class DatasetType>   //template parameter can be const!
class DataView
{
public:
	typedef typename std::remove_const<DatasetType>::type dataset_type;   //(non const) type of the underlying dataset
	typedef typename dataset_type::element_type value_type;
	typedef typename dataset_type::const_element_reference const_reference;
	typedef typename dataset_type::batch_type batch_type;
	// We want to support immutable as well as mutable datasets. So we query whether the dataset
	// is mutable and change the reference type to const if the dataset is immutable.
	typedef typename boost::mpl::if_<
		std::is_const<DatasetType>,
		typename dataset_type::const_element_reference,
		typename dataset_type::element_reference
	>::type reference;

private:
	typedef typename boost::mpl::if_<
		std::is_const<DatasetType>,
		typename dataset_type::const_batch_range,
		typename dataset_type::batch_range
	>::type batch_range;
	template<class Reference, class View>
	class IteratorBase: public SHARK_ITERATOR_FACADE<
		IteratorBase<Reference,View>,
		value_type,
		std::random_access_iterator_tag,
		Reference
	>{
	public:
		IteratorBase(){}
	
		IteratorBase(View& view, std::size_t position)
		: mpe_view(&view),m_position(position) {}
	
		template<class R,class V>
		IteratorBase(IteratorBase<R,V> const& other)
		: mpe_view(other.mpe_view),m_position(other.position){}
		
		/// \brief returns the position of the element referenced by the iterator inside the dataset
		///
		/// This is usefull for bagging, when identical elements between several susbsets are to be identified
		std::size_t index()const{
			return mpe_view->index(m_position);
		}

	private:
		friend class SHARK_ITERATOR_CORE_ACCESS;
		template <class, class> friend class IteratorBase;

		void increment() {
			++m_position;
		}
		void decrement() {
			--m_position;
		}

		void advance(std::ptrdiff_t n){
			m_position+=n;
		}
	
		template<class R,class V>
		std::ptrdiff_t distance_to(IteratorBase<R,V> const& other) const{
			return (std::ptrdiff_t)other.m_position - (std::ptrdiff_t)m_position;
		}
	
		template<class R,class V>
		bool equal(IteratorBase<R,V> const& other) const{
			return m_position == other.m_position;
		}
		Reference dereference() const { 
			return (*mpe_view)[m_position];
		}

		View* mpe_view;
		std::size_t m_position;
	};
public:
	typedef IteratorBase<reference,DataView<DatasetType> > iterator;
	typedef IteratorBase<const_reference, DataView<DatasetType> const > const_iterator;

	DataView(){}
	DataView(DatasetType& dataset)
	:m_dataset(dataset),m_indices(dataset.numberOfElements())
	{
		std::size_t index = 0;
		for(std::size_t i = 0; i != dataset.numberOfBatches(); ++i){
			std::size_t batchSize = Batch<value_type>::size(dataset.batch(i));
			for(std::size_t j = 0; j != batchSize; ++j,++index){
				m_indices[index].batch = i;
				m_indices[index].positionInBatch = j;
				m_indices[index].datasetIndex = index;
			}
		}
	}

	/// create a subset of the dataset type using only the elemnt indexed by indices
	template<class IndexRange>
	DataView(DataView<DatasetType> const& view, IndexRange const& indices)
	:m_dataset(view.m_dataset),m_indices(indices.size())
	{
		for(std::size_t i = 0; i != m_indices.size(); ++i)
			m_indices[i] = view.m_indices[indices[i]];
	}

	reference operator[](std::size_t position){
		SIZE_CHECK(position < size());
		Index const& index = m_indices[position];
		return getBatchElement(m_dataset.batch(index.batch),index.positionInBatch);
	}
	const_reference operator[](std::size_t position) const{
		SIZE_CHECK(position < size());
		Index const& index = m_indices[position];
		return getBatchElement(m_dataset.batch(index.batch),index.positionInBatch);
	}
	
	reference front(){
		SIZE_CHECK(size() != 0);
		return (*this)[0];
	}
	const_reference front()const{
		SIZE_CHECK(size() != 0);
		return (*this)[0];
	}
	reference back(){
		SIZE_CHECK(size() != 0);
		return (*this)[size()-1];
	}
	const_reference back()const{
		SIZE_CHECK(size() != 0);
		return (*this)[size()-1];
	}

	/// \brief Position of the element in the dataset.
	///
	/// This is useful for bagging, when identical elements among
	/// several subsets are to be identified.
	std::size_t index(std::size_t position)const{
		return m_indices[position].datasetIndex;
	}

	/// \brief Index of the batch holding the element.
	std::size_t batch(std::size_t position) const {
		return m_indices[position].batch;
	}

	/// \brief Index inside the batch holding the element.
	std::size_t positionInBatch(std::size_t position) const {
		return m_indices[position].positionInBatch;
	}

	std::size_t size() const{
		return m_indices.size();
	}

	iterator begin(){
		return iterator(*this, 0);
	}
	const_iterator begin() const{
		return const_iterator(*this, 0);
	}
	iterator end(){
		return iterator(*this, size());
	}
	const_iterator end() const{
		return const_iterator(*this, size());
	}
	
	dataset_type const& dataset()const{
		return m_dataset;
	}
private:
	dataset_type m_dataset;
	// Stores for an element of the dataset, at which position of which batch it is located
	// as well as the real index of the element inside the dataset
	struct Index{
		std::size_t batch;//the batch in which the element is located
		std::size_t positionInBatch;//at which position in the batch it is
		std::size_t datasetIndex;//index inside the dataset
	};
	std::vector<Index> m_indices;//stores for every element of the set it's position inside the dataset
};

/// \brief creates a subset of a DataView with elements indexed by indices
///
/// \param view the view for which the subset is to be created
/// \param indizes the index of the elements to be stored in the view 
template<class DatasetType,class IndexRange>
DataView<DatasetType> subset(DataView<DatasetType> const& view, IndexRange const& indizes){
	//O.K. todo: Remove constructor later on, this is a quick fix.
	return DataView<DatasetType>(view,indizes);
}

/// \brief creates a random subset of a DataView with given size
///
/// \param view the view for which the subset is to be created
/// \param size the size of the subset
template<class DatasetType>
DataView<DatasetType> randomSubset(DataView<DatasetType> const& view, std::size_t size){
	std::vector<std::size_t> indices(view.size());
	std::iota(indices.begin(),indices.end(),0);
	partial_shuffle(indices.begin(),indices.begin()+size,indices.end());
	return subset(view,boost::make_iterator_range(indices.begin(),indices.begin()+size));
}

/// \brief Creates a batch given a set of indices
///
/// \param view the view from which the batch is to be created
/// \param indizes the set of indizes defining the batch
template<class DatasetType,class IndexRange>
typename DataView<DatasetType>::batch_type subBatch(
	DataView<DatasetType> const& view, 
	IndexRange const& indizes
){
	//create a subset of the view containing the elements of the batch
	DataView<DatasetType> batchElems = subset(view,indizes);
	
	//and now use the batch range construction to create it
	return createBatch(batchElems);
}

/// \brief Creates a random batch of a given size
///
/// \param view the view from which the batch is to be created
/// \param size the size of the batch
template<class DatasetType>
typename DataView<DatasetType>::batch_type randomSubBatch(
	DataView<DatasetType> const& view, 
	std::size_t size
){
	std::vector<std::size_t> indices(view.size());
	std::iota(indices.begin(),indices.end(),0);
	partial_shuffle(indices.begin(),indices.begin()+size,indices.end());
	return subBatch(view,boost::make_iterator_range(indices.begin(),indices.begin()+size));
}

/// \brief Creates a View from a dataset.
///
/// This is just a helper function to omit the actual type of the view
///
/// \param set the dataset from which to create the view
template<class DatasetType>
DataView<DatasetType>  toView(DatasetType& set){
	return DataView<DatasetType>(set);
}

/// \brief Creates a new dataset from a View.
///
/// When the elements of a View needs to be processed repeatedly it is often better to use
/// the packed format of the Dataset again, since then the faster batch processing can be used
///
/// \param view the view from which to create the new dataset
/// \param batchSize the size of the batches in the dataset
template<class T>
typename DataView<T>::dataset_type 
toDataset(DataView<T> const& view, std::size_t batchSize = DataView<T>::dataset_type::DefaultBatchSize){
	if(view.size() == 0)
		return typename DataView<T>::dataset_type();
	//O.K. todo: this is slow for sparse elements, use subBatch or something similar.
	std::size_t elements = view.size();
	typename DataView<T>::dataset_type dataset(elements,view[0],batchSize);
	std::copy(view.begin(),view.end(),dataset.elements().begin());
	return dataset;
}

/// Return the number of classes (size of the label vector)
/// of a classification dataset with RealVector label encoding.
template <class DatasetType>
std::size_t numberOfClasses(DataView<DatasetType> const& view){
	return numberOfClasses(view.dataset());
}

/// Return the input dimensionality of the labeled dataset represented by the view
template <class DatasetType>
std::size_t inputDimension(DataView<DatasetType> const& view){
	return inputDimension(view.dataset());
}
/// Return the label dimensionality of the labeled dataset represented by the view
template <class DatasetType>
std::size_t labelDimension(DataView<DatasetType> const& view){
	return labelDimension(view.dataset());
}

/// Return the dimensionality of the dataset represented by the view
template <class DatasetType>
std::size_t dataDimension(DataView<DatasetType> const& view){
	return dataDimension(view.dataset());
}


/** @*/
}
#endif