using System;
using System.Collections.Generic;
using Unity.Collections;
using Unity.Mathematics;
using Unity.Collections.LowLevel.Unsafe;

namespace UnityEngine.U2D.UTess
{

        enum UEventType
    {
        EVENT_POINT = 0,
        EVENT_END = 1,
        EVENT_START = 2,
    };

    struct UEvent
    {
        public float2 a;
        public float2 b;
        public int idx;
        public int type;
    };

    struct UHull
    {
        public float2 a;
        public float2 b;
        public int idx;

        public ArraySlice<int> ilarray;
        public int ilcount;
        public ArraySlice<int> iuarray;
        public int iucount;
    };

    struct UStar
    {
        public ArraySlice<int> points;
        public int pointCount;
    };

    struct UBounds
    {
        public double2 min;
        public double2 max;
    };

    struct UCircle
    {
        public float2 center;
        public float radius;
    };

    struct UTriangle
    {
        public float2 va;
        public float2 vb;
        public float2 vc;
        public UCircle c;
        public float area;
        public int3 indices;
    };

    struct UEncroachingSegment
    {
        public float2 a;
        public float2 b;
        public int index;
    }

    internal interface ICondition2<in T, in U>
    {
        bool Test(T x, U y, ref float t);
    }

    struct XCompare : IComparer<double>
    {
        public int Compare(double a, double b)
        {
            return (a < b) ? -1 : 1;
        }
    }

    unsafe struct IntersectionCompare : IComparer<int2>
    {
        public NativeArray<double2> points;
        public NativeArray<int2> edges;

        public fixed double xvasort[4];
        public fixed double xvbsort[4];

        public int Compare(int2 a, int2 b)
        {
            var e1a = edges[a.x];
            var e1b = edges[a.y];
            var e2a = edges[b.x];
            var e2b = edges[b.y];

            xvasort[0] = points[e1a.x].x;
            xvasort[1] = points[e1a.y].x;
            xvasort[2] = points[e1b.x].x;
            xvasort[3] = points[e1b.y].x;

            xvbsort[0] = points[e2a.x].x;
            xvbsort[1] = points[e2a.y].x;
            xvbsort[2] = points[e2b.x].x;
            xvbsort[3] = points[e2b.y].x;

            fixed (double* xvasortPtr = xvasort)
            {
                ModuleHandle.InsertionSort<double, XCompare>(xvasortPtr, 0, 3, new XCompare());
            }

            fixed (double* xvbsortPtr = xvbsort)
            {
                ModuleHandle.InsertionSort<double, XCompare>(xvbsortPtr, 0, 3, new XCompare());
            }

            for (int i = 0; i < 4; ++i)
                if (xvasort[i] - xvbsort[i] != 0)
                    return xvasort[i] < xvbsort[i] ? -1 : 1;
            return points[e1a.x].y < points[e1a.x].y ? -1 : 1;
        }
    }

    struct TessEventCompare : IComparer<UEvent>
    {
        public int Compare(UEvent a, UEvent b)
        {
            float f = (a.a.x - b.a.x);
            if (0 != f)
                return (f > 0) ? 1 : -1;

            f = (a.a.y - b.a.y);
            if (0 != f)
                return (f > 0) ? 1 : -1;

            int i = a.type - b.type;
            if (0 != i)
                return i;

            if (a.type != (int)UEventType.EVENT_POINT)
            {
                float o = ModuleHandle.OrientFast(a.a, a.b, b.b);
                if (0 != o)
                {
                    return (o > 0) ? 1 : -1;
                }
            }

            return a.idx - b.idx;
        }
    }

    struct TessEdgeCompare : IComparer<int2>
    {
        public int Compare(int2 a, int2 b)
        {
            int i = a.x - b.x;
            if (0 != i)
                return i;
            i = a.y - b.y;
            return i;
        }
    }

    struct TessCellCompare : IComparer<int3>
    {
        public int Compare(int3 a, int3 b)
        {
            int i = a.x - b.x;
            if (0 != i)
                return i;
            i = a.y - b.y;
            if (0 != i)
                return i;
            i = a.z - b.z;
            return i;
        }
    }

    struct TessJunctionCompare : IComparer<int2>
    {
        public int Compare(int2 a, int2 b)
        {
            int i = a.x - b.x;
            if (0 != i)
                return i;
            i = a.y - b.y;
            return i;
        }
    }

    struct DelaEdgeCompare : IComparer<int4>
    {
        public int Compare(int4 a, int4 b)
        {
            int i = a.x - b.x;
            if (0 != i)
                return i;
            i = a.y - b.y;
            if (0 != i)
                return i;
            i = a.z - b.z;
            if (0 != i)
                return i;
            i = a.w - b.w;
            return i;
        }
    }

    struct TessLink
    {

        internal NativeArray<int> roots;
        internal NativeArray<int> ranks;

        internal static TessLink CreateLink(int count, Allocator allocator)
        {
            TessLink link = new TessLink();
            link.roots = new NativeArray<int>(count, allocator);
            link.ranks = new NativeArray<int>(count, allocator);

            for (int i = 0; i < count; ++i)
            {
                link.roots[i] = i;
                link.ranks[i] = 0;
            }
            return link;
        }

        internal static void DestroyLink(TessLink link)
        {
            link.ranks.Dispose();
            link.roots.Dispose();
        }

        internal int Find(int x)
        {
            var x0 = x;
            while (roots[x] != x)
            {
                x = roots[x];
            }
            while (roots[x0] != x)
            {
                var y = roots[x0];
                roots[x0] = x;
                x0 = y;
            }
            return x;
        }

        internal void Link(int x, int y)
        {
            var xr = Find(x);
            var yr = Find(y);
            if (xr == yr)
            {
                return;
            }
            var xd = ranks[xr];
            var yd = ranks[yr];
            if (xd < yd)
            {
                roots[xr] = yr;
            }
            else if (yd < xd)
            {
                roots[yr] = xr;
            }
            else
            {
                roots[yr] = xr;
                ++ranks[xr];
            }
        }
    };

    internal struct ModuleHandle
    {
    
        // Max Edge Count with Subdivision allowed. This is already a very relaxed limit
        // and anything beyond are basically littered with numerous paths.
        internal static readonly  int kMaxArea = 65536;
        internal static readonly  int kMaxEdgeCount = 65536;
        internal static readonly  int kMaxIndexCount = 65536;
        internal static readonly  int kMaxVertexCount = 65536;
        internal static readonly  int kMaxTriangleCount = kMaxIndexCount / 3;
        internal static readonly  int kMaxRefineIterations = 48;
        internal static readonly  int kMaxSmoothenIterations = 256;
        internal static readonly  float kIncrementAreaFactor = 1.2f;
    
        internal static void Copy<T>(NativeArray<T> src, int srcIndex, NativeArray<T> dst, int dstIndex, int length)
            where T : struct
        {
            NativeArray<T>.Copy(src, srcIndex, dst, dstIndex, length);
        }

        internal static void Copy<T>(NativeArray<T> src, NativeArray<T> dst, int length)
            where T : struct
        {
            Copy(src, 0, dst, 0, length);
        }

        internal static unsafe void InsertionSort<T, U>(void* array, int lo, int hi, U comp)
            where T : struct where U : IComparer<T>
        {
            int i, j;
            T t;
            for (i = lo; i < hi; i++)
            {
                j = i;
                t = UnsafeUtility.ReadArrayElement<T>(array, i + 1);
                while (j >= lo && comp.Compare(t, UnsafeUtility.ReadArrayElement<T>(array, j)) < 0)
                {
                    UnsafeUtility.WriteArrayElement<T>(array, j + 1, UnsafeUtility.ReadArrayElement<T>(array, j));
                    j--;
                }
                UnsafeUtility.WriteArrayElement<T>(array, j + 1, t);
            }
        }        
        
        // Search Lower Bounds 
        internal static int GetLower<T, U, X>(NativeArray<T> values, int count, U check, X condition)
            where T : struct where U : struct where X : ICondition2<T, U>
        {
            int l = 0;
            int h = count - 1;
            int i = l - 1;
            while (l <= h)
            {
                int m = ((int)(l + h)) >> 1;
                float t = 0;
                if (condition.Test(values[m], check, ref t))
                {
                    i = m;
                    l = m + 1;
                }
                else
                {
                    h = m - 1;
                }
            }
            return i;
        }

        // Search Upper Bounds
        internal static int GetUpper<T, U, X>(NativeArray<T> values, int count, U check, X condition)
            where T : struct where U : struct where X : ICondition2<T, U>
        {
            int l = 0;
            int h = count - 1;
            int i = h + 1;
            while (l <= h)
            {
                int m = ((int)(l + h)) >> 1;
                float t = 0;
                if (condition.Test(values[m], check, ref t))
                {
                    i = m;
                    h = m - 1;
                }
                else
                {
                    l = m + 1;
                }
            }
            return i;
        }

        // Search for Equal
        internal static int GetEqual<T, U, X>(NativeArray<T> values, int count, U check, X condition)
            where T : struct where U : struct where X : ICondition2<T, U>
        {
            int l = 0;
            int h = count - 1;
            while (l <= h)
            {
                int m = ((int)(l + h)) >> 1;
                float t = 0;
                condition.Test(values[m], check, ref t);
                if (t == 0)
                {
                    return m;
                }
                else if (t <= 0)
                {
                    l = m + 1;
                }
                else
                {
                    h = m - 1;
                }
            }
            return -1;
        }

        // Simple Orientation test.
        internal static float OrientFast(float2 a, float2 b, float2 c)
        {
            float epsilon = 1.1102230246251565e-16f;
            float det = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
            if (math.abs(det) < epsilon) return 0;
            return det;
        }

        // This is needed when doing PlanarGraph as it requires high precision separation of points.
        internal static double OrientFastDouble(double2 a, double2 b, double2 c)
        {
            double epsilon = 1.1102230246251565e-16f;
            double det = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
            if (math.abs(det) < epsilon) return 0;
            return det;
        }

        internal static UCircle CircumCircle(UTriangle tri)
        {
            float xa = tri.va.x * tri.va.x;
            float xb = tri.vb.x * tri.vb.x;
            float xc = tri.vc.x * tri.vc.x;
            float ya = tri.va.y * tri.va.y;
            float yb = tri.vb.y * tri.vb.y;
            float yc = tri.vc.y * tri.vc.y;
            float c = 2f * ((tri.vb.x - tri.va.x) * (tri.vc.y - tri.va.y) - (tri.vb.y - tri.va.y) * (tri.vc.x - tri.va.x));
            float x = ((tri.vc.y - tri.va.y) * (xb - xa + yb - ya) + (tri.va.y - tri.vb.y) * (xc - xa + yc - ya)) / c;
            float y = ((tri.va.x - tri.vc.x) * (xb - xa + yb - ya) + (tri.vb.x - tri.va.x) * (xc - xa + yc - ya)) / c;
            float vx = (tri.va.x - x);
            float vy = (tri.va.y - y);
            return new UCircle { center = new float2(x, y), radius = math.sqrt((vx * vx) + (vy * vy)) };
        }

        internal static bool IsInsideCircle(UCircle c, float2 v)
        {
            return math.distance(v, c.center) < c.radius;
        }

        internal static float TriangleArea(float2 va, float2 vb, float2 vc)
        {
            float3 a = new float3(va.x, va.y, 0);
            float3 b = new float3(vb.x, vb.y, 0);
            float3 c = new float3(vc.x, vc.y, 0);
            float3 v = math.cross(a - b, a - c);
            return math.abs(v.z) * 0.5f;
        }

        internal static float Sign(float2 p1, float2 p2, float2 p3)
        {
            return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
        }

        internal static bool IsInsideTriangle(float2 pt, float2 v1, float2 v2, float2 v3)
        {
            float d1, d2, d3;
            bool has_neg, has_pos;

            d1 = Sign(pt, v1, v2);
            d2 = Sign(pt, v2, v3);
            d3 = Sign(pt, v3, v1);

            has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
            has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

            return !(has_neg && has_pos);
        }
        
        internal static bool IsInsideTriangleApproximate(float2 pt, float2 v1, float2 v2, float2 v3)
        {
            float d0, d1, d2, d3;
            d0 = TriangleArea(v1, v2, v3);
            d1 = TriangleArea(pt, v1, v2);
            d2 = TriangleArea(pt, v2, v3);
            d3 = TriangleArea(pt, v3, v1);
            float epsilon = 1.1102230246251565e-16f;
            return Mathf.Abs(d0 - (d1 + d2 + d3)) < epsilon;
        }        
        
        internal static bool IsInsideCircle(float2 a, float2 b, float2 c, float2 p)
        {
            float ab = math.dot(a, a);
            float cd = math.dot(b, b);
            float ef = math.dot(c, c);

            float ax = a.x;
            float ay = a.y;
            float bx = b.x;
            float by = b.y;
            float cx = c.x;
            float cy = c.y;

            float circum_x = (ab * (cy - by) + cd * (ay - cy) + ef * (by - ay)) /
                                (ax * (cy - by) + bx * (ay - cy) + cx * (by - ay));
            float circum_y = (ab * (cx - bx) + cd * (ax - cx) + ef * (bx - ax)) /
                                (ay * (cx - bx) + by * (ax - cx) + cy * (bx - ax));

            float2 circum = new float2();
            circum.x = circum_x / 2;
            circum.y = circum_y / 2;
            float circum_radius = math.distance(a, circum);
            float dist = math.distance(p, circum);
            return circum_radius - dist > 0.00001f;
        }
        
    }    
    
    // Constrained Delaunay Triangulation.
    struct Tessellator
    {

        // For Processing.
        NativeArray<int2> m_Edges;
        NativeArray<UStar> m_Stars;
        NativeArray<int3> m_Cells;
        int m_CellCount;

        // For Storage.
        NativeArray<int> m_ILArray;
        NativeArray<int> m_IUArray;
        NativeArray<int> m_SPArray;
        int m_NumEdges;
        int m_NumHulls;
        int m_NumPoints;
        int m_StarCount;

        // Intermediates.
        NativeArray<int> m_Flags;
        NativeArray<int> m_Neighbors;
        NativeArray<int> m_Constraints;
        Allocator m_Allocator;


        struct TestHullPointL : ICondition2<UHull, float2>
        {
            public bool Test(UHull h, float2 p, ref float t)
            {
                t = ModuleHandle.OrientFast(h.a, h.b, p);
                return t < 0;
            }
        }

        struct TestHullPointU : ICondition2<UHull, float2>
        {
            public bool Test(UHull h, float2 p, ref float t)
            {
                t = ModuleHandle.OrientFast(h.a, h.b, p);
                return t > 0;
            }
        }

        static float FindSplit(UHull hull, UEvent edge)
        {
            float d = 0;
            if (hull.a.x < edge.a.x)
            {
                d = ModuleHandle.OrientFast(hull.a, hull.b, edge.a);
            }
            else
            {
                d = ModuleHandle.OrientFast(edge.b, edge.a, hull.a);
            }

            if (0 != d)
            {
                return d;
            }

            if (edge.b.x < hull.b.x)
            {
                d = ModuleHandle.OrientFast(hull.a, hull.b, edge.b);
            }
            else
            {
                d = ModuleHandle.OrientFast(edge.b, edge.a, hull.b);
            }

            if (0 != d)
            {
                return d;
            }
            return hull.idx - edge.idx;
        }

        struct TestHullEventLe : ICondition2<UHull, UEvent>
        {
            public bool Test(UHull h, UEvent p, ref float t)
            {
                t = FindSplit(h, p);
                return t <= 0;
            }
        }

        struct TestHullEventE : ICondition2<UHull, UEvent>
        {
            public bool Test(UHull h, UEvent p, ref float t)
            {
                t = FindSplit(h, p);
                return t == 0;
            }
        }

        void SetAllocator(Allocator allocator)
        {
            m_Allocator = allocator;
        }

        bool AddPoint(NativeArray<UHull> hulls, int hullCount, NativeArray<float2> points, float2 p, int idx)
        {
            int l = ModuleHandle.GetLower(hulls, hullCount, p, new TestHullPointL());
            int u = ModuleHandle.GetUpper(hulls, hullCount, p, new TestHullPointU());
            if (l < 0 || u < 0)
                return false;
            for (int i = l; i < u; ++i)
            {
                UHull hull = hulls[i];

                int m = hull.ilcount;
                while (m > 1 && ModuleHandle.OrientFast(points[hull.ilarray[m - 2]], points[hull.ilarray[m - 1]], p) > 0)
                {
                    int3 c = new int3();
                    c.x = hull.ilarray[m - 1];
                    c.y = hull.ilarray[m - 2];
                    c.z = idx;
                    m_Cells[m_CellCount++] = c;
                    m -= 1;
                }

                hull.ilcount = m + 1;
                if (hull.ilcount > hull.ilarray.Length)
                    return false;
                hull.ilarray[m] = idx;

                m = hull.iucount;
                while (m > 1 && ModuleHandle.OrientFast(points[hull.iuarray[m - 2]], points[hull.iuarray[m - 1]], p) < 0)
                {
                    int3 c = new int3();
                    c.x = hull.iuarray[m - 2];
                    c.y = hull.iuarray[m - 1];
                    c.z = idx;
                    m_Cells[m_CellCount++] = c;
                    m -= 1;
                }

                hull.iucount = m + 1;
                if (hull.iucount > hull.iuarray.Length)
                    return false;                
                hull.iuarray[m] = idx;

                hulls[i] = hull;
            }
            return true;
        }

        static void InsertHull(NativeArray<UHull> Hulls, int Pos, ref int Count, UHull Value)
        {
            if (Count < Hulls.Length - 1)
            {
                for (int i = Count; i > Pos; --i)
                    Hulls[i] = Hulls[i - 1];
                Hulls[Pos] = Value;
                Count++;
            }
        }

        static void EraseHull(NativeArray<UHull> Hulls, int Pos, ref int Count)
        {
            if (Count < Hulls.Length)
            {
                for (int i = Pos; i < Count - 1; ++i)
                    Hulls[i] = Hulls[i + 1];
                Count--;
            }
        }

        bool SplitHulls(NativeArray<UHull> hulls, ref int hullCount, NativeArray<float2> points, UEvent evt)
        {
            int index = ModuleHandle.GetLower(hulls, hullCount, evt, new TestHullEventLe());
            if (index < 0)
                return false;
            
            UHull hull = hulls[index];

            UHull newHull;
            newHull.a = evt.a;
            newHull.b = evt.b;
            newHull.idx = evt.idx;

            int y = hull.iuarray[hull.iucount - 1];
            newHull.iuarray = new ArraySlice<int>(m_IUArray, newHull.idx * m_NumHulls, m_NumHulls);
            newHull.iucount = hull.iucount;
            for (int i = 0; i < newHull.iucount; ++i)
                newHull.iuarray[i] = hull.iuarray[i];
            hull.iuarray[0] = y;
            hull.iucount = 1;
            hulls[index] = hull;

            newHull.ilarray = new ArraySlice<int>(m_ILArray, newHull.idx * m_NumHulls, m_NumHulls);
            newHull.ilarray[0] = y;
            newHull.ilcount = 1;

            InsertHull(hulls, index + 1, ref hullCount, newHull);
            return true;
        }

        bool MergeHulls(NativeArray<UHull> hulls, ref int hullCount, NativeArray<float2> points, UEvent evt)
        {
            float2 temp = evt.a;
            evt.a = evt.b;
            evt.b = temp;
            int index = ModuleHandle.GetEqual(hulls, hullCount, evt, new TestHullEventE());
            if (index < 0)
                return false;

            UHull upper = hulls[index];
            UHull lower = hulls[index - 1];

            lower.iucount = upper.iucount;
            for (int i = 0; i < lower.iucount; ++i)
                lower.iuarray[i] = upper.iuarray[i];

            hulls[index - 1] = lower;
            EraseHull(hulls, index, ref hullCount);
            return true;
        }

        static void InsertUniqueEdge(NativeArray<int2> edges, int2 e, ref int edgeCount)
        {
            TessEdgeCompare edgeComparer = new TessEdgeCompare();
            var validEdge = true;
            for (int j = 0; validEdge && j < edgeCount; ++j)
                if (edgeComparer.Compare(e, edges[j]) == 0)
                    validEdge = false;
            if (validEdge)
                edges[edgeCount++] = e;
        }

        void PrepareDelaunay(NativeArray<int2> edges, int edgeCount)
        {
            m_StarCount = m_CellCount * 3;
            m_Stars = new NativeArray<UStar>(m_StarCount, m_Allocator);
            m_SPArray = new NativeArray<int>(m_StarCount * m_StarCount, m_Allocator);

            var UEdgeCount = 0;
            var UEdges = new NativeArray<int2>(m_StarCount, m_Allocator);

            // Input Edges.
            for (int i = 0; i < edgeCount; ++i)
            {
                int2 e = edges[i];
                e.x = (edges[i].x < edges[i].y) ? edges[i].x : edges[i].y;
                e.y = (edges[i].x > edges[i].y) ? edges[i].x : edges[i].y;
                edges[i] = e;
                InsertUniqueEdge(UEdges, e, ref UEdgeCount);
            }

            m_Edges = new NativeArray<int2>(UEdgeCount, m_Allocator);
            for (int i = 0; i < UEdgeCount; ++i)
                m_Edges[i] = UEdges[i];
            UEdges.Dispose();

            unsafe
            {
                ModuleHandle.InsertionSort<int2, TessEdgeCompare>(
                    NativeArrayUnsafeUtility.GetUnsafeBufferPointerWithoutChecks(m_Edges), 0, m_Edges.Length - 1,
                    new TessEdgeCompare());
            }

            // Init Stars.
            for (int i = 0; i < m_StarCount; ++i)
            {
                UStar s = m_Stars[i];
                s.points = new ArraySlice<int>(m_SPArray, i * m_StarCount, m_StarCount);
                s.pointCount = 0;
                m_Stars[i] = s;
            }

            // Fill stars.
            for (int i = 0; i < m_CellCount; ++i)
            {
                int a = m_Cells[i].x;
                int b = m_Cells[i].y;
                int c = m_Cells[i].z;
                UStar sa = m_Stars[a];
                UStar sb = m_Stars[b];
                UStar sc = m_Stars[c];
                sa.points[sa.pointCount++] = b;
                sa.points[sa.pointCount++] = c;
                sb.points[sb.pointCount++] = c;
                sb.points[sb.pointCount++] = a;
                sc.points[sc.pointCount++] = a;
                sc.points[sc.pointCount++] = b;
                m_Stars[a] = sa;
                m_Stars[b] = sb;
                m_Stars[c] = sc;
            }

        }

        int OppositeOf(int a, int b)
        {
            ArraySlice<int> points = m_Stars[b].points;
            for (int k = 1, n = m_Stars[b].pointCount; k < n; k += 2)
                if (points[k] == a)
                    return points[k - 1];
            return -1;
        }

        struct TestEdgePointE : ICondition2<int2, int2>
        {
            public bool Test(int2 h, int2 p, ref float t)
            {
                TessEdgeCompare tc = new TessEdgeCompare();
                t = tc.Compare(h, p);
                return t == 0;
            }
        }

        int FindConstraint(int a, int b)
        {
            int2 e;
            e.x = a < b ? a : b;
            e.y = a > b ? a : b;
            return ModuleHandle.GetEqual(m_Edges, m_Edges.Length, e, new TestEdgePointE());
        }

        void AddTriangle(int i, int j, int k)
        {
            UStar si = m_Stars[i];
            UStar sj = m_Stars[j];
            UStar sk = m_Stars[k];
            si.points[si.pointCount++] = j;
            si.points[si.pointCount++] = k;
            sj.points[sj.pointCount++] = k;
            sj.points[sj.pointCount++] = i;
            sk.points[sk.pointCount++] = i;
            sk.points[sk.pointCount++] = j;
            m_Stars[i] = si;
            m_Stars[j] = sj;
            m_Stars[k] = sk;
        }

        void RemovePair(int r, int j, int k)
        {
            UStar s = m_Stars[r];
            ArraySlice<int> points = s.points;
            for (int i = 1, n = s.pointCount; i < n; i += 2)
            {
                if (points[i - 1] == j && points[i] == k)
                {
                    points[i - 1] = points[n - 2];
                    points[i] = points[n - 1];
                    s.points = points;
                    s.pointCount = s.pointCount - 2;
                    m_Stars[r] = s;
                    return;
                }
            }
        }

        void RemoveTriangle(int i, int j, int k)
        {
            RemovePair(i, j, k);
            RemovePair(j, k, i);
            RemovePair(k, i, j);
        }

        void EdgeFlip(int i, int j)
        {
            int a = OppositeOf(i, j);
            int b = OppositeOf(j, i);
            RemoveTriangle(i, j, a);
            RemoveTriangle(j, i, b);
            AddTriangle(i, b, a);
            AddTriangle(j, a, b);
        }

        bool Flip(NativeArray<float2> points, ref NativeArray<int> stack, ref int stackCount, int a, int b, int x)
        {
            int y = OppositeOf(a, b);

            if (y < 0)
            {
                return true;
            }

            if (b < a)
            {
                int tmp = a;
                a = b;
                b = tmp;
                tmp = x;
                x = y;
                y = tmp;
            }

            if (FindConstraint(a, b) != -1)
            {
                return true;
            }

            if (ModuleHandle.IsInsideCircle(points[a], points[b], points[x], points[y]))
            {
                if ((2 + stackCount) >= stack.Length)
                    return false;
                stack[stackCount++] = a;
                stack[stackCount++] = b;
            }

            return true;
        }

        NativeArray<int3> GetCells(ref int count)
        {
            NativeArray<int3> cellsOut = new NativeArray<int3>(m_NumPoints * (m_NumPoints + 1), m_Allocator);
            count = 0;
            for (int i = 0, n = m_Stars.Length; i < n; ++i)
            {
                ArraySlice<int> points = m_Stars[i].points;
                for (int j = 0, m = m_Stars[i].pointCount; j < m; j += 2)
                {
                    int s = points[j];
                    int t = points[j + 1];
                    if (i < math.min(s, t))
                    {
                        int3 c = new int3();
                        c.x = i;
                        c.y = s;
                        c.z = t;
                        cellsOut[count++] = c;
                    }
                }
            }

            return cellsOut;
        }

        internal bool ApplyDelaunay(NativeArray<float2> points, NativeArray<int2> edges)
        {

            NativeArray<int> stack = new NativeArray<int>(m_NumPoints * (m_NumPoints + 1), m_Allocator);
            int stackCount = 0;
            var valid = true;

            PrepareDelaunay(edges, m_NumEdges);
            for (int a = 0; valid && (a < m_NumPoints); ++a)
            {
                UStar star = m_Stars[a];
                for (int j = 1; j < star.pointCount; j += 2)
                {
                    int b = star.points[j];

                    if (b < a)
                    {
                        continue;
                    }

                    if (FindConstraint(a, b) >= 0)
                    {
                        continue;
                    }

                    int x = star.points[j - 1], y = -1;
                    for (int k = 1; k < star.pointCount; k += 2)
                    {
                        if (star.points[k - 1] == b)
                        {
                            y = star.points[k];
                            break;
                        }
                    }

                    if (y < 0)
                    {
                        continue;
                    }

                    if (ModuleHandle.IsInsideCircle(points[a], points[b], points[x], points[y]))
                    {
                        if ((2 + stackCount) >= stack.Length)
                        {
                            valid = false;
                            break;
                        }

                        stack[stackCount++] = a;
                        stack[stackCount++] = b;
                    }
                }
            }

            var flipFlops = m_NumPoints * m_NumPoints;
            while (stackCount > 0 && valid)
            {
                int b = stack[stackCount - 1];
                stackCount--;
                int a = stack[stackCount - 1];
                stackCount--;

                int x = -1, y = -1;
                UStar star = m_Stars[a];
                for (int i = 1; i < star.pointCount; i += 2)
                {
                    int s = star.points[i - 1];
                    int t = star.points[i];
                    if (s == b)
                    {
                        y = t;
                    }
                    else if (t == b)
                    {
                        x = s;
                    }
                }

                if (x < 0 || y < 0)
                {
                    continue;
                }

                if (!ModuleHandle.IsInsideCircle(points[a], points[b], points[x], points[y]))
                {
                    continue;
                }

                EdgeFlip(a, b);

                valid = Flip(points, ref stack, ref stackCount, x, a, y);
                valid = valid && Flip(points, ref stack, ref stackCount, a, y, x);
                valid = valid && Flip(points, ref stack, ref stackCount, y, b, x);
                valid = valid && Flip(points, ref stack, ref stackCount, b, x, y);
                valid = valid && (--flipFlops > 0);
            }

            stack.Dispose();
            return valid;
        }

        struct TestCellE : ICondition2<int3, int3>
        {
            public bool Test(int3 h, int3 p, ref float t)
            {
                TessCellCompare tc = new TessCellCompare();
                t = tc.Compare(h, p);
                return t == 0;
            }
        }

        int FindNeighbor(NativeArray<int3> cells, int count, int a, int b, int c)
        {
            int x = a, y = b, z = c;
            if (b < c)
            {
                if (b < a)
                {
                    x = b;
                    y = c;
                    z = a;
                }
            }
            else if (c < a)
            {
                x = c;
                y = a;
                z = b;
            }

            if (x < 0)
            {
                return -1;
            }

            int3 key;
            key.x = x;
            key.y = y;
            key.z = z;
            return ModuleHandle.GetEqual(cells, count, key, new TestCellE());
        }

        NativeArray<int3> Constrain(ref int count)
        {
            var cells = GetCells(ref count);
            int nc = count;
            for (int i = 0; i < nc; ++i)
            {
                int3 c = cells[i];
                int x = c.x, y = c.y, z = c.z;
                if (y < z)
                {
                    if (y < x)
                    {
                        c.x = y;
                        c.y = z;
                        c.z = x;
                    }
                }
                else if (z < x)
                {
                    c.x = z;
                    c.y = x;
                    c.z = y;
                }

                cells[i] = c;
            }

            unsafe
            {
                ModuleHandle.InsertionSort<int3, TessCellCompare>(
                    NativeArrayUnsafeUtility.GetUnsafeBufferPointerWithoutChecks(cells), 0, m_CellCount - 1,
                    new TessCellCompare());
            }

            // Out
            m_Flags = new NativeArray<int>(nc, m_Allocator);
            m_Neighbors = new NativeArray<int>(nc * 3, m_Allocator);
            m_Constraints = new NativeArray<int>(nc * 3, m_Allocator);
            var next = new NativeArray<int>(nc * 3, m_Allocator);
            var active = new NativeArray<int>(nc * 3, m_Allocator);

            int side = 1, nextCount = 0, activeCount = 0;

            for (int i = 0; i < nc; ++i)
            {
                int3 c = cells[i];
                for (int j = 0; j < 3; ++j)
                {
                    int x = j, y = (j + 1) % 3;
                    x = (x == 0) ? c.x : (j == 1) ? c.y : c.z;
                    y = (y == 0) ? c.x : (y == 1) ? c.y : c.z;

                    int o = OppositeOf(y, x);
                    int a = m_Neighbors[3 * i + j] = FindNeighbor(cells, count, y, x, o);
                    int b = m_Constraints[3 * i + j] = (-1 != FindConstraint(x, y)) ? 1 : 0;
                    if (a < 0)
                    {
                        if (0 != b)
                        {
                            next[nextCount++] = i;
                        }
                        else
                        {
                            active[activeCount++] = i;
                            m_Flags[i] = 1;
                        }
                    }
                }
            }

            while (activeCount > 0 || nextCount > 0)
            {
                while (activeCount > 0)
                {
                    int t = active[activeCount - 1];
                    activeCount--;
                    if (m_Flags[t] == -side)
                    {
                        continue;
                    }

                    m_Flags[t] = side;
                    int3 c = cells[t];
                    for (int j = 0; j < 3; ++j)
                    {
                        int f = m_Neighbors[3 * t + j];
                        if (f >= 0 && m_Flags[f] == 0)
                        {
                            if (0 != m_Constraints[3 * t + j])
                            {
                                next[nextCount++] = f;
                            }
                            else
                            {
                                active[activeCount++] = f;
                                m_Flags[f] = side;
                            }
                        }
                    }
                }

                for (int e = 0; e < nextCount; e++)
                    active[e] = next[e];
                activeCount = nextCount;
                nextCount = 0;
                side = -side;
            }

            active.Dispose();
            next.Dispose();
            return cells;
        }

        internal NativeArray<int3> RemoveExterior(ref int cellCount)
        {
            int constrainedCount = 0;
            NativeArray<int3> constrained = Constrain(ref constrainedCount);

            NativeArray<int3> cellsOut = new NativeArray<int3>(constrainedCount, m_Allocator);
            cellCount = 0;
            for (int i = 0; i < constrainedCount; ++i)
            {
                if (m_Flags[i] == -1)
                {
                    cellsOut[cellCount++] = constrained[i];
                }
            }

            constrained.Dispose();
            return cellsOut;
        }

        internal NativeArray<int3> RemoveInterior(int cellCount)
        {
            int constrainedCount = 0;
            NativeArray<int3> constrained = Constrain(ref constrainedCount);

            NativeArray<int3> cellsOut = new NativeArray<int3>(constrainedCount, m_Allocator);
            cellCount = 0;
            for (int i = 0; i < constrainedCount; ++i)
            {
                if (m_Flags[i] == 1)
                {
                    cellsOut[cellCount++] = constrained[i];
                }
            }

            constrained.Dispose();
            return cellsOut;
        }

        internal bool Triangulate(NativeArray<float2> points, int pointCount, NativeArray<int2> edges, int edgeCount)
        {
            m_NumEdges = edgeCount;
            m_NumHulls = edgeCount * 2;
            m_NumPoints = pointCount;
            m_CellCount = 0;
            m_Cells = new NativeArray<int3>(ModuleHandle.kMaxTriangleCount, m_Allocator);
            m_ILArray = new NativeArray<int>(m_NumHulls * (m_NumHulls + 1), m_Allocator); // Make room for -1 node.
            m_IUArray = new NativeArray<int>(m_NumHulls * (m_NumHulls + 1), m_Allocator); // Make room for -1 node.

            NativeArray<UHull> hulls = new NativeArray<UHull>(m_NumPoints * 8, m_Allocator);
            int hullCount = 0;

            NativeArray<UEvent> events = new NativeArray<UEvent>(m_NumPoints + (m_NumEdges * 2), m_Allocator);
            int eventCount = 0;

            for (int i = 0; i < m_NumPoints; ++i)
            {
                UEvent evt = new UEvent();
                evt.a = points[i];
                evt.b = new float2();
                evt.idx = i;
                evt.type = (int)UEventType.EVENT_POINT;
                events[eventCount++] = evt;
            }

            for (int i = 0; i < m_NumEdges; ++i)
            {
                int2 e = edges[i];
                float2 a = points[e.x];
                float2 b = points[e.y];
                if (a.x < b.x)
                {
                    UEvent _s = new UEvent();
                    _s.a = a;
                    _s.b = b;
                    _s.idx = i;
                    _s.type = (int)UEventType.EVENT_START;

                    UEvent _e = new UEvent();
                    _e.a = b;
                    _e.b = a;
                    _e.idx = i;
                    _e.type = (int)UEventType.EVENT_END;

                    events[eventCount++] = _s;
                    events[eventCount++] = _e;
                }
                else if (a.x > b.x)
                {
                    UEvent _s = new UEvent();
                    _s.a = b;
                    _s.b = a;
                    _s.idx = i;
                    _s.type = (int)UEventType.EVENT_START;

                    UEvent _e = new UEvent();
                    _e.a = a;
                    _e.b = b;
                    _e.idx = i;
                    _e.type = (int)UEventType.EVENT_END;

                    events[eventCount++] = _s;
                    events[eventCount++] = _e;
                }
            }

            unsafe
            {
                ModuleHandle.InsertionSort<UEvent, TessEventCompare>(
                    NativeArrayUnsafeUtility.GetUnsafeBufferPointerWithoutChecks(events), 0, eventCount - 1,
                    new TessEventCompare());
                ;
            }

            var hullOp = true;
            float minX = events[0].a.x - (1 + math.abs(events[0].a.x)) * math.pow(2.0f, -16.0f);
            UHull hull;
            hull.a.x = minX;
            hull.a.y = 1;
            hull.b.x = minX;
            hull.b.y = 0;
            hull.idx = -1;
            hull.ilarray = new ArraySlice<int>(m_ILArray, m_NumHulls * m_NumHulls, m_NumHulls); // Last element
            hull.iuarray = new ArraySlice<int>(m_IUArray, m_NumHulls * m_NumHulls, m_NumHulls);
            hull.ilcount = 0;
            hull.iucount = 0;
            hulls[hullCount++] = hull;
            
            
            for (int i = 0, numEvents = eventCount; i < numEvents; ++i)
            {

                switch (events[i].type)
                {
                    case (int) UEventType.EVENT_POINT:
                    {
                        hullOp = AddPoint(hulls, hullCount, points, events[i].a, events[i].idx);
                    }
                        break;

                    case (int) UEventType.EVENT_START:
                    {
                        hullOp = SplitHulls(hulls, ref hullCount, points, events[i]);
                    }
                        break;

                    default:
                    {
                        hullOp = MergeHulls(hulls, ref hullCount, points, events[i]);
                    }
                        break;
                }

                if (!hullOp)
                    break;
            }

            events.Dispose();
            hulls.Dispose();
            return hullOp;
        }

        internal static bool Tessellate(Allocator allocator, NativeArray<float2> pgPoints, int pgPointCount, NativeArray<int2> pgEdges, int pgEdgeCount, ref NativeArray<float2> outputVertices, ref int vertexCount, ref NativeArray<int> outputIndices, ref int indexCount)
        {
            // Process.
            Tessellator tess = new Tessellator();
            tess.SetAllocator(allocator);
            int maxCount = 0, triCount = 0;
            var valid = tess.Triangulate(pgPoints, pgPointCount, pgEdges, pgEdgeCount);
            valid = valid && tess.ApplyDelaunay(pgPoints, pgEdges);
            if (valid)
            {
                // Output.
                NativeArray<int3> cells = tess.RemoveExterior(ref triCount);
                for (var i = 0; i < triCount; ++i)
                {
                    var a = (UInt16)cells[i].x;
                    var b = (UInt16)cells[i].y;
                    var c = (UInt16)cells[i].z;
                    if (a != b && b != c && a != c)
                    {
                        outputIndices[indexCount++] = a;
                        outputIndices[indexCount++] = c;
                        outputIndices[indexCount++] = b;
                    }
                    maxCount = math.max(math.max(math.max(cells[i].x, cells[i].y), cells[i].z), maxCount);
                }
                maxCount = (maxCount != 0) ? (maxCount + 1) : 0;
                for (var i = 0; i < maxCount; ++i)
                    outputVertices[vertexCount++] = pgPoints[i];
                cells.Dispose();
            }

            tess.Cleanup();
            return valid;
        }

        internal void Cleanup()
        {
            if (m_Edges.IsCreated) m_Edges.Dispose();
            if (m_Stars.IsCreated) m_Stars.Dispose();
            if (m_SPArray.IsCreated) m_SPArray.Dispose();
            if (m_Cells.IsCreated) m_Cells.Dispose();
            if (m_ILArray.IsCreated) m_ILArray.Dispose();
            if (m_IUArray.IsCreated) m_IUArray.Dispose();
            if (m_Flags.IsCreated) m_Flags.Dispose();
            if (m_Neighbors.IsCreated) m_Neighbors.Dispose();
            if (m_Constraints.IsCreated) m_Constraints.Dispose();
        }

    }
    
}
