
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Drawing;
using System.Windows.Forms;

/// <summary>
/// stores/retrieves data objects by their cartesian point values 
/// </summary>
public class classQuadTree
{
    /// <summary>
    /// quad tree divides each search area into four equally sized quadrants if more than one data point is found in a given search area
    /// </summary>
    public enum enuCorners { TL, TR, BL, BR };
    classQuadTree cMe;
    /// <summary>
    /// denies access to quadTree if a search/insertion is in progress
    /// </summary>
    System.Threading.Semaphore semQuadTreeBusy = new System.Threading.Semaphore(0, 1);

    /// <summary>
    /// size of the Quad tree is defined at instantiation
    /// </summary>
    public RectangleF Range
    { get { return cQuad.rec; } }

    /// <summary>
    /// root quad tree search area is the same class as all sub quadrants
    /// </summary>
    public classQuadTreeCorner cQuad = null;

    /// <summary>
    /// initializes a quadtree with the Floating point rectangle specified as its region
    /// </summary>
    /// <param name="RectangleF">defines the size of the space which this tree charts</param>
    public classQuadTree(RectangleF RectangleF)
    {
        cMe = this;
        semQuadTreeBusy.Release();
        cQuad = new classQuadTreeCorner(RectangleF, ref cMe);
    }

    /// <summary>
    /// erases all points in the QuadTree
    /// </summary>
    public void Clear() { cQuad.Clear(); }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="ptf"></param>
    /// <param name="data"></param>
    /// <returns></returns>
    public bool Insert(PointF ptf, ref object data)
    {
        SemSet();
        //ptf.X = -123;
        classQuadTreeData cQData = new classQuadTreeData(ptf, ref data);
        bool bolRetVal = cQuad.Data_Set(ref cQData);
        semRelease();
        return bolRetVal;
    }

    SizeF szSearchVariance = new SizeF();
    /// <summary>
    /// extends point searches by +/- SearchVariance_X in the X-axis
    /// </summary>
    public float SearchVariance_X
    {
        get { return szSearchVariance.Width; }
        set { szSearchVariance.Width = value; }
    }
    /// <summary>
    /// extends point searches by +/- SearchVariance_Y in the Y-axis
    /// </summary>
    public float SearchVariance_Y
    {
        get { return szSearchVariance.Height; }
        set { szSearchVariance.Height= value; }
    }

    /// <summary>
    /// returns all data Objects located within a SearchVariance distance of point ptf
    /// </summary>
    /// <param name="ptf">point being searched in the Quad Tree</param>
    /// <returns>the data object stored in the QuadTree for point ptf</returns>
    public List<classQuadTreeData> Search(PointF ptf)
    {
        if (cQuad == null) return null;
        RectangleF recFSearch = new RectangleF(ptf.X - szSearchVariance.Width, ptf.Y - szSearchVariance.Height, szSearchVariance.Width * 2, szSearchVariance.Height * 2);
        return Search(recFSearch);
    }
    /// <summary>
    /// returns all data objects located within the search rectangle
    /// </summary>
    /// <param name="recFSearch">search area</param>
    /// <returns>list of objects contained within the search area</returns>
    public List<classQuadTreeData> Search(RectangleF recFSearch)
    {

        SemSet();

        List<classQuadTreeData> lstRetVal = new List<classQuadTreeData>();
        cQuad.Data_Get(recFSearch, ref lstRetVal);

        semRelease();
        return lstRetVal;
    }

    /// <summary>
    /// recursively traverses through the quad tree and returns a list of data objects
    /// </summary>
    /// <returns>returns the results in ordered of increasing X and increasing Y </returns>
    public List<classQuadTreeData> TraverseQuadTree()
    {
        List<classQuadTreeData> lstRetVal = new List<classQuadTreeData>();
        if (cQuad != null)
            cQuad.TraverseQuadTree(ref lstRetVal);

        IEnumerable<classQuadTreeData> query = lstRetVal.OrderBy(num => num, new SpecialComparer());
        lstRetVal = query.ToList<classQuadTreeData>();
        return lstRetVal;
    }

    /// <summary>
    /// compares two classQuadTreeData by their PointF values
    /// </summary>
    public class SpecialComparer : IComparer<classQuadTreeData>
    {
        static string strFormat = "00000000.0000000"; // good for floating points 
        /// <summary>
        /// compare two strings formed by concatenating the X + Y values into string format
        /// </summary>
        public int Compare(classQuadTreeData cData1, classQuadTreeData cData2)
        {
            string str1 = cData1.ptf.X.ToString(strFormat)+ ":" + cData1.ptf.Y.ToString(strFormat);
            string str2 = cData2.ptf.X.ToString(strFormat) + ":" + cData2.ptf.Y.ToString(strFormat);

            return string.Compare(str1, str2);
        }
    }

    /// <summary>
    /// stalls this thread until the semaphore is released by another thread in order to avoid multiple threads accessing this shared resource
    /// </summary>
    void SemSet()
    {
        semQuadTreeBusy.WaitOne();
    }

    /// <summary>
    /// releases the semaphore and allows other threads to access this shared resource QuadTree
    /// </summary>
    void semRelease()
    {
        semQuadTreeBusy.Release();
    }

    /// <summary>
    /// one of four quadrants that make up the quadrant one level up
    /// </summary>
    public class classQuadTreeCorner
    {
        public classQuadTreeCorner[] cCorners = new classQuadTreeCorner[4];
        bool bolDivided = false;
        public RectangleF rec = new RectangleF();
        public classQuadTree cTree = null;
        List<classQuadTreeData > lstData = new List<classQuadTreeData>();

        ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // used to draw the quadrants on the user-interface of TestQuadTree 
        // NEEDED ONLY FOR DEMONSTRATION 
        ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
   /*     public void Debug_Report()
        {
            if (bolDivided)
            {
                for (int intCornerCounter = 0; intCornerCounter < 4; intCornerCounter++)
                {
                    cCorners[intCornerCounter].Debug_Report();
                }
            }
            else
                test_Quad_Tree.formTestQuadTree.instance.lstQuadCorners.Add(this);
        }*/
        ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

        /// <summary>
        /// instantiates a sub quadrant of the quadrant being currently scanned that has a width/height half the size of its parent quadrant
        /// </summary>
        /// <param name="RectangleF">floating point rectangle used to define this quadrant's size and position</param>
        /// <param name="Tree">point back to tree to which this quadrant belongs</param>
        public classQuadTreeCorner(RectangleF RectangleF, ref classQuadTree Tree)
        {
            rec = RectangleF;
            cTree = Tree;
        }

        /// <summary>
        /// erases all data from this QuadTree
        /// </summary>
        public void Clear()
        {
            cCorners = new classQuadTreeCorner[4];
            lstData  = null;
            bolDivided = false;
        }
    
        /// <summary>
        /// recurses through QuadTree and adds data to the lstRetVal passed along as a reference parameter
        /// </summary>
        /// <param name="lstRetVal">the reference parameter by which the results of the traversal are returned.  Results are ordered from left to right, top down </param>
        public void TraverseQuadTree(ref List<classQuadTreeData> lstRetVal)
        {
            if (lstData.Count >0)
            {
                for (int intDataItemCounter =0; intDataItemCounter < lstData.Count; intDataItemCounter++)
                lstRetVal.Add(lstData[intDataItemCounter]);
            }
            else
            {
                if (cCorners[0] != null)
                    for (int intCornerCounter = 0; intCornerCounter < 4; intCornerCounter++)
                    {
                        cCorners[intCornerCounter].TraverseQuadTree(ref lstRetVal);
                    }
            }
        }

        /// <summary>
        /// retrieves the object of data that was stored at some point within a (+/- SearchVariance) of point ptf
        /// </summary>
        /// <param name="recF">area to be searched</param>
        /// <returns>returns the first instance of data found within the SearchVariance parameter</returns>
        public void Data_Get(RectangleF recFSearch, ref List<classQuadTreeData> lstRetVal)
        {
            if (lstData.Count >0)
            {
                PointF ptfData = lstData[0].ptf;
                if (ptfData.X >= recFSearch.Left
                    && ptfData.X <= recFSearch.Right
                    && ptfData.Y >= recFSearch.Top
                    && ptfData.Y <= recFSearch.Bottom)
                {
                    for (int intDataCounter = 0; intDataCounter < lstData.Count; intDataCounter++)
                        lstRetVal.Add(lstData[intDataCounter]);
                    return;
                }
                else
                    return;
            }
            else if (cCorners[0] != null)
            {
                for (int intCornerCounter = 0; intCornerCounter < 4; intCornerCounter++)
                {
                    classQuadTreeCorner cThisCorner = cCorners[intCornerCounter];
                    if (classQuadTree.RectanglesIntersect(cThisCorner.rec, recFSearch))
                    {
                        cThisCorner.Data_Get(recFSearch, ref lstRetVal);
                    }
                }
            }

            return ;
        }

        /// <summary>
        /// locates appropriate quadrant in which to place data by recursively testing quadrant data content
        /// </summary>
        /// <param name="data">a data package that includes the storage location as well as the data to be stored</param>
        /// <returns>returns false only if the exact same floating point has already contains a data object</returns>
        public bool Data_Set(ref classQuadTreeData data)
        {
            //SpriteEditor_2017.panelDebug.instance.Hide();
            bool bolRetVal = false ;

            List<classQuadTreeData> lstNewData = new List<classQuadTreeData>();
            lstNewData.Add(data);

            if (lstData.Count > 0) // if this quadrant already has data then it must be subdivided
            { // test if must divide this quadtree
                if (lstData[0].ptf.X == data.ptf.X
                    && lstData[0].ptf.Y == data.ptf.Y)
                { // new data is in exact location as old data -> add to existing data list
                   lstData.Add(data);
                    return true;
                }
                else
                { // new data item is inside this corner but at different location from old data item(s) in list
                    // must divide this quadrant
                    // move all existing data to temp list
                    while (lstData.Count > 0)
                    {
                        classQuadTreeData cDataRef = lstData[0];     // PointF to current data
                        lstNewData.Add(cDataRef);                  // insert new PointFer into list
                        lstData.Remove(lstData[0]);         // set this.cData PointF to null
                    }
                    // divide this quadrant into four quadrants
                    bolDivided = true;

                    float fltWidth_New = rec.Width / 2f;
                    float fltHeight_New = rec.Height / 2f;
                    RectangleF recTL = new RectangleF(rec.Left, rec.Top, fltWidth_New, fltHeight_New);
                    cCorners[(int)enuCorners.TL] = new classQuadTreeCorner(recTL, ref cTree);

                    RectangleF recTR = new RectangleF(rec.Left + fltWidth_New, rec.Top, fltWidth_New, fltHeight_New);
                    cCorners[(int)enuCorners.TR] = new classQuadTreeCorner(recTR, ref cTree);

                    RectangleF recBL = new RectangleF(rec.Left, rec.Top + fltHeight_New, fltWidth_New, fltHeight_New);
                    cCorners[(int)enuCorners.BL] = new classQuadTreeCorner(recBL, ref cTree);

                    RectangleF recBR = new RectangleF(rec.Left + fltWidth_New, rec.Top + fltHeight_New, fltWidth_New, fltHeight_New);
                    cCorners[(int)enuCorners.BR] = new classQuadTreeCorner(recBR, ref cTree);
                }
            }

            if (bolDivided)  // if this quadrant is already subdivided then send this(these) data object(s) down to the appropriate sub-quadrant
            { // insert into the appropriate sub-quadrant
                for (int intDataCounter = 0; intDataCounter < lstNewData.Count; intDataCounter++)
                {
                    for (int intCornerCounter = 0; intCornerCounter < 4; intCornerCounter++)
                    {
                        if (PointFInRectangleF(lstNewData[intDataCounter].ptf, cCorners[intCornerCounter].rec))
                        {
                            classQuadTreeData cDataToPassDown = lstNewData[intDataCounter];
                            bool bolInsert =  cCorners[intCornerCounter].Data_Set(ref cDataToPassDown);
                            bolRetVal = bolRetVal || bolInsert;
                            break;
                        }
                    }
                }
            }
            else // if this quadrant it not divided by the time the program flow reaches here then the data should be stored here
            {
                lstData.Add(lstNewData[0]);
                bolRetVal = true;
            }
            return bolRetVal;
        }

        /// <summary>
        /// tests whether a point is located within a given rectangle parameter
        /// </summary>
        /// <param name="ptf">point being tested</param>
        /// <param name="rec">rectangle being tested</param>
        /// <returns>true only if the point is within the rectangle</returns>
        bool PointFInRectangleF(PointF ptf, RectangleF rec)
        {
            return (ptf.X >= rec.Left
                        && ptf.X <= rec.Right
                        && ptf.Y >= rec.Top
                        && ptf.Y <= rec.Bottom);
        }
    }

    /// <summary>
    /// data class that holds the data contained in a leaf quadrant
    /// </summary>
    public class classQuadTreeData
    {
        public PointF ptf;
        public object Data;
        /// <summary>
        /// initializes an instance of classQuadTreeData
        /// </summary>
        /// <param name="PointF">point at which this data is to be stored</param>
        /// <param name="data">a data object stored at PointF</param>
        public classQuadTreeData(PointF PointF, ref object data)
        {
            ptf = PointF;
            Data = data;
        }
    }

    /// <summary>
    /// test used by search function to test whether the point is within the tolerance area of the current quadrant
    /// </summary>
    /// <param name="rec1">the first rectangle being tested</param>
    /// <param name="rec2">the second rectangle being tested</param>
    /// <returns>true if these two rectangles intersect</returns>
    public static bool RectanglesIntersect(RectangleF rec1, RectangleF rec2)
    {
        if (rec1.Width == 0 || rec1.Height == 0
            || rec2.Width == 0 || rec2.Height == 0) return false;
        bool bolHorizontal = (rec1.Left > rec2.Left && rec1.Right < rec2.Right)             // rec 1 inside rec2
                          || (rec1.Left < rec2.Left && rec1.Right > rec2.Right)             // rec 1 envelopes rec2
                          || (rec1.Left < rec2.Left && rec1.Right > rec2.Left)              // rec 1 straddles rec2's left side
                          || (rec1.Left < rec2.Right && rec1.Right > rec2.Right);           // rec 1 straddles rec2's right side

        bool bolVertical = (rec1.Top > rec2.Top && rec1.Bottom < rec2.Bottom)               // rec 1 inside rec2
                          || (rec1.Top < rec2.Top && rec1.Bottom > rec2.Bottom)             // rec 1 envelopes rec2
                          || (rec1.Top < rec2.Top && rec1.Bottom > rec2.Top)                // rec 1 straddles rec2's Top side
                          || (rec1.Top < rec2.Bottom && rec1.Bottom > rec2.Bottom);         // rec 1 straddles rec2's Bottom side
        return bolVertical && bolHorizontal;
    }
}