Sithid

using System;
using System.Text;
using System.Drawing;
using System.Collections.Generic;

namespace Sithid.QuadTree
{
    public class QuadNode<T> : IQuadObject where T: IQuadObject
    {
        protected const byte _MAX_OBJECTS_ = 4;

        private QuadNode<T> m_Parent;
        private RectangleF m_Bounds;
        private PointF m_Location;

        private List<T> m_BranchItems;
        private List<QuadNode<T>> m_Children;

        private T m_LastObject;

        public QuadNode<T> Parent
        {
            get
            {
                return m_Parent;
            }
            set
            {
                m_Parent = value;
            }
        }

        public RectangleF Bounds
        {
            get
            {
                return m_Bounds;
            }
            set
            {
                m_Bounds = value;
            }
        }

        public PointF Location
        {
            get
            {
                return m_Location;
            }
            set
            {
                m_Location = value;
            }
        }

        public List<T> BranchItems
        {
            get
            {
                return m_BranchItems;
            }
            set
            {
                m_BranchItems = value;
            }
        }

        public List<QuadNode<T>> Children
        {
            get
            {
                return m_Children;
            }
            set
            {
                m_Children = value;
            }
        }

        public bool IsRoot
        {
            get
            {
                return ( m_Parent == this );
            }
        }

        public int TotalObjects
        {
            get
            {
                int count = m_BranchItems.Count;

                if( m_Children != null )
                {
                    for( int i = 0; i < m_Children.Count; ++i )
                    {
                        count += m_Children[i].TotalObjects;
                    }
                }

                return count;
            }
        }

        public QuadNode( RectangleF bounds, QuadNode<T> parent )
        {
            m_Parent = parent == null ? this : parent;
            m_Bounds = bounds;          

            m_BranchItems = new List<T>();
            m_Children = null;
            m_LastObject = default(T);
        }

        public void Add(T val)
        {
            m_LastObject = val;

            QuadNode<T> node = FindParent( val.Bounds, val.Location, m_Parent );

            List<QuadNode<T>> m_Intersects = new List<QuadNode<T>>();

            if( node.Children != null )
            {
                for( int i = 0; i < node.Children.Count; ++i )
                {
                    if( node.Children[i].Bounds.IntersectsWith( val.Bounds ) )
                    {
                        m_Intersects.Add( node.Children[i] ); 
                    }
                }

                if( m_Intersects.Count > 1 )
                {
                    node.BranchItems.Add( val );
                }
                else
                {
                    m_Intersects[0].Add( val );
                }
            }
            else
            {
                if( node.BranchItems != null )
                {
                    if( node.BranchItems.Count < _MAX_OBJECTS_ )
                    {
                        node.BranchItems.Add( val );
                    }
                    else
                    {
                        node.Split();

                        QuadNode<T> recurse = FindParent( val.Bounds, val.Location, node );
                        recurse.Add( val );
                    }
                }
            }
        }

        private QuadNode<T> FindParent( RectangleF bounds, PointF loc, QuadNode<T> recurse )
        {
            if( recurse != null )
            {
                for( int i = 0; recurse.Children != null && i < recurse.Children.Count; ++i )
                {
                    if( recurse.Children[i].Bounds.IntersectsWith( bounds ) )
                    {
                        recurse = FindParent( bounds, loc, recurse.Children[i] );
                    }
                }
            }
            else
            {
                return this;
            }

            return recurse;
        }

        public void Split()
        {
            float x = m_Bounds.Left;
            float y = m_Bounds.Top;

            float halfx = m_Bounds.Width / 2;
            float halfy = m_Bounds.Height / 2;

            m_Children = new List<QuadNode<T>>();

            m_Children.Add( new QuadNode<T>( new RectangleF( x, y, halfx, halfy ), this ) );
            m_Children.Add( new QuadNode<T>( new RectangleF( x + halfx, y, halfx, halfy ), this ) );
            m_Children.Add( new QuadNode<T>( new RectangleF( x, y + halfy, halfx, halfy ), this ) );
            m_Children.Add( new QuadNode<T>( new RectangleF( x + halfx, y + halfy, halfx, halfy ), this ) );

            for( int i = 0; i < m_BranchItems.Count; ++i )
            {
                for( int j = 0; j < m_Children.Count; ++j )
                {
                    if( m_Children[j].Bounds.IntersectsWith( m_BranchItems[i].Bounds ) )
                    {
                        m_Children[j].Add( m_BranchItems[i] );
 
                        m_BranchItems.Remove( m_BranchItems[i] );
                        --i;

                        break;
                    }
                }
            }
        }

        public void Draw( Graphics g, Point mousePos, bool useMouse )
        {
            Brush b = Brushes.Black;
            Pen p = new Pen( Color.Red, 1f );
            PointF p1, p2, p3, p4;

            if( useMouse )
            {
                if( m_Bounds.Contains( mousePos ) )
                {
                    if( m_Children != null )
                    {
                        for( int i = 0; i < m_Children.Count; ++i )
                        {
                            m_Children[i].Draw( g, mousePos, useMouse );
                        }
                    }
                    else
                    {
                        p1 = new PointF( m_Bounds.Left, m_Bounds.Top );
                        p2 = new PointF( m_Bounds.Right, m_Bounds.Top );
                        p3 = new PointF( m_Bounds.Left, m_Bounds.Bottom );
                        p4 = new PointF( m_Bounds.Right, m_Bounds.Bottom );

                        g.DrawLine( p, p1, p2 );
                        g.DrawLine( p, p2, p4 );
                        g.DrawLine( p, p1, p3 );
                        g.DrawLine( p, p3, p4 );

                        for( int i = 0; i < m_BranchItems.Count; ++i )
                        {
                            g.FillRectangle( b, m_BranchItems[i].Bounds );
                        }
                    }
                }

            }
            else
            {
                if( m_Children != null )
                {
                    for( int i = 0; i < m_Children.Count; ++i )
                    {
                        m_Children[i].Draw( g, mousePos, useMouse );
                    }
                }
                else
                {
                    for( int i = 0; i < m_BranchItems.Count; ++i )
                    {
                        g.FillRectangle( b, m_BranchItems[i].Bounds );
                    }

                    p1 = new PointF( m_Bounds.Left, m_Bounds.Top );
                    p2 = new PointF( m_Bounds.Right, m_Bounds.Top );
                    p3 = new PointF( m_Bounds.Left, m_Bounds.Bottom );
                    p4 = new PointF( m_Bounds.Right, m_Bounds.Bottom );

                    g.DrawLine( p, p1, p2 );
                    g.DrawLine( p, p2, p4 );
                    g.DrawLine( p, p1, p3 );
                    g.DrawLine( p, p3, p4 );
                }
            }

            p.Dispose();
        }
    }
}