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

// 递归与分治算法

namespace AlgorithmCollection.Recursion
{

    public struct DivisionDescriptor
    {
        public int left;
        public int right;
        public object userdata;
    }

    public static class RecursionHelper
    {
        #region 全排列，返回数据的所有组合

        public static void Permutations<T>(List<T> data, ref List<List<T>> perms)          //  A B C D 
        {                                                                                  //  + A (BCD)
            List<List<T>> outPerms = new List<List<T>>();                                  //  	+ B (CD)
            List<T> temp = new List<T>(data.Count);                                        //  		+ C(D)
            DivideAndConquer(data,                                                         //  			+D
                (IList<T> dataList) => // init                                             //  		+ D(C)
                {                                                                          //  			+C
                    DivisionDescriptor div = new DivisionDescriptor();                     //  	+ C (BD)
                    div.userdata = -1;                                                     //  		+ B(D)
                    div.left = 0;                                                          //  		+ D(B)
                    div.right = dataList.Count - 1;                                        //  	+ D (BC)
                    return div;                                                            //  		+ B(C)
                },                                                                         //  		+ C(B)
                (IList<T> dataList, DivisionDescriptor div) => // adhoc 最小子任务处理      //  + B (ACD)
                {                                                                          //  + C (ABD)
                    temp.Add(dataList[div.left]);                                          //  + D (ABC)
                    List<T> newCompose = new List<T>(temp);                                
                    outPerms.Add(newCompose);                                              
                    temp.RemoveAt(temp.Count - 1);                                         
                },                                                                         
                (IList<T> dataList, 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, // 合并
                (IList<T> dataList, 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<T>(IList<T> dataList);
        public delegate void AdHoc<T>(IList<T> dataList, DivisionDescriptor division);
        public delegate DivisionDescriptor[] Divide<T>(IList<T> dataList, DivisionDescriptor division, out bool bAdhoc);
        public delegate void Merge<T>(IList<T> dataList, DivisionDescriptor[] divisions);
        public delegate void Postprocess<T>(IList<T> dataList, DivisionDescriptor div);

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

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

        // 分治算法框架，非递归
        public static void DivideAndConquer_NoneRecursion<T>(IList<T> dataList, int threshold, AdHoc<T> adhoc, Divide<T> divide, Merge<T> merge)
        {

        }

        #endregion 

    }
}