using System;
using System.Collections;
using System.Collections.Generic;
using AlgorithmCollection;
using UnityEngine;

// 递归与分治算法
namespace AlgorithmCollection.Recursion
{

    public static class RecursionHelper
    {
        #region 全排列，返回数据的所有组合
        public static void Permutations<T>(List<T> dataList, ref List<List<T>> perms) 
        {                                                                             
            List<List<T>> outPerms = new List<List<T>>();                            //  A B C D 
			List<T> temp = new List<T>(dataList.Count);                              //  + A (BCD)
			DNC(                                                                     //  	+ B (CD)
				() => // init                                            	         //  		+ C(D)
				{                                                                    //  			+D
					DivisionDescriptor div = new DivisionDescriptor();               //  		+ D(C)
					div.userdata = -1;                                               //  			+C
					div.left = 0;                                                    //  	+ C (BD)
					div.right = dataList.Count - 1;                                  //  		+ B(D)
					return div;                                                      //  		+ D(B)
				},                                                                   //  	+ D (BC)
				(DivisionDescriptor div, out DivisionDescriptor[] divs) => // 划分   //  		+ B(C)
				{                                                                    //  		+ C(B)
					int left = div.left; // 包含第一个元素在内的范围			         //  + B (ACD)
					int right = div.right;                                           //  + C (ABD)
					int pivot = (int)div.userdata; // 第一个元素在范围内的索引         //  + D (ABC)
					int l = left;
					if (pivot != -1)
					{
						temp.Add(dataList[pivot]);
						Algorithms.Swap(ref dataList, pivot, left);
						l = left + 1;                                        
					}
                    divs = new DivisionDescriptor[right - l + 1];       
					int j = 0;                                               
					for (int i = l; i <= right; ++i)                         
					{
                        divs[j].left = l;
                        divs[j].right = right;
                        divs[j].userdata = (int)i;
						j++;
					}
                    return l == right;
                },
				(DivisionDescriptor div) => // solve 最小子任务处理   
				{
					temp.Add(dataList[div.left]);
					List<T> newCompose = new List<T>(temp);
					outPerms.Add(newCompose);
					temp.RemoveAt(temp.Count - 1);
				},
				(DivisionDescriptor div) => //子任务后处理
				{
					int pivot = (int)div.userdata; // 第一个元素的索引
					int left = div.left;
					int right = div.right;
					Algorithms.Swap(ref dataList, pivot, left);
					temp.RemoveAt(temp.Count - 1);
				}
            );
            perms = outPerms;
        }

        // 生成器形式，每次返回一个组合
        public static IEnumerable Permutations<T>(List<T> data)
        {
            foreach (var perm in _Permutations(data, 0, data.Count - 1))
            {
                yield return perm;
            }
        }

        // 计算start~end范围内的全排列
        private static IEnumerable _Permutations<T>(List<T> data, int start, int end, List<T> perm = null)
        {
			if (perm == null)
                perm = new List<T>(data.Count);
            if (start == end)
            {
                perm.Add(data[start]);
                yield return perm;
                perm.RemoveAt(perm.Count - 1);
            }
            else
            {
                for (int i = start; i <= end; ++i)
                {
                    perm.Add(data[i]);
                    Algorithms.Swap(ref data, start, i);
                    IEnumerator itor = _Permutations(data, start + 1, end, perm).GetEnumerator();
                    while (itor.MoveNext())
                        yield return itor.Current;
                    Algorithms.Swap(ref data, start, i);
                    perm.RemoveAt(perm.Count - 1);
                }
            }
        }
        #endregion

        #region 分治

        public delegate DivisionDescriptor Init();
        public delegate void Solve(DivisionDescriptor division);
        public delegate bool Divide(DivisionDescriptor division, out DivisionDescriptor[] divs);//返回值代表是否达到最小问题阈值
        public delegate void Merge(DivisionDescriptor[] divisions);
        public delegate void Postprocess(DivisionDescriptor div);

        // 分治算法框架
        public static void DNC(Init init, Divide divide, Solve solve, Postprocess postprocess = null, Merge merge = null)
        {
            DivisionDescriptor div = init();
            _DivideAndConquer(div, solve, divide, merge, postprocess);
        }

        private static void _DivideAndConquer(DivisionDescriptor div, Solve solve, Divide divide, Merge merge, Postprocess postprocess)
        {
            DivisionDescriptor[] division;
            bool bUnit = divide(div, out division);
            if (!bUnit)
            {
                for(int i = 0; i < division.Length; ++i)
                {
                    _DivideAndConquer(division[i], solve, divide, merge, postprocess);
                    postprocess?.Invoke(division[i]);
                }
                merge?.Invoke(division);
            }
            else
            {
                for(int i = 0; i < division.Length; ++i)
                {
                    solve(division[i]);
                }
            }
        }
        #endregion

        #region 动态规划

        private static void DP()
        {

        }
        #endregion 


    }
}