using System;
using System.Collections.Generic;

namespace Oni.Motoko
{
    internal class Stripify
    {
        private const int BeginStrip = int.MinValue;
        private int[] tlist;
        private int[] adjacency;
        private int[] degree;
        private List<int> strips;
        private bool[] used;

        public static int[] FromTriangleList(int[] triangleList)
        {
            var triStrips = new Stripify(triangleList);
            return triStrips.Run();
        }

        public static int[] ToTriangleList(int[] triangleStrips)
        {
            int triangleCount = 0;

            for (int i = 0; i < triangleStrips.Length; i++)
            {
                triangleCount++;

                if (triangleStrips[i] < 0)
                    triangleCount -= 2;
            }

            var triangles = new int[triangleCount * 3];
            int pos = 0;
            var face = new int[3];
            int order = 0;

            for (int i = 0; i < triangleStrips.Length; i++)
            {
                if (triangleStrips[i] < 0)
                {
                    face[0] = triangleStrips[i] & int.MaxValue;
                    i++;
                    face[1] = triangleStrips[i];
                    i++;
                    order = 0;
                }
                else
                {
                    face[order] = face[2];
                    order = (order + 1) % 2;
                }

                face[2] = triangleStrips[i];

                Array.Copy(face, 0, triangles, pos, 3);
                pos += 3;
            }

            return triangles;
        }

        private Stripify(int[] triangleList)
        {
            tlist = triangleList;
        }

        private int[] Run()
        {
            strips = new List<int>();

            GenerateAdjacency();

            while (GenerateStrip())
                ;

            //
            // Generate 1 triangle long strips for all triangles that were not included
            // in triangle strips
            //

            for (int i = 0; i < degree.Length; i++)
            {
                if (!used[i])
                {
                    int j = i * 3;

                    strips.Add(tlist[j + 0] | BeginStrip);
                    strips.Add(tlist[j + 1]);
                    strips.Add(tlist[j + 2]);

                    used[i] = true;
                }
            }

            return strips.ToArray();
        }

        private bool GenerateStrip()
        {
            int current = -1;

            int minDegree = 4;
            int minAdjacentDegree = 4;

            //
            // Find a triangle to start with. The triangle with the lowest degree
            // is picked as a start triangle. If multiple triangles have the same 
            // degree then the adjacent triangles are checked for lowest degree.
            //

            for (int t = 0; t < degree.Length; t++)
            {
                if (used[t] || degree[t] == 0)
                    continue;

                if (degree[t] < minDegree)
                {
                    minDegree = degree[t];
                    minAdjacentDegree = 4;
                    current = t;
                }
                else if (degree[t] == minDegree)
                {
                    //
                    // We have 2 candidates for a start triangle with the same degree.
                    // Check their neighbours for lowest degree to decide which candidate to use.
                    //

                    for (int k = 0; k < 3; k++)
                    {
                        int a = adjacency[t * 3 + k];

                        if (a == -1 || used[a] || degree[a] == 0)
                            continue;

                        if (degree[a] < minAdjacentDegree)
                        {
                            minAdjacentDegree = degree[a];
                            current = t;
                        }
                    }
                }
            }

            if (current == -1)
            {
                //
                // A start triangle cannot be found. Either there are no more unused triangles left
                // or all remaining triangles have degree = 0.
                //

                return false;
            }

            UseTriangle(current);

            //
            // Find a triangle adjacent to the start triangle so we can decide
            // on a vertex order for the start triangle. If there are multiple
            // adjacent triangles the one with lowest degree is used.
            //

            int next = -1;
            int edge = 0;

            minDegree = 4;

            for (int e = 0; e < 3; e++)
            {
                int a = adjacency[current * 3 + e];

                if (a == -1 || used[a])
                    continue;

                //
                // NOTE: Don't check for degree = 0. The previous UseTriangle(current) can make 
                // adjacent triangles have a 0 degree. It works because all we are interested in
                // is which adjacent triangle has the lowest degree.
                //

                if (degree[a] < minDegree)
                {
                    minDegree = degree[a];
                    next = a;
                    edge = e;
                }
            }

            //
            // Begin a new triangle strip
            //

            var triangle = new int[3];

            triangle[0] = tlist[(current * 3) + (edge + 2) % 3];
            triangle[1] = tlist[(current * 3) + (edge + 0) % 3];
            triangle[2] = tlist[(current * 3) + (edge + 1) % 3];

            strips.Add(triangle[0] | BeginStrip);
            strips.Add(triangle[1]);
            strips.Add(triangle[2]);

            //
            // Continue the triangle strip as long as possible
            //

            int order = 0;

            while (next != -1)
            {
                UseTriangle(next);

                triangle[0] = triangle[1 + order];

                //
                // Search an edge in triangle "next" that matches the "exit" edge of triangle "current"
                //

                for (int v = 0; v < 3; v++)
                {
                    int t = next * 3;

                    if (tlist[t + v] == triangle[(2 + order) % 3] && tlist[t + (v + 1) % 3] == triangle[order])
                    {
                        edge = (v + 2 - order) % 3;
                        triangle[1 + order] = tlist[t + (v + 2) % 3];
                        break;
                    }
                }

                strips.Add(triangle[1 + order]);

                //
                // Replace "current" with "next" and find a "next" triangle that is adjacent with "current"
                //

                current = next;
                next = adjacency[current * 3 + edge];

                if (next == -1 || used[next])
                    break;

                UseTriangle(next);

                //
                // Alternate vertex ordering
                //

                order = (order + 1) % 2;
            }

            return true;
        }

        private void UseTriangle(int t)
        {
            degree[t] = 0;
            used[t] = true;

            //
            // Decrease the degree of all adjacent triangles by 1.
            //

            for (int e = 0; e < 3; e++)
            {
                int a = adjacency[t * 3 + e];

                if (a != -1 && degree[a] > 0)
                    degree[a]--;
            }
        }

        #region private struct Edge

        private struct Edge : IEquatable<Edge>
        {
            public readonly int V1;
            public readonly int V2;

            public Edge(int V1, int V2)
            {
                this.V1 = V1;
                this.V2 = V2;
            }

            public static bool operator ==(Edge e1, Edge e2) => e1.V1 == e2.V1 && e1.V2 == e2.V2;
            public static bool operator !=(Edge e1, Edge e2) => e1.V1 != e2.V1 || e1.V2 != e2.V2;
            public bool Equals(Edge edge) => V1 == edge.V1 && V2 == edge.V2;
            public override bool Equals(object obj) => obj is Edge && Equals((Edge)obj);
            public override int GetHashCode() => V1 ^ V2;
        }

        #endregion

        private void GenerateAdjacency()
        {
            adjacency = new int[tlist.Length];
            degree = new int[tlist.Length / 3];
            used = new bool[tlist.Length / 3];

            for (int i = 0; i < adjacency.Length; i++)
                adjacency[i] = -1;

            //
            // Store all the edges in a dictionary for easier lookup
            //

            var edges = new Dictionary<Edge, int>();

            for (int t = 0; t < tlist.Length; t += 3)
            {
                for (int v = 0; v < 3; v++)
                {
                    var edge = new Edge(tlist[t + v], tlist[t + (v + 1) % 3]);

                    edges[edge] = t / 3;
                }
            }

            //
            // Fill the adjacency array
            //

            for (int t = 0; t < tlist.Length; t += 3)
            {
                for (int e = 0; e < 3; e++)
                {
                    //
                    // We already have an adjacent triangle for this edge.
                    // This means that there are 3 or more triangles that have a 
                    // common edge but this is not very common and we'll just 
                    // ignore it.
                    //

                    if (adjacency[t + e] != -1)
                        continue;

                    //
                    // Notice that the edge must be reversed compared to the
                    // order they were stored in the dictionary to preserve
                    // trinangle vertex ordering.
                    //

                    var edge = new Edge(tlist[t + (e + 1) % 3], tlist[t + e]);

                    int k;

                    //
                    // Note the k != t / 3 check to avoid making degenerate triangles
                    // adjacent to themselfs.
                    //

                    if (edges.TryGetValue(edge, out k) && k != t / 3)
                    {
                        adjacency[t + e] = k;
                        degree[t / 3]++;
                    }
                }
            }
        }
    }
}