using System;
using System.Collections;
using System.Collections.Generic;
using AlgorithmCollection;
using AlgorithmCollection.Recursion;

namespace AlgorithmCollection.Searching
{

	public static class SearchingHelper
	{

		// 二分搜索，返回索引号
		// O(logn)
		public static int BinarySearch<T>(T[] dataList, T value) where T : IComparable, IEquatable<T>
		{
			int n = dataList.Length;
			int left = 0;
			int right = n - 1;
			while (left <= right)
			{
				int middle = (right + left) / 2;
				T midValue = dataList[middle];
				if (value.Equals(midValue))
					return middle;
				if (value.CompareTo(midValue) > 0)
					left = middle + 1;
				if (value.CompareTo(midValue) < 0)
					right = middle - 1;
			}
			return -1; // 没找到
		}

        public static int BinarySearch<T>(List<T> data, T value) where T : IComparable, IEquatable<T>
        {
            int index = -1;
            RecursionHelper.DNC(
                () => 
                {
                    DivisionDescriptor div = new DivisionDescriptor();
                    div.left = 0;
                    div.right = data.Count - 1;
                    return div;
                },
                (DivisionDescriptor div, out DivisionDescriptor[] division) =>
                {
                    int left = div.left;
                    int right = div.right;
                    division = new DivisionDescriptor[1];
                    if(right <= left)
                    {
                        division[0].left = left;
                        division[0].right = right;
                        return true;
                    }
                    int mid = (left + right) / 2;
                    T midValue = data[mid];
                    if(midValue.CompareTo(value) > 0)
                    {
                        division[0].left = left;
                        division[0].right = mid - 1;
                    }
                    else if (midValue.CompareTo(value) < 0)
                    {
                        division[0].left = mid + 1;
                        division[0].right = right;
                    }
                    else
                    {
                        division[0].left = mid;
                        division[0].right = mid;
                        return true;
                    }
                    return false;
                },
				(DivisionDescriptor div) =>
				{
					if (data[div.left].CompareTo(value) == 0)
					{
						index = div.left;
					}
				}
				);
            return index;
        }

		// 查找最大值
		// O(n)
		public static int FindMax<T>(IList<T> dataList) where T : IList, IComparable
		{
			int max = 0;
			for(int i = 0; i < dataList.Count; ++i)
			{
				if (dataList[i].CompareTo(dataList[max]) > 0)
					max = i;
			}
			return max;
		}

		// 查找最小值
		// O(n)
		public static int FindMin<T>(IList<T> dataList) where T : IList, IComparable
		{
			int min = 0;
			for (int i = 0; i < dataList.Count; ++i)
			{
				if (dataList[i].CompareTo(dataList[min]) < 0)
					min = i;
			}
			return min;
		}

		// 找到第n大或者第n小，类比快速排序
        // O(n)
		public static bool Select<T>(IList<T> data, int n, bool bMin, ref T findValue) where T : IComparable
		{
            bool suc = false;
			T v = default(T);
			RecursionHelper.DNC(
			()=>
			{
				DivisionDescriptor div = new DivisionDescriptor();
				div.left = 0;
				div.right = data.Count - 1;
				div.userdata = n;
				return div;
			},
			(DivisionDescriptor division, out DivisionDescriptor[] div) =>
			{
                div = new DivisionDescriptor[1];
                int left = division.left;
				int right = division.right;
				int remain = (int)division.userdata;
				if(right <= left)
				{
                    div[0].left = left;
                    div[0].right = right;
                    div[0].userdata = remain;
                    return true;
				}
				int l = left;
				int r = right + 1;
				T val = data[l];
				while (true)
				{
					while ((bMin && data[++l].CompareTo(val) <= 0 || !bMin && data[++l].CompareTo(val) >= 0) && l < right);
					while ((bMin && data[--r].CompareTo(val) >= 0 || !bMin && data[--r].CompareTo(val) <= 0) && r > left);
					if (l >= r)
						break;
					Algorithms.Swap(ref data, l, r);
				}
				Algorithms.Swap(ref data, left, r);
				int count = r - left + 1;
				if(count > remain)
				{
					div[0].left = left;
					div[0].right = r - 1;
					div[0].userdata = remain;
				}
				else if(count < remain)
				{
					div[0].left = r + 1;
					div[0].right = right;
					div[0].userdata = remain - count;
				}
				else
				{
                    div[0].left = r;
                    div[0].right = r;
                    div[0].userdata = 0;
                    return true;
                }
                return false;
			},
			(DivisionDescriptor division)=>
			{
                if((int)division.userdata == 0)
                {
                    int i = division.left;
                    v = data[i];
                    suc = true;
                }
            }
			);
            if (suc)
            {
                findValue = v;
                return true;
            }
			return false;
		}

	}

}