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)
            DivideAndConquer(                                            //  	+ 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) => // adhoc 最小子任务处理       //  		+ B(C)
                {                                                        //  		+ C(B)
                    temp.Add(dataList[div.left]);                        //  + B (ACD)
                    List<T> newCompose = new List<T>(temp);              //  + C (ABD)
                    outPerms.Add(newCompose);                            //  + D (ABC)
                    temp.RemoveAt(temp.Count - 1);                       
                },                                                       
                (DivisionDescriptor div, out bool bAdhoc) => // 划分    
                {
                    int left = div.left; // 包含第一个元素在内的范围
                    int right = div.right;
                    int pivot = (int)div.userdata; // 第一个元素在范围内的索引
                    DivisionDescriptor[] divisions;
                    int l = left;
                    if (pivot != -1)
                    {
                        temp.Add(dataList[pivot]);
                        Algorithms.Swap(ref dataList, pivot, left);
                        l = left + 1;
                    }
                    divisions = new DivisionDescriptor[right - l + 1];
                    int j = 0;
                    for (int i = l; i <= right ; ++i)
                    {
                        divisions[j].left = l;
                        divisions[j].right = right;
                        divisions[j].userdata = (int)i;
                        j++;
                    }
                    bAdhoc = l == right;
                    return divisions;
                },
                null, // 合并
                (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 AdHoc(DivisionDescriptor division);
        public delegate DivisionDescriptor[] Divide(DivisionDescriptor division, out bool bAdhoc);
        public delegate void Merge(DivisionDescriptor[] divisions);
        public delegate void Postprocess(DivisionDescriptor div);

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

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

        #endregion 

    }
}