#ifndef PFOR_PFOR_CLUSTERS_H
#define PFOR_PFOR_CLUSTERS_H

#include "comparators.h"
#include "conditions.h"
#include "expression/algorithm.h"
#include "expression/tuple.h"
#include "expression/info.h"
#include "expression/subexpression.h"
#include "mp/pack.h"
#include "mp/tuple.h"
#include "parallelizable.h"

namespace pfor {

/**
 */
template<typename> struct ClusterExpressionIdsImpl;

template<typename I, typename W, typename R, typename... Ts>
struct ClusterExpressionIdsImpl<Pack<Pack<I, W, R>, Ts...>> {
	using type = PackPrepend<typename ClusterExpressionIdsImpl<Pack<Ts...>>::type, I>;
};

template<>
struct ClusterExpressionIdsImpl<Pack<>> {
	using type = Pack<>;
};

template<typename Cluster>
using ClusterExpressionIds = typename ClusterExpressionIdsImpl<Cluster>::type;

/**
 */
template<typename> struct ClustersExpressionIdsImpl;

template<typename Cluster, typename... Clusters>
struct ClustersExpressionIdsImpl<Pack<Cluster, Clusters...>> {
	using type = PackPrepend<typename ClustersExpressionIdsImpl<Pack<Clusters...>>::type, ClusterExpressionIds<Cluster>>;
};

template<>
struct ClustersExpressionIdsImpl<Pack<>> {
	using type = Pack<>;
};

template<typename Clusters>
using ClustersExpressionIds = typename ClustersExpressionIdsImpl<Clusters>::type;

/**
 */
template<typename Clusters, typename E, typename = Clusters, typename = Pack<E>> struct ClustersInsertImpl;

template<typename Cluster, typename... Clusters, typename E, typename IndependantClusters, typename CurrentCluster>
struct ClustersInsertImpl<Pack<Cluster, Clusters...>, E, IndependantClusters, CurrentCluster> {
	static constexpr bool depends   = clusterDepends<Cluster, E>;
	using next_clusters             = Pack<Clusters...>;
	using tmp_independant_clusters  = PackRemove<IndependantClusters, Cluster>;
	using new_independant_clusters  = If<depends, tmp_independant_clusters, IndependantClusters>;
	using tmp_current_cluster       = PackSort<ComparatorExpressionInfo, PackMerge<CurrentCluster, Cluster>>;
	using new_current_cluster       = If<depends, tmp_current_cluster, CurrentCluster>;
	using type                      = typename ClustersInsertImpl<next_clusters, E, new_independant_clusters, new_current_cluster>::type;
};

template<typename E, typename IndependantClusters, typename CurrentCluster>
struct ClustersInsertImpl<Pack<>, E, IndependantClusters, CurrentCluster> {
	using type = PackAppend<IndependantClusters, CurrentCluster>;
};

template<typename Clusters, typename E>
using ClustersInsert = typename ClustersInsertImpl<Clusters, E>::type;

/**
 */
namespace impl {

template<typename, typename> struct ClustersGenImpl;

template<typename Clusters, typename H, typename... Ts>
struct ClustersGenImpl<Clusters, Pack<H, Ts...>> {
	using tmp_out   = ClustersInsert<Clusters, H>;
	using type      = typename ClustersGenImpl<tmp_out, Pack<Ts...>>::type;
};

template<typename Clusters>
struct ClustersGenImpl<Clusters, Pack<>> {
	using type      = Clusters;
};

template<typename ExprInfo>
using ClustersGen = typename ClustersGenImpl<Pack<>, ExprInfo>::type;

}

template<typename E>
struct ClustersGen {
	using comma_splitted_expr = expr::SplitComma<E>;
	using expr_info           = expr::ExpressionInfo<comma_splitted_expr>;
	using clusters            = impl::ClustersGen<expr_info>;
	using clusters_ids        = ClustersExpressionIds<clusters>;
	using type                = PackSort<ComparatorUIntPack, clusters_ids>;
};

/**
 */
template<bool, typename, typename> struct FilterClustersImpl;

template<bool par, typename E, typename Cluster, typename... Clusters>
struct FilterClustersImpl<par, E, Pack<Cluster, Clusters...>> {
	using expr_type     = expr::ExpressionsTuple<E>;
	using tuple_type    = SubTuple<expr_type, Cluster>;
	using subexpr_type  = expr::SubExpression<tuple_type>;

	using merge_cluster = If<true ^ par ^ parallelizable<subexpr_type>, Cluster, Pack<>>;
	using next          = typename FilterClustersImpl<par, E, Pack<Clusters...>>::type;
	using type          = PackMerge<next, merge_cluster>;
};

template<bool par, typename E>
struct FilterClustersImpl<par, E, Pack<>> {
	using type = Pack<>;
};

template<bool par, typename E, typename Clusters>
using FilterClusters = typename FilterClustersImpl<par, E, Clusters>::type;

/**
 */
template<typename E, typename Clusters>
using SequentialCluster = typename FilterClustersImpl<false, E, Clusters>::type;

/**
 */
template<typename E, typename Clusters>
using ParallelCluster = typename FilterClustersImpl<true, E, Clusters>::type;

/**
 */
template<typename, typename> struct ExpressionFromClusters;

}

#endif