﻿using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// 四叉树节点
/// </summary>
/// <typeparam name="T"></typeparam>
public class QuadTreeNode<T>
{
    /// <summary>
    /// 节点拥有的叶子节点
    /// </summary>
    protected List<QuadTreeLeaf<T>> items;
    /// <summary>
    /// 节点拥有的分支
    /// </summary>
    protected QuadTreeNode<T>[] branch;
    /// <summary>
    /// 节点空间最大容量，受minSize影响
    /// </summary>
    protected int maxItems;
    /// <summary>
    /// 节点空间分割的最小大小（最小宽度，高度）
    /// </summary>
    protected float minSize;

    /// <summary>
    /// 节点的空间
    /// </summary>
    public Rect bounds;

    public QuadTreeNode(float x, float y, float width, float height, int maximumItems, float minSize = -1)
    {
        bounds = new Rect(x, y, width, height);
        maxItems = maximumItems;
        this.minSize = minSize;
        items = new List<QuadTreeLeaf<T>>();
    }

    public bool HasChildren()
    {
        if (branch != null)
            return true;
        else
            return false;
    }

    /// <summary>
    /// 将节点空间分割4份
    /// </summary>
    protected void Split()
    {
        if (minSize != -1)
        {
            if (bounds.width <= minSize && bounds.height <= minSize)
            {
                return;
            }
        }

        float nsHalf = bounds.height - bounds.height / 2;
        float ewHalf = bounds.width - bounds.width / 2;

        branch = new QuadTreeNode<T>[4];
        branch[0] = new QuadTreeNode<T>(bounds.x, bounds.y, ewHalf, nsHalf, maxItems, minSize);
        branch[1] = new QuadTreeNode<T>(bounds.x + ewHalf, bounds.y, ewHalf, nsHalf, maxItems, minSize);
        branch[2] = new QuadTreeNode<T>(bounds.x, bounds.y + nsHalf, ewHalf, nsHalf, maxItems, minSize);
        branch[3] = new QuadTreeNode<T>(bounds.x + ewHalf, bounds.y + nsHalf, ewHalf, nsHalf, maxItems, minSize);

        foreach (var item in items)
        {
            AddNode(item);
        }

        items.Clear();
    }

    /// <summary>
    /// 根据坐标获得相应的子空间
    /// (返回包含该坐标的子节点)
    /// </summary>
    /// <param name="pos"></param>
    /// <returns></returns>
    protected QuadTreeNode<T> GetChild(Vector2 pos)
    {
        if (bounds.Contains(pos))
        {
            if (branch != null)
            {
                for (int i = 0; i < branch.Length; i++)
                    if (branch[i].bounds.Contains(pos))
                        return branch[i].GetChild(pos);

            }
            else
                return this;
        }
        return null;
    }
    /// <summary>
    /// 增加叶子节点数据
    /// </summary>
    /// <param name="leaf"></param>
    /// <returns></returns>
    private bool AddNode(QuadTreeLeaf<T> leaf)
    {
        if (branch == null)
        {
            this.items.Add(leaf);

            if (this.items.Count > maxItems)
                Split();
            return true;
        }
        else
        {
            QuadTreeNode<T> node = GetChild(leaf.Pos);
            if (node != null)
            {
                return node.AddNode(leaf);
            }
        }
        return false;
    }

    public bool AddNode(Vector2 pos, T obj)
    {
        return AddNode(new QuadTreeLeaf<T>(pos, obj));
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="pos">可以是空间任意位置，只是根据这个位置找到所在的空间去删除对象</param>
    /// <param name="obj"></param>
    /// <returns></returns>
    public bool RemoveNode(Vector2 pos, T obj)
    {
        if (branch == null)
        {
            for (int i = 0; i < items.Count; i++)
            {
                QuadTreeLeaf<T> qtl = items[i];
                if (qtl.LeafObject.Equals(obj))
                {
                    items.RemoveAt(i);
                    return true;
                }
            }
        }
        else
        {
            QuadTreeNode<T> node = GetChild(pos);
            if (node != null)
            {
                return node.RemoveNode(pos, obj);
            }
        }
        return false;
    }

    public bool UpdateNode(Vector2 pos, T obj)
    {
        // TODO  参找RemoveNode
        return false;
    }

    /// <summary>
    /// 得到在一个Rect内的所有数据（根据两个rect是否有交集）
    /// </summary>
    /// <param name="rect"></param>
    /// <param name="nodes"></param>
    /// <returns></returns>
    public int GetNode(Rect rect, ref List<T> nodes)
    {
        if (branch == null)
        {
            foreach (QuadTreeLeaf<T> item in items)
            {
                if (rect.Contains(item.Pos))
                {
                    nodes.Add(item.LeafObject);
                }
            }
        }
        else
        {
            for (int i = 0; i < branch.Length; i++)
            {
                if (branch[i].bounds.Overlaps(rect))
                    branch[i].GetNode(rect, ref nodes);
            }
        }
        return nodes.Count;
    }

    /// <summary>
    /// 根据坐标得到坐标附近节点的数据(圆心+半径)
    /// </summary>
    /// <param name="pos"></param>
    /// <param name="ShortestDistance">离坐标最短距离</param>
    /// <param name="list"></param>
    /// <returns></returns>
    public int GetNodeRecRange(Vector2 pos, float ShortestDistance, ref List<T> list)
    {
        float distance;
        if (branch == null)
        {
            foreach (QuadTreeLeaf<T> leaf in this.items)
            {
                distance = Vector2.Distance(pos, leaf.Pos);

                if (distance < ShortestDistance)
                {
                    list.Add(leaf.LeafObject);
                }
            }
        }
        else
        {
            for (int i = 0; i < branch.Length; i++)
            {
                float childDistance = branch[i].bounds.PointToBorderDistance(pos);
                if (childDistance < ShortestDistance * ShortestDistance)
                {
                    branch[i].GetNodeRecRange(pos, ShortestDistance, ref list);
                }
            }
        }
        return list.Count;
    }

    public void DrawBounds()
    {
        if(HasChildren())
        {
            foreach(var i in branch)
            {
                i.DrawBounds();
            }
        }
        else
        {
            Gizmos.color = Color.black;
            Gizmos.DrawWireCube(bounds.center, bounds.size);
        }
    }
}