using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using RetroGUI;

/* Duparc's method, as it's meant to be done.
 * Starting from all possible positions ( a list of length 2^(2*width+4))
 * additional lines are generated that match.
 * Supports patterns with width up to 31-2!
 * Additionally, TODO: Version with own checker of patterns.
 * Probably could be sped up in the generating of next line by knowing the first thing about the Game of Life.
 */

/* Amount of memory starts at 4*2^(2*width+4) bytes*/

namespace RetroParlor
{

    public class real_Duparc:FormRoutines //DOESN'T inherit from BaseRoutines!
    {
        byte[,] goal;
        bool hasOrphans=true; //not used yet
        byte testwidth;
        byte width;
        int numRows; //why would anyone try to atavise anything longer than 256?
        //stupid question, EVERYBODY wants to!
        uint maxnum;
        uint maxResults;
        uint numResults;
        Method touse;

        public List<byte[,]> foundPositions;

        public List<uint[]> lastRow = new List<uint[]>();
        public List<uint[]> thisRow = new List<uint[]>();

        public real_Duparc()
        {
        }

        public void TestMe(byte[,] goalpos, bool OrphanQ, Method method, uint maxresults)
        {
            FullInitialize(goalpos,OrphanQ,method,maxresults);
            Atavise();
        }

        public void FullInitialize(byte[,] goalpos, bool OrphanQ,Method method,uint maxresults)
        {
            hasOrphans = OrphanQ;
            goal = goalpos;
            width = (byte)goal.GetLength(0);
            testwidth = (byte)(width + 2);
            numRows = goal.GetLength(1);
            maxnum = Pow2(testwidth);
            numResults = 0;
            maxResults = maxresults;
            touse = method;
        }

        public void Atavise()
        {
            foundPositions = new List<byte[,]>();
            if (touse == Method.BFS)
            {
                AtaviseBFS();
            }
            else
            {
                AtaviseDFS();
            }
        }

        public void AtaviseBFS()
        {
            //prepare for row1
            AppendLineToBuffer("Preparing...");
            lastRow = new List<uint[]>();
            thisRow = new List<uint[]>();
            for (uint foo = 0; foo < maxnum; foo++)
            {
                for (uint bar = 0; bar < maxnum; bar++)
                {
                    thisRow.Add(new uint[2] { foo, bar });
                }
            }

            AppendLineToBuffer("Running...");
            byte[] row;
            int num;
            for (int l = 0; l < numRows; l++)
            {
                AppendLineToBuffer("Row +"+ l.ToString());
                lastRow = new List<uint[]>(thisRow);
                thisRow = new List<uint[]>();
                row = GetRow(l);
                num = 0;
                foreach (uint[] testcase in lastRow)
                {
                    GenerateNexts(testcase,Unencode(testcase[l]), Unencode(testcase[l + 1]),row);
                    num++;
                    SetProgress((float)l / numRows + (float)num / (lastRow.Count * numRows));
                }
                AppendLineToBuffer("Finished line" + l.ToString());
            }
            AppendLineToBuffer("Reconstructing lines...");
            foreach (uint[] path in thisRow)
            {
                ReconstructPath(path);
            }
        }

        public void AtaviseDFS()
        {
            //prepare for row1
            AppendLineToBuffer("Preparing...");
            for (uint foo = 0; foo < maxnum; foo++)
            {
                for (uint bar = 0; bar < maxnum; bar++)
                {
                    ComputeDFS(new uint[2] { foo, bar },0);
                    SetProgress((float)(foo*maxnum+ bar) / (maxnum * maxnum));
                }
            }
        }

        private void ComputeDFS(uint[] path, int level)
        {
            if (numResults == maxResults)
            {
                return;
            }
            if (level == numRows)
            {
                ReconstructPath(path);
                return;
            }
            List<uint[]> myRows = new List<uint[]>();
            byte[] row = GetRow(level);
            myRows = GenerateNexts4DFS(path, Unencode(path[level]), Unencode(path[level + 1]),row);
            foreach (uint[] newpath in myRows)
            {
                if (numResults == maxResults)
                {
                    return;
                }
                ComputeDFS(newpath, level + 1);
            }
        }

        /// <summary>
        /// Reconstructs a pattern from a path and adds it to foundResults
        /// </summary>
        /// <param name="path"></param>
        private void ReconstructPath(uint[] path)
        {
            byte[,] temp = new byte[testwidth, path.Length];
            byte[] bits;
            for (int y = 0; y < path.Length; y++)
            {
                bits = Unencode(path[y]);
                for (int x = 0; x < testwidth; x++)
                {
                    temp[x, y] = bits[x];
                }
            }
            foundPositions.Add(temp);
            numResults++;
        }


        /// <summary>
        /// Generates additions to thisRow given the previous result and the one before that.
        /// </summary>
        /// <param name="lastRow"></param>
        /// <param name="thisRow"></param>
        private void GenerateNexts(uint[] previousRows, byte[] lRow, byte[] tRow, byte[] row)
        {
            //TODO: Make this use a BFS or DFS search!
            //Right now it's *really* dumb!

            byte[] testrow;
            int nsum;
            bool isgood; //yes I'm actually trying to avoid gotos here isn't this good?
            int c; //WHYYYYY

            for (uint i = 0; i < maxnum; i++)
            {
                testrow = Unencode(i);
                //custom version of run1step
                isgood=true;
                for (int t = 0; t < width ; t++)
                {
                    nsum = lRow[t] + lRow[t + 1] + lRow[t + 2] + tRow[t] + tRow[t + 2] + testrow[t] + testrow[t + 1] + testrow[t + 2];
                    c = ((nsum == 3 || (tRow[t + 1] == 1 && nsum == 2)) ? 1 : 0);
                    if(c !=row[t]){
                        isgood=false;
                        break;
                    }
                }
                if(isgood){
                    thisRow.Add(AppendOnto(previousRows, i));
                }
            }
        }

        private List<uint[]> GenerateNexts4DFS(uint[] previousRows, byte[] lRow, byte[] tRow, byte[] row)
        {
            //TODO: Make this use a BFS or DFS search!
            //Right now it's *really* dumb!

            byte[] testrow;
            int nsum;
            bool isgood; //yes I'm actually trying to avoid gotos here isn't this good?
            int c; //WHYYYYY
            List<uint[]> resultRows = new List<uint[]>();

            for (uint i = 0; i < maxnum; i++)
            {
                testrow = Unencode(i);
                //custom version of run1step
                isgood = true;
                for (int t = 0; t < width; t++)
                {
                    nsum = lRow[t] + lRow[t + 1] + lRow[t + 2] + tRow[t] + tRow[t + 2] + testrow[t] + testrow[t + 1] + testrow[t + 2];
                    c = ((nsum == 3 || (tRow[t + 1] == 1 && nsum == 2)) ? 1 : 0);
                    if (c != row[t])
                    {
                        isgood = false;
                        break;
                    }
                }
                if (isgood)
                {
                    resultRows.Add(AppendOnto(previousRows, i));
                }
            }
            return resultRows;
        }

        public uint Pow2(byte pow)
        {
            return (uint)(1 << pow);
        }

        public byte[] Unencode(uint num)
        {
            //also, reverses!
            byte[] result = new byte[32];
            for (int l = 0; l <32; l++)
            {
                result[l] = (byte)(num % 2);
                num=num >> 1;
            }
            return result;
        }

        public uint Encode(byte[] pat)
        {
            uint num = 0;
            for (int n = 0; n < 32; n++)
            {
                num = (num << 1) + pat[n];
            }
            return num;
        }

        public byte[] GetRow(int i)
        {
            byte[] result = new byte[width];
            for (int x = 0; x < width; x++)
            {
                result[x] = goal[x, i];
            }
            return result;
        }

        public uint[] AppendOnto(uint[] a, uint b)
        {
            uint[] res = new uint[a.GetLength(0) + 1];
            a.CopyTo(res, 0);
            res[a.GetLength(0)] = b;
            return res;
        }


    }
}


/*        ____________________________________________
 *        |                                          |
 *        |  ______________________________________  |
 *        | |                                      | |
 *        | |  ___________________________________ | |
 *        | | |                                  | | |
 *        | | |  ______________________________  | | |
 *        | | |  | TOO MANY BOXES             |  | | |
 *        | | |  |____________________________|  | | |
 *        |__------------------------------------_____
 */