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

namespace SokobanResultSearch
{
    class SokobanInitializationProvider : InitializationProvider
    {
        #region Private class fields

        /// <summary>
        /// Representation of the player steps in integer array.
        /// </summary>
        private static readonly int[] _directions = new int[] { 1, -1, 1 << 8, -1 << 8 };

        #endregion

        /// <summary>
        /// Gets the map of the distances without any obstacles for each goal state.
        /// </summary>
        public override int[] GetWrongPlaces(int[] table, int[] goalPositions)
        {
            //Creates new instance of  wrong box positions
            int[] wrongBoxesPositions = new int[table.Length];
            List<short> wrongPositions;

            for (int i = 0; i < table.Length; i++)
            {
                for (int j = 0; j < 32; j++)
                {
                    /*
                     * If the position is not a goal position or a wrong position and
                     * it does not contain wall
                     */
                if ((table[i] & (1 << j)) == 0 && (wrongBoxesPositions[i] & (1 << j)) == 0 &&
                    (goalPositions[i] & (1 << j))  == 0)
                {
                    //If top left corner...
                    if ((table[i] & (1 << j - 1)) > 0 && (table[i - 1] & (1 << j)) > 0)
                    {
                        //Sets wrong position
                        wrongBoxesPositions[i] |= (1 << j);

                        //Searches wrong positions
                        if ((wrongPositions = SearchWrongPosition(table, goalPositions, (short)((i << 8) | (byte)j + 1))) != null)
                        {
                            //Sets wrong positions
                            foreach (short wrongPosition in wrongPositions)
                            {
                                wrongBoxesPositions[wrongPosition >> 8] |= (1 << (byte)wrongPosition);
                            }
                        }

                        //Searches wrong positions
                        if ((wrongPositions = SearchWrongPosition(table, goalPositions, (short)(((i + 1) << 8) | (byte)j))) != null)
                        {
                            //Sets wrong positions
                            foreach (short wrongPosition in wrongPositions)
                            {
                                wrongBoxesPositions[wrongPosition >> 8] |= (1 << (byte)wrongPosition);
                            }

                        }
                    }
                    else //If top right corner... 
                        if ((table[i] & (1 << j + 1)) > 0 && (table[i - 1] & (1 << j)) > 0)
                        {
                            //Sets wrong position
                            wrongBoxesPositions[i] |= (1 << j);

                            //Searches wrong positions
                            if ((wrongPositions = SearchWrongPosition(table, goalPositions, (short)((i << 8) | (byte)j - 1))) != null)
                            {
                                //Sets wrong positions
                                foreach (short wrongPosition in wrongPositions)
                                {
                                    wrongBoxesPositions[wrongPosition >> 8] |= (1 << (byte)wrongPosition);
                                }
                            }

                            //Searches wrong positions
                            if ((wrongPositions = SearchWrongPosition(table, goalPositions, (short)(((i + 1) << 8) | (byte)j))) != null)
                            {
                                //Sets wrong positions
                                foreach (short wrongPosition in wrongPositions)
                                {
                                    wrongBoxesPositions[wrongPosition >> 8] |= (1 << (byte)wrongPosition);
                                }
                            }
                        }
                        else //If bottom left corner...
                            if ((table[i] & (1 << j - 1)) > 0 && (table[i + 1] & (1 << j)) > 0)
                            {
                                //Sets wrong position
                                wrongBoxesPositions[i] |= (1 << j);

                                //Searches wrong positions
                                if ((wrongPositions = SearchWrongPosition(table, goalPositions, (short)((i << 8) | (byte)j + 1))) != null)
                                {
                                    //Setes wrong positions
                                    foreach (short wrongPosition in wrongPositions)
                                    {
                                        wrongBoxesPositions[wrongPosition >> 8] |= (1 << (byte)wrongPosition);
                                    }
                                }

                                //Searches wrong positions
                                if ((wrongPositions = SearchWrongPosition(table, goalPositions, (short)(((i - 1) << 8) | (byte)j))) != null)
                                {
                                    //Sets wrong positions
                                    foreach (short wrongPosition in wrongPositions)
                                    {
                                        wrongBoxesPositions[wrongPosition >> 8] |= (1 << (byte)wrongPosition);
                                    }
                                }
                            }
                            else //If bottom right corner...
                                if ((table[i] & (1 << j + 1)) > 0 && (table[i + 1] & (1 << j)) > 0)
                                {
                                    //Sets wrong position
                                    wrongBoxesPositions[i] |= (1 << j);

                                    //Searches wrong positions
                                    if ((wrongPositions = SearchWrongPosition(table, goalPositions, (short)((i << 8) | (byte)j - 1))) != null)
                                    {
                                        //Sets wrong positions
                                        foreach (short wrongPosition in wrongPositions)
                                        {
                                            wrongBoxesPositions[wrongPosition >> 8] |= (1 << (byte)wrongPosition);
                                        }
                                    }

                                    //Searches wrong positions
                                    if ((wrongPositions = SearchWrongPosition(table, goalPositions, (short)(((i - 1) << 8) | (byte)j))) != null)
                                    {
                                        //Sets wrong positions
                                        foreach (short wrongPosition in wrongPositions)
                                        {
                                            wrongBoxesPositions[wrongPosition >> 8] |= (1 << (byte)wrongPosition);
                                        }
                                    }
                                }
                    }
                }
            }
            return wrongBoxesPositions;
        }

        /// <summary>
        /// Gets the representation of the goal positions in int array.
        /// All bytes with value 1 are goal position signs.
        /// </summary>
        public override int[] GetGoalPositions(byte[,] table)
        {
            int dimX = table.GetLength(0);
            int dimY = table.GetLength(1);
            int[] result = new int[dimX];

            for (int i = 0; i < dimX; i++)
            {
                for (int j = 0; j < dimY; j++)
                {
                    if ((table[i, j] & 4) == 4)
                        result[i] |= (1 << j);
                }
            }

            return result;
        }

        /// <summary>
        /// Initializes the start state.
        /// </summary>
        public override State GetStartState(byte[,] table)
        {
            State result                 = new State();

            int dimX = table.GetLength(0);
            int dimY = table.GetLength(1);
            for (int i = 0; i < dimX; i++)
            {
                for (int j = 0; j < dimY; j++)
                {
                    if (table[i, j] == 1)
                        result.PlayerPosition = (short)((i << 8) | j);

                    if (table[i, j] == 2 || table[i, j] == 6)
                        result.BoxesPositions += (char)(i << 8 | j);
                }
            }
            char[] temp = result.BoxesPositions.ToCharArray();
            Array.Sort<char>(temp);

            result.BoxesPositions = new string(temp);

            return result;
        }

        /// <summary>
        /// Gets the table without the boxes and the player.
        /// </summary>
        public override int[] GetEmptyTable(byte[,] table, short playerPosition)
        {
            int dimX = table.GetLength(0);
            int dimY = table.GetLength(1);
            int[] result = new int[dimX];

            for (int i = 0; i < dimX; i++)
            {
                result[i] = -1;
            }

            short[] openStates  = new short[dimX * dimY];
            int index           = 1;

            //
            openStates[0]       = playerPosition;
            for (int i = 0; i < index; i++)
            {
                for (int j = 0; j < _directions.Length; j++)
                {
                    //
                    short position = (short)(openStates[i] + _directions[j]);
                    if ((table[position >> 8,(byte)position]) != 3 &&
                        (result[position >> 8] & (1 << (byte)position)) != 0)
                    {
                        result[position >> 8]   ^= (1 << (byte)position);
                        openStates[index]       = position;
                        ++index;
                    }
                }
            }

            return result;
        }

        /// <summary>
        /// Gets the count of empty places.
        /// </summary
        public override int GetEmptyPositionsCount(int[] table)
        {
            int result = 0;
            for (int i = 0; i < table.Length; i++)
            {
                for (int j = 0; j < 32; j++)
                {
                    if ((table[i] & (1 << j)) == 0)
                        ++result;
                }
            }

            return result;
        }

        /// <summary>
        /// Converts goal positions representation from array to string.
        /// </summary
        public override string ConvertGoalPositonsToString(int[] goalPositions)
        {
            string result = "";

            for (int i = 0; i < goalPositions.Length; i++)
            {
                for (int j = 0; j < 32; j++)
                {
                    if ((goalPositions[i] & (1 << j)) != 0)
                        result += (char)(i << 8 | j); 
                }
            }

            char[] temp = result.ToCharArray();
            Array.Sort<char>(temp);

            return new string(temp);
        }

        /// <summary>
        /// Gets the list of wrong positions starting from a corner.
        /// </summary>
        private List<short> SearchWrongPosition(int[] table, int[] goalPositions, short position)
        {
            //Depth-first search
            if ((table[position >> 8] & (1 << (byte)position)) == 0)
            {
                //Creates new instance of wrong places
                List<short> wrongPlaces = new List<short>();

                //Adds the first element to wrong places
                wrongPlaces.Add(position);

                for (int i = 0; i < wrongPlaces.Count; i++)
                {
                    //If a goal position is available...
                    if ((goalPositions[wrongPlaces[i] >> 8] & (1 << (byte)(wrongPlaces[i]))) > 0)
                        return null;

                    //Inits coordinates
                    byte x = (byte)(wrongPlaces[i] >> 8);
                    byte y = (byte)wrongPlaces[i];

                    //Steps to the right
                    byte positionX = x;
                    byte positionY = (byte)(y + 1);
                    short pos = (short)((positionX << 8) | positionY);

                    if ((table[positionX] & (1 << positionY)) == 0 && (table[x] & (1 << (y - 1))) == 0 && wrongPlaces.IndexOf(pos) == -1)
                        wrongPlaces.Add(pos);

                    //Steps to the left
                    positionX = x;
                    positionY = (byte)(y - 1);
                    pos = (short)((positionX << 8) | positionY);

                    if ((table[positionX] & (1 << positionY)) == 0 && (table[x] & (1 << (y + 1))) == 0 && wrongPlaces.IndexOf(pos) == -1)
                        wrongPlaces.Add(pos);

                    //Steps up
                    positionX = (byte)(x + 1);
                    positionY = y;
                    pos = (short)((positionX << 8) | positionY);

                    if ((table[positionX] & (1 << positionY)) == 0 && (table[x - 1] & (1 << (y))) == 0 && wrongPlaces.IndexOf(pos) == -1)
                        wrongPlaces.Add(pos);

                    //Steps down
                    positionX = (byte)(x - 1);
                    positionY = y;
                    pos = (short)((positionX << 8) | positionY);

                    if ((table[positionX] & (1 << positionY)) == 0 && (table[x + 1] & (1 << (y))) == 0 && wrongPlaces.IndexOf(pos) == -1)
                        wrongPlaces.Add(pos);
                }

                return wrongPlaces;
            }
            return null;
        }

        /// <summary>
        /// Gets the map of the distances without any obstacles for each goal state.
        /// </summary>
        public override int[, ,] GetNoObstacleDistance(int[] table, string goalPositions, int emptyPositionsCount)
        {
            int[, ,] result = new int[table.Length, 32, goalPositions.Length];

            for (int i = 0; i < goalPositions.Length; i++)
            {
                int[] tableClone = new int[table.Length];
                Array.Copy(table, tableClone, table.Length);

                short[,] openStates  = new short[emptyPositionsCount,2];
                int index           = 1;

                openStates[0, 0]  = (short)goalPositions[i];
                tableClone[goalPositions[i] >> 8] |= (1 << (byte)goalPositions[i]);

                for (int j = 0; j < index; j++)
                {
                    for (int k = 0; k < _directions.Length; k++)
                    {
                        short position = (short)(openStates[j, 0] + _directions[k]);
                        if ((tableClone[position >> 8] & (1 << (byte)position)) == 0)
                        {
                            tableClone[position >> 8] |= (1 << (byte)position);
                            openStates[index, 0] = position;
                            openStates[index, 1] = (short)(openStates[j, 1] + 1);
                            result[position >> 8, (byte)position, i] = openStates[index, 1];
                            ++index;
                        }
                    }
                }
            }

            return result;
        }
    }
}
