using System.Collections;
using System.Collections.Generic;
using AlgorithmCollection;
using AlgorithmCollection.Recursion;
using AlgorithmCollection.Searching;
using AlgorithmCollection.Sorting;
using UnityEngine;

public class Test_Recursion : MonoBehaviour
{
    void Start()
    {
        TestPermutations();
        //TestHanoi();
        //TestBinarySearch();
        //TestMergeSort();
        //TestQuickSort();
        //TestBubbleSort();
    }

    void TestPermutations()
    {
        // 全排列
        //Debug.Log("全排列");
        //List<char> data = new List<char> { 'a', 'b', 'c' };
        //int count = 0;
        //foreach (List<char> p in RecursionHelper.Permutations(data))
        //{
        //    count++;
        //    string content = "";
        //    p.ForEach((char c) => content += c + "  ");
        //    Debug.Log(content);
        //}
        //Debug.Assert(count == Algorithms.Factorial(data.Count));

        Debug.Log("全排列");
        List<char> data = new List<char> { 'a', 'b', 'c' , 'd'};
        int count = 0;
        List<List<char>> perms = new List<List<char>>();
        RecursionHelper.Permutations(data, ref perms);
        foreach (List<char> p in perms)
        {
            count++;
            string content = "";
            p.ForEach((char c) => content += c + "  ");
            Debug.Log(content);
        }
        Debug.Assert(count == Algorithms.Factorial(data.Count));
    }

    // 汉诺塔，a柱上顺序大小的积木移动到c柱
    void TestHanoi()
    {
        Debug.Log("汉诺塔");
        Hanoi(3, 'a', 'b', 'c');
    }

    // 把n个积木从a移动到c
    void Hanoi(int n, char a, char b, char c)
    {
        if (n <= 0)
            return;
        Hanoi(n - 1, a, c, b); // 把a柱上面n-1个移动到b柱
        Debug.Log(a + "->" + c); // 把a柱下面最大的积木移到c柱，这个大积木移动完毕可以不用考虑
        Hanoi(n - 1, b, a, c); // 把b柱的n-1个移动到c柱
    }

    void TestBinarySearch()
    {
        Debug.Log("二分搜索");
        int[] value = { 1, 2, 3, 6, 7, 8 }; //升序数组
        int index = SearchingHelper.BinarySearch(value, 6);
        Debug.Log(index);

        List<int> value2 = new List<int>(){ 1, 2, 3, 6, 7, 8 }; //升序数组
        index = SearchingHelper.BinarySearch(value2, 3);
        Debug.Log(index);
    }

    void TestMergeSort()
    {
    // 局部有序->整体有序
        int[] value = { 9, 7, 2, 3, 4, 6, 1 };
        SortingHelper.MergeSort(value, true);
        string content = "";
        for (int i = 0; i < value.Length; ++i)
        {
            content += value[i] + "  ";
        }
        Debug.Log(content);

        SortingHelper.MergeSort_NoneRecursion(value);
        content = "";
        for (int i = 0; i < value.Length; ++i)
        {
            content += value[i] + "  ";
        }
        Debug.Log(content);
    }

    void TestQuickSort()
    {
    // 整体有序->局部有序
        int[] value = { 9, 7, 2, 3, 4, 6, 1 };
        SortingHelper.QuickSort(value, true);
        string content = "";
        for (int i = 0; i < value.Length; ++i)
        {
            content += value[i] + "  ";
        }
        Debug.Log(content);

        SortingHelper.QuickSort(value);
        content = "";
        for (int i = 0; i < value.Length; ++i)
        {
            content += value[i] + "  ";
        }
        Debug.Log(content);
    }

    void TestBubbleSort()
    {
        int[] value = { 9, 7, 2, 3, 4, 6, 1 };
        SortingHelper.BubbleSort(value, true);
        string content = "";
        for (int i = 0; i < value.Length; ++i)
        {
            content += value[i] + "  ";
        }
        Debug.Log(content);

        SortingHelper.BubbleSort(value);
        content = "";
        for (int i = 0; i < value.Length; ++i)
        {
            content += value[i] + "  ";
        }
        Debug.Log(content);
    }

}