using System;
using System.Linq;

namespace OctreeRendering
{
    class Octree<T> where T : class
    {
        public int Size { get; set; }
        public Node Root { get; set; }

        public Octree()
        {
            Clear();
        }

        public void Clear()
        {
            Root = new Node();
        }

        public bool IsFilled(Vector3i position)
        {
            Node node = FindNode(position, false);
            return node != null && node.Filled;
        }

        public void Fill(Vector3i position, T data)
        {
            Node node = FindNode(position, true);
            node.Data = data;
            node.Filled = true;
            // Merge is posible
            node.TryMerge();
        }

        public void Free(Vector3i position)
        {
            Node node = FindNode(position, false);

            if (node != null && node.Leaf)
            {
                node.Data = null;
                node.Filled = false;

                // Collapse branch if possible
                // TODO : Un-LINQ that shit
                while (node.Parent != null)
                {
                    Node parent = node.Parent;
                    if (parent.Children.All(n => n == null || !n.Filled))
                        parent.Collapse();
                    else
                        break;
                    node = parent;
                }
            }
        }

        Node FindNode(Vector3i position, bool create)
        {
            // We are searching for the center of a cell!
            var cellCenter = position + new Vector3f(0.5f);

            var center = new Vector3f(Size / 2.0f);
            var halfSize = new Vector3f(Size / 2.0f);

            Node node = Root;

            while (!node.Filled && center != cellCenter)
            {
                var cellSign = Vector3f.Sign(cellCenter - center);
                if (node.Leaf || node[cellSign] == null)
                    if (create)
                        node = (node[cellSign] = new Node(node));
                    else
                    {
                        node = null;
                        break;
                    }
                else
                    node = node[cellSign];

                halfSize /= 2;
                center += halfSize * cellSign;
            }

            return node;
        }

        public class Node
        {
            public Node Parent { get; private set; }
            public Node[] Children { get; private set; }

            public T Data { get; set; }
            public bool Filled { get; set; }

            public ContainmentType FrustumContainment { get; set; }
            public bool WasOccluded { get; set; }
            public bool IsOccluded { get; set; }

            public int Id { get; set; }
            public bool QueryPerformed { get; set; }
            public int SynchronousQueriesLeft { get; set; }

            public Node() { }
            public Node(Node parent)
            {
                Parent = parent;
            }

            public void Collapse()
            {
                Data = null;
                Children = null;
                Filled = false;
            }

            public Node this[Vector3i signVector]
            {
                get { return this[OctreeHelper.GetNodeIndex(signVector)]; }
                set { this[OctreeHelper.GetNodeIndex(signVector)] = value; }
            }

            public Node this[int i]
            {
                get { return Leaf ? null : Children[i]; }
                set
                {
                    if (Leaf)   Children = new Node[8];
                    Children[i] = value;
                }
            }

            public bool Leaf
            {
                get { return Children == null; }
            }

            public void TryMerge()
            {
                if (Parent == null) return;

                Parent.Filled = true;
                for (int i = 0; i < 6 && Parent.Filled; i++)
                {
                    var childNode = Parent.Children[i];
                    Parent.Filled &= childNode != null && childNode.Filled;
                }
                Parent.TryMerge();
            }
        }
    }

    static class OctreeHelper
    {
        public static int GetNodeIndex(Vector3i signVector)
        {
            var v = signVector;
            // Front nodes
            if (v.Z == 1)
                if (v.Y == 1)
                    if (v.X == 1)
                        return 0; // ( 1,  1,  1)
                    else
                        return 1; // (-1,  1,  1)
                else
                    if (v.X == 1)
                        return 2; // ( 1, -1,  1)
                    else
                        return 3; // (-1, -1,  1)
            //else
                if (v.Y == 1)
                    if (v.X == 1)
                        return 4; // ( 1,  1, -1)
                    else
                        return 5; // (-1,  1, -1)
                //else
                    if (v.X == 1)
                        return 6; // ( 1, -1, -1)
                    //else
                        return 7; // (-1, -1, -1)
        }

        public static readonly Vector3i[] Signs = new[]
        {
            Vector3i.One,
            new Vector3i(-1, 1, 1),
            new Vector3i(1, -1, 1),
            new Vector3i(-1, -1, 1),
            new Vector3i(1, 1, -1),
            new Vector3i(-1, 1, -1),
            new Vector3i(1, -1, -1),
            new Vector3i(-1, -1, -1)
        };
    }
}
